BUILDING ALTERNATE ROUTES IN REACTIVE ROUTING NETWORKS

• US 20130250808A1
• Filed: 06/15/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,030,939 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, an intermediate node in a computer network may receive one or more reactive routing route requests (RREQs) from an originating node and, based on those RREQs, may build a first directed acyclic graph (DAG) in the computer network that may be rooted at the originating node. The intermediate node may then forward the RREQs towards a target node in the computer network. The intermediate node may then receive one or more reactive routing route responses (RREPs) from the target node. Based on those RREPs, the intermediate node may then build a second DAG in the computer network that may be rooted at the target node. The intermediate node may then forward the RREPs towards the originating node. In this manner, the intermediate node may then forward traffic from the originating node toward the target node according to the second DAG (with alternate routes to the target node).

Claims

1. A method, comprising:

receiving, at an intermediate node in a computer network, one or more reactive routing route requests (RREQs) from an originating node;

building, based on the RREQs, a first directed acyclic graph (DAG) in the computer network rooted at the originating node;

forwarding the RREQs toward a target node;

receiving, at the intermediate node, one or more reactive routing route replies (RREPs) from the target node;

building, based on the RREPs, a second DAG in the computer network rooted at the target node; and

forwarding the RREPs toward the originating node.

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

forwarding traffic originated by the originating node toward the target node according to the second DAG, wherein the second DAG provides one or more alternate routes to the target node.

3. The method as in claim 1, wherein the RREPs are multicast from the target node to the originating node along one or more links in the first DAG.

4. The method as in claim 3, wherein the second DAG comprises a link-reversal of one or more links in the first DAG.

5. The method as in claim 4, wherein the one or more links comprise a subset of links in the first DAG.

6. The method as in claim 1, wherein the RREPs comprise a path search bound (PSB) indicator that directs the RREPs towards the originating node.

7. The method as in claim 6, further comprising:

accepting a particular RREP only in response to an associated path-cost being less than or equal to the PSB indicator of the particular RREP.

8. The method as in claim 7, wherein the associated path-cost is one of either a cost to reach the originator or an estimated transmission count (ETX) to reach the originator.

9. The method as in claim 6, wherein the second DAG comprises links that are not present in the first DAG.

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

adjusting the PSB by the intermediate node when forwarding the RREPs toward the originating node.

11. The method as in claim 6, wherein the PSB is a value set by the target node.

12. The method as in claim 6, wherein the PSB is a value set on at least one of a per-class-of-service basis and a per-destination basis.

13. An apparatus, comprising:

one or more network interfaces to communicate as a node in a communication 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;

receive one or more reactive routing route requests (RREQs) from an originating node;

build a first directed acyclic graph (DAG) in the computer network rooted at the originating node;

forward the RREQs towards a target node;

receive one or more reactive routing route replies (RREPs) from the target node;

build a second DAG in the computer network rooted at the target node; and

forward the RREPs toward the originating node.

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

forward traffic originated by the originating node toward the target node according to the second DAG, wherein the second DAG provides one or more alternate routes to the target node.

15. The apparatus as in claim 13, wherein the process is configured to build the second DAG by multi-casting the RREP from the target node to the originating node along one or more links in the first DAG.

16. The apparatus as in claim 13, wherein the second DAG comprises a link-reversal of one or more links in the first DAG.

17. The apparatus as in claim 13, wherein the RREPs comprise a path search bound (PSB) indicator that directs the RREPs towards the originating node.

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

accept a particular RREP only in response to an associated path-cost being less than or equal to the PSB indicator of the particular RREP.

19. The apparatus as in claim 17, wherein the second DAG comprises links that are not present in the first DAG.

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

adjust the PSB when forwarding the RREPs toward the originating node.

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

receive one or more reactive routing route requests (RREQs) from an originating node;

build a first directed acyclic graph (DAG) in the computer network rooted at the originating node;

forward the RREQs towards a target node;

receive one or more reactive routing route replies (RREPs) from the target node;

build a second DAG in the computer network rooted at the target node; and

forward the RREPs toward the originating node.

22. The computer-readable medium as in claim 21, wherein the software when executed is further operable to:

forward traffic originated by the originating node toward the target node according to the second DAG, wherein the second DAG provides one or more alternate routes to the target node.