REGION-BASED ROUTE DISCOVERY IN REACTIVE ROUTING NETWORKS

• US 20130250809A1
• Filed: 06/29/2012
• Published: 09/26/2013
• 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
• Granted Patent: US 9,510,264 B2
• Time in Patent Office: Days
• US Class Current: 370/255
• 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 to target node.

Claims

1. A method, comprising:

receiving, at a region anchor node of a computer network, 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 a region of the computer network, the region comprising one or more nodes proximate to the region anchor node;

flooding the RREQ to the region;

receiving, at the region anchor node, one or more reactive routing route replies (RREPs) returned by the target node in the 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 a network node within the computer network is dynamically configured by;

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

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

dynamically configuring the network node as a region anchor node.

4. The method as in claim 3, 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 3, 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. A method, comprising:

determining a need to communicate with a target node in a particular network region;

identifying a region anchor node for the particular network region;

unicasting a route request (RREQ) to the region anchor node using a unicast route;

receiving, from the region anchor node, a route reply (RREP) having one or more region routes from the region anchor node to the target node; and

establishing one or more routes from the originator node to the target node by concatenating the unicast route to the region anchor node and the one or more region routes.

9. The method as in claim 8, further comprising:

selecting the region anchor node using historical topological information about the network.

10. The method as in claim 8, further comprising:

maintaining an originator directed acyclic graph (DAG) rooted at the originator node as the unicast route to the region anchor node.

11. An apparatus, comprising:

one or more network interfaces to communicate as a region anchor 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;

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 to the region;

receive one or more reactive routing route replies (RREPs) returned by the target node within the 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.

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

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

receives region anchor advertisement from an existing region anchor node;

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

dynamically configures the apparatus as a region anchor node.

14. The apparatus as in claim 11, 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.

15. The apparatus as in claim 11, 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.

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

17. The apparatus as in claim 11, 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.

18. An apparatus, comprising:

one or more network interfaces to communicate as an originator node in a computer network;

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;

determine a need to communicate with a target node in a particular network region;

to identify a region anchor node for the particular network region;

unicast a route request (RREQ) to the region anchor node using a unicast route;

receive, from the region anchor node, a route reply (RREP) having one or more region routes from the region anchor node to the target node; and

establish one or more routes from the originator node to the target node by concatenating the unicast route to the region anchor node and the one or more region routes.

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

select the region anchor node using historical topological information about the network.

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

maintain an originator directed acyclic graph (DAG) rooted at the originator node as the unicast route to the region anchor node.