On-demand diverse path computation for limited visibility computer networks

• US 8,743,768 B2
• Filed: 02/27/2012
• Issued: 06/03/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.
• Primary Examiner(s): Vu, Huy D
• Assistant Examiner(s): CHIANG, KUO TUNG
• Application Number:
  US13/405,895
• Publication Number:
  US 20130223275A1
• Time in Patent Office: 827 Days
• Field of Search: 370/312, 370/252, 370/264, 370/392, 370/425
• US Class Current: 370/312
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/26 Route discovery packet

Abstract

In one embodiment, a source device detects a packet flow that meets criteria for multi-path forwarding, and forwards a probe packet on a primary path from the source device to a destination device, the probe packet carrying an indication to cause a plurality of transit devices along the primary path to add their respective local neighbor topology to the forwarded probe packet, and also to cause the destination device to compute a diverse path from the primary path based on the accumulated local neighbor topologies in the probe packet. Accordingly, the source device may receive a returned diverse path as computed by the destination device in response to the probe packet, and may thus forward the packet flow on the primary path and the diverse path from the source device to the destination device according to the multi-path forwarding.

Claims

1. A method, comprising:

detecting, at a source device, a packet flow that meets criteria for multi-path forwarding;

inserting a probe packet into a header of the packet flow;

forwarding the packet flow on a primary path from the source device to a destination device, the probe packet carrying a multi-path forwarding indicator and a topology accumulation indicator to cause a plurality of transit devices along the primary path to add their respective local neighbor topology to the forwarded probe packet, and also to cause the destination device to compute a diverse path from the primary path based on the accumulated local neighbor topologies in the probe packet, wherein the probe packet is an initial packet of the packet flow;

receiving, at the source device, a returned diverse path as computed by the destination device in response to the probe packet; and

forwarding the packet flow on the primary path and the diverse path from the source device to the destination device according to the multi-path forwarding.

2. The method as in claim 1, wherein the criteria to be met for multi-path forwarding comprises one or more criteria selected from a group consisting of:

one or more particular traffic types;

one or more particular traffic priorities;

one or more particular traffic classes;

one or more particular applications sourcing the traffic;

one or more particular destinations;

a destination within a configured distance;

traffic during one or more particular times; and

traffic during one or more particular events.

3. The method as in claim 1, wherein the diverse path is selected from a link-diverse path and a node-diverse path.

4. The method as in claim 3, wherein the indication specifically requests one of either a link-diverse path and a node-diverse path.

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

receiving a notice at the source device from the destination device that no diverse path could be computed; and

, in response,

computing a new primary path to the destination device; and

forwarding a new probe packet on the new primary path to request re-computation of a diverse path based on the new primary path and associated local neighbor topologies accumulated in the new probe packet.

6. The method as in claim 1, wherein the probe packet further carries a jitter-based indication to cause the destination device to wait a configured time after receiving a first packet for the packet flow on either the primary path or the diverse path for a copy of a the first packet on either the diverse path or the primary path, respectively, prior to processing the first packet.

7. A method, comprising:

determining a local neighbor topology by a network device;

receiving a probe packet from a packet flow on a primary path from a source device to a destination device, the probe packet carrying an indication that requests diverse path computation by the destination device of the primary path, wherein the probe packet is an initial packet of the packet flow;

in response to the indication, adding the local neighbor topology of the network device to an accumulation, within the probe packet, of respective local neighbor topologies of other transit devices along the primary path; and

forwarding the probe packet with the accumulation of local neighbor topologies toward the destination device along the primary path.

8. The method as in claim 7, wherein the local neighbor topology of the network device comprises a subset of reachable neighbors of the network device.

9. The method as in claim 8, wherein the subset of reachable neighbors comprises a set of one or more neighbors reachable from neighbors of a previous-hop and a next-hop from the network device along the primary path.

10. A method, comprising:

receiving a probe packet from a packet flow on a primary path from a source device at a destination device, the probe packet carrying an indication that requests that the destination device compute a diverse path of the primary path for the packet flow, wherein the probe packet is an initial packet of the packet flow;

retrieving the primary path of the probe packet;

retrieving, from the probe packet, an accumulation of respective local neighbor topologies of transit devices along the primary path;

computing a diverse path from the primary path based on the accumulation of local neighbor topologies in the probe packet; and

returning, from the destination device to the source device, the computed diverse path.

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

receiving the packet flow on the primary path and the diverse path from the source device; and

processing the received packet flow according to multi-path forwarding.

12. The method as in claim 10, wherein the diverse path is selected from a link-diverse path and a node-diverse path.

13. The method as in claim 12, wherein the indication specifically requests one of either a link-diverse path and a node-diverse path.

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

determining that no diverse path could be computed;

returning a notice to the source device from the destination device that no diverse path could be computed;

receiving a new probe packet on a new primary path; and

computing a diverse path from the new primary path based on a new accumulation of local neighbor topologies in the new probe packet.

15. The method as in claim 10, wherein the probe packet further carries a jitter-based indication, the method further comprising:

configuring the destination device to wait a configured time after receiving a first packet for the packet flow on either the primary path or the diverse path for a copy of a the first packet on either the diverse path or the primary path, respectively;

in response receiving the copy of the first packet, processing the first packet and the copy of the first packet at substantially the same time; and

in response to not receiving the copy of the first packet within the configured time, processing the first packet.

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

detect a packet flow that meets criteria for multi-path forwarding for which the apparatus is a source device;

insert a probe packet into a header of the packet flow;

forward the packet flow on a primary path from the source device to a destination device, the probe packet carrying a multi-path forwarding indicator and a topology accumulation indicator to cause a plurality of transit devices along the primary path to add their respective local neighbor topology to the forwarded probe packet, and also to cause the destination device to compute a diverse path from the primary path based on the accumulated local 14 neighbor topologies in the probe packet, wherein the probe packet is an initial packet of the packet flow;

receive a returned diverse path as computed by the destination device in response to the probe packet; and

forward the packet flow on the primary path and the diverse path to the destination device according to the multi-path forwarding.

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

determine a local neighbor topology of the apparatus;

receive, as a transit device, another probe packet on another primary path from another source device to another destination device;

in response to the other probe packet, add the local neighbor topology to an accumulation within the other probe packet of respective local neighbor topologies of transit devices along the other primary path; and

forward the other probe packet with the associated accumulation of local neighbor topologies toward the other destination device along the other primary path.

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

receive a probe packet of a packet flow from a source device on a primary path for which the apparatus is a destination device, the probe packet carrying an indication that requests that the apparatus as the destination device compute a diverse path of the primary path for the packet flow, wherein the probe packet is an initial packet of the packet flow;

retrieve the primary path of the probe packet;

retrieve, from the probe packet, an accumulation of respective local neighbor topologies of transit devices along the primary path;

compute a diverse path from the primary path based on the accumulation of local neighbor topologies in the probe packet; and

return the computed diverse path to the source device.

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

determine a local neighbor topology of the apparatus;

receive, as a transit device, another probe packet on another primary path from another source device to another destination device;

in response to the other probe packet, add the local neighbor topology to an accumulation within the other probe packet of respective local neighbor topologies of transit devices along the other primary path; and

forward the other probe packet with the associated accumulation of local neighbor topologies toward the other destination device along the other primary path.