Push-based short-cut requests within a directed acyclic graph

• US 8,874,788 B2
• Filed: 11/05/2012
• Issued: 10/28/2014
• Est. Priority Date: 11/05/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.
• Primary Examiner(s): NANO, SARGON N
• Application Number:
  US13/668,744
• Publication Number:
  US 20140129734A1
• Time in Patent Office: 722 Days
• Field of Search: 709238-244, 370/229, 370/232, 370/255, 370/256
• US Class Current: 709/241
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

In one embodiment, a root of a directed acyclic graph (DAG) may determine transmission of critical traffic from a first device to a second device in a computer network using the DAG, and may also determine a maximum tolerable delay of the critical traffic. As such, the root may compute, based on a known topology of the computer network, a constrained shortest path first (CSPF) point-to-point (P2P) path from the first device to the second device to meet the maximum tolerable delay. The root may then inform the first device of the P2P path to the second device to cause the first device to use the P2P path for the critical traffic.

Claims

1. A method, comprising:

determining, at a root of a directed acyclic graph (DAG), transmission of critical traffic from a first device to a second device in a computer network using the DAG;

determining a maximum tolerable delay of the critical traffic;

computing, based on a known topology of the computer network, a constrained shortest path first (CSPF) point-to-point (P2P) path from the first device to the second device to meet the maximum tolerable delay; and

informing the first device of the P2P path to the second device to cause the first device to use the P2P path for the critical traffic.

2. The method as in claim 1, wherein determining the critical traffic comprises:

receiving registration regarding identification of critical traffic from the first device to the second device; and

identifying the critical traffic while transmitted using the DAG.

3. The method as in claim 1, wherein determining the critical traffic comprises:

detecting an explicit indication within the critical traffic while transmitted using the DAG.

4. The method as in claim 1, wherein the critical traffic is one of either actual data from the first device to the second device or an explicit signaling message indicating the intent to transmit critical traffic.

5. The method as in claim 1, wherein determining the maximum tolerable delay comprises:

detecting an explicit notification of the maximum tolerable delay from within the critical traffic.

6. The method as in claim 1, wherein determining the maximum tolerable delay comprises:

receiving configuration of the maximum tolerable delay for all critical traffic.

7. The method as in claim 1, wherein determining the maximum tolerable delay comprises:

detecting a type of the critical traffic, wherein the type of the critical traffic is associated with a corresponding maximum tolerable delay.

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

computing, based on a known topology of the computer network, a plurality of CSPF P2P paths from the first device to the second device to meet the maximum tolerable delay; and

informing the first device of the plurality of P2P paths to the second device to cause the first device to use the P2P paths for the critical traffic.

9. The method as in claim 1, wherein there is a plurality of second devices, the method further comprising:

computing, based on a known topology of the computer network, a CSPF point-to-multipoint (P2MP) path from the first device to the second devices to meet the maximum tolerable delay; and

informing the first device of the P2MP path to the second devices to cause the first device to use the P2MP path for the critical traffic.

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

determining an inability to compute a P2P path based on the known topology of the computer network to meet the maximum tolerable delay; and

, in response,

requesting an expanded topology view from at least a subset of devices within the computer network.

11. The method as in claim 10, wherein requesting comprises:

unicasting a request to each of the subset of devices.

12. The method as in claim 10, wherein requesting comprises:

including within a routing protocol control message a list of the subset of devices from which the expanded topology view is requested.

13. An apparatus, comprising:

one or more network interfaces to communicate as a root of a directed acyclic graph (DAG) within 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;

determining transmission of critical traffic from a first device to a second device in a computer network using the DAG;

determining a maximum tolerable delay of the critical traffic;

computing, based on a known topology of the computer network, a constrained shortest path first (CSPF) point-to-point (P2P) path from the first device to the second device to meet the maximum tolerable delay; and

informing the first device of the P2P path to the second device to cause the first device to use the P2P path for the critical traffic.

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

detect an explicit indication within the critical traffic while transmitted using the DAG.

15. The apparatus as in claim 13, wherein the process when executed to determine the maximum tolerable delay is further operable to:

detect an explicit notification of the maximum tolerable delay from within the critical traffic.

16. The apparatus as in claim 13, wherein the process when executed to determine the maximum tolerable delay is further operable to:

detect a type of the critical traffic, wherein the type of the critical traffic is associated with a corresponding maximum tolerable delay.

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

compute, based on a known topology of the computer network, a plurality of CSPF P2P paths from the first device to the second device to meet the maximum tolerable delay; and

inform the first device of the plurality of P2P paths to the second device to cause the first device to use the P2P paths for the critical traffic.

18. The apparatus as in claim 13, wherein there is a plurality of second devices, the process when executed is further operable to:

compute, based on a known topology of the computer network, a CSPF point-to-multipoint (P2MP) path from the first device to the second devices to meet the maximum tolerable delay; and

inform the first device of the P2MP path to the second devices to cause the first device to use the P2MP path for the critical traffic.

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

determine an inability to compute a P2P path based on the known topology of the computer network to meet the maximum tolerable delay; and

, in response,

request an expanded topology view from a subset of devices within the computer network.

20. The apparatus as in claim 19, wherein the process when executed to request is further operable to one of either unicast a request to each of the subset of devices or include within a routing protocol control message a list of the subset of devices from which the expanded topology view is requested.

21. A method, comprising:

determining, at a first device, transmission of critical traffic from the first device to a second device in a computer network, the critical traffic associated with a maximum tolerable delay;

sending a request to a root of a directed acyclic graph (DAG) to compute a constrained shortest path first (CSPF) point-to-point (P2P) path from the first device to the second device to meet the maximum tolerable delay;

receiving the P2P path to the second device; and

using the P2P path for the critical traffic.

22. An apparatus, comprising:

one or more network interfaces to communicate within a directed acyclic graph (DAG) within 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, as a first device, transmission of critical traffic from the first device to a second device in a computer network, the critical traffic associated with a maximum tolerable delay;

send a request to a root of a directed acyclic graph (DAG) to compute a constrained shortest path first (CSPF) point-to-point (P2P) path from the first device to the second device to meet the maximum tolerable delay;

receive the P2P path to the second device; and

use the P2P path for the critical traffic.