Detecting packet loss and retransmission in a network environment

• US 9,240,939 B2
• Filed: 10/22/2013
• Issued: 01/19/2016
• Est. Priority Date: 10/22/2013
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Nguyen, Khanh Vinh, Ben-Dvora, Nir, Nagulapalli, Harinadh
• Primary Examiner(s): Mui, Gary
• Application Number:
  US14/060,569
• Publication Number:
  US 20150109942A1
• Time in Patent Office: 819 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 43/0835 One way packet loss
• CPC Class Codes: H04L 43/12 Network monitoring probes

Abstract

One example method is provided for detecting end-to-end packet loss and retransmission occurring in a connection of a network environment. The method can include monitoring packets transmitted from a sender to a receiver and acknowledgement packets from the receiver to the sender using a probe located in a path between the sender and the receiver in the network environment; identifying, by the probe, a first packet as a possibly-retransmitted packet if the first packet has a fall back sequence number; classifying, by the probe, the first packet as a retransmitted packet using one or more conditions based, at least in part, on one or more of the following: characteristic(s) of the possibly-retransmitted packet, characteristic(s) of sequence numbers observed by the probe, and characteristic(s) of acknowledgements observed by the probe.

Claims

1. A method for detecting end-to-end packet loss and retransmission occurring in a connection of a network environment, the method comprising:

monitoring packets transmitted from a sender to a receiver and acknowledgement packets from the receiver to the sender using a probe located in a path between the sender and the receiver in the network environment;

maintaining a two-state variable for storing either;

(1) a missing sequence number in the sequence numbers of packets observed before the first packet, or (2) a no-gap value which indicates that the sequence numbers of packets observed before the first packet do not have a missing sequence number;

identifying, by the probe, a first packet as a possibly-retransmitted packet if the first packet has a fall back sequence number; and

if the two-state variable holds a no-gap value, classifying, by the probe, the possibly-retransmitted packet as a retransmitted packet.

2. The method of claim 1, wherein:

identifying, by the probe, the first packet as a possibly-retransmitted packet comprises determining whether the sequence number in the first packet is less than a next expected sequence number, indicating that the sequence numbers of the packets are not monotonically increasing; and

wherein the next expected sequence number is stored in a variable previously updated based on a sum of the sequence number of a second packet observed before the first packet and the length of the second packet, and the second packet is not identified as a possibly-retransmitted packet.

3. The method of claim 1, further comprising:

determining whether a delay, observed by the probe, between (1) the time of the possibly-retransmitted packet and (2) the time of the acknowledgement expecting the possibly-retransmitted packet exceeds a predetermined threshold; and

if the delay exceeds the predetermined threshold, classifying the possibly-retransmitted packet as a retransmitted packet.

4. The method of claim 3, wherein the predetermined threshold is an estimated round-trip time between the sender and the receiver in the network environment.

5. The method of claim 1, further comprising:

determining whether the probe has observed a number of repeated acknowledgements, expecting the possibly-retransmitted packet, from the receiver greater than or equal to a predetermined number of repeated acknowledgements, indicating a fast transmission has occurred; and

if the probe has observed more than the predetermined number of repeated acknowledgements, classifying the possibly-retransmitted packet as a retransmitted packet.

6. The method of claim 5, wherein the predetermined number of repeated acknowledgement is 3.

7. The method of claim 1, further comprising:

incrementing a variable for storing a number of observed repeated acknowledgements if the sequence number expected by two consecutive acknowledgements transmitted from the receiver to the sender are the same, otherwise, resetting the variable to zero.

8. The method of claim 1, further comprising:

if the two-state variable holds a missing sequence number and the sequence number of the possibly-retransmitted packet is equal to the missing sequence number, classifying the possibly-retransmitted packet is an out-of-order packet; and

updating the two-state variable to hold the no-gap value.

9. The method of claim 1, further comprising:

if the sequence number of the first packet is greater than a next expected sequence number, indicating that the sequence numbers observed in the packets exhibits a gap,

wherein the next expected sequence number is stored in a variable previously updated based on a sum of the sequence number of a second packet observed before the first packet and the length of the second packet, and the second packet is not identified as a possibly-retransmitted packet; and

updating the two-state variable to hold the next expected sequence number as the missing sequence number.

10. The method of claim 1, further comprising:

if the sequence number in the first packet is greater a last observed sequence number, indicating that the first packet is not a possibly-retransmitted packet;

updating a first variable for storing a last observed sequence number with the sequence number in the first packet; and

updating a second variable for storing a next expected sequence number based on the sum of the sequence number in the first packet and the length of the first packet; and

using the first variable and/or the second variable for determining, by the probe, whether a third packet observed after the first packet is a possibly-retransmitted packet.

11. One or more non-transitory media that includes code for execution that when executed by a processor configure the processor to perform operations for detecting end-to-end packet loss and retransmission occurring in a connection of a network environment, the operations comprising:

monitoring packets transmitted from a sender to a receiver and acknowledgement packets from the receiver to the sender using a probe located in a path between the sender and the receiver in the network environment;

maintaining a two-state variable for storing either;

(1) a missing sequence number in the sequence numbers of packets observed before the first packet, or (2) a no-gap value which indicates that the sequence numbers of packets observed before the first packet do not have a missing sequence number;

identifying, by the probe, a first packet as a possibly-retransmitted packet if the first packet has a fall back sequence number; and

if the two-state variable holds a no-gap value, classifying, by the probe, the possibly-retransmitted packet as a retransmitted packet.

12. The one or more non-transitory media of claim 11, wherein the operations further comprise:

determining whether a delay, observed by the probe, between (1) the time of the possibly-retransmitted packet and (2) the time of the acknowledgement expecting the possibly-retransmitted packet exceeds a predetermined threshold; and

if the delay exceeds the predetermined threshold, classifying the possibly-retransmitted packet as a retransmitted packet.

13. The one or more non-transitory media of claim 11, wherein the operations further comprise:

determining whether the probe has observed a number of repeated acknowledgements, expecting the possibly-retransmitted packet, from the receiver greater than or equal to a predetermined number of repeated acknowledgements, indicating a fast transmission has occurred; and

if the probe has observed more than the predetermined number of repeated acknowledgements, classifying the possibly-retransmitted packet as a retransmitted packet.

14. The one or more non-transitory media of claim 11, wherein the operations further comprise:

if the two-state variable holds a missing sequence number and the sequence number of the possibly-retransmitted packet is equal to the missing sequence number, classifying that the possibly-retransmitted packet is an out-of-order packet; and

updating the two-state variable to hold the no-gap value.

15. A probe for detecting end-to-end packet loss and retransmission occurring in a connection of a network environment, the probe located in a path between the sender and the receiver in the network environment, the probe comprising:

a memory for storing data comprising one or more variables;

one or more processors operable to execute instructions associated with the data, instructions comprising;

monitoring packets transmitted from a sender to a receiver and acknowledgement packets from the receiver to the sender using a probe located in a path between the sender and the receiver in the network environment;

maintaining a two-state variable in the memory for storing either;

(1) a missing sequence number in the sequence numbers of packets observed before the first packet, or (2) a no-gap value which indicates that the sequence numbers of packets observed before the first packet do not have a missing sequence number;

identifying, by the probe, a first packet as a possibly-retransmitted packet if the first packet has a fall back sequence number; and

if the two-state variable holds a no-gap value, classifying, by the probe, the possibly-retransmitted packet as a retransmitted packet.

16. The probe of claim 15, wherein the instructions further comprise:

determining whether a delay, observed by the probe, between (1) the time of the possibly-retransmitted packet and (2) the time of the acknowledgement expecting the possibly-retransmitted packet exceeds a predetermined threshold; and

if the delay exceeds the predetermined threshold, classifying the possibly-retransmitted packet as a retransmitted packet.

17. The probe of claim 15, wherein the instructions further comprise:

determining whether the probe has observed a number of repeated acknowledgements, expecting the possibly-retransmitted packet, from the receiver greater than or equal to a predetermined number of repeated acknowledgements, indicating a fast transmission has occurred; and

if the probe has observed more than the predetermined number of repeated acknowledgements, classifying the possibly-retransmitted packet as a retransmitted packet.

18. The probe of claim 15, wherein the instructions further comprise:

if the two-state variable holds a missing sequence number and the sequence number of the possibly-retransmitted packet is equal to the missing sequence number, classifying that the possibly-retransmitted packet is an out-of-order packet; and

updating the two-state variable to hold the no-gap value.

19. A method for detecting end-to-end packet loss and retransmission occurring in a connection of a network environment, the method comprising:

monitoring packets transmitted from a sender to a receiver and acknowledgement packets from the receiver to the sender using a probe located in a path between the sender and the receiver in the network environment;

identifying, by the probe, a first packet as a possibly-retransmitted packet if the first packet has a fall back sequence number;

determining whether a delay, observed by the probe, between (1) the time of the possibly-retransmitted packet and (2) the time of the acknowledgement expecting the possibly-retransmitted packet exceeds a predetermined threshold; and

if the delay exceeds the predetermined threshold, classifying the possibly-retransmitted packet as a retransmitted packet.

20. The method of claim 19, wherein:

identifying, by the probe, the first packet as a possibly-retransmitted packet comprises determining whether the sequence number in the first packet is less than a next expected sequence number, indicating that the sequence numbers of the packets are not monotonically increasing; and

wherein the next expected sequence number is stored in a variable previously updated based on a sum of the sequence number of a second packet observed before the first packet and the length of the second packet, and the second packet is not identified as a possibly-retransmitted packet.

21. The method of claim 19, wherein the predetermined threshold is an estimated round-trip time between the sender and the receiver in the network environment.

22. The method of claim 19, further comprising:

determining whether the probe has observed a number of repeated acknowledgements, expecting the possibly-retransmitted packet, from the receiver greater than or equal to a predetermined number of repeated acknowledgements, indicating a fast transmission has occurred; and

if the probe has observed more than the predetermined number of repeated acknowledgements, classifying the possibly-retransmitted packet as a retransmitted packet.

23. The method of claim 22, wherein the predetermined number of repeated acknowledgement is 3.

24. The method of claim 19, further comprising:

incrementing a variable for storing a number of observed repeated acknowledgements if the sequence number expected by two consecutive acknowledgements transmitted from the receiver to the sender are the same, otherwise, resetting the variable to zero.

25. The method of claim 19, further comprising:

determining whether there is no gap in sequence numbers observed by the probe;

if there is no gap, classifying the possibly-retransmitted packet as a retransmitted packet.

26. The method of claim 19, further comprising:

maintaining a two-state variable for storing either;

(1) a missing sequence number in the sequence numbers of packets observed before the first packet, OR

(2) a no-gap value which indicates that the sequence numbers of packets observed before the first packet do not have a missing sequence number.

27. The method of claim 26, further comprising:

determining whether the two-state variable is holding a no-gap value, indicating that the possibly-retransmitted packet is a retransmitted packet; and

if the two-state variable has a no-gap value, classifying the possibly-retransmitted packet as a retransmitted packet.

28. The method of claim 26, further comprising:

determining whether the two-state variable is holding a missing sequence number;

if the two-state variable holds a missing sequence number and the sequence number of the possibly-retransmitted packet is equal to the missing sequence number, classifying the possibly-retransmitted packet is an out-of-order packet; and

updating the two-state variable to hold the no-gap value.

29. The method of claim 26, further comprising:

if the sequence number of the first packet is greater than a next expected sequence number, indicating that the sequence numbers observed in the packets exhibits a gap,

wherein the next expected sequence number is stored in a variable previously updated based on a sum of the sequence number of a second packet observed before the first packet and the length of the second packet, and the second packet is not identified as a possibly-retransmitted packet; and

updating the two-state variable to hold the next expected sequence number as the missing sequence number.

30. The method of claim 19, further comprising:

if the sequence number in the first packet is greater a last observed sequence number, indicating that the first packet is not a possibly-retransmitted packet;

updating a first variable for storing a last observed sequence number with the sequence number in the first packet; and

updating a second variable for storing a next expected sequence number based on the sum of the sequence number in the first packet and the length of the first packet;

and

using the first variable and/or the second variable for determining, by the probe, whether a third packet observed after the first packet is a possibly-retransmitted packet.

31. One or more non-transitory media that includes code for execution that when executed by one or more processors configure the one or more processors to perform operations for detecting end-to-end packet loss and retransmission occurring in a connection of a network environment, the operations comprising:

monitoring packets transmitted from a sender to a receiver and acknowledgement packets from the receiver to the sender using a probe located in a path between the sender and the receiver in the network environment;

identifying, by the probe, a first packet as a possibly-retransmitted packet if the first packet has a fall back sequence number;

determining whether a delay, observed by the probe, between (1) the time of the possibly-retransmitted packet and (2) the time of the acknowledgement expecting the possibly-retransmitted packet exceeds a predetermined threshold; and

if the delay exceeds the predetermined threshold, classifying the possibly-retransmitted packet as a retransmitted packet.

32. The one or more non-transitory media of claim 31, wherein the predetermined threshold is an estimated round-trip time between the sender and the receiver in the network environment.

33. The one or more non-transitory media of claim 31, wherein the operations further comprises:

maintaining a two-state variable for storing either;

(1) a missing sequence number in the sequence numbers of packets observed before the first packet, OR

(2) a no-gap value which indicates that the sequence numbers of packets observed before the first packet do not have a missing sequence number.

34. The one or more non-transitory media of claim 33, wherein the operations further comprises:

determining whether the two-state variable is holding a no-gap value, indicating that the possibly-retransmitted packet is a retransmitted packet; and

if the two-state variable has a no-gap value, classifying the possibly-retransmitted packet as a retransmitted packet.

35. The one or more non-transitory media of claim 33, wherein the operations further comprises:

determining whether the two-state variable is holding a missing sequence number;

if the two-state variable holds a missing sequence number and the sequence number of the possibly-retransmitted packet is equal to the missing sequence number, classifying the possibly-retransmitted packet is an out-of-order packet; and

updating the two-state variable to hold the no-gap value.

36. A probe for detecting end-to-end packet loss and retransmission occurring in a connection of a network environment, the probe located in a path between the sender and the receiver in the network environment, the probe comprising:

a memory for storing data comprising one or more variables;

one or more processors operable to execute instructions associated with the data, instructions comprising;

monitoring packets transmitted from a sender to a receiver and acknowledgement packets from the receiver to the sender using a probe located in a path between the sender and the receiver in the network environment;

identifying, by the probe, a first packet as a possibly-retransmitted packet if the first packet has a fall back sequence number;

determining whether a delay, observed by the probe and determined based on the one or more variables in the memory, between (1) the time of the possibly-retransmitted packet and (2) the time of the acknowledgement expecting the possibly-retransmitted packet exceeds a predetermined threshold; and

if the delay exceeds the predetermined threshold, classifying the possibly-retransmitted packet as a retransmitted packet.

37. The probe of claim 36, wherein the instructions further comprise:

determining whether the probe has observed a number of repeated acknowledgements, expecting the possibly-retransmitted packet, from the receiver greater than or equal to a predetermined number of repeated acknowledgements, indicating a fast transmission has occurred; and

if the probe has observed more than the predetermined number of repeated acknowledgements, classifying the possibly-retransmitted packet as a retransmitted packet.

38. The probe of claim 36, wherein the instructions further comprise:

determining whether there is no gap in sequence numbers observed by the probe based on a two-state variable stored in the memory, wherein the two-state variable stores either (1) a missing sequence number in the sequence numbers of packets observed before the first packet, or (2) a no-gap value which indicates that the sequence numbers of packets observed before the first packet do not have a missing sequence number;

if the two-state variable indicates there is no gap, classifying the possibly-retransmitted packet as a retransmitted packet.