Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Routing 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.

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

At least 37 records · Page 2
All sourcesNASA NTRSDOE OSTI
NASA NTRS2017

A Machine Learning Concept for DTN Routing

This paper discusses the concept and architecture of a machine learning based router for delay tolerant space networks. The techniques of reinforcement learning and Bayesian learning are used to supplement the routing decisions of the popular Contact Graph Routing algorithm. An introduction to the concepts of Contact Graph Routing, Q-routing and Naive Bayes classification are given. The development of an architecture for a cross-layer feedback framework for DTN (Delay-Tolerant Networking) protocols is discussed. Finally, initial simulation setup and results are given.

Delay Tolerant Networks↗
NASA NTRS1991

Method and apparatus for eliminating unsuccessful tries in a search tree

A circuit switching system in an M-ary, n-cube connected network completes a best-first path from an originating node to a destination node by latching valid legs of the path as the path is being sought out. Each network node is provided with a routing hyperswitch sub-network, (HSN) connected between that node and bidirectional high capacity communication channels of the n-cube network. The sub-networks are all controlled by routing algorithms which respond to message identification headings (headers) on messages to be routed along one or more routing legs. The header includes information embedded therein which is interpreted by each sub-network to route and historically update the header. A logic circuit, available at every node, implements the algorithm and automatically forwards or back-tracks the header in the network legs of various paths until a completed path is latched.

Peterson, John C.↗
NASA NTRS2011

Dynamic Weather Routes: A Weather Avoidance Concept for Trajectory-Based Operations

The integration of convective weather modeling with trajectory automation for conflict detection, trial planning, direct routing, and auto resolution has uncovered a concept that could help controllers, dispatchers, and pilots identify improved weather routes that result in significant savings in flying time and fuel burn. Trajectory automation continuously and automatically monitors aircraft in flight to find those that could potentially benefit from improved weather reroutes. Controllers, dispatchers, and pilots then evaluate reroute options to assess their suitability given current weather and traffic. In today's operations aircraft fly convective weather avoidance routes that were implemented often hours before aircraft approach the weather and automation does not exist to automatically monitor traffic to find improved weather routes that open up due to changing weather conditions. The automation concept runs in real-time and employs two keysteps. First, a direct routing algorithm automatically identifies flights with large dog legs in their routes and therefore potentially large savings in flying time. These are common - and usually necessary - during convective weather operations and analysis of Fort Worth Center traffic shows many aircraft with short cuts that indicate savings on the order of 10 flying minutes. The second and most critical step is to apply trajectory automation with weather modeling to determine what savings could be achieved by modifying the direct route such that it avoids weather and traffic and is acceptable to controllers and flight crews. Initial analysis of Fort Worth Center traffic suggests a savings of roughly 50% of the direct route savings could be achievable.The core concept is to apply trajectory automation with convective weather modeling in real time to identify a reroute that is free of weather and traffic conflicts and indicates enough time and fuel savings to be considered. The concept is interoperable with today's integrated FMS/datalink. Auxiliary(lat/long) waypoints define a minimum delay reroute between current position and a downstream capture fix beyond the weather. These auxiliary waypoints can be uplinked to equipped aircraft and auto-loaded into the FMS. Alternatively, for unequipped aircraft, auxiliary waypoints can be replaced by nearby named fixes, but this could reduce potential savings. The presentation includes an overview of the automation approach and focuses on several cases in terms of potential savings, reroute complexity, best auxiliary waypoint solution vs. named fix solution, and other metrics.

McNally, B. David↗
NASA NTRS1986

Hybrid routing technique for a fault-tolerant, integrated information network

The evolutionary growth of the space station and the diverse activities onboard are expected to require a hierarchy of integrated, local area networks capable of supporting data, voice, and video communications. In addition, fault-tolerant network operation is necessary to protect communications between critical systems attached to the net and to relieve the valuable human resources onboard the space station of time-critical data system repair tasks. A key issue for the design of the fault-tolerant, integrated network is the development of a robust routing algorithm which dynamically selects the optimum communication paths through the net. A routing technique is described that adapts to topological changes in the network to support fault-tolerant operation and system evolvability.

Meredith, B. D.↗
NASA NTRS1985

Analysis of adaptive algorithms for an integrated communication network

Techniques were examined that trade communication bandwidth for decreased transmission delays. When the network is lightly used, these schemes attempt to use additional network resources to decrease communication delays. As the network utilization rises, the schemes degrade gracefully, still providing service but with minimal use of the network. Because the schemes use a combination of circuit and packet switching, they should respond to variations in the types and amounts of network traffic. Also, a combination of circuit and packet switching to support the widely varying traffic demands imposed on an integrated network was investigated. The packet switched component is best suited to bursty traffic where some delays in delivery are acceptable. The circuit switched component is reserved for traffic that must meet real time constraints. Selected packet routing algorithms that might be used in an integrated network were simulated. An integrated traffic places widely varying workload demands on a network. Adaptive algorithms were identified, ones that respond to both the transient and evolutionary changes that arise in integrated networks. A new algorithm was developed, hybrid weighted routing, that adapts to workload changes.

Reed, Daniel A.↗
NASA NTRS1998

Weather Avoidance Using Route Optimization as a Decision Aid: An AWIN Topical Study

The aviation community is faced with reducing the fatal aircraft accident rate by 80 percent within 10 years. This must be achieved even with ever increasing, traffic and a changing National Airspace System. This is not just an altruistic goal, but a real necessity, if our growing level of commerce is to continue. Honeywell Technology Center's topical study, "Weather Avoidance Using Route Optimization as a Decision Aid", addresses these pressing needs. The goal of this program is to use route optimization and user interface technologies to develop a prototype decision aid for dispatchers and pilots. This decision aid will suggest possible diversions through single or multiple weather hazards and present weather information with a human-centered design. At the conclusion of the program, we will have a laptop prototype decision aid that will be used to demonstrate concepts to industry for integration into commercialized products for dispatchers and/or pilots. With weather a factor in 30% of aircraft accidents, our program will prevent accidents by strategically avoiding weather hazards in flight. By supplying more relevant weather information in a human-centered format along with the tools to generate flight plans around weather, aircraft exposure to weather hazards can be reduced. Our program directly addresses the NASA's five year investment areas of Strategic Weather Information and Weather Operations (simulation/hazard characterization and crew/dispatch/ATChazard monitoring, display, and decision support) (NASA Aeronautics Safety Investment Strategy: Weather Investment Recommendations, April 15, 1997). This program is comprised of two phases, Phase I concluded December 31, 1998. This first phase defined weather data requirements, lateral routing algorithms, an conceptual displays for a user-centered design. Phase II runs from January 1999 through September 1999. The second phase integrates vertical routing into the lateral optimizer and combines the user interface into a prototype software testbed. Phase II concludes with a dispatcher and pilot evaluation of the route optimizer decision aid. This document describes work completed in Phase I in contract with NASA Langley August 1998 - December 1998. This report includes: (1) Discuss how weather hazards were identified in partnership with experts, and how weather hazards were prioritized; (2) Static representations of display layouts for integrated planning function (3) Cost function for the 2D route optimizer; (4) Discussion of the method for obtaining, access to raw data of, and the results of the flight deck user information requirements definition; (5) Itemized display format requirements identified for representing weather hazards in a route planning aid.

Source record↗
NASA NTRS1991

The performance evaluation of a new neural network based traffic management scheme for a satellite communication network

A neural-network-based traffic management scheme for a satellite communication network is described. The scheme consists of two levels of management. The front end of the scheme is a derivation of Kohonen's self-organization model to configure maps for the satellite communication network dynamically. The model consists of three stages. The first stage is the pattern recognition task, in which an exemplar map that best meets the current network requirements is selected. The second stage is the analysis of the discrepancy between the chosen exemplar map and the state of the network, and the adaptive modification of the chosen exemplar map to conform closely to the network requirement (input data pattern) by means of Kohonen's self-organization. On the basis of certain performance criteria, whether a new map is generated to replace the original chosen map is decided in the third stage. A state-dependent routing algorithm, which arranges the incoming call to some proper path, is used to make the network more efficient and to lower the call block rate. Simulation results demonstrate that the scheme, which combines self-organization and the state-dependent routing mechanism, provides better performance in terms of call block rate than schemes that only have either the self-organization mechanism or the routing mechanism.

Ansari, Nirwan↗
NASA NTRS2012

I-FORCAST: Rapid Flight Planning Tool

I-FORCAST (Instrument - Field of Regard Coverage Analysis and Simulation Tool) is a flight planning tool specifically designed for quickly verifying the feasibility and estimating the cost of airborne remote sensing campaigns (see figure). Flights are simulated by being broken into three predefined routing algorithms as necessary: mapping in a snaking pattern, mapping the area around a point target (like a volcano) with a star pattern, and mapping the area between a list of points. The tool has been used to plan missions for radar, lidar, and in-situ atmospheric measuring instruments for a variety of aircraft. It has also been used for global and regional scale campaigns and automatically includes landings when refueling is required. The software has been compared to the flight times of known commercial aircraft route travel times, as well as a UAVSAR (Uninhabited Aerial Vehicle Synthetic Aperture Radar) campaign, and was within 15% of the actual flight time. Most of the discrepancy is due to non-optimal flight paths taken by actual aircraft to avoid restricted airspace and used to follow landing and take-off corridors.

Oaida, Bogdan↗
NASA NTRS2004

NASA Tech Briefs, June 2004

Topics covered include: COTS MEMS Flow-Measurement Probes; Measurement of an Evaporating Drop on a Reflective Substrate; Airplane Ice Detector Based on a Microwave Transmission Line; Microwave/Sonic Apparatus Measures Flow and Density in Pipe; Reducing Errors by Use of Redundancy in Gravity Measurements; Membrane-Based Water Evaporator for a Space Suit; Compact Microscope Imaging System with Intelligent Controls; Chirped-Superlattice, Blocked-Intersubband QWIP; Charge-Dissipative Electrical Cables; Deep-Sea Video Cameras Without Pressure Housings; RFID and Memory Devices Fabricated Integrally on Substrates; Analyzing Dynamics of Cooperating Spacecraft; Spacecraft Attitude Maneuver Planning Using Genetic Algorithms; Forensic Analysis of Compromised Computers; Document Concurrence System; Managing an Archive of Images; MPT Prediction of Aircraft-Engine Fan Noise; Improving Control of Two Motor Controllers; Electro-deionization Using Micro-separated Bipolar Membranes; Safer Electrolytes for Lithium-Ion Cells; Rotating Reverse-Osmosis for Water Purification; Making Precise Resonators for Mesoscale Vibratory Gyroscopes; Robotic End Effectors for Hard-Rock Climbing; Improved Nutation Damper for a Spin-Stabilized Spacecraft; Exhaust Nozzle for a Multitube Detonative Combustion Engine; Arc-Second Pointer for Balloon-Borne Astronomical Instrument; Compact, Automated Centrifugal Slide-Staining System; Two-Armed, Mobile, Sensate Research Robot; Compensating for Effects of Humidity on Electronic Noses; Brush/Fin Thermal Interfaces; Multispectral Scanner for Monitoring Plants; Coding for Communication Channels with Dead-Time Constraints; System for Better Spacing of Airplanes En Route; Algorithm for Training a Recurrent Multilayer Perceptron; Orbiter Interface Unit and Early Communication System; White-Light Nulling Interferometers for Detecting Planets; and Development of Methodology for Programming Autonomous Agents.

Source record↗
NASA NTRS1991

The effect of model uncertainty on some optimal routing problems

The effect of model uncertainties on optimal routing in a system of parallel queues is examined. The uncertainty arises in modeling the service time distribution for the customers (jobs, packets) to be served. For a Poisson arrival process and Bernoulli routing, the optimal mean system delay generally depends on the variance of this distribution. However, as the input traffic load approaches the system capacity the optimal routing assignment and corresponding mean system delay are shown to converge to a variance-invariant point. The implications of these results are examined in the context of gradient-based routing algorithms. An example of a model-independent algorithm using online gradient estimation is also included.

Mohanty, Bibhu↗
NASA NTRS1994

Crossbar Switches For Optical Data-Communication Networks

Optoelectronic and electro-optical crossbar switches called "permutation engines" (PE's) developed to route packets of data through fiber-optic communication networks. Basic network concept described in "High-Speed Optical Wide-Area Data-Communication Network" (NPO-18983). Nonblocking operation achieved by decentralized switching and control scheme. Each packet routed up or down in each column of this 5-input/5-output permutation engine. Routing algorithm ensures each packet arrives at its designated output port without blocking any other packet that does not contend for same output port.

Monacos, Steve P.↗
NASA NTRS1994

Design for dependability: A simulation-based approach

This research addresses issues in simulation-based system level dependability analysis of fault-tolerant computer systems. The issues and difficulties of providing a general simulation-based approach for system level analysis are discussed and a methodology that address and tackle these issues is presented. The proposed methodology is designed to permit the study of a wide variety of architectures under various fault conditions. It permits detailed functional modeling of architectural features such as sparing policies, repair schemes, routing algorithms as well as other fault-tolerant mechanisms, and it allows the execution of actual application software. One key benefit of this approach is that the behavior of a system under faults does not have to be pre-defined as it is normally done. Instead, a system can be simulated in detail and injected with faults to determine its failure modes. The thesis describes how object-oriented design is used to incorporate this methodology into a general purpose design and fault injection package called DEPEND. A software model is presented that uses abstractions of application programs to study the behavior and effect of software on hardware faults in the early design stage when actual code is not available. Finally, an acceleration technique that combines hierarchical simulation, time acceleration algorithms and hybrid simulation to reduce simulation time is introduced.

Goswami, Kumar K.↗
NASA NTRS1994

Unstructured grids on SIMD torus machines

Unstructured grids lead to unstructured communication on distributed memory parallel computers, a problem that has been considered difficult. Here, we consider adaptive, offline communication routing for a SIMD processor grid. Our approach is empirical. We use large data sets drawn from supercomputing applications instead of an analytic model of communication load. The chief contribution of this paper is an experimental demonstration of the effectiveness of certain routing heuristics. Our routing algorithm is adaptive, nonminimal, and is generally designed to exploit locality. We have a parallel implementation of the router, and we report on its performance.

Bjorstad, Petter E.↗
NASA NTRS1996

Balancing Contention and Synchronization on the Intel Paragon

The Intel Paragon is a mesh-connected distributed memory parallel computer. It uses an oblivious and deterministic message routing algorithm: this permits us to develop highly optimized schedules for frequently needed communication patterns. The complete exchange is one such pattern. Several approaches are available for carrying it out on the mesh. We study an algorithm developed by Scott. This algorithm assumes that a communication link can carry one message at a time and that a node can only transmit one message at a time. It requires global synchronization to enforce a schedule of transmissions. Unfortunately global synchronization has substantial overhead on the Paragon. At the same time the powerful interconnection mechanism of this machine permits 2 or 3 messages to share a communication link with minor overhead. It can also overlap multiple message transmission from the same node to some extent. We develop a generalization of Scott's algorithm that executes complete exchange with a prescribed contention. Schedules that incur greater contention require fewer synchronization steps. This permits us to tradeoff contention against synchronization overhead. We describe the performance of this algorithm and compare it with Scott's original algorithm as well as with a naive algorithm that does not take interconnection structure into account. The Bounded contention algorithm is always better than Scott's algorithm and outperforms the naive algorithm for all but the smallest message sizes. The naive algorithm fails to work on meshes larger than 12 x 12. These results show that due consideration of processor interconnect and machine performance parameters is necessary to obtain peak performance from the Paragon and its successor mesh machines.

Bokhari, Shahid H.↗
NASA NTRS2000

Adaptivity in Agent-Based Routing for Data Networks

Adaptivity, both of the individual agents and of the interaction structure among the agents, seems indispensable for scaling up multi-agent systems (MAS s) in noisy environments. One important consideration in designing adaptive agents is choosing their action spaces to be as amenable as possible to machine learning techniques, especially to reinforcement learning (RL) techniques. One important way to have the interaction structure connecting agents itself be adaptive is to have the intentions and/or actions of the agents be in the input spaces of the other agents, much as in Stackelberg games. We consider both kinds of adaptivity in the design of a MAS to control network packet routing. We demonstrate on the OPNET event-driven network simulator the perhaps surprising fact that simply changing the action space of the agents to be better suited to RL can result in very large improvements in their potential performance: at their best settings, our learning-amenable router agents achieve throughputs up to three and one half times better than that of the standard Bellman-Ford routing algorithm, even when the Bellman-Ford protocol traffic is maintained. We then demonstrate that much of that potential improvement can be realized by having the agents learn their settings when the agent interaction structure is itself adaptive.

Wolpert, David H.↗
NASA NTRS2010

Reconfigurable Robust Routing for Mobile Outreach Network

The Reconfigurable Robust Routing for Mobile Outreach Network (R3MOO N) provides advanced communications networking technologies suitable for the lunar surface environment and applications. The R3MOON techn ology is based on a detailed concept of operations tailored for luna r surface networks, and includes intelligent routing algorithms and wireless mesh network implementation on AGNC's Coremicro Robots. The product's features include an integrated communication solution inco rporating energy efficiency and disruption-tolerance in a mobile ad h oc network, and a real-time control module to provide researchers an d engineers a convenient tool for reconfiguration, investigation, an d management.

Lin, Ching-Fang↗
NASA NTRS2004

NASA Tech Briefs, February 2004

Topics include: Simulation Testing of Embedded Flight Software; Improved Indentation Test for Measuring Nonlinear Elasticity; Ultraviolet-Absorption Spectroscopic Biofilm Monitor; Electronic Tongue for Quantitation of Contaminants in Water; Radar for Measuring Soil Moisture Under Vegetation; Modular Wireless Data-Acquisition and Control System; Microwave System for Detecting Ice on Aircraft; Routing Algorithm Exploits Spatial Relations; Two-Finger EKG Method of Detecting Evasive Responses; Updated System-Availability and Resource-Allocation Program; Routines for Computing Pressure Drops in Venturis; Software for Fault-Tolerant Matrix Multiplication; Reproducible Growth of High-Quality Cubic-SiC Layers; Nonlinear Thermoelastic Model for SMAs and SMA Hybrid Composites; Liquid-Crystal Thermosets, a New Generation of High-Performance Liquid-Crystal Polymers; Formulations for Stronger Solid Oxide Fuel-Cell Electrolytes; Simulation of Hazards and Poses for a Rocker-Bogie Rover; Autonomous Formation Flight; Expandable Purge Chambers Would Protect Cryogenic Fittings; Wavy-Planform Helicopter Blades Make Less Noise; Miniature Robotic Spacecraft for Inspecting Other Spacecraft; Miniature Ring-Shaped Peristaltic Pump; Compact Plasma Accelerator; Improved Electrohydraulic Linear Actuators; A Software Architecture for Semiautonomous Robot Control; Fabrication of Channels for Nanobiotechnological Devices; Improved Thin, Flexible Heat Pipes; Miniature Radioisotope Thermoelectric Power Cubes; Permanent Sequestration of Emitted Gases in the Form of Clathrate Hydrates; Electrochemical, H2O2-Boosted Catalytic Oxidation System; Electrokinetic In Situ Treatment of Metal-Contaminated Soil; Pumping Liquid Oxygen by Use of Pulsed Magnetic Fields; Magnetocaloric Pumping of Liquid Oxygen; Tailoring Ion-Thruster Grid Apertures for Greater Efficiency; and Lidar for Guidance of a Spacecraft or Exploratory Robot.

Source record↗
NASA NTRS2004

NASA Tech Briefs, December 2004

opics include: High-Rate Digital Receiver Board; Signal Design for Improved Ranging Among Multiple Transceivers; Automated Analysis, Classification, and Display of Waveforms; Fast-Acquisition/Weak-Signal-Tracking GPS Receiver for HEO; Format for Interchange and Display of 3D Terrain Data; Program Analyzes Radar Altimeter Data; Indoor Navigation using Direction Sensor and Beacons; Software Assists in Responding to Anomalous Conditions; Software for Autonomous Spacecraft Maneuvers; WinPlot; Software for Automated Testing of Mission-Control Displays; Nanocarpets for Trapping Microscopic Particles; Precious-Metal Salt Coatings for Detecting Hydrazines; Amplifying Electrochemical Indicators; Better End-Cap Processing for Oxidation-Resistant Polyimides; Carbon-Fiber Brush Heat Exchangers; Solar-Powered Airplane with Cameras and WLAN; A Resonator for Low-Threshold Frequency Conversion; Masked Proportional Routing; Algorithm Determines Wind Speed and Direction from Venturi-Sensor Data; Feature-Identification and Data-Compression Software; Alternative Attitude Commanding and Control for Precise Spacecraft Landing; Inspecting Friction Stir Welding using Electromagnetic Probes; and Helicity in Supercritical O2/H2 and C7H16/N2 Mixing Layers.

Source record↗