ISR research accomplishments
Temporally-Ordered Routing Algorithm
Research team
M. Scott Corson, Vincent Park, Matthew Impett (all ISR)
Accomplishment
The Temporally-Ordered Routing Algorithm (TORA) is a scalable routing algorithm originally designed for Mobile Ad Hoc Networks (MANETs). It represents a significant departure from traditional routing technology, and is potentially applicability for use in fixed/mobile-converged Internet domains as well.
Use of non-shortest path routing. TORA was originally conceived as a MANET routing algorithm where it is intended for use in large-scale, dynamic, bandwidth-constrained MANETs. The principle objective behind its design is the achievement of "flat scalability", i.e. achieving a high degree of scalability (measured as the number of routers in a domain) with a "flat", non-hierarchical routing algorithm. In its operation the algorithm attempts to suppress, to the greatest extent possible, the generation of far-reaching control message propagation. To do so, the protocol forgoes support of shortest-path routing--a significant departure from traditional routing algorithms.
Approach. TORA builds and maintains a Directed Acyclic Graph rooted at a destination. For a given destination, each participating node i is assigned a height defined as an ordered quintuple
Impact
No two nodes may have the same height (i.e. the set of heights is totally-ordered).
Information may flow from nodes
with higher heights to nodes with lower heights. Conceptually,
information can be thought of as a fluid that may only flow downhill
(see adjoining Figure). By maintaining a set of totally-ordered
heights at all times, it is easy to see how loop-free, multipath
routing is assured. Information would have to flow uphill to
form a loop, and this is not permitted.
Ongoing work
TORA has and is being transitioned to the commercial world:
- NOVA Engineering of Cincinnati, Ohio has developed TORA as a MANET routing protocol, and it is available in a product for purchase.
- Telcordia will be developing a separate commercial MANET kernel that utilizes TORA as its unicast routing protocol.
- The Boeing Company is currently funding research to extend TORA enabling the deployment of large-scale ad hoc networks.
- British Telecommunications, PLC is funding extensions to and IETF-based standardization of TORA to permit development of large-scale Fixed/Mobile-Converged IP-Based networks.
- National Science Foundation-funded research is exploring the usage of TORA to enable development of bi-level, community-based ad hoc networks.
Extensions of the protocol may permit:
- Development of large-scale, ad hoc domains numbering in the thousands of routers for usage in battlefield scenarios or for large-scale sensor webs,
- The fusion of fixed and MANET routing permitting, for the first time, the deployment of Internet routing technology for IP-based cellular networks that handles mobility within the routing protocol,
- The deployment of large-scale, community ad hoc wireless networks that overlay urban areas, eliminating the need to use fixed network infrastructures for localized urban communications.
For more information
TORA was developed under funding from the Army Research Laboratory under its ATIRP Program and as part of the Navy’s ongoing education program.
NOVA Engineering of Cincinnati, Ohio has developed TORA as a MANET routing protocol, and it is available in a product for purchase. The product is the NovaRoam Wireless Router at http://www.nova-eng.com/novaroam.html.
V. Park, M.S. Corson, “A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks,” Proc. IEEE INFOCOM ‘97, April 1997.
V. Park, M.S. Corson, “A Performance Comparison of the Temporally-Ordered Routing Algorithm and Ideal Link State Routing,” in Proc. ISCC '98, Athens, Greece, July 1998.
Additional information on TORA and some of its extensions can be found at:
M. Scott Corson, A. O’Neill, “An Approach to Fixed/Mobile-Converged Routing”, Institute for Systems Research Technical Report, TR 2000-5, University of Maryland, March 2000.
V. Park, S. Corson, "The Temporally-Ordered Routing Protocol (TORA) Specification," Internet Draft (work in progress), October 1999.
A. O'Neill, G. Tsirtsis, S. Corson, "Edge Mobility Architecture", Internet Draft (work in progress), October 1999.
