Region-based route discovery in reactive routing networks

• US 9,510,264 B2
• Filed: 06/29/2012
• Issued: 11/29/2016
• Est. Priority Date: 03/23/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Hui, Jonathan W., Vasseur, Jean-Philippe
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): AGA, SORI A
• Application Number:
  US13/538,238
• Publication Number:
  US 20130250809A1
• Time in Patent Office: 1,614 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 45/32 Flooding denial of service attacks H04L63/1458
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04W 40/023 Limited or focused flooding to selected areas of a network
• CPC Class Codes: H04W 40/20 based on geographic position or location
• CPC Class Codes: H04W 40/28 for reactive routing

Abstract

In one embodiment, a region anchor node may receive a unicasted route request (RREQ) for a target node. The region anchor node may then flood the RREQ to a region within which it resides. Subsequently, the region anchor node may receive one or more reactive routing route replies (RREPs) returned by the target node within the region. Based on the RREPs, the region anchor node may build one or more region routes from the region anchor node to the target node, and returns the one or more region routes to the originator node to cause the originator node to concatenate the one or more region routes and the unicast route of the original RREQ to form a path from the originator node to the target node.

Claims

1. A method, comprising:

dynamically configuring a network node between a root node and a destination node in a computer network as a region anchor node;

receiving, at the region anchor node, a route request (RREQ) for a target node in a particular network region, the RREQ having been unicast by an originator node of the computer network to the region anchor node via a unicast route, the region anchor node configured to communicate with the originator node and the particular network region of the computer network, the particular network region comprising one or more nodes proximate to the region anchor node;

flooding the RREQ from the region anchor node on an as needed basis, the RREQ limited to the particular network region;

receiving, at the region anchor node, one or more reactive routing route replies (RREPs) returned by the target node in the particular network region;

building, based on the RREPs, one or more region routes from the region anchor node to the target node; and

returning the one or more region routes to the originator node to cause the originator node to concatenate the one or more region routes and the unicast route to form a path from the originator node to the target node.

2. The method as in claim 1, wherein the region anchor node is selected by the originator node using historical topological information about the network.

3. The method as in claim 1, further comprising:

wherein the network node within the computer network is dynamically configured as the region anchor node by;

receiving, at the network node, a region anchor advertisement from an existing region anchor node; and

determining, based on the region anchor advertisement, that the network node should be a region anchor node.

4. The method as in claim 1, wherein the network node is dynamically configured as a region anchor node when it has not received a region anchor advertisement for a period of time.

5. The method as in claim 1, wherein a dynamically configured region anchor node is converted back to a network node if the dynamically configured region anchor node determines that the number of proximate region anchor nodes in the network exceeds a threshold value.

6. The method as in claim 1, wherein the unicast route is created and maintained by the originator node.

7. The method as in claim 1, wherein the unicast route from the originator node to the region anchor node is based on an originator directed acyclic graph (DAG) rooted at the originator node, wherein the region anchor node is located within the originator DAG.

8. An apparatus, comprising:

one or more network interfaces to communicate as a region anchor node between a root node and a destination node in a computer network, the network interfaces configured to communicate with the originator node and a region of the computer network, the region comprising one or more nodes proximate to the region anchor node;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

dynamically configure the apparatus as a region anchor node;

receive a route request (RREQ) for a target node in a particular network region, the RREQ having been unicast by an originator node to the region anchor node via a unicast route;

flood the RREQ from the apparatus on an as needed basis, the RREQ limited to the particular network region;

receive one or more reactive routing route replies (RREPs) returned by the target node within the particular network region;

build, based on the RREPs, one or more region routes from the region anchor node to the target node; and

return the one or more region routes to the originator node to cause the originator node to concatenate the one or more region routes and the unicast route to form a path from the originator node to the target node.

9. The apparatus as in claim 8, wherein the region anchor node is selected by the originator node using historical topological information about the network.

10. The apparatus as in claim 8, wherein a network node within the computer network is dynamically configured to be the region anchor node by a process that:

receives region anchor advertisement from an existing region anchor node; and

determines, based on the region anchor advertisement, that the apparatus should be a region anchor node.

11. The apparatus as in claim 8, wherein the apparatus is dynamically configured as a region anchor node when it has not received a region anchor advertisement for a period of time.

12. The apparatus as in claim 8, wherein the process when executed is further operable to:

convert from a region anchor node to a network node in response to determining that the number of proximate region anchor nodes in the network exceeds a threshold value.

13. The apparatus as in claim 8, wherein the unicast route is created and maintained by the originator node.

14. The apparatus as in claim 8, wherein the unicast route from the originator node to the region anchor node is based on an originator directed acyclic graph (DAG) rooted at the originator node, wherein the region anchor node is located within the originator DAG.

15. A tangible, non-transitory, computer-readable media having a process encoded thereon, the process when executed by a processor operable to:

dynamically configure a network node between a root node and a destination node in a computer network as a region anchor node;

receive a route request (RREQ) for a target node in a particular network region, the RREQ having been unicast by an originator node to the region anchor node via a unicast route;

flood the RREQ from the region anchor node on an as needed basis, the RREQ limited to the particular network region;

receive one or more reactive routing route replies (RREPs) returned by the target node within the particular network region;

build, based on the RREPs, one or more region routes from the region anchor node to the target node; and

return the one or more region routes to the originator node to cause the originator node to concatenate the one or more region routes and the unicast route to form a path from the originator node to the target node.

16. The tangible, non-transitory, computer-readable media as in claim 15, wherein a network node within the computer network is dynamically configured to be the region anchor node by a process that:

receives region anchor advertisement from an existing region anchor node; and

determines, based on the region anchor advertisement, that the apparatus should be a region anchor node.

17. The tangible, non-transitory, computer-readable media as in claim 15, wherein the process when executed is further operable to:

convert from a region anchor node to a network node in response to determining that the number of proximate region anchor nodes in the network exceeds a threshold value.