NTRS - NASA Technical Reports Server

Back to Results
Introducing Tropical Geometric Approaches to Delay Tolerant Networking OptimizationDelay Tolerant Networking (DTN) is the standard approach to the networking of space systems with the goal of supporting the Solar System Internet (SSI). Current space networks have a small scale and often depend on rigorously scheduled (pre-determined) contact opportunities; this manual approach inhibits scalability. The goal of this paper is to recast these scheduling problems in order to apply the optimization machinery of tropical geometry.

Contact opportunities in space are dependent on such factors as orbital mechanics and asset availability, which induce time-varying connectivity; indeed, end-to-end connectivity might never occur. Routing optimization within this structure is classically difficult and typically utilizes Dijkstra's algorithm as applied to contact graphs. Alternatively, we follow the successes of tropical geometry in train schedule optimization, job assignments, and even traditional networking, by extending this approach to this more general (i.e. disconnected) problem space.

These successes imply tropical geometry provides a useful framework in the context of DTNs, starting with applications to queuing theory and long-haul links. Recently, tropical geometry has been applied to parametric path optimization on graphs with variable edge weights. In this work, we extend these advances to account for the problem of routing in a space network, and find that tropical geometry is well-suited to the challenges offered by this new setting, including contact schedules featuring probabilities. Our approach leverages the combinatorial nature of the problem to give feasible shortest path trees in the presence of variable channel conditions and latency, evolving topologies, and uncertainty inherent in space routing.

We discuss our tropical approach to DTN for two Python implementations, a Verilog Tropical ALU implementation, tropical frameworks for other parametric graph problems, and solution stability. Lastly, a program for future work is included to illuminate the path ahead.
Document ID
Acquisition Source
Glenn Research Center
Document Type
Conference Paper
Jacob Cleveland
(Glenn Research Center Cleveland, Ohio, United States)
Alan Hylton
(Glenn Research Center Cleveland, Ohio, United States)
Robert Short
(Glenn Research Center Cleveland, Ohio, United States)
Brendan Mallery
(Tufts University Medford, Massachusetts, United States)
Robert Green
(University at Albany, State University of New York Albany, New York, United States)
Justin Curry
(University at Albany, State University of New York Albany, New York, United States)
Devavrat Vivek Dabke
(Princeton University Princeton, New Jersey, United States)
Olivia Freides
(American University Washington, DC)
Date Acquired
March 2, 2022
Subject Category
Space Communications, Spacecraft Communications, Command And Tracking
Theoretical Mathematics
Meeting Information
Meeting: 43rd IEEE Aerospace Conference
Location: Big Sky, MT
Country: US
Start Date: March 5, 2022
End Date: March 12, 2022
Sponsors: Institute of Electrical and Electronics Engineers
Funding Number(s)
WBS: 278371.01.06
Distribution Limits
Use by or on behalf of the US Gov. Permitted.
Technical Review
Single Expert
Delay Tolerant Networking
Tropical Geometry
Algebraic Geometry
Network Optimization
No Preview Available