NASA Logo

NTRS

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
20220003679
Document Type
Conference Paper
Authors
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
43rd IEEE Aerospace Conference(Big Sky, MT)
Funding Number(s)
WBS: 278371.01.06
Distribution Limits
Public
Copyright
Use by or on behalf of the US Gov. Permitted.
Technical Review
Single Expert
Keywords
Delay Tolerant Networking
DTN
Tropical Geometry
Algebraic Geometry
Network Optimization
Verilog
ALU

Available Downloads

NameType AeroConf_2022___Tropical_Geometry_20220301_ScanCopy.pdf STI
No Preview Available