REACHABILITY RATE COMPUTATION WITHOUT LINK LAYER ACKNOWLEDGMENTS

• US 20120307653A1
• Filed: 06/01/2011
• Published: 12/06/2012
• Est. Priority Date: 06/01/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., Shaffer, Shmuel
• Granted Patent: US 8,885,501 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 47/22 Traffic shaping
• CPC Class Codes: H04L 47/25 with rate being modified by the source upon detecting a change of network conditions
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers
• CPC Class Codes: H04W 28/10 Flow control between communication endpoints
• CPC Class Codes: H04W 40/14 based on stability
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

In one embodiment, a device in a computer network receives a particular packet associated with a transmission attempts value, the associated transmission attempts value indicative of a first number of times a transmitter has attempted to transmit the particular packet. In response, the device increases by one a stored successful attempts value stored at the device, the stored successful attempts value indicative of a second number of times the device has received the same particular packet. As such, a reachability rate of a link from the transmitter to the device may be determined based on comparing the associated transmission attempts value to the stored successful attempts value.

Claims

1. A method, comprising:

receiving, at a device in a computer network, a particular packet associated with a transmission attempts value, the associated transmission attempts value indicative of a first number of times a transmitter has attempted to transmit the particular packet;

in response, increasing by one a stored successful attempts value stored at the device, the stored successful attempts value indicative of a second number of times the device has received the same particular packet; and

determining a reachability rate of a link from the transmitter to the device based on comparing the associated transmission attempts value to the stored successful attempts value.

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

determining whether the received particular packet is the same as a previously received packet based on a packet identification.

3. The method as in claim 2, wherein the packet identification is selected from a group consisting of:

an explicit packet identifier value; and

a computed identification of the packet, the computed identification further selected from a second group consisting of;

a hash result of the packet;

a checksum of the packet; and

a direct comparison between the received particular packet and the previously received packet.

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

determining that the received particular packet is not the same as a previously received packet; and

in response, initializing the stored successful attempts value at one.

5. The method as in claim 1, wherein the reachability rate is an expected transmission count (ETX) value, the step of determining comprising:

dividing the associated transmission attempts value by the stored successful attempts value to determine the ETX.

6. The method as in claim 1, wherein the associated transmission attempts value is carried within the particular packet, the method further comprising:

forwarding the particular packet to a next-hop device, the forwarded particular packet having the stored successful attempts value from the device as an updated associated transmission attempts value carried within the forwarded particular packet.

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

in response to rerouting the particular packet to a backup next-hop device, initializing the associated transmission attempts value within the forwarded particular packet at one.

8. The method as in claim 1, wherein the associated transmission attempts value is carried within the particular packet, and wherein determining the reachability rate occurs at the device, the method further comprising:

transmitting the reachability rate to the transmitter.

9. The method as in claim 8, wherein at least one of determining the reachability rate and transmitting the reachability rate is in response to a trigger selected from a group consisting of:

a crossed reachability rate threshold;

a number of received packets;

an updated reachability rate; and

expiration of a timer.

10. The method as in claim 1, wherein determining the reachability rate occurs at a rate selected from a group consisting of:

at each received particular packet;

at each received particular packet that is a particular type of packet;

at each received particular packet that has the associated transmission attempts value; and

at a select periodicity of packets.

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

transmitting the stored successful attempts value to the transmitter; and

wherein determining the reachability rate occurs at the transmitter.

12. 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 particular packet carrying a transmission attempts value, the associated transmission attempts value indicative of a first number of times a transmitter has attempted to transmit the particular packet;

in response, increase by one a stored successful attempts value, the stored successful attempts value indicative of a second number of times the process has received the same particular packet; and

determine a reachability rate of a link from the transmitter to the network interfaces based on comparing the associated transmission attempts value to the stored successful attempts value.

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

determine whether the received particular packet is the same as a previously received packet based on a packet identification.

14. The apparatus as in claim 13, wherein the packet identification is selected from a group consisting of:

an explicit packet identifier value; and

a computed identification of the packet, the computed identification further selected from a second group consisting of;

a hash result of the packet;

a checksum of the packet; and

a direct comparison between the received particular packet and the previously received packet.

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

determine that the received particular packet is not the same as a previously received packet; and

in response, initialize the stored successful attempts value at one.

16. The apparatus as in claim 12, wherein the reachability rate is an expected transmission count (ETX) value, wherein the process when executed to determine is further operable to:

divide the associated transmission attempts value by the stored successful attempts value to determine the ETX.

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

forward the particular packet to a next-hop device, the forwarded particular packet having the stored successful attempts value from the apparatus as an updated associated transmission attempts value within the forwarded particular packet.

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

transmit the reachability rate to the transmitter.

19. A method, comprising:

transmitting, from a transmitter device, a particular packet to a next-hop device in a computer network, the particular packet associated with a transmission attempts value, the associated transmission attempts value indicative of a first number of times the transmitter has attempted to transmit the particular packet;

receiving, at the transmitter from the next-hop device, a stored successful attempts value indicative of a second number of times the next-hop device has received the same particular packet from the transmitter; and

determining a reachability rate of a link from the transmitter to the next-hop device based on comparing the associated transmission attempts value to the stored successful attempts value.

20. The method as in claim 19, wherein the reachability rate is an expected transmission count (ETX) value, the step of determining comprising:

dividing the associated transmission attempts value by the stored successful attempts value to determine the ETX.