Delay budget based forwarding in communication networks

• US 9,124,482 B2
• Filed: 07/19/2011
• Issued: 09/01/2015
• Est. Priority Date: 07/19/2011
• 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): Chriss, Andrew
• Assistant Examiner(s): Rivas, Salvador E
• Application Number:
  US13/185,805
• Publication Number:
  US 20130022042A1
• Time in Patent Office: 1,505 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/08 Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/30 Routing of multiclass traffic
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/56 implementing delay-aware scheduling
• CPC Class Codes: H04W 72/12 Wireless traffic scheduling
• CPC Class Codes: H04W 72/51 based on terminal or device properties

Abstract

In one embodiment, certain nodes in a computer network maintain a plurality of routing topologies, each associated with a different corresponding delay (e.g., dynamically adjusted). Upon receiving a packet with an indicated delay budget at a particular node, the node updates the delay budget based on an incurred delay up to and including the particular node since the indicated delay budget was last updated, and selects a particular routing topology on which to forward the packet based on the updated delay budget and the corresponding routing topology delays. The packet may then be forwarded with the updated delay budget on the selected routing topology, accordingly.

Claims

1. A method, comprising:

maintaining a plurality of routing topologies within a computer network, each of the routing topologies associated with a different corresponding delay;

receiving a packet with an indicated delay budget at a particular node;

updating the delay budget by subtracting an incurred delay up to and including the particular node since the indicated delay budget was last updated, wherein the incurred delay includes a queuing delay at the particular node between receiving the packet and forwarding the packet away from the particular node;

selecting a particular routing topology of the plurality of routing topologies on which to forward the packet based on the updated delay budget and the corresponding routing topology delays; and

forwarding the packet with the updated delay budget on the particular routing topology.

2. The method as in claim 1, wherein the corresponding delay associated with the routing topologies are particular to one or more specific destinations within the computer network, and wherein selecting the particular routing topology comprises:

determining that there is no known delay for a particular destination of the packet; and

in response, forwarding the packet on a default routing topology.

3. The method as in claim 1, further comprising, in response to determining a condition that there is no routing topology to satisfy the updated delay budget:

selecting a particular routing topology of the plurality of routing topologies with a shortest delay; and

recording the condition.

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

dynamically adjusting resource allocation for one or more of the routing topologies based on at least of either a proportion of satisfied delay budgets and a proportion of unsatisfied delay budgets.

5. The method as in claim 4, wherein resource allocation is selected from a group consisting of:

a number of communication slots in a frequency hopping sequence;

a number of queuing buffers, and one or more routing topology determination constraints.

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

detecting that a proportion of delay budgets not satisfied is above a threshold; and

in response, allocating additional resources for one or more of the routing topologies to reduce the corresponding associated delays.

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

detecting that a proportion of delay budgets satisfied is above a threshold; and

in response, releasing resources from one or more of the routing topologies to relax the corresponding associated delays.

8. The method as in claim 1, wherein updating the delay budget comprises subtracting at least one of either a transmission delay to reach the particular node since the indicated delay budget was last updated and a queuing delay associated with the particular node between receiving the packet and forwarding the packet.

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

computing the plurality of routing topologies with different delays based on corresponding characteristic trade-offs.

10. The method as in claim 1, wherein the routing topologies are selected from a group consisting of:

directed acyclic graph (DAG) instances; and

multi-topology routing (MTR) instances.

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

generating a second packet by the particular device;

inserting an associated delay budget into the second packet; and

forwarding the second packet.

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

determining the associated delay budget from an application initiating the packet at the particular node.

13. The method as in claim 1, wherein the particular node is a first node of a subset of all nodes in a computer network that are configured to update the delay budget and select routing topologies on which to forward the packet, and wherein the delay budget is updated based on the incurred delay since the indicated delay budget was last updated by a second node of the subset.

14. 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;

maintain a plurality of routing topologies within the computer network, each of the routing topologies associated with a different corresponding delay;

receive a packet with an indicated delay budget;

update the delay budget by subtracting an incurred delay up to and including the apparatus since the indicated delay budget was last updated, wherein the incurred delay includes a queuing delay at the particular node between receiving the packet and forwarding the packet away from the particular node;

select a particular routing topology of the plurality of routing topologies on which to forward the packet based on the updated delay budget and the corresponding routing topology delays; and

forward the packet with the updated delay budget on the particular routing topology.

15. The apparatus as in claim 14, wherein the corresponding delay associated with the routing topologies are particular to one or more specific destinations within the computer network, and wherein the process when executed to select the particular routing topology is further operable to:

determine that there is no known delay for a particular destination of the packet; and

in response, forward the packet on a default routing topology.

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

determine a condition that there is no routing topology to satisfy the updated delay budget; and

in response, select a particular routing topology of the plurality of routing topologies with a shortest delay and record the condition.

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

dynamically adjust resource allocation for one or more of the routing topologies based on at least of either a proportion of satisfied delay budgets and a proportion of unsatisfied delay budgets.

18. The apparatus as in claim 14, wherein the process when executed to update the delay budget is further operable to:

subtract at least one of either a transmission delay to reach the apparatus since the indicated delay budget was last updated and a queuing delay associated with the apparatus between receiving the packet and forwarding the packet.

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

generating a second packet by the particular device;

inserting an associated delay budget into the second packet; and

forwarding the second packet.

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

maintain a plurality of routing topologies within the computer network, each of the routing topologies associated with a different corresponding delay;

receive a packet with an indicated delay budget;

update the delay budget by subtracting an incurred delay up to and including the particular node since the indicated delay budget was last updated, wherein the incurred delay includes a queuing delay at the particular node between receiving the packet and forwarding the packet away from the particular node;

select a particular routing topology of the plurality of routing topologies on which to forward the packet based on the updated delay budget and the corresponding routing topology delays; and

forward the packet with the updated delay budget on the particular routing topology.