Diverse path forwarding through trial and error

• US 9,094,324 B2
• Filed: 09/16/2013
• Issued: 07/28/2015
• Est. Priority Date: 07/22/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): HOANG, THAI D
• Application Number:
  US14/027,973
• Publication Number:
  US 20140016643A1
• Time in Patent Office: 680 Days
• Field of Search: 3703952-39532, 709230-244, 714 5- 8
• US Class Current: 1/1
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/7453 using hashing

Abstract

In one embodiment, a node determines an intention to transmit a diversely forwarded packet through a computer network, and as such, transmits a first version of the packet having a packet identifier (ID) and a first distinguisher value to a first next-hop node, and transmits a second version of the packet having the same packet ID and a second distinguisher value different from the first distinguisher value to a second next-hop node different from the first next-hop node. In another embodiment, a next-hop node that receives the packet determines whether any previously received packet at the next-hop node had a same packet ID and a different distinguisher value. In response to determining that no previously received packet has the same packet ID and different distinguisher value, the next-hop node stores the packet ID and the distinguisher value, and forwards the packet to a selected next-hop node.

Claims

1. A method, comprising:

determining an intention to transmit a diversely forwarded packet through a computer network;

transmitting a first version of the packet having a packet identifier (ID) and a first distinguisher value to a first next-hop node; and

transmitting a second version of the packet having the same packet ID and a second distinguisher value different from the first distinguisher value to a second next-hop node different from the first next-hop node;

wherein nodes of the computer network are configured to determine whether any previously received packet at the respective node had a same packet ID and a different distinguisher value as a respectively received packet, and to forward the packet only in response to determining that no previously received packet at the respective node has the same packet ID and different distinguisher value.

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

determining whether the packet is a particular type of packet to be diversely forwarded; and

transmitting the second version of the packet only in response to the packet being the particular type of packet.

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

waiting a length of time after transmitting the first version of the packet prior to transmitting the second version of the packet.

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

transmitting a third version of the packet having the same packet ID and a third distinguisher value different from the first and second distinguisher values to a third next-hop node different from the first and second next-hop nodes.

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

determining that the first version of the packet did not reach a destination of the diversely forwarded packet; and

in response, retransmitting the first version of the packet to the first next-hop node as a retransmission with the same packet ID and the first distinguisher value.

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

selecting at least one of the first and second next-hop nodes based on a knowledge that the selected next-hop node is configured to participate in determining whether any previously received packet at the selected next-hop node had a same packet ID and a different distinguisher value than the respective transmitted version of the packet.

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

determine an intention to transmit a diversely forwarded packet through a computer network;

transmit a first version of the packet having a packet identifier (ID) and a first distinguisher value to a first next-hop node; and

transmit a second version of the packet having the same packet ID and a second distinguisher value different from the first distinguisher value to a second next-hop node different from the first next-hop node;

wherein nodes of the computer network are configured to determine whether any previously received packet at the respective node had a same packet ID and a different distinguisher value as a respectively received packet, and to forward the packet only in response to determining that no previously received packet at the respective node has the same packet ID and different distinguisher value.