Reduced-overhead protocol for discovering new neighbor nodes and detecting the loss of existing neighbor nodes in a network Number:7,031,288 from the United States Patent and Trademark Office (PTO) owispatent

Title: Reduced-overhead protocol for discovering new neighbor nodes and detecting the loss of existing neighbor nodes in a network

Abstract: A protocol for discovering a new neighbor node and detecting the loss of an existing neighbor node in a network is described. A node receives a neighbor discovery message from a neighbor node. The node receiving the neighbor discovery message periodically transmits a predetermined number of neighbor discovery messages in response to the received neighbor discovery message. Each neighbor discovery message includes an identity of the neighbor node. After transmitting the predetermined number of neighbor discovery messages, the node transmits neighbor discovery messages that omit the identity of the neighbor node until another neighbor discovery message is received from the neighbor node that indicates a change in a communications state associated with the neighbor node.

Patent Number: 7,031,288 Issued on 04/18/2006 to Ogier

---

Inventors:	Ogier; Richard G. (Half Moon Bay, CA)
Assignee:	SRI International (Menlo Park, CA)
Appl. No.:	728192
Filed:	December 1, 2000

---

Current U.S. Class:	370/338 ; 370/351; 370/401; 370/439
Current International Class:	H04Q 7/24 (20060101)
Field of Search:	370/229,230,230.1,235,238,248,252,254,256,257,258,278,310.2,312,315,329,331,332,335,338,346,350,377,384,402,255,399,395.32,228,400,410,448,477,342,401,408,440,496,282,432,491,328,351,352,392,395.52,437,465,468,469,397,313,353,354,386,389,395.31,404,405,439 375/133,225 455/73,343.3,519,574 709/220,224,238,250,477,200,223,242 710/100,104

---

References Cited [Referenced By]

---

U.S. Patent Documents

	5056085		October 1991		Vu
	5079767		January 1992		Perlman
	5506838		April 1996		Flanagan
	5572528		November 1996		Shuen
	5574860		November 1996		Perlman et al.
	5657317		August 1997		Mahany et al.
	5732086		March 1998		Liang et al.
	5805818		September 1998		Perlman et al.
	5844900		December 1998		Hong et al.
	6023461		February 2000		Raychaudhuri et al.
	6026077		February 2000		Iwata
	6044062		March 2000		Brownrigg et al.
	6058422		May 2000		Ayanoglu et al.
	6088730		July 2000		Kato et al.
	6097707		August 2000		Hodzic et al.
	6104712		August 2000		Robert et al.
	6178172		January 2001		Rochberger
	6192053		February 2001		Angelico et al.
	6212188		April 2001		Rochberger et al.
	6304556		October 2001		Haas
	6385174		May 2002		Li
	6456599		September 2002		Elliott
	6556574		April 2003		Pearce et al.
	6621805		September 2003		Kondylis et al.
	6625124		September 2003		Fan et al.
	6704293		March 2004		Larsson et al.
	6856627		February 2005		Saleh et al.
	2003/0037167		February 2003		Garcia-Luna-Aceves et al.

Foreign Patent Documents

	0 944 210		Sep., 1999		EP

Other References

"IP Mobility Support," C. Perkins, Editor, IBM, Oct. 1996, http://www.ietf.org/rfc/rfc2002.txt, printed Oct. 4, 2000, 56 pages. cite- d by other . "IPv6--the Next Generation Internet Protocol," Jack McCann, UNIX Internet Engineering, Digital Equipment Corporation, May 13, 1998, http://www.bblisa.org/docs/May.sub.--98/sld001.htm, printed Sep. 6, 2000, 45 pages. cited by other . "An Ipv6 Aggregatable Global Unicast Address Format," P, Hinden, Nokia; M. O'Dell, UUNET; S. Deering, Cisco, Jul. 1998, http://www.ietf.org/rfc/rfc2374.txt?number=2374, printed Oct. 10, 2000, 9 pages. cited by other . "IP Version 6 Addressing Architecture," R. Hinden, Nokia, S. Deering, Cisco Systems, Jul. 1998, http://www.ietf.org/rfc/rfc2373.txt?number=2373, printed Oct. 17, 2000, 19 pages. cited by other . "Internet Protocol, Version 6 (IPv6) Specification," S. Deering, Cisco; R. Hinden, Nokia, Dec. 1998, http://www.ietf.org/rfc/rfc2460.txt?number=2460, printed Oct. 10, 2000, 28 pages. cited by other . "A Reliable, Efficient Topology Broadcast Protocol for Dynamic Networks," by Bhargav Bellur and Richard G. Ogier, Appeared in IEEE INFOCOM '99 Proceedings. cited by other . "IP Network Address Translator (NAT) Terminology and Considerations," P. Srisuresh, M. Holdrege, Lucent Technologies, Aug. 1999, http://www.ietf.org/rfc/rfc2663.txt, printed Oct. 11, 2000, 26 pages. cit- ed by other . "Mobile IP Network Access Identifier Extension for IPv4," P. Calhoun, Sun Microsystems Laboratories, C. Perkins, Nokia Research Center, Mar. 2000, http://www.ietf.org/rfc/rfc2794.txt, printed Oct. 4, 2000, 7 pages. cited by other . "Guidelines For 64-Bit Global Identifier (EUI-64) Registration Authority," http://standards.ieee.org/regauth/oui/tutorials/EUI64.html, printed Nov. 3, 2000, 2 pages. cited by other . International Search Report dated Oct. 7, 2002 for corresponding application, PCT/US01/28466. cited by other . Tsirtsis et al. (Feb. 2000) "Network Address Translation--Protocol Translation (NAT-PT)", Request for Comments: 2766, Campio Communications, 16 pgs. cited by other . Gilligan et al. (Mar. 13, 1999) "Transition Mechanisms for Ipv6 Host and Routers", Internet Draft Online!, retrieved from the Internet on Jan. 14, 2002: <URL:http://www.ietf.org/proceedings/99jul/I-D/draft-ietf-ngtran- s-mech-04/txt>, pp. 1-24. cited by other . Hinden et al. (Jul. 1998) "An Ipv6 Aggregatable Global Unicast Address Format", Internet Draft Online!, retrieved from the Internet on Jan. 14, 2002: <URL:http://www.faqs.org/rfcs/rfc2374.html>, pp. 1-8. cited by other . Templin (Mar. 2000) "An Ipv6-Ipv4 Compatibility Aggregatable Global Unicast Address Format", Internet Draft Online!, retrieved from the Internet on Jan. 15, 2002: <URL:http://alternic.net/drafts/drafts-t-u/draft-templin-ngtrans-v6v4c- ompat-00.txt>, pp. 1-12. cited by other . Templin (Sep. 22, 2000) "An Ipv6-Ipv4 Compatibility Aggregatable Global Unicast Address Format for Incremental Deployment of Ipv6 Nodes within Predominantly Ipv4-based Intranets", Internet Draft Online!, retrieved from the Internet on Jan. 14, 2002: <URL:http://www.join.uni-muenster.de/drafts/draft-templin-ngtrans-v6v4- compat-01.txt>, pp. 1-14. cited by other . "A Multicast Routing Protocol for Multihop Wireless Networks," Chunhung Richard Lin and Shiang-Wei Chao, Global Telecommunications Conference--Globecomm '99, p. 235-239. cited by other.

Primary Examiner: Sam; Phirin
Attorney, Agent or Firm: Tong, Esq.; Kin-Wah Patterson & Sheridan, LLP

---

Government Interests

---

GOVERNMENT SUPPORT

This invention was funded with government support under Contract No. DAAB07-96-D-H002, awarded by the U.S. Army Communications and Electronics Command. The United States government has certain rights to this invention.

---

Parent Case Text

---

RELATED APPLICATION

This application claims the benefit of the filing date of co-pending U.S. Provisional Application, Serial No. 60/232,046, filed Sep. 12, 2000, entitled "Reduced Overhead Hello Protocol," the entirety of which provisional application is incorporated by reference herein.

---

Claims

---

What is claimed is:

1. A method of operating a network having a plurality of nodes, comprising: maintaining in a receiving node a neighbor table comprised of each known neighbor node of the receiving node and the communication status of each known neighbor node; receiving a HELLO message containing an address of a new sending node; transmitting a NEIGHBOR message that includes an address of the receiving node to said new sending node; receiving a NEIGHBOR ACK message from said new sending node; updating said neighbor table to reflect discovery of said new sending node and communication status of said new sending node; and transmitting at least one HELLO message comprising only a list of neighbor nodes that have communication status changes, wherein each of said at least one HELLO message includes the address of the receiving node and a list of neighbor nodes that have their communication status changed to a lost status, wherein a neighbor node is determined to be in the lost status when a HELLO message containing the address of that neighbor node has not been heard by the receiving node in a predetermined period of time.

2. The method of claim 1, wherein the predetermined period of time corresponds to a HELLO-INTERVAL period multiplied by a predetermined number K.

3. The method of claim 1, further comprising subsequently transmitting at least one HELLO message containing the address of the receiving node but not the address of a neighbor node that was previously in the list of neighbor nodes in the lost state.

4. The method of claim 1, further comprising subsequently transmitting at least one HELLO message containing a list of neighbor nodes in a lost status, wherein that list of neighbor nodes includes a neighbor node that was in a previous list of neighbor nodes in a heard status.

5. The method of claim 1, further comprising subsequently transmitting at least one HELLO message containing a list of neighbor nodes in a lost status, wherein that list of neighbor nodes includes a neighbor node that was in a previous list of neighbor nodes in a symmetric status.

6. The method of claim 1, further comprising subsequently transmitting at least one HELLO message containing a list of neighbor nodes in a symmetric status, wherein that list of neighbor nodes includes a neighbor node that was in a previous list of neighbor nodes in a heard status.

7. A network having a plurality of nodes, comprising: a new sending node; and a receiving node having a neighbor table comprised of each known neighbor node of the receiving node and the communication status of each known neighbor node, wherein said receiving node receives a HELLO message from said new sending node containing an address of said new sending node, wherein said receiving node transmits a NEIGHBOR message that includes an address of the receiving node to said new sending node, wherein said receiving node receives a NEIGHBOR ACK message from said new sending node, wherein said receiving node updates said neighbor table to reflect discovery of said new sending node and communication status of said new sending node, wherein said receiving node transmits at least one HELLO message comprising only a list of neighbor nodes that have communication status changes, and wherein each of said at least one HELLO message includes the address of the receiving node and a list of neighbor nodes that have their communication status changed to a lost status, wherein a neighbor node is determined to be in the lost status when a HELLO message containing the address of that neighbor node has not been heard by the receiving node in a predetermined period of time.

8. The network of claim 7, wherein the predetermined period of time corresponds to a HELLO-INTERVAL period multiplied by a predetermined number K.

9. The network of claim 7, wherein said receiving node subsequently transmits at least one HELLO message containing the address of the receiving node but not the address of a neighbor node that was previously in the list of neighbor nodes in the lost state.

10. The network of claim 7, wherein said receiving node subsequently transmits at least one HELLO message containing a list of neighbor nodes in a lost status, wherein that list of neighbor nodes includes a neighbor node that was in a previous list of neighbor nodes in a heard status.

11. The network of claim 7, wherein said receiving node subsequently transmits at least one HELLO message containing a list of neighbor nodes in a lost status, wherein that list of neighbor nodes includes a neighbor node that was in a previous list of neighbor nodes in a symmetric status.

12. The network of claim 7, wherein said receiving node subsequently transmits at least one HELLO message containing a list of neighbor nodes in a symmetric status, wherein that list of neighbor nodes includes a neighbor node that was in a previous list of neighbor nodes in a heard status.

13. A method of operating a network having a plurality of nodes, comprising: maintaining in a receiving node a neighbor table comprised of each known neighbor node of the receiving node and the communication status of each known neighbor node; receiving a HELLO message containing an address of a new sending node; transmitting a NEIGHBOR message that includes an address of the receiving node to said new sending node; receiving a NEIGHBOR ACK message from said new sending node; updating said neighbor table to reflect discovery of said new sending node and communication status of said new sending node; and transmitting at least one HELLO message comprising only a list of neighbor nodes that have communication status changes, wherein each of said at least one HELLO message includes the address of the receiving node and a list of neighbor nodes that have their communication status changed to a heard status, wherein neighbor nodes in the heard status have been heard by the receiving node but have not been determined to have heard a previous HELLO message from the receiving node.

14. A method of operating a network having a plurality of nodes, comprising: maintaining in a receiving node a neighbor table comprised of each known neighbor node of the receiving node and the communication status of each known neighbor node; receiving a HELLO message containing an address of a new sending node; transmitting a NEIGHBOR message that includes an address of the receiving node to said new sending node; receiving a NEIGHBOR ACK message from said new sending node; updating said neighbor table to reflect discovery of said new sending node and communication status of said new sending node; and transmitting at least one HELLO message comprising only a list of neighbor nodes that have communication status changes, wherein each of said at least one HELLO message includes the address of the receiving node and a list of neighbor nodes that have their communication status changed to a symmetric status, wherein neighbor nodes in the symmetric status have been heard by the receiving node and have been determined to have heard a previous HELLO message from the receiving node.

15. A network having a plurality of nodes, comprising: a new sending node; and a receiving node having a neighbor table comprised of each known neighbor node of the receiving node and the communication status of each known neighbor node, wherein said receiving node receives a HELLO message from said new sending node containing an address of said new sending node, wherein said receiving node transmits a NEIGHBOR message that includes an address of the receiving node to said new sending node, wherein said receiving node receives a NEIGHBOR ACK message from said new sending node, wherein said receiving node updates said neighbor table to reflect discovery of said new sending node and communication status of said new sending node, wherein said receiving node transmits at least one HELLO message comprising only a list of neighbor nodes that have communication status changes, and wherein each of said at least one HELLO message includes the address of the receiving node and a list of neighbor nodes that have their communication status changed to a heard status, wherein neighbor nodes in the heard status have been heard by the receiving node but have not been determined to have heard a previous HELLO message from the receiving node.

16. A network having a plurality of nodes, comprising: a new sending node; and a receiving node having a neighbor table comprised of each known neighbor node of the receiving node and the communication status of each known neighbor node, wherein said receiving node receives a HELLO message from said new sending node containing an address of said new sending node, wherein said receiving node transmits a NEIGHBOR message that includes an address of the receiving node to said new sending node, wherein said receiving node receives a NEIGHBOR ACK message from said new sending node, wherein said receiving node updates said neighbor table to reflect discovery of said new sending node and communication status of said new sending node, wherein said receiving node transmits at least one HELLO message comprising only a list of neighbor nodes that have communication status changes, and wherein each of said at least one HELLO message includes the address of the receiving node and a list of neighbor nodes that have their communication status changed to a symmetric status, wherein neighbor nodes in the symmetric status have been heard by the receiving node and have been determined to have heard a previous HELLO message from the receiving node.

---

Description

---

BACKGROUND

In mobile wireless networks and in the Internet, each router must keep informed of the neighboring routers with which it can establish bi-directional communications using a neighbor discovery protocol. Many existing neighbor discovery protocols have excessive communication overhead, and thus consume excessive bandwidth in networks with limited bandwidth. There remains, therefore, a need for an improved neighbor discovery protocol that can efficiently establish bi-directional links between communications entities.

SUMMARY OF THE INVENTION

One objective of the invention is to provide a protocol that enables nodes in a mobile ad hoc network or in an internet to quickly detect neighboring nodes with which the nodes have a direct and symmetric link (i.e., the nodes at both ends of the link can hear each other). Another objective is for the protocol to operate under conditions typically adverse to reliable communications, such as asymmetric (unidirectional) links between any two nodes in the network at any time, frequent changes in the state of the links because of the mobility of nodes and interference caused, for example, by intervening obstacles, and unsuccessfully transmitted packets because of noise in the communication channel. Still another objective is for the protocol to be responsive to network topology changes.

In one aspect, the invention features a method for discovering a neighbor node in a network of nodes. A neighbor discovery message is received from a neighbor node. A predetermined number of neighbor discovery messages are periodically transmitted in response to the received neighbor discovery message. Each neighbor discovery message includes an identity of the neighbor node. After transmitting the predetermined number of neighbor discovery messages, neighbor discovery messages that omit the identity of the neighbor node are transmitted until another neighbor discovery message is received from the neighbor node that indicates a change in a communications state associated with the neighbor node.

If a neighbor discovery message is not received from the neighbor node within a predetermined time period, that neighbor node is determined to be in a lost state. The predetermined time period has a duration that approximately equals the duration of a time interval between subsequent transmissions of neighbor discovery messages multiplied by the predetermined number.

When a neighbor discovery message is received from the neighbor node by a particular node, the neighbor node is identified as being in a symmetric state if the received neighbor discovery message includes an identity of the particular node in a list of neighbor nodes identified by the neighbor node as being in a heard state. In response to identifying the neighbor node as being in the symmetric state, the identity of the neighbor node can be omitted from a subsequently transmitted neighbor discovery message. In another embodiment, the particular node includes the identity of the neighbor node in subsequently transmitted neighbor discovery message so that other nodes can know which nodes have established a symmetric link with the particular node.

Each transmitted neighbor discovery message includes a list of neighbor nodes that are identified as being in a heard state and a list of neighbor nodes that are identified as being in a lost state. Each transmitted neighbor discovery message can also include a list of neighbor nodes that are identified as being in a symmetric state.

In another aspect, the invention features a network that comprises a node. The node (i) receives from a neighbor node a neighbor discovery message, (ii) periodically transmits a predetermined number of neighbor discovery messages that each includes an identity of the neighbor node in response to the received neighbor discovery message, and (iii) after transmitting the predetermined number of neighbor discovery messages, transmits neighbor discovery messages that omit the identity of the neighbor node until another neighbor discovery message is received from the neighbor node that indicates a change in a communications state associated with the neighbor node.

BRIEF DESCRIPTION OF THE DRAWINGS

The invention is pointed out with particularity in the appended claims. The objectives advantages of the invention described above, as well as further objectives and advantages of the invention, may be better understood by reference to the following description taken in conjunction with the accompanying drawings, in which:

FIG. 1 is a block diagram of an embodiment of a mobile internetworking system including a plurality of subnets in communication with the Internet;

FIG. 2 is a block diagram of a portion of an embodiment of protocol stack that can be implemented by each of the routing nodes in each subnet to communicate in accordance with the principles of the invention;

FIG. 3 is a flow diagram illustrating an embodiment of a process by which each routing node selects a parent neighbor node and children neighbor node(s) for each potential source node in the subnet to define a minimum-hop-path tree for each potential source node along which routing nodes receive and forward link-state updates originating from that source node;

FIG. 4 is a diagram illustrating an embodiment of an exemplary minimum-hop-path tree for the nodes in the subnet of FIG. 1;

FIG. 5 is a block diagram illustrating the operation of a partial topology version of the TBRPF protocol;

FIG. 6 is a diagram of an embodiment of a format of a message header for an atomic TBRPF protocol message;

FIG. 7 is a diagram of an embodiment of a format of a compound TBRPF message;

FIGS. 8A and 8B are diagrams of embodiments of a format of a NEW PARENT protocol message;

FIG. 9 is a diagram of an embodiment of a format for a CANCEL PARENT message;

FIGS. 10A and 10B are diagrams of embodiments of exemplary formats for link-state update messages;

FIG. 11 is a diagram of an embodiment of an exemplary format of a RETRANSMISSION_OF_BROADCAST message;

FIG. 12 is a flow diagram of an embodiment of a process performed by the nodes of the subnet to achieve neighbor discovery;

FIG. 13 is a diagram of a packet format for the protocol messages used for neighbor discovery;

FIG. 14 are a flow diagram of another embodiment of a process for performing neighbor discovery;

FIG. 15A is a diagram of a format for an IPv6 address including a prefix and an interface identifier;

FIG. 15B is a diagram of an embodiment of the interface identifier including a 24-bit company identifier concatenated with a 40-bit extension identifier;

FIG. 15C is a diagram of an embodiment of the interface identifier including a 24-bit company identifier concatenated with the 40-bit extension identifier;

FIG. 15D is a diagram of an IPv6-IPv4 compatibility address;

FIG. 15E is a diagram of an embodiment of a message format for tunneling an IPv6-IPv4 compatibility address through IPv4 infrastructure;

FIG. 16 is a flow diagram of an embodiment of a process by which a router tests an IPv6-IPv4 compatibility address;

FIG. 17 is a flow diagram of an embodiment of a process by which a mobile node and a server exchange messages;

FIGS. 18A and 18B are diagrams illustrating an example of the operation of a message queue.

DESCRIPTION OF THE INVENTION

FIG. 1 shows an embodiment of an internetworking system 2 including communication sub-networks ("subnets") 10, 20 that are components of a worldwide network of networks 30 (i.e., the "Internet"). The Internet 30 includes communications entities, (e.g., hosts and routers), that exchange messages according to an Internet Protocol (IP) such as IPv4 (version 4) and IPv6 (version 6). On the Internet 30, entities implementing IPv6 may coexist with IPv4 entities. In general, the IPv4 and IPv6 versions are incompatible. The incompatibility is due, in part, to the difference in addressing format: the IPv4 specifies a 32-bit address format, whereas the IPv6 specifies a 128-bit address format.

A server 40 is connected to the Internet 30 by a wire-line or wireless connection. The server 40 can be internal or external to the subnet 10. For purposes such as hosting application programs, delivering information or Web pages, hosting databases, handling electronic mail ("e-mail"), or controlling access to other portions of the Internet 30, the server 40 is a computer system that typically handles multiple connections to other entities (e.g., client systems) simultaneously. Although represented as a single server 40, other embodiments can have a group of interconnected servers. The data on the server 40 are replicated on one or more of these interconnected servers to provide redundancy in the event that a connection to the server 40 cannot be established.

Each subnet 10, 20 includes one or more networks that can include both local area network (LAN) and wide area network (WAN) components. Each subnet 10, 20 may be a freely accessible component of the public Internet 30, or a private Intranet. The subnet 10 includes IP hosts 12, routers 14, and a gateway 16 (collectively referred to as nodes 18). As used hereafter, a router 14 is any node 18 that forwards IP packets not explicitly addressed to itself, and an IP host 12 is any node 18 that is not a router 14. Examples of devices that can participate as a node 18 in the subnet 10 include laptop computers, desktop computers, wireless telephones, and personal digital assistants (PDAs), network computers, television sets with a service such as Web TV, client computer systems, server computer systems. The gateway 16 is a particular type of routing node 14 that connects the subnet 10 to the Internet 30. The subnet 20 is similarly configured with nodes 18' (i.e., hosts 12', routers 14', and gateways 16').

The subnet 10 can be associated with one organization or administrative domain, such as an Internet service provider (ISP), which associates each node 18 with an assigned IPv6 or IPv4 network address. Each IPv6 address is globally unique, whereas each IPv4 address is locally unique at least within the subnet 10, and may be globally unique. Presumably, the assigned IP address has some topological relevance to the "home" subnet 10 of the node 18 so that the nodes 18 of the subnet 10 can be collectively identified by a common address prefix for routing purposes (called address aggregation). In one embodiment, the gateway 16 is a dual-stack node; that is, the gateway 16 has two IP addresses, an IPv6 address and an IPv4 address, and can route packets to IPv4 and IPv6 nodes.

Although it is conceivable that all nodes 18 in subnet 10 are initially assigned network addresses that follow a common address convention and have a common network prefix, dynamic topology changes may result in nodes 18 leaving their home subnet 10 to join a "foreign" subnet (e.g., subnet 20) and new nodes joining the home subnet 10. Because the nodes 18 maintain the same IP address irrespective of whether the node 18 changes its location within the subnet 10 or moves to the foreign subnet 20, mobility may result in a heterogeneous conglomerate of IPv6 and IPv4 addresses, having various network prefixes, within the single subnet 10 unless some form of dynamic address assignment or other address-renumbering scheme is used. Further, the gradual transition from the use of IPv4 network addresses to IPv6 network addresses within the subnet 10 increases the likelihood of such a heterogeneous conglomeration. Thus, like the Internet 30, the infrastructure of the subnet 10 can become heterogeneous; some nodes 18 can be IPv4 nodes, while others are IPv6 nodes.

In the subnet 10, each node 18 can establish connectivity with one or more other nodes 18 through broadcast or point-to-point links. In general, each link is a communication facility or medium over which nodes 18 can communicate at the link layer (i.e., the protocol layer immediately below the Internet Protocol layer.) Such communication links can be wire-line (e.g., telephone lines) or wireless; thus, nodes 18 are referred to as wireless or wire-line depending upon the type of communication link that the node 18 has to the subnet 10. Examples of wireless communication links are microwave links, radio frequency (RF) links, infrared (IR) links, and satellite links. Protocols for establishing link layer links include Ethernet, PPP (Point-to-Point Protocol) links, X.25, Frame Relay, or ATM (asynchronous transfer mode). Each wireless node 18, e.g., IP host A 12, has a range 22 of communication within which that node 18 can establish a connection to the subnet 10. When beyond the range 22 of communication, the IP host A 12 cannot communicate with the server 40 on the Internet 30 or with other nodes 18 in the subnet 10.

Each broadcast link connecting multiple nodes 18 is mapped into multiple point-to-point bi-directional links. For example, a pair of nodes 18 is considered to have established a bi-directional link, if each node 18 can reliably receive messages from the other. For example, IP host A 12 and node B 14 have established a bi-directional link 24 if and only if IP host A 12 can receive messages sent from node B 14 and node B 14 can receive messages sent from IP host A 12 at a given instant in time. Nodes 18 that have established a bi-directional link are considered to be adjacent (i.e., neighboring nodes). Such a bi-directional link 24 between the two nodes A and B is represented by a pair of unidirectional links (A, B) and (B, A). Each link has at least one positive cost (or metric) that can vary in time, and for any given cost, such cost for the link (A, B) may be different from that for the link (B, A). Any technique for assigning costs to links can be used to practice the invention. For example, the cost of a link can be one, for minimum-hop routing, or the link delay plus a constant bias.

In one embodiment, the subnet 10 is a mobile "ad hoc" network ("MANET") in that the topology of the subnet 10 and the state of the links (i.e., link state) between the nodes 18 in the subnet 10 can change frequently because several of the nodes 18 are mobile. That is, each mobile node 18 may move from one location to another location within the same subnet 10 or to another subnet 20, dynamically breaking existing links and establishing new links with other nodes 18, 18' as a result. Such movement by one node 18 does not necessarily result in breaking a link, but may diminish the quality of the communications with another node 18 over that link. In this case, a cost of that link has increased. Movement that breaks a link may interrupt any on-going communications with other nodes 18 in the subnet 10 or in the foreign subnet 20, or with servers (e.g., server 40) connected to the Internet 30. In another embodiment, the position of every node 18 in the subnet 10 is fixed (i.e., a static network configuration in which no link state changes occur due to node mobility). As the principles of the invention apply to both static and dynamic network configurations, a reference to the subnet 10 contemplates both types of network environments.

The following example illustrates the operation of the subnet 10. Consider, for example, that node A is communicating with the server 40 over a route through subnet 10 that includes the link (A, B) to node B 14, when node A 12 moves from its present location. This movement breaks the communication link with node B 14 and, as a result, interrupts communications with the server 40. The relocation of node A 12 may break a link with one or more other nodes 18 as well. As one example, the movement by node A 12 may temporarily take node A 12 out of communication range with node B 14, and upon returning within range, node A 12 can reestablish the broken link 24 with node B 14. In this example, the link 24 is intermittent. As another example, node A 12 may move to a different location within the subnet 10 altogether and reestablish a bi-directional link 26 with a different node, (e.g., here node H). In yet another example, node A 12 may move to the foreign subnet 20 and establish a bi-directional link 28 with a node 14' in the subnet 20 (e.g., node M 14').

Each router 14 in the subnet 10 is responsible for detecting, updating, and reporting changes in cost and up-or-down status of each outgoing communication link to neighbor nodes. Thus, each router 14 in the subnet 10 runs a link-state-routing protocol for disseminating subnet topology and link-state information to the other routers 14 in the subnet 10. Each router 14 also executes a neighbor discovery protocol for detecting the arrival of new neighbor nodes and the loss of existing neighbor nodes. To achieve discovery, IP hosts 12 connected to the subnet 10 also run the neighbor discovery protocol. IP hosts 12 can also operate as routers by running the link-state-routing protocol (in the description, such routing IP hosts are categorically referred to as routers 14). The link-state-routing protocol, referred to as a topology broadcast based on reverse-path forwarding (TBRPF) protocol, seeks to substantially minimize the amount of update and control traffic required to maintain shortest (or nearly shortest) paths to all destinations in the subnet 10.

In brief, the TBRPF protocol performed by each of the routers 14 in the subnet 10 operates to inform a subset of the neighboring routers 14 in the subnet 10 of the current network topology and corresponding link-state information. Thus, for the examples above, each router 14 in the subnet 10 that detects a change in a link to node A 12, (e.g., node B 14 in the cost of the link (B, A)), operates as the source (i.e., source node) of an update. Each source node sends a message to a neighbor of that source node, informing the neighbor of the update to that link. Each router 14 receiving the update may subsequently forward the update to zero or more neighbor nodes, until the change in the topology of the subnet 10 disseminates to the appropriate routers 14 in the subnet 10.

To transmit update messages, the TBRPF protocol supports unicast transmissions (e.g., point-to-point or receiver directed), in which a packet reaches only a single neighbor, and broadcast transmissions, in which a single packet is transmitted simultaneously to all neighbor nodes. In particular, the TBRPF protocol allows an update to be sent either on a common broadcast channel or on one or more unicast channels, depending on the number of neighbors that need to receive the update.

Upon recovering the same link to node B 14, or upon reestablishing a new link to another node 18 in the same subnet 10 or in the foreign subnet 20, the node A 12 can resume the interrupted communications with server 40. In effect, one of the nodes 18, 18' in the subnet 10, 20, respectively, using the neighbor discovery protocol, discovers node A 12 and, using the TBRPF protocol, initiates dissemination of topology and link-state information associated with the link to node A 12. The routers 14 also use the TBRPF protocol to disseminate this information to the other routers in the respective subnet 10 so that one or more routes to the node A 12 become available for communication with the server 40.

In one embodiment, such communications resume at their point of interruption. In brief, node A 12 maintains, in local cache, copies of objects that are located on the server 40. When node A 12 and the server 40 are in communication, node A 12 updates the objects as necessary, thereby maintaining substantially up-to-date copies of the objects. Thus, when node A 12 moves out of the communication range 22 with the subnet 10, the node A 12 initially has up-to-date information. Then when node A 12 reconnects to the subnet 10, the server 40 forwards previously undelivered updates to the objects locally stored at node A 12, along a route determined by information stored at each of the routing nodes 14. In the event node A 12 reconnects to the foreign subnet 20, a hand-off protocol, such as MobileIP, is used to achieve the redirection of the messages between the server 40 and the node A 12.

The route taken by the object updates may traverse a heterogeneous IPv6/IPv4 infrastructure. Normally, IPv6 nodes are unable to route packets to other IPv6 nodes 18 over routes that pass through IPv4 infrastructure. In one embodiment, described in more detail below, the nodes 18 use an IPv6-IPv4 compatible aggregatable global unicast address format to achieve such routing. This IPv6-IPv4 compatibility address format also enables incremental deployment of IPv6 nodes 18 that do not share a common multiple access data-link with another IPv6 node 18.

Accordingly, the internetworking system 2 provides various mobile ad hoc extensions to the Internet 30 that are particularly suited to the dynamic environment of mobile ad hoc networks. Such extensions, which are described further below, include techniques for (1) disseminating update information to nodes 18 in the subnet 10 using the TBRPF protocol; (2) detecting the appearance and disappearance of new neighbor nodes using a neighbor discovery protocol; (3) establishing an address format that facilitates deployment of IPv6 nodes in a predominantly IPv4 network infrastructure; (4) updating information upon resuming communications between nodes; and (5) adaptively using network bandwidth to establish and maintain connections between nodes 18 and the server 40.

FIG. 2 shows a portion of an embodiment of protocol stack 50 that can be used by each of the routing nodes 14, 14' to communicate with other routing nodes 14 in the subnet 10, 20 and on the Internet 30, and thereby implement the various extensions to the Internet 30 described herein. The protocol stack 50 includes a data-link layer 54, a network layer 62, and a transport layer 70.

The data link layer 54 can implemented by any conventional data link protocol (e.g., IEEE 802.11) with an addressing scheme that supports broadcast, multicast and unicast addressing with best-effort (not guaranteed) message delivery services between nodes 18 having instantaneous bi-directional links. For such implementations, each node 18 in the subnet 10 has a unique data link layer unicast address assignment.

The network layer 62 is the protocol layer responsible for assuring that packets arrive at their proper destination. Some of the mobile ad hoc extensions for the Internet 30 described herein operate at the network layer 62, such as the TBRPF protocol and the OPv6-IPv4 compatibility address format, described in more detail below. Embodiments that redirect communications from foreign subnets to home subnets also use hand-off mechanisms such as Mobile IP, which operate at the network layer 62. At the transport layer 70, other mobile ad hoc extensions to the Internet 30 are implemented, such as techniques for updating communications upon restoring connections between nodes and for adaptively using the network bandwidth.

1. Topology Broadcast based on Reverse-Path Forwarding (TBRPF) Protocol

In brief, the TBRPF protocol uses the concept of reverse-path forwarding to broadcast each link-state update in the reverse direction along a tree formed by the minimum-hop paths from all routing nodes 14 to the source of the update. That is, each link-state update is broadcast along the minimum-hop-path tree rooted at the source (i.e., source node "src") of the update. The minimum-hop-path trees (one tree per source) are updated dynamically using the topology and link-state information that are received along the minimum-hop-path trees themselves. In one embodiment, minimum-hop-path trees are used because they change less frequently than shortest-path trees that are determined based on a metric, such as delay. Other embodiments of the TBRPF protocol can use other types of trees, such as shortest path trees, to practice the principles of the invention.

Based on the information received along the minimum-hop-path trees, each node 18 in the subnet 10 computes a parent node and children nodes, if any, for the minimum-hop-path tree rooted at each source node src. Each routing node 14 may receive and forward updates originating from a source node src along the minimum-hop-path tree rooted at that source node src. Each routing node 14 in the subnet 10 also engages in neighbor discovery to detect new neighbor nodes and the loss of existing neighbor nodes. Consequently, the routing node 14 may become the source of an update and thus may generate an update message. When forwarding data packets to a destination node, each routing node 14 selects the next node on a route to the destination.

To communicate according to the TBRPF protocol, each routing node 14 (or node i, when referred to generally) in the subnet 10 stores the following information: 1. A topology table, denoted TT_i, consisting of all link-states stored at node i. The entry for link (u, v) in this table is denoted TT_i(u, v) and includes the most recent update (u, v, c, sn) received for link (u, v). The component c represents the cost associated with the link, and the component sn is a serial number for identifying the most recent update affecting link (u, v) received by the node i. The components c and sn of the entry for the link (u, v) is denoted TT_i(u, v).c and TT_i(u, v).sn. Optionally, the dissemination of multiple link metrics is attainable by replacing the single cost c with a vector of multiple metrics. 2 . A list of neighbor nodes, denoted N_i. 3. For each node u other than node i, the following is maintained: a. The parent, denoted p_i(u), which is the neighbor node ("nbr") of node i that is the next node on a minimum-hop path from node i to node u, as obtained from the topology table TT_i. b. A list of children nodes of node i, denoted children_i(u). c. The sequence number of the most recent link-state update originating from node u received by node i, denoted sn_i(u). The sequence number is included in the link-state update message. The use of sequence numbers helps achieve reliability despite topology changes, because node i avoids sending another node information that the other node already has. Each node i maintains a counter (i.e., the sequence number) for each link that the node i monitors. That counter is incremented each time the status of the link changes. d. The routing table entry for node u, consisting of the next node on a preferred path to node u. The routing table entry for node u can be equal to the parent p_i(u) if minimum-hop routing is used for data packets. However, in general, the routing table entry for node u is not p_i(u), because the selection of routes for data traffic can be based on any objective. One embodiment of the TBRPF protocol uses the following message types: LINK-STATE UPDATE: A message containing one or more link-state updates (u, v, c, sn). NEW PARENT: A message informing a neighbor node that the node has selected that neighbor node to be a parent with respect to one or more sources of updates. CANCEL PARENT: A message informing a neighbor that it is no longer a parent with respect to one or more sources of updates. HELLO: A message sent periodically by each node i for neighbor discovery. NEIGHBOR: A message sent in response to a HELLO message. NEIGHBOR ACK: A message sent in response to a NEIGHBOR message. ACK: A link-level acknowledgment to a unicast transmission. NACK: A link-level negative acknowledgment reporting that one or more update messages sent on the broadcast channel were not received. RETRANSMISSION OF BROADCAST: A retransmission, on a unicast channel, of link-state updates belonging to an update message for which a NACK message was received. HEARTBEAT: A message sent periodically on the broadcast channel when there are no updates to be sent on this channel, used to achieve reliable link-level broadcast of update messages based on NACKs. END OF BROADCAST: A message sent to a neighbor over a unicast channel, to report that updates originating from one or more sources are now being sent on the unicast channel instead of the broadcast channel. The formats for the various types of TBRPF protocol messages are described below. Building the Minimum-hop-Path Tree for a Source

FIG. 3 shows an embodiment of a process by which each routing node 14 selects a parent neighbor node and children neighbor node(s) for each potential source node src in the subnet 10. The selection of the parent and children neighbor nodes for each potential source node src define a minimum-hop-path tree for that potential source node along which the routing nodes 14 receive and forward link-state updates originating from that source node src. Pseudo-code describing the network-level procedures performed by each routing node 14 is in Appendix A.

Node i receives (step 90) a message over a communication link. The received message can represent a link-state update, the discovery of a new neighbor node, the loss of a neighbor node, a change in the cost of a link to a neighbor node, a selection of a new parent neighbor node, or a cancellation of a parent neighbor node. Pseudo-code for processing these types of received messages is provided in Appendix A; the corresponding procedures are called Process_Update, Link_Up, Link_Down, Link_Change, Process_New_Parent, and Process_Cancel_Parent, respectively. The general procedure followed in response to all of these events, and the specific procedure followed by a node that has just started and has no topology information are described below.

If node i receives a message representing a link-state update, the discovery of a new neighbor node, the loss of a neighbor node, or a change in the cost of a link to a neighbor node, node i enters (step 100) the new link-state information, if any into the topology table, TT_i, and forwards (step 102) the link-state information in a link-state update to the neighbor nodes in children_i(src), where src is the source node at which the update originated. Node i then computes (step 104) the parent nodes p_i(u) for all potential source nodes src by running a shortest-path algorithm such as Dijkstra's algorithm. If this computation results in a change to the parent node p_i(u) for any source u, node i then sends a NEW PARENT(u, sn) message, where sn=sn_i(u), to the new parent node p_i(u) and a CANCEL PARENT message to the old parent node (step 106).

If node i receives (step 90) a NEW PARENT(u, sn) message from a sending node with source u and sequence number sn, node i adds(step 108) the sending node to node i's list of children nodes children_i(u) for that source u, and then sends (step 110) the sending node a LINK-STATE UPDATE message containing all updates in node i's topology table, TT_i, originating from source u and having a sequence number greater than sn. If node i receives (step 90) a CANCEL PARENT(u) message from a sending node with source u, node i removes (step 112) the sending node from node i's list of children nodes children_i(u) for that source u.

Consider, for example, the case in which node i initially has no topology information. Accordingly, node i has no links to neighbor nodes, and its topology table TT_i is empty. Also the parent node is p_i(src)=NULL (i.e., not defined), the children_i(src) is the empty set, and sn_i(src)=0 for each source node src. Upon receiving (step 90) messages representing the discovery of neighbor nodes, node i executes the Link_Up procedure to process each link established with each neighbor node nbr. Because each neighbor node nbr of node i is (trivially) the next node on the minimum-hop path from node i to neighbor node nbr, node i selects (step 104) each of its neighbor nodes nbr as the new parent node p_i(nbr) for source node nbr. Execution of the Link-Up procedure results in node i sending (step 106) a NEW PARENT message to each neighbor node nbr. Therefore, the NEW PARENT message sent to a new neighbor node nbr contains the neighbor node nbr (and possibly other sources) in its source list.

In response to the NEW PARENT message, then each neighbor node nbr informs (step 110) node i of the outgoing links of neighbor node nbr. Information about the outgoing links of neighbor node nbr allows node i to compute minimum-hop paths to the nodes at the other end of the outgoing links, and thus to compute (step 104) new parents p_i(src), for all source nodes src that are two hops away. Node i sends (step 106) a NEW PARENT message to each of these computed new parents. Then each parent p_i(src) for each such source node src informs (step 110) node i of the outgoing links for source node src, which allows node i to compute (step 104) new parents for all source nodes that are three hops away. This process continues until node i has computed parent nodes for all sources nodes src in the subnet 10. As a result, for a given source node src, the parents p_i(src) for all nodes i other than source node src define a minimum-hop-path tree rooted at source node src (after the protocol has converged).

Node i cancels an existing parent p_i(src) by sending a CANCEL PARENT(src) message containing the identity of the source node src. Consequently, the set of children, children_i(src), at node i with respect to source node src is the set of neighbor nodes from which node i has received a NEW PARENT message containing the identity of source node src without receiving a subsequent CANCEL PARENT message for that source node src. Node i can also simultaneously select a neighbor node as the parent for multiple sources, so that the node i sends a NEW PARENT(src_list, sn_list) message to the new parent, where src_list is the list of source nodes and sn_list is the corresponding list of sequence numbers. Similarly, a CANCEL PARENT message can contain a list of sources.

In one embodiment, the TBRPF does not use NEW PARENT and CANCEL PARENT messages in the generation the minimum-hop-path tree. Instead, each node i computes the minimum-hop paths from each neighbor node nbr to all destinations (e.g., by using breadth-first search or Dijkstra's shortest-path algorithm). Consequently, each node i computes the parents p_nbr(src) for each neighbor node nbr and source node src, from which node i determines which neighbor nodes nbr are its children for the given source node src. Although this process eliminates NEW PARENT and CANCEL PARENT messages, the process also requires that each node i (1) sends all updates originating from the source node src to any child node in children_i(src), or (2) periodically sends updates along the minimum-hop-path tree, because node i does not know the sequence number sn_nbr(src) from the neighbor node nbr and thus does not know what updates the neighbor node nbr already has. Either of these actions ensures that each neighbor node nbr receives the most recent information for each link.

FIG. 4 shows an embodiment of an exemplary minimum-hop-path tree 120 for the nodes 18 in the subnet 10 of FIG. 1. For the sake of illustration, assume that node D is the source of an update. The parent 122 for nodes C, G, and H with respect to the source node D is node D; the parent 124 for node F with respect to source node D is node H; the parent 126 for nodes A and B with respect to source node D is node F; the parent 128 for node E is node B; and the parent 130 for node L is node A. (In this example, node A is a routing node 14, and thus runs the TBRPF protocol.)

Conversely, the children 132 of node D are nodes C, G, and H; the child 134 of node H is node F; the children 136 of node F are nodes A and B; the child 138 of node B is node E, and the child 140 of node A is node L. As shown, nodes C, E, G, and L are leaf nodes, which, in accordance with the TBRPF protocol, do not have to forward updates originating from the source node D.

Updating the Minimum-Hop-Path Tree

In brief, the TBRPF protocol disseminates link-state updates generated by a source node src along the minimum-hop-path tree rooted at node src and dynamically updates the minimum-hop-path tree based on the topology and link-state information received along the minimum-hop-path tree. More specifically, whenever the topology table TT_i of node i changes, the node i computes its parent p_i(src) with respect to every source node src (see the procedure Update_Parents in Appendix A). The node i computes parents by (1) computing minimum-hop paths to all other nodes using, for example, Dijkstra's algorithm, and (2) selecting the next node on the minimum-hop path to each source node src to be the parent for that source node src (see the procedure Compute_New_Parents in Appendix A). The computation of parents occurs when the node i receives a topology update, establishes a link to a new neighbor node, or detects a failure or change in cost of a link to an existing neighbor node.

In one embodiment, node i computes a new parent p_i(src) for a given source node src even though the path to the source node src through the new parent has the same number of hops as the path to the source node src through the old parent. In another embodiment, the node keeps the old parent node in this event, thus reducing the overhead of the TBRPF protocol. This embodiment can be implemented, for example, by using the procedure Compute_New_Parents2 (given in Appendix A) instead of the procedure Compute_New_Parents.

If the parent p_i(src) changes, node i sends the message CANCEL PARENT(src) to the current (i.e., old) parent, if the old parent exists. Upon receiving the CANCEL PARENT(src) message, the old parent ("k") removes node i from the list children_k(src).

Node i also sends the message NEW PARENT(src, sn) to the newly computed parent if the new parent exists, where sn=sn_i(src) is the sequence number of the most recent link-state update originating from source node src received by node i. This sequence number indicates the "position" up to which node i has received updates from the old parent, and indicates to the new parent that it should send only those updates that occurred subsequently (i.e., after that sequence number).

Upon receiving the NEW PARENT(src, sn) message, the new parent "j" for p_i(src) adds node i to the list children_i(src) and sends to node i a link-state update message consisting of all the link states originating from source node src in its topology table that have a sequence number greater than sn (see the procedure Process_New_Parent in Appendix A).