System for communicating labeled routing trees to establish...

Details System for communicating labeled routing trees to establish... System for communicating labeled routing trees to establish...

1999-10-15

2004-12-28

Nguyen, Hanh (Department: 2662)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C370S338000, C370S351000, C370S256000, C709S241000, C709S242000

Reexamination Certificate

active

06836463

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to routing protocols in computer networks, and more particularly, routing protocols in ad hoc networks with radio links.
BACKGROUND
Multi-hop packet-radio networks, or ad hoc networks, consist of mobile hosts interconnected by routers that can also move. The deployment of such routers is ad hoc and the topology of such networks is very dynamic, because of host and router mobility, signal loss and interference, and power outages. In addition, the channel bandwidth available in ad hoc networks is relatively limited compared to wired networks, and untethered routers may need to operate with battery-life constraints. In these networks, routing must preferably be accomplished using as few a number of control messages and neighbor-to-neighbor handshakes as possible, in order to conserve channel bandwidth for user data and preserve the battery life of untethered nodes. Because of the dynamics of the topology in an ad hoc network, broadcast radio links are preferable for interconnecting routers without the need for topology planning.
Routing protocols for computer networks can be categorized according to: (a) the type of information the protocols use to compute preferred paths, and (b) the way in which routers obtain routing information. In terms of the type of information used by routing protocols, routing protocols can be classified into link-state protocols and distance-vector protocols. Routers running a link-state protocol use topology information to make routing decisions; routers running a distance-vector protocol use distances and, in some cases, path information, to destinations to make routing decisions.
In terms of the way in which routers obtain information, routing protocols have been classified as either table-driven or on-demand. In an on-demand routing protocol, routers maintain path information for only those destinations that they need to contact as a source or relay of information. The basic approach consists of allowing a router that does not know how to reach a destination to send a flood-search message to obtain the path information it needs. One of the first routing protocols of this type was proposed to establish virtual circuits in the MSE network, see V. O. K. Li and R. Chang, “Proposed routing algorithms for the US Army mobile subscriber equipment (MSE) network,” Proc. IEEE MILCOM'86, Monterey, Calif., October 1986, and there are several other, recent examples of this approach (e.g., AODV, see C. Perkins, “Ad Hoc On Demand Distance Vector (AODV) Routing,” draft-ietf-manet-aodv-00.txt, November 1997; ABR, see C-K. Toh, “Wireless ATM & Ad Hoc Networks,” Kluwer, November 1996; DSR, see D. Johnson and D. Maltz, “Protocols for Adaptive Wireless and Mobile Networking,” IEEE Pers. Commun., Vol. 3, No. 1, February 1996; TORA, see V. Park and M. Corson, “A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks,”′ Proc. IEEE INFOCOM 97, Kobe, Japan, April 1997; SSA, see R. Dube et al., “Signal Stability-Based Adaptive Routing (SSA) for Ad Hoc Mobile Networks,” IEEE Pers. Commun., February 1997; and ZRP, see Z. Haas and M. Pearlman, “The Zone Routing Protocol for Highly Reconfigurable Ad Hoc Networks,” Proc. ACM SIGCOMM 98, Vancouver, British Columbia, August 1998). The Dynamic Source Routing (DSR) protocol has been shown to outperform many other on-demand routing protocols. J. Broch et al, “A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols,” Proc. ACM MOBICOM 98, Dallas, Tex., October 1998. The existing on-demand routing protocols differ on the specific mechanisms used to disseminate flood-search packets and the responses thereto, the means used to cache information received during other nodes' searches, and the manner in which to determine the cost of a link and the existence of a neighbor. However, one common characteristic of all of the on-demand routing protocols reported to date is that such protocols are based on distances to destinations. Stated differently, there have been no on-demand link-state routing protocol proposals to date.
In a table-driven scheme, each router maintains path information for each known destination in the network and updates its routing-table entries as needed. Examples of table-driven algorithms based on distance vectors are the routing protocol of the DARPA packet-radio network, J. Jubin and J. Tomow, “The DARPA Packet Radio Network Protocols,” Proceedings of the IEEE, Vol. 75, No. 1, January 1987; DSDV, C. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,” Proc. ACM SIGCOMM 94, London, UK, October 1994; WRP, S. Murthy and J. J. Garcia-Luna-Aceves, “An Efficient Routing Protocol for Wireless Networks,” ACM Mobile Networks and Applications Journal, Special issue on Routing in Mobile Communication Networks, 1996; WIRP, J. J. Garcia-Luna-Aceves et al., “Wireless Internet Gateways (WINGS),” Proc. IEEE MILCOM'97, Monterey, Calif., November 1997; and least-resistance routing protocols, M Pursley and H. B. Russell, “Routing in Frequency-Hop Packet Radio Networks with Partial-Band Jamming,” IEEE Trans. Commun., Vol. 41, No. 7, pp. 1117-1124, 1993.
Prior table-driven approaches to link-state routing in packet-radio networks are based on topology broadcasts. However, disseminating complete link-state information to all routers incurs excessive communication overhead in an ad hoc network because of the dynamics of the network and the small bandwidth available. Accordingly, all existing link-state routing approaches for packet-radio networks have been based on hierarchical routing schemes. R. Ramanathan and M. Steenstrup, “Hierarchically-organized, Multihop Mobile Wireless Networks for Quality-of-Service Support,” ACM Mobile Networks and Applications, Vol.3, No. 1, pp. 101-119, 1998; C. V. Ramamoorthy and W. Tsai, “An Adaptive Hierarchical Routing Algorithm,” Proceedings of IEEE COMPSAC '83, Chicago, Ill., pp. 93-104, November 1983; and M. Steenstrup (ed.), Routing in Communication Networks, Prentice-Hall, 1995. Also, prior proposals for link-state routing using partial link-state data without clusters, see, e.g., J. J. Garcia-Luna-Aceves and J. Behrens, “Distributed, scalable routing based on vectors of link states,” IEEE Journal on Selected Areas in Communications, Vol. 13, No. 8, 1995; and J. J. Garcia-Luna-Aceves and M. Spohn, “Scalable Link-State Internet Routing,” Proc. IEEE International Conference on Network Protocols (ICNP 98), Austin, Tex., Oct. 14-16, 1998, require routers to explicitly inform their neighbors which links they use and which links they stop using.
A number of prior routing protocols are based on the notion of routing trees, in which routers communicate either the state (i.e., cost or length) of the links in a shortest-path routing tree, or the distance from the root of the tree and the second-to-last hop in the routing tree for each node in the tree. An early example of this type of protocol was proposed in U.S. Pat. No. 4,466,060 to Riddle. In Riddle's protocol, a router communicates different routing trees to different neighbors; such trees are called “exclusionary trees” and specify the preferred paths to destinations excluding those paths that involve the router to which the update is being sent. An update packet or message specifies an entire exclusionary tree. Another protocol based on routing trees was reported by Garcia-Luna-Aceves, J. J. Garcia-Luna-Aceves, “A Fail-Safe Routing Algorithm for Multihop Packet-Radio networks,” Proc. IEEE Infocom 86, Miami, Fla., April 1986, which protocol differs from Riddle's protocol in that the same routing tree is sent incrementally by a router to all its neighbors. A. Humblet, “Another Adaptive Shortest-Path Algorithm,” IEEE Trans. Comm., Vol.39, No.6, June 1991, pp.995-1003 (and see U.S. Pat. No. 4,987,536); Cheng et al., C. Cheng et al., “A Loop-Free Extended Bellman-Ford Routing Protocol without Bouncing Effect”, Proc. ACM SIGCOMM 89, pp.224-236; B. Rajagopalan and M. Faim

Affiliated with

Also associated with

Rating

System for communicating labeled routing trees to establish... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System for communicating labeled routing trees to establish..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for communicating labeled routing trees to establish... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3316766