Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1999-03-12
2003-12-23
Pham, Chi (Department: 2663)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S254000, C370S400000
Reexamination Certificate
active
06667957
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is directed to a highly-adaptive, loop-free, distributed routing algorithm for dynamic networks. The invention utilizes one of a family of algorithms which is known as a “link reversal” algorithm. The invention structures reactions as a temporally-ordered sequence of diffusing computations, with each computation including a sequence of directed link reversals. The invention is well suited for use in large, dynamic, bandwidth-constrained networks. In such networks, rapid route maintenance with a minimum of communication overhead provides higher performance.
2. Description of the Related Art
Traditionally, practical datagram routing algorithms are designed for operation in static or quasi-static networks with hardwired links. In such networks bandwidth is relatively abundant, and the protocol design goals involve minimization of router state (to permit scalability) and rapid reaction to topological changes when they occur (to ensure good data routing performance). In other words, limiting protocol storage and time complexity are the primary design goals.
Distance-vector routing algorithms based on the distributed Bellmann-Ford (BF) computation, such as the Routing Information Protocol (RIP) were among the earliest approaches. However, these approaches suffered from the well-known “counting-to-infinity” problem that affected the time complexity (i.e., convergence times) of these protocols. There has been a large amount of theoretical and practical work seeking to remedy this problem and improve the performance of distance-vector approaches. The development of link-state routing algorithms provided an alternative approach, in which the entire network topology is distributed to all nodes, allowing each router to independently compute paths to every destination. However, nearly all of this work continued in the direction started by the BF work and focused on the problem of “shortest-path” routing. Shortest path routing techniques seek to route traffic over the “least cost” path to the destination (often times the shortest path measured in hop count), an approach that optimal routing theory indicates is favorable during periods of light traffic. One aspect inherent in this work is that supporting a shortest-path computation requires a certain amount of communication complexity within the routing protocol. This, in turn, requires that sufficient bandwidth be available in the network to enable the computation while still leaving enough bandwidth for actual data routing.
The invention considers the problem of routing in a dynamic network. An example of such a network is a mobile, multihop, wireless network which can be envisioned as a collection of routers (equipped with wireless receiver/transmitters) that are free to move about arbitrarily. The status of the communication links between the routers, at any given time, is a function of their positions, transmission power levels, antenna patterns, co-channel interference levels, and other time-varying factors. Thus, the mobility of the routers and variability of other connectivity factors result in a network with a potentially rapidly and unpredictably changing topology. Congested links are also an expected characteristic of such a network, as wireless links inherently have significantly lower capacity than their hardwired counterparts and are therefore more prone to congestion. The highly dynamic and bandwidth-constrained nature of mobile networks most dramatically alters the trade-offs to be made in protocol design. Thus, it is communication complexity, not storage complexity, that is the greater determinant of protocol scalability in these networks. The combination of network size, topology dynamics and available bandwidth determines when approaches that do not perform shortest-path routing may be more desirable.
SUMMARY OF THE INVENTION
A routing algorithm which is well-suited for operation in a relatively dynamic or bandwidth-constrained networking environment, for example a mobile wireless networking environment, should therefore possess the following attributes:
Executes distributedly
Provides loop-free routes
Provides multiple routes (to alleviate congestion)
Establishes routes quickly (so they may be used before the topology changes)
Minimizes communication overhead by localizing algorithmic reaction to topological changes when possible (to conserve available bandwidth and increase scalability)
Based on these attributes, the inventors have developed a method referred to as the Temporally Ordered Routing Algorithm (TORA) which is a new routing method that is tailored for operation in a highly-dynamic networking environment, such as a mobile network. TORA's design is based largely on the notion that high reactivity (i.e., low time complexity) and bandwidth conservation (i.e., low communication complexity) are of greater importance than routing optimality (i.e., determination of the shortest-path). A key concept in its design is an attempt to decouple (to the greatest extent possible) the generation of potentially far-reaching control message propagation from the dynamics of the network topology. The “scope” of control messaging following topological changes is typically localized to a very small set of nodes near the change without having to resort to a dynamic, hierarchical routing solution with its attendant complexity. A possible enhancement to the protocol (to be discussed later) would be to imbed farther-reaching control message propagation into the protocol as a secondary mechanism. This propagation would occur periodically at a very low rate, independent of the network topology dynamics, and would be employed as a means of infrequent route optimization and soft-state route verification.
TORA is distributed, in that nodes need only maintain information about adjacent nodes (i.e., one-hop knowledge). Like a distance-vector routing algorithm, TORA maintains state on a per-destination basis. This property is exploited in the design by establishing routing for each given destination on-demand, since it may not be necessary (nor desirable) to maintain routes between every source/destination pair at all times. The overhead expended to establish a route between a given source/destination pair will be wasted if the source does not require the route prior to its invalidation due to topological changes. Thus, TORA is “source initiated” and creates a set of routes to a given destination only when there is message traffic for that destination. It guarantees all routes are loop-free, and typically provides multiple routes for any source/destination pair that requires a route. Since having a single route is sufficient, many topological changes require no algorithmic reaction. Following topological changes that do require reaction, the protocol quickly re-establishes valid routes. This ability to initiate and react infrequently serves to further minimize communication overhead. Finally, in the event of a network partition, the protocol detects the partition and erases all invalid routes. While not described here, TORA may be easily modified to run in a traditional proactive, “destination-initiated” mode where all nodes actively maintain routing to a given destination (presumably a “frequent destination” for many nodes), thereby removing the need for source-initiated, on-demand route creation.
REFERENCES:
patent: 4905233 (1990-02-01), Cain et al.
patent: 5088032 (1992-02-01), Bosack
patent: 5138615 (1992-08-01), Lamport et al.
patent: 5412654 (1995-05-01), Perkins
M.S. Corson, S. Batsell and J. Macker, Architectural considerations for mobile mesh networking, working draft, May 1996, available at http://tonnant.itd.nrl.navy.mil/mmnet/mmnetRFC.txt.*
V.D. Park, M.S. Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Apr. 1997, Proceeding INFOCOM '97.
Corson Mathew Scott
Park Vincent Douglas
George Keith M.
Pham Chi
Squire Sanders & Dempsey L.L.P.
University of Maryland
LandOfFree
Adaptive routing method for a dynamic network does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive routing method for a dynamic network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive routing method for a dynamic network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3170917