System and method for disseminating topology and link-state information to routing nodes in a mobile ad hoc network

• US 20020062388A1
• Filed: 12/01/2000
• Published: 05/23/2002
• Est. Priority Date: 09/12/2000
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: SRI International, Inc.
• Inventors: Ogier, Richard G., Bellur, Bhargav R., Templin, Fred Lambert
• Granted Patent: US 7,698,463 B2
• Time in Patent Office: Days
• US Class Current: 709/238
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/167 Adaptation for transition between two IP versions, e.g. between IPv4 and IPv6 translation of Internet protocol [IP] addresses H04L61/2503
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 40/30 for proactive routing
• CPC Class Codes: H04W 40/38 adapting due to varying relative distances between nodes
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• CPC Class Codes: H04W 48/10 using broadcasted information
• CPC Class Codes: H04W 80/00 Wireless network protocols or protocol adaptations to wireless operation
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Described is a link-state routing protocol used in a mobile ad hoc network or in an Internet for disseminating topology and link-state information throughout the network. Reverse-path forwarding is used to broadcast each update along the minimum-hop-path tree rooted at the source of the update. Each path tree has the source node as a root node, a parent node, and zero or more children nodes. Updates are received from the parent node in the path tree for the source node that originates the update. Each update includes information related to a link in the network. A determination is made whether to forward the update message to children nodes, if any, in the path tree maintained for the source node originating the update in response to information in the received update. This information itself can indicate whether the update is to be forwarded to other nodes.

Claims

1. In a multi-hop network including a plurality of nodes, a method for disseminating topology and link-state information over the multi-hop network, comprising:

maintaining a path tree for each source node in the network that can produce an update message, each path tree having that source node as a root node, a parent node, and zero or more children nodes;

receiving an update message from the parent node in the path tree maintained for the source node that originated the received update message, the update message including information related to a link in the network; and

determining whether to forward the update message to children nodes, if any, in the path tree maintained for the source node that originated the update message in response to the information in the received update message.

2. The method of claim 1 wherein the information related to the link indicates whether the update message is to be forwarded to other nodes.

3. The method of claim 1 wherein the path tree associated with each source node is a minimum-hop-path tree.

4. The method of claim 1 further comprising obtaining link-state information from one or more nodes in the path tree maintained for a given source node for use in developing the path tree to that source node.

5. The method of claim 1 wherein the link is a wireless communication link.

6. The method of claim 1 further comprising sending a new parent message to a node selecting that node as a new parent node for the source node originating the update message.

7. The method of claim 6 further comprising receiving from the new parent node in response to the new parent message link-state information associated with the source node that originated the update message.

8. The method of claim 7 wherein the new parent message included a serial number and the link-state information received in response to the new parent message is associated with update messages having serial numbers that are greater than the serial number included in the new parent message.

9. The method of claim 1 further comprising:

determining that a path through a new parent node for the source node originating the update message has the same number of node hops as the path through the current parent node, and

maintaining the current parent node as the parent node for the given source node.

10. The method of claim 1 further comprising:

determining that a path to the source node originating the update message ceases to exist; and

maintaining the current parent node as the parent node for the source node.

11. The method of claim 1 further comprising broadcasting the update message to the children nodes if the number of children nodes exceeds a predefined threshold when forwarding the update message to children nodes.

12. The method of claim 1 further comprising transmitting the update message to each child node using a unicast mode if the number of children nodes is less than a predefined threshold when forwarding the update message to children nodes.

13. The method of claim 1 further comprising:

computing a parent node for each neighbor node and source node; and

determining which neighbor nodes are children nodes for a given source node;

14. A network, comprising:

a plurality of nodes in communication with each other over communication links, each node maintaining a path tree for each source node in the network that can produce an update message, each path tree having that source node as a root node, a parent node, and zero or more children nodes,

wherein one of the nodes (i) receives an update message from the parent node in the path tree maintained for the source node that originated the received update message, the update message including information related to a link in the network, (ii) and determines whether to forward the update message to children nodes, if any, in the path tree maintained for the source node that originated the update message in response to the information in the received update message.