SEARCH · Search NASA

Results for “Dijkstra's algorithm”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

9 records

All sources NASA NTRS DOE OSTI

NASA NTRS2013

Enhanced Contact Graph Routing (ECGR) MACHETE Simulation Model

Contact Graph Routing (CGR) for Delay/Disruption Tolerant Networking (DTN) space-based networks makes use of the predictable nature of node contacts to make real-time routing decisions given unpredictable traffic patterns. The contact graph will have been disseminated to all nodes before the start of route computation. CGR was designed for space-based networking environments where future contact plans are known or are independently computable (e.g., using known orbital dynamics). For each data item (known as a bundle in DTN), a node independently performs route selection by examining possible paths to the destination. Route computation could conceivably run thousands of times a second, so computational load is important. This work refers to the simulation software model of Enhanced Contact Graph Routing (ECGR) for DTN Bundle Protocol in JPL's MACHETE simulation tool. The simulation model was used for performance analysis of CGR and led to several performance enhancements. The simulation model was used to demonstrate the improvements of ECGR over CGR as well as other routing methods in space network scenarios. ECGR moved to using earliest arrival time because it is a global monotonically increasing metric that guarantees the safety properties needed for the solution's correctness since route re-computation occurs at each node to accommodate unpredicted changes (e.g., traffic pattern, link quality). Furthermore, using earliest arrival time enabled the use of the standard Dijkstra algorithm for path selection. The Dijkstra algorithm for path selection has a well-known inexpensive computational cost. These enhancements have been integrated into the open source CGR implementation. The ECGR model is also useful for route metric experimentation and comparisons with other DTN routing protocols particularly when combined with MACHETE's space networking models and Delay Tolerant Link State Routing (DTLSR) model.

Segui, John S.↗

NASA NTRS2013

Contact Graph Routing Enhancements Developed in ION for DTN

The Interplanetary Overlay Network (ION) software suite is an open-source, flight-ready implementation of networking protocols including the Delay/Disruption Tolerant Networking (DTN) Bundle Protocol (BP), the CCSDS (Consultative Committee for Space Data Systems) File Delivery Protocol (CFDP), and many others including the Contact Graph Routing (CGR) DTN routing system. While DTN offers the capability to tolerate disruption and long signal propagation delays in transmission, without an appropriate routing protocol, no data can be delivered. CGR was built for space exploration networks with scheduled communication opportunities (typically based on trajectories and orbits), represented as a contact graph. Since CGR uses knowledge of future connectivity, the contact graph can grow rather large, and so efficient processing is desired. These enhancements allow CGR to scale to predicted NASA space network complexities and beyond. This software improves upon CGR by adopting an earliest-arrival-time cost metric and using the Dijkstra path selection algorithm. Moving to Dijkstra path selection also enables construction of an earliest- arrival-time tree for multicast routing. The enhancements have been rolled into ION 3.0 available on sourceforge.net.

Segui, John S.↗

NASA NTRSDate not supplied

Contact Multigraph Routing: Overview and Implementation

In Delay Tolerant Networking (DTN), the standard routing algorithm used to navigate time-varying networks has been Contact Graph Routing (CGR). In CGR, a globally distributed list of contacts, periods during which two DTN nodes may communicate, is used to construct a contact graph, in which contacts are vertices. A version of Dijkstra’s algorithm can then be used to find paths through this model of the timevarying network. However, since contact graphs may be large compared to the network, potentially growing with the square of the number of network nodes and linearly with the time interval represented, the resulting algorithm does not scale well with the size of the network or time. Any improvement to the routing algorithm will bring significant returns to scale. In a previous paper, we briefly introduced an alternative to the contact graph model for routing. This alternative model is based on a multigraph (a graph in which there may be multiple edges between a pair of vertices) where vertices represent network nodes instead of contacts. A version of Dijkstra’s algorithm in these multigraph models reduces the time needed to perform the same routing computations done in the existing CGR algorithm. Moreover, a modified version of Yen’s algorithm for multigraphs is included. Our variation of CGR, which we call Contact Multigraph Routing (CMR), provides an in-line replacement for the previously used pathfinding algorithms. This paper describes an implementation created based on the CMR approach, and experimental comparisons to traditional CGR are given. In addition, we explore some additional modifications to the routing pipeline traditionally assumed in CGR. These modifications range from the theoretical to the practical in terms of size and scope. We step forward our understanding of sheaftheoretic networking and describe how to model the routing pipeline using sheaves. We detail some enhanced route selection criteria that addresses some of the added complexity of DTNbased systems. We also include a future works section on future improvements and implementations that would be of service to the broader DTN community.

contact graph routing↗

NASA NTRSDate not supplied

Towards Sheaf Theoretic Analyses for Delay Tolerant Networking

The goal of Delay Tolerant Networking (DTN) is to take a collection of heterogeneous, disparate connections between satellites, space assets, ground stations, and ground infrastructure and bring it together into a cohesive, functioning overlay network. Depending on the systems being considered, one can find links with a one-way light time exceeding minutes (and hours),periodic links which can sometimes be predicted by orbital mechanics, and restrictions based on the variety of capabilities built into these systems. These characteristics preclude traditional network models and routing techniques and have classically led to either rigid routing tables or purely probabilistic models. As the deeper underlying structures remain unknown, development of more DTN-optimized algorithms has lacked the necessary foundation. In a continuation of previous work, the goal of this paper is to identify and study these fundamental structures that exist in delay tolerant networks (DTN), with a focus on space networks. The current routing methodology has been to use contact graph routing (CGR) algorithms. CGR models a series of known contacts as a static graph. For CGR to work, this graph must be globally consistent and must have an accurate picture of the network. Because this is a globally controlled structure, there is little room for flexibility in the event of changes to the network which would naturally occur as the network grows. As a response to the desire for flexibility as the network changes, we introduced the mathematical structure known as sheaves to DTNs last year. The tag-line for sheaves is that they are a mathematically precise way of gluing local data together into unique global data. Thus, sheaves lend extra power to traditional models(and routing algorithms) by taking additional information and merging it, in as consistent a manner as possible, with the representation itself. The clearest example of how Earth-bound networks exhibit behavior that is “sheafy” is link state routers, which build a local-to-global picture of their network by gluing local information together into a global network, exactly as a sheaf would do. For routing within delay tolerant networks to truly exploit this structure, a deeper structure than a graph is required. In this paper, we develop sheaves that can work over directed graphs such as temporal flow networks, we construct a sheaf representation for Dijkstra’s algorithm, and we outline a construction for routing sheaves capable of modeling multicast scenarios. Finally, there is a section of future work suggesting follow-on research.

Robert Short↗

NASA NTRS2010

Graph-Based Path-Planning for Titan Balloons

A document describes a graph-based path-planning algorithm for balloons with vertical control authority and little or no horizontal control authority. The balloons are designed to explore celestial bodies with atmospheres, such as Titan, a moon of Saturn. The algorithm discussed enables the balloon to achieve horizontal motion using the local horizontal winds. The approach is novel because it enables the balloons to use arbitrary wind field models. This is in contrast to prior approaches that used highly simplified wind field models, such as linear, or binary, winds. This new approach works by discretizing the space in which the balloon operates, and representing the possible states of the balloon as a graph whose arcs represent the time taken to move from one node to another. The approach works with arbitrary wind fields, by looking up the wind strength and direction at every node in the graph from an arbitrary wind model. Having generated the graph, search techniques such as Dijkstra s algorithm are then used to find the set of vertical actuation commands that takes the balloon from the start to the goal in minimum time. In addition, the set of reachable locations on the moon or planet can be determined.

Blackmore, Lars James↗

NASA NTRSDate not supplied

Introducing Tropical Geometric Approaches to Delay Tolerant Networking Optimization

Delay 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.

Delay Tolerant Networking↗

NASA NTRSDate not supplied

Sheaf Theoretic Models for Routing in Delay Tolerant Networks

One key to communications scalability is routing; as such the goal of this paper is to build upon successful efforts towards general routing for space-based networks. With the ever-increasing accessibility of space, the number of assets is increasing, which becomes a critical communications burden in terms of scheduling, spectrum allocation, and resource allocation. In order to mitigate these concerns, a true networking approach is necessary; a standard approach for space systems is Delay Tolerant Networking (DTN). For DTN to be a meaningful answer to the Solar System Internet (SSI) question, DTN must offer meaningful routing solutions that span the heterogeneous collection of links and nodes. This, in turn, depends on the general structure of these disconnected networks -- a structure that remains largely unknown. In ground communications networks, routing decisions are made based on several pathfinding algorithms working in tandem. In previous work, we modeled Dijkstra's pathfinding algorithm using sheaves and provided a more general framework for determining paths using sheaves over graphs. Continuing our sheaf-theoretic approach, we introduce here an expansion of our pathfinding sheaf to handle more general information, and we expand on additional pathfinding algorithms that can be represented using sheaves. Moreover, we demonstrate means of combining multiple algorithms into a single sheaf structure so that changes of scale can be presented in the language of sheaves. In addition, space communications networks rely upon radio transmitter antennas which can establish broadcast and multicast communications options, rather than the primarily unicast options available to wired networks. Last year, we also introduced a multicast routing sheaf for presenting broadcast, unicast, and multicast communications over a graph. Extending that work, we also introduce queuing sheaves so that we can blend these communications options together to simulate a variety of routing options across space networks. In addition, we include examples to illustrate the applicability of this abstract theory to routing in disconnected networks.

Robert Short↗

NASA NTRS1988

Search Problems in Mission Planning and Navigation of Autonomous Aircraft

An architecture for the control of an autonomous aircraft is presented. The architecture is a hierarchical system representing an anthropomorphic breakdown of the control problem into planner, navigator, and pilot systems. The planner system determines high level global plans from overall mission objectives. This abstract mission planning is investigated by focusing on the Traveling Salesman Problem with variations on local and global constraints. Tree search techniques are applied including the breadth first, depth first, and best first algorithms. The minimum-column and row entries for the Traveling Salesman Problem cost matrix provides a powerful heuristic to guide these search techniques. Mission planning subgoals are directed from the planner to the navigator for planning routes in mountainous terrain with threats. Terrain/threat information is abstracted into a graph of possible paths for which graph searches are performed. It is shown that paths can be well represented by a search graph based on the Voronoi diagram of points representing the vertices of mountain boundaries. A comparison of Dijkstra's dynamic programming algorithm and the A* graph search algorithm from artificial intelligence/operations research is performed for several navigation path planning examples. These examples illustrate paths that minimize a combination of distance and exposure to threats. Finally, the pilot system synthesizes the flight trajectory by creating the control commands to fly the aircraft.

Krozel, James A.↗

NASA NTRS2009

Decomposition Algorithm for Global Reachability Analysis on a Time-Varying Graph with an Application to Planetary Exploration

Hot air (Montgolfiere) balloons represent a promising vehicle system for possible future exploration of planets and moons with thick atmospheres such as Venus and Titan. To go to a desired location, this vehicle can primarily use the horizontal wind that varies with altitude, with a small help of its own actuation. A main challenge is how to plan such trajectory in a highly nonlinear and time-varying wind field. This paper poses this trajectory planning as a graph search on the space-time grid and addresses its computational aspects. When capturing various time scales involved in the wind field over the duration of long exploration mission, the size of the graph becomes excessively large. We show that the adjacency matrix of the graph is block-triangular, and by exploiting this structure, we decompose the large planning problem into several smaller subproblems, whose memory requirement stays almost constant as the problem size grows. The approach is demonstrated on a global reachability analysis of a possible Titan mission scenario.

Dijkstra's algorithm↗