Dynamic directed acyclic graph (DAG) root bypass for computer networks

• US 8,630,177 B2
• Filed: 02/27/2012
• Issued: 01/14/2014
• Est. Priority Date: 02/27/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Hui, Jonathan W., Mahamuni, Atul B.
• Primary Examiner(s): Vu, Huy D
• Assistant Examiner(s): CHIANG, KUO TUNG
• Application Number:
  US13/405,828
• Publication Number:
  US 20130223218A1
• Time in Patent Office: 687 Days
• Field of Search: 370/232, 370/229, 370/230, 370/231, 370/254, 370/255, 370/256
• US Class Current: 370/232
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

In one embodiment, traffic flows through a root node of a primary directed acyclic graph (DAG) in a computer network are monitored to detect whether a particular traffic flow is above a path cost threshold. If so, then a corresponding source device may be instructed to cease using the primary DAG for the particular traffic flow, and specific action may be taken based on whether the particular traffic flow is point-to-point (P2P) or point-to-multipoint (P2MP). In particular, in response to the particular traffic flow being P2P, a source route may be computed and sent to the source device to cause the source device to use the source route for the particular traffic flow, while in response to the particular traffic flow being P2MP, the source device may be instructed to create a secondary DAG for the particular traffic flow with the source device as the secondary DAG root.

Claims

1. A method, comprising:

monitoring traffic flows through a root node of a primary directed acyclic graph (DAG) in a computer network;

detecting that a particular traffic flow of the monitored traffic flows is above a path cost threshold;

determining whether the particular traffic flow from a corresponding source device is point-to-point (P2P) or point-to-multipoint (P2MP);

in response to the particular traffic flow being P2P, computing and sending a source route to the source device to cause the source device to use the source route for the particular traffic flow; and

in response to the particular traffic flow being P2MP, instructing the source device to create a secondary DAG for the particular traffic flow with the source device as the secondary DAG root.

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

in response to the particular traffic flow being P2MP to a number of destinations below a DAG creation threshold, computing and sending a plurality of source routes to the source device to cause the source device to use the plurality of source routes to reach the destinations for the particular traffic flow instead of creating the secondary DAG.

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

receiving redirected traffic of the particular traffic flow on the primary DAG at the root node from the source device to a destination device, the redirected traffic indicating a failure of the source route; and

in response, computing and sending a new source route to the source device to cause the source device to use the new source route for the particular traffic flow.

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

instructing the source device to use the source route or the secondary DAG for a period of time.

5. The method as in claim 1, wherein monitoring comprises:

monitoring traffic flows per traffic type, wherein the particular traffic flow is associated with a specific traffic type.

6. The method as in claim 1, wherein monitoring comprises:

monitoring only one or more specific types of traffic flows.

7. The method as in claim 1, wherein the path cost threshold is based on a service level agreement (SLA).

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

sending traffic flow information of the particular traffic flow to a management device for the computer network in response to the particular traffic flow being above a traffic rate threshold; and

receiving the path cost threshold for the particular traffic flow from the management device based on the SLA.

9. The method as in claim 1, wherein the path cost threshold is a maximum allowed path cost from a given source device to a given destination device.

10. The method as in claim 1, wherein the path cost threshold is a maximum allowed path cost stretch, wherein path cost stretch is computed as a difference between a first cost of a source-routed route from a given source device to a given destination device and a second cost of a DAG route on the primary DAG from the given source device to the given destination device.

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

determining that the path cost threshold cannot be met for the particular traffic flow with either the source route or the secondary DAG; and

in response, notifying a management device for the computer network that the path cost threshold cannot be met.

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

determining that the path cost threshold cannot be met for the particular traffic flow with either the source route or the secondary DAG; and

in response, moving one or more other traffic flows off of the primary DAG to meet the path cost threshold for the particular traffic flow.

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

detecting a level of congestion of the primary DAG near the root node that surpasses a congestion threshold; and

in response, computing and sending the source route or instructing the source device to create the secondary DAG, respectively.

14. A method, comprising:

sourcing one or more traffic flows through a root node of a primary directed acyclic graph (DAG) in a computer network;

receiving instructions to cease sourcing a particular traffic flow of the traffic flows in response to the particular traffic flow being above a path cost threshold;

in response to the particular traffic flow being point-to-point (P2P), receiving and using a source route for the particular traffic flow; and

in response to the particular traffic flow being point-to-multipoint (P2MP), receiving and acting on instructions to create a secondary DAG for the particular traffic flow with the source device as the secondary DAG root.

15. The method as in claim 14, further comprising:

in response to the particular traffic flow being P2MP to a number of destinations below a DAG creation threshold, receiving and using a plurality of source routes to reach the destinations for the particular traffic flow instead of creating the secondary DAG.

16. The method as in claim 14, further comprising:

detecting a failure of the source route for the particular traffic flow;

redirecting traffic for the particular traffic flow onto the primary DAG via the root node, the traffic indicating a failure of the source route; and

in response, receiving and using a new source route for the particular traffic flow.

17. The method as in claim 14, further comprising:

receiving instructions to use the source route or the secondary DAG for a period of time.

18. The method as in claim 14, wherein the particular traffic flow is associated with a specific traffic type.

19. The method as in claim 14, further comprising:

monitoring the particular traffic flow on the secondary DAG;

detecting that the particular traffic flow is below a traffic rate threshold for a configured length of time; and

in response, tearing down the secondary DAG and redirecting the particular traffic flow onto the primary DAG.

20. An apparatus, comprising:

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

monitor traffic flows through a root node of the primary directed acyclic graph (DAG) in the computer network;

detect that a particular traffic flow of the monitored traffic flows is above a path cost threshold;

determine whether the particular traffic flow from a corresponding source device is point-to-point (P2P) or point-to-multipoint (P2MP);

in response to the particular traffic flow being P2P, compute and send a source route to the source device to cause the source device to use the source route for the particular traffic flow; and

in response to the particular traffic flow being P2MP, instruct the source device to create a secondary DAG for the particular traffic flow with the source device as the secondary DAG root.

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

in response to the particular traffic flow being P2MP to a number of destinations below a DAG creation threshold, compute and send a plurality of source routes to the source device to cause the source device to use the plurality of source routes to reach the destinations for the particular traffic flow instead of creating the secondary DAG.

22. An apparatus, comprising:

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

source one or more traffic flows through a root node of a primary directed acyclic graph (DAG) in the computer network;

receive instructions to cease sourcing a particular traffic flow of the traffic flows in response to the particular traffic flow being above a path cost threshold;

in response to the particular traffic flow being point-to-point (P2P), receive and use a source route for the particular traffic flow; and

in response to the particular traffic flow being point-to-multipoint (P2MP), receive and act on instructions to create a secondary DAG for the particular traffic flow with the apparatus as the secondary DAG root.

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

in response to the particular traffic flow being P2MP to a number of destinations below a DAG creation threshold, receive and use a plurality of source routes to reach the destinations for the particular traffic flow instead of creating the secondary DAG.

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

detect a failure of the source route for the particular traffic flow;

redirect traffic for the particular traffic flow onto the primary DAG via the root node, the traffic indicating a failure of the source route; and

in response, receive and use a new source route for the particular traffic flow.

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

monitor the particular traffic flow on the secondary DAG;

detect that the particular traffic flow is below a traffic rate threshold for a configured length of time; and

in response, tear down the secondary DAG and redirect the particular traffic flow onto the primary DAG.