Diverse path forwarding through trial and error

• US 8,559,442 B2
• Filed: 07/22/2011
• Issued: 10/15/2013
• 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:
  US13/188,609
• Publication Number:
  US 20130022046A1
• Time in Patent Office: 816 Days
• Field of Search: 3703952-39532, 709230-244, 714 5- 8
• US Class Current: 370/395.32
• 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:

receiving, at a node, a packet having a packet identifier (ID) and a distinguisher value;

determining whether any previously received packet at the node had a same packet ID and a different distinguisher value; and

in response to determining that no previously received packet has the same packet ID and different distinguisher value;

i) storing the packet ID and the distinguisher value; and

ii) forwarding the packet to a selected next-hop node.

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

determining whether the received packet is a particular type of packet; and

determining whether any previously received packet at the node had the same packet ID and different distinguisher value only in response to the packet being the particular type of packet.

3. The method as in claim 1, wherein determining whether any previously received packet at the node had the same packet ID and different distinguisher value comprises:

computing a hash of the packet as the packet ID; and

determining whether a stored hash from any previously received packet at the node is the same as the computed hash of the packet.

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

discarding a particular previously received packet from storage upon expiration of a length of time since the particular previously received packet was stored.

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

determining that a particular previously received packet has the same packet ID and a same distinguisher value; and

in response, forwarding the packet to the selected next-hop node as a retransmission, the selected next-hop node being a same node to which the particular previously received packet was forwarded.

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

in response to determining that a particular previously received packet has the same packet ID and different distinguisher value, returning a signal to a transmitting node of the packet that the particular previously received packet has the same packet ID and different distinguisher value.

7. The method as in claim 6, wherein the returned signal is selected from a group consisting of:

a negative acknowledgment (NACK); and

an explicit message.

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

receiving, from the selected next-hop node, a signal that the forwarded packet has the same packet ID and different distinguisher value of another packet previously received by the selected next-hop node; and

in response, forwarding the packet to a different next-hop node.

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

in response to determining that a particular previously received packet has the same packet ID and different distinguisher value, forwarding the packet to a different next-hop node than a next-hop node to which the particular previously received packet was forwarded.

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

selecting the selected next-hop node 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 forwarded packet.

11. 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 packet having a packet identifier (ID) and a distinguisher value;

determine whether any previously received packet at the apparatus had a same packet ID and a different distinguisher value; and

in response to determining that no previously received packet has the same packet ID and different distinguisher value;

i) store the packet ID and the distinguisher value; and

ii) forward the packet to a selected next-hop node.

12. The apparatus as in claim 11, wherein the process when executed to determine whether any previously received packet at the apparatus had the same packet ID and different distinguisher value is further operable to:

compute a hash of the packet as the packet ID; and

determine whether a stored hash from any previously received packet at the apparatus is the same as the computed hash of the packet.

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

determine that a particular previously received packet has the same packet ID and a same distinguisher value; and

in response, forward the packet to the selected next-hop node as a retransmission, the selected next-hop node being a same node to which the particular previously received packet was forwarded.

14. The apparatus as in claim 11, wherein the process when executed is further operable to, in response to determining that a particular previously received packet has the same packet ID and different distinguisher value:

return a signal to a transmitting node of the packet that the particular previously received packet has the same packet ID and different distinguisher value.

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

receive, from the selected next-hop node, a signal that the forwarded packet has the same packet ID and different distinguisher value of another packet previously received by the selected next-hop node; and

in response, forward the packet to a different next-hop node.

16. The apparatus as in claim 11, wherein the process when executed is further operable to, in response to determining that a particular previously received packet has the same packet ID and different distinguisher value:

forward the packet to a different next-hop node than a next-hop node to which the particular previously received packet was forwarded.