Adaptive topology discovery in communication networks

• US 7,366,113 B1
• Filed: 06/02/2003
• Issued: 04/29/2008
• Est. Priority Date: 12/27/2002
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Fetzer, Christof, Chandra, Ranveer, Hogstedt, Karin
• Primary Examiner(s): Rao; Seema S.
• Assistant Examiner(s): DUONG, CHRISTINE T
• Application Number:
  US10/452,708
• Time in Patent Office: 1,793 Days
• Field of Search: 370254-258, 370/338, 370/400, 455 411- 413, 455/446
• US Class Current: 370/255
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/32 Flooding denial of service attacks H04L63/1458
• CPC Class Codes: H04W 40/246 Connectivity information discovery

Abstract

A topology discovery process is used to discover all of the links in an ad hoc network and thereby ascertain the topology of the entire network. One of the nodes of the network, referred to as the coordinator, receives the topology information which can then be used to, for example, distribute a routing table to each other node of the network. The process has a Diffusion phase in which a k-resilient mesh, k>1, is created by propagating a topology request message through the network. Through this process, the nodes obtain information from which they are able to discern their local neighbor information. In a subsequent, Gathering phase, the local neighbor information is reported upstream from a node to its parents in the mesh and thence to the parents'"'"' parents and so forth back to the coordinator. The robustness of the Diffusion phase is enhanced by allowing a node to have more than one parent as well as by a number of techniques, including use of a so-called diffusion acknowledgement message. The robustness of the Gathering phase is enhanced by a number of techniques including the use of timeouts that ensure that a node will report its neighbor information upstream even if it never receives neighbor information from one or more downstream neighbors and the use of a panic mode that enhances the probability that a node will get its neighbor information, and its descendents'"'"' neighbor information, reported upstream even if that node has lost connectivity with all of its parents.

Claims

1. A method carried out by a plurality of nodes of a communication network at least a portion of which is an ad hoc network in which at least some messages are communicated between originating nodes and destination nodes without being routed via any intermediate nodes, the method comprising carrying out an exhaustive topology discovery of at least a portion of said ad hoc network,

wherein said exhaustive topology discovery comprises discovering all of the nodes of at least said portion of said ad hoc network, and all of the links between each pair of such nodes,

wherein information identifying all of the discovered nodes and all of the discovered links is collected by an individual one of the nodes of the communication network,

wherein two or more of said discovered links are wireless links,

wherein said discovering comprises a diffusion phase and a subsequent gathering phase,

wherein said diffusion phase comprises

a) a first one of the nodes of said communication network broadcasting a topology discovery request,

b) each of second nodes that receive said topology discovery request recording said first node as its parent and broadcasting said topology discovery request modified to identify said first node as its parent,

c) each of third nodes that did not receive the topology discovery request broadcasted by the first node but did receive a modified version thereof broadcasted by one of said second nodes,

i) recording that one of said second nodes as its parent and

ii) broadcasting said topology discovery request modified to identify said one of said second nodes as its parent,

and wherein said diffusion phase further comprises each node that had broadcasted a modified version of said topology discovery request rebroadcasting said modified version if that node has not received an acknowledgment message within a predetermined time after having broadcast said modified version.

2. The method of claim 1 further comprising

each node that had broadcasted a modified version of said topology discovery request transmitting an acknowledgment message in response to receipt of a version of the topology discovery request that it had transmitted.

3. A method carried out by a plurality of nodes of a communication network at least a portion of which is an ad hoc network in which at least some messages are communicated between originating nodes and destination nodes without being routed via any intermediate nodes, the method comprising carrying out an exhaustive topology discovery of at least a portion of said ad hoc network,

wherein said exhaustive topology discovery comprises discovering all of the nodes of at least said portion of said ad hoc network, and all of the links between each pair of such nodes,

wherein information identifying all of the discovered nodes and all of the discovered links is collected by an individual one of the nodes of the communication network,

wherein two or more of said discovered links are wireless links,

wherein said discovering comprises a diffusion phase and a subsequent gathering phase,

wherein said diffusion phase comprises

a) first ones of said nodes of said communication network broadcasting respective topology discovery requests,

b) at least a second node that receives said topology discovery requests recording each of said first nodes as its parents and broadcasting the topology discovery request received from each said first node modified to identify that node as its parent,

c) each of third nodes that did not receive the topology discovery requests broadcasted by the first nodes but did receive a modified version thereof broadcasted by said second node,

i) recording said second node as its parent and

ii) broadcasting said topology discovery request modified to identify said second node as its parent,

wherein said diffusion phase further comprises each of the nodes of the communication network that receive a version of said topology discovery request identifying itself as the parent of the sending node recording that sending node as its child,

and wherein said gathering phase comprises

a) each of said third nodes that did not receive the topology discovery request transmitting to each of its parents a gathering response that at least includes that third node'"'"'s neighbor information, and

b) said second node transmitting to at least one of said first ones of said nodes a gathering response that includes that second node'"'"'s neighbor information and further includes all of its children'"'"'s neighbor information received by said second node in a gathering response from those children,

c) the neighbor information of a node including an identification of that node'"'"'s parents and children, if any, and further includes identification of other nodes with which that node is linked.

4. The method of claim 3 wherein said each of said third nodes and said second node transmit said gathering response to an individual one of its parents no later than the expiration of a timeout period associated with that individual parent.

5. The method of claim 4 wherein said timeout period is measured from the point in time at which the node transmitting the gathering response had received said topology discovery request from said individual one of its parents and wherein the duration of said timeout period is a function of a hop count included in that request message.

6. The method of claim 3 wherein any of said third nodes and said second node that is unable to successfully transmit a gathering response to any of its parents transmits a gathering response to at least one other of its neighbor nodes.

7. A method carried out by a plurality of nodes of a communication network at least a portion of which is an ad hoc network in which at least some messages are communicated between originating nodes and destination nodes without being routed via any intermediate nodes, the method comprising carrying out an exhaustive topology discovery of at least a portion of said ad hoc network,

wherein said exhaustive topology discovery comprises discovering all of the nodes of at least said portion of said ad hoc network, and all of the links between each pair of such nodes,

wherein information identifying all of the discovered nodes and all of the discovered links is collected by an individual one of the nodes of the communication network,

wherein two or more of said discovered links are wireless links,

wherein said discovering comprises a diffusion phase and a subsequent gathering phase,

wherein said diffusion phase comprises

a) a first one of the nodes of said communication network broadcasting a topology discovery request,

b) each of second nodes that receive said topology discovery request recording said first node as its parent and broadcasting said topology discovery request modified to identify said first node as its parent,

c) each of third nodes that did not receive the topology discovery request broadcasted by the first node but did receive a modified version thereof broadcasted by one of said second nodes,

i) recording that one of said second nodes as its parent and

ii) broadcasting said topology discovery request modified to identify said one of said second nodes as its parent,

wherein said diffusion phase further comprises each of the nodes of the communication network that receive a version of said topology discovery request identifying itself as the parent of the sending node recording that sending node as its child,

and wherein said gathering phase comprises

a) at least individual ones of the nodes of the communication network transmitting to each of their parents a gathering response that identifies those individual nodes'"'"' neighbor information and further identifies any other nodes'"'"' neighbor information that those individual nodes receive in gathering responses from their children,

b) the neighbor information of a node including an identification of that node'"'"'s parents and of its children, if any, and further includes identification of other nodes with which that node is linked.

8. The method of claim 7 wherein the gathering response is transmitted to said each parent no later than the expiration of a timeout period associated with that parent.

9. The method of claim 8 wherein said timeout period is measured from the point in time at which each of said individual ones of the nodes of the communication network had received said topology discovery request from the parent to which the gathering response is to be transmitted, and wherein the duration of said timeout period is a function of a hop count included in that request message.

10. The method of claim 7 wherein any of said individual nodes that is unable to successfully transmit a gathering response to any of its parents transmits a gathering response to at least one other of its neighbor nodes.

11. A method carried out by a plurality of nodes of a communication network at least a portion of which is an ad hoc network in which at least some messages are communicated between originating nodes and destination nodes without being routed via any intermediate nodes, the method comprising carrying out an exhaustive topology discovery of at least a portion of said ad hoc network,

wherein said exhaustive topology discovery comprises discovering all of the nodes of at least said portion of said ad hoc network and all of the links between each pair of such nodes,

wherein information identifying all of the discovered nodes and all of the discovered links is collected by an individual one of the nodes of the communication network,

wherein two or more of said discovered links are wireless links,

wherein said discovering comprises a diffusion phase and a subsequent gathering phase,

wherein said diffusion phase comprises

a) a first one of the nodes of said communication network broadcasting a topology discovery request,

b) each of second nodes that receive said topology discovery request recording said first node as its parent and broadcasting said topology discovery request modified to identify said first node as its parent,

c) each of third nodes that did not receive the topology discovery request broadcasted by the first node but did receive a modified version thereof broadcasted by one of said second nodes,

i) recording that one of said second nodes as its parent and

ii) broadcasting said topology discovery request modified to identify said one of said second nodes as its parent,

and wherein each of the nodes of the communication network that receives a modified version of a topology discovery request that that node had itself sent broadcasts an acknowledgment message upon receipt of said modified version from another node and wherein each of the nodes of the communication network that broadcasts a topology discovery request retransmits it if does not receive an acknowledgment message in response.

12. A method for use by a first node of a communication network comprising a plurality of nodes, said first node being a wireless node and at least a portion of said communication network being an ad hoc network in which at least some originating and destination nodes communicate messages between one another that are not routed via any intermediate nodes, the method comprising

receiving a request message from at least two other nodes in said network,

recording each said other node as concurrently being parents of said first node,

broadcasting a modified version of each received request message, said modified version identifying a respective one of said other nodes as a parent of said first node and identifying said first node as the node sending said modified version,

receiving a version of each said request message in which said first node is identified as the parent of the node sending that version of that request message,

recording the sending node as a child of said first node,

receiving individual response messages from respective children of said first node, each response message including neighbor information of the respective child, and

transmitting to each said other node a response message that includes the neighbor information of all of said children and the neighbor information of said first node,

the neighbor information of a node including an identification of that node'"'"'s parents and of its children, if any, and further includes identification of other nodes with which that node is linked.

13. The method of claim 12 wherein if neither of said other nodes receives said response message, said first node transmits at least a portion of said response message to at least one other node with which said first node is linked.

14. The method of claim 12 wherein said first node transmits said response message to each said other node no later than the expiration of a timeout period associated with that other node.

15. The method of claim 14 wherein the timeout period associated with each said other node is measured from the point in time at which said first node received said request message from that other node and wherein the duration of said timeout period is a function of a hop count included in the request message received from that other node.

16. A wireless node for operating within a communication network, at least a portion of said communication network being an ad hoc network in which at least some originating and destination nodes communicate messages between one another that are not routed via any intermediate nodes, the wireless node including a processor and said wireless node having stored therein instructions that, when executed by the processor, cause the wireless node to respond to receipt of a request message from at least two other nodes in said network by

recording each said other node as concurrently being parents of said wireless node, and

broadcasting a modified version of each received request message, said modified version identifying a respective one of said other nodes as a parent of said wireless node and identifying said wireless node as the node sending said modified version

wherein said instructions further cause said wireless node to respond to receipt of a version of each said request message in which said wireless node is identified as the parent of the node sending that version of that request message by recording the sending node as a child of said wireless node,

and wherein said instructions further cause said wireless node to respond to receipt of individual response messages from respective children of said wireless node, each response message including neighbor information of the respective child, by

transmitting to each said other node a response message that includes the neighbor information of all of said children and the neighbor information of said wireless node,

the neighbor information of a node including an identification of that node'"'"'s parents and of its children, if any, and further includes identification of other nodes with which that node is linked.

17. The wireless node of claim 16 wherein if neither of said other nodes receives said response message, said instructions further cause said processor to transmit at least a portion of said response message to at least one other node with which said wireless node is linked.

18. The wireless node of claim 16 wherein said instructions cause said wireless node to transmit said response message to each said other node no later than the expiration of a timeout period associated with that other node.

19. The wireless node of claim 18 wherein the timeout period associated with each said other node is measured from the point in time at which said wireless node received said request message from that other node and wherein the duration of said timeout period is a function of a hop count included in the request message received from that other node.

20. A computer-readable medium containing computer-readable instructions to perform a method within a wireless node operating within an ad hoc network in which at least some originating and destination nodes communicate messages between one another that are not routed via any intermediate nodes, the method comprising

receiving a request message from at least two other nodes in said network,

recording each said other node as concurrently being parents of said wireless node, and

broadcasting a modified version of each received request message, said modified version identifying a respective one of said other nodes as the parent of said wireless node and identifying said wireless node as the node sending said modified version,

wherein said method further comprises responding to receipt of a version of each said request message in which said wireless node is identified as the parent of the node sending that version of that request message by recording the sending node as a child of said wireless node,

and wherein said method further comprises causing said wireless node to respond to receipt of individual response messages from respective children of said wireless node, each response message including neighbor information of the respective child, by

transmitting to each said other node a response message that includes the neighbor information of all of said children and the neighbor information of said wireless node,

the neighbor information of a node including an identification of that node'"'"'s parents and of its children, if any, and further includes identification of other nodes with which that node is linked.

21. The computer-readable medium of claim 20 wherein said method further comprises

transmitting at least a portion of said response message to at least one other node with which said wireless node is linked if neither of said other nodes receives said response message.

22. The computer-readable medium of claim 20 wherein said wireless node transmits said response message to each said other node no later than the expiration of a timeout period associated with that other node.

23. The computer-readable medium of claim 22 wherein the timeout period associated with each said other node is measured from the point in time at which said wireless node received said request message from that other node and wherein the duration of said timeout period is a function of a hop count included in the request message received from that other node.