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

• US 7,698,463 B2
• Filed: 12/01/2000
• Issued: 04/13/2010
• Est. Priority Date: 09/12/2000
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: SRI International, Inc.
• Inventors: Ogier, Richard G., Templin, Fred Lambert, Bellur, Bhargav R.
• Primary Examiner(s): Winder, Patrice
• Assistant Examiner(s): CHOUDHURY, AZIZUL Q
• Application Number:
  US09/728,020
• Publication Number:
  US 20020062388A1
• Time in Patent Office: 3,420 Days
• Field of Search: 709/223, 709/224
• US Class Current: 709/242
• 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. A method for disseminating topology and link state information in a multi-hop network, the method comprising:

maintaining, at a source node in the multi-hop network, a path tree rooted at the source node;

originating, at the source node, an update message containing topology or link state information, wherein said originating includes deciding what information to include in the update message, said information comprising one or more of;

at least one non-delete update for a link in the oath tree that has changed or is new or at least one delete update for a link that is not in the path tree but is in a reported set of links; and

sending the update message, by the source node, to one or more children of the source node that are indicated by the path tree rooted at the source node.

2. The method of claim 1, wherein the update message relates to one or more links in the network.

3. The method of claim 1, wherein the update message includes data indicating whether the update message should be forwarded by the one or more children of the source node.

4. The method of claim 1, wherein the path tree is a minimum hop path tree.

5. The method of claim 1, wherein the maintaining comprises:

receiving, by the source node, link state information for one or more nodes in the path tree.

6. The method of claim 1, wherein the source node is connected to the one or more children of the source node by one or more wireless communication links.

7. The method of claim 1, wherein the sending comprises broadcasting the update message to the one or more children of the source node, if a number of the one or more children of the source node exceeds a predefined threshold.

8. The method of claim 7, wherein the predefined threshold is one.

9. The method of claim 1, wherein the sending comprises transmitting the update message to the one or more children of the source node by a unicast mode, if a number of the one or more children of the source node is less than or equal to a predefined threshold.

10. The method of claim 9, wherein the predefined threshold is one.

11. A method for disseminating topology and link state information in a multi-hop network including a plurality of nodes, the method comprising:

receiving, at a first node in the multi-hop network, an update message containing topology or link state information, the update message being received from a parent of the first node that is indicated by a path tree rooted at a source from which the update message originated, wherein the source decides what information to include in the update message, said information comprising one or more of;

at least one non-delete update for a link in the path tree that has changed or is new or at least one delete update for a link that is not in the oath tree but is in a reported set of links;

updating, at the first node, a table of network topology stored at the first node in accordance with the update message; and

forwarding the update message, by the first node, to one or more children of the first node that are indicated by the path tree rooted at the source.

12. The method of claim 11, wherein the update message relates to one or more links in the network.

13. The method of claim 11, wherein the update message includes data indicating whether the update message should be forwarded by the first node.

14. The method of claim 11, wherein the path tree is a minimum hop path tree.

15. The method of claim 11, wherein the first node is connected to the parent of the first node by a wireless communication link.

16. The method of claim 11, further comprising:

sending, by the first node, a new parent message to a second node in the network, wherein the new parent message indicates that the second node has been selected as a parent for the first node.

17. The method of claim 16, further comprising:

receiving, by the first node, a new update message from the second node.

18. The method of claim 17, wherein the new update message includes a serial number, the serial number being greater than a serial number provided by the first node to second node in the new parent message.

19. The method of claim 11, wherein the forwarding comprises broadcasting the update message to the one or more children of the first node, if a number of the one or more children of the first node exceeds a predefined threshold.

20. The method of claim 11, wherein the forwarding comprises transmitting the update message to the one or more children of the first node by a unicast mode, if a number of the one or more children of the first node is less than a predefined threshold.