Method and apparatus for one-way passive loss measurements using sampled flow statistics

• US 7,924,739 B2
• Filed: 12/22/2008
• Issued: 04/12/2011
• Est. Priority Date: 12/22/2008
• Status: Expired due to Fees

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Gu, Yu, Duffield, Nicholas, Sen, Subhabrata, Breslau, Lee
• Primary Examiner(s): Jung; Min
• Application Number:
  US12/317,420
• Publication Number:
  US 20100157840A1
• Time in Patent Office: 841 Days
• Field of Search: 370/241, 370/252, 370/253, 370/389, 370/229, 370/231, 370/236, 709/224
• US Class Current: 370/253
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/5009 Determining service level performance parameters or violations of service level contracts, e.g. violations of agreed response time or mean time between failures [MTBF]
• CPC Class Codes: H04L 43/026 using flow identification
• CPC Class Codes: H04L 43/0835 One way packet loss
• CPC Class Codes: H04L 43/103 with adaptive polling, i.e. dynamically adapting the polling rate
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A packet loss estimation technique is disclosed that utilizes the sampled flow level statistics that are routinely collected in operational networks, thereby obviating the need for any new router features or measurement infrastructure. The technique is specifically designed to handle the challenges of sampled flow-level aggregation such as information loss resulting from packet sampling, and generally comprises: receiving a first record of sampled packets for a flow from a first network element; receiving a second record of sampled packets for the flow from a second network element communicating with the first network element; correlating sampled packets from the flow at the first network element and the second network element to a measurement interval; and estimating the packet loss using a count of the sampled packets correlated to the measurement interval.

Claims

1. A method for estimating one-way packet loss in a packet network, the method comprising:

receiving a first record of sampled packets for a flow from a first network element;

receiving a second record of sampled packets for the flow from a second network element in communication with the first network element;

determining, for a measurement interval, a first count of the sampled packets in the first record received from the first network element and a second count of the sampled packets in the second record received from the second network element, the first and second counts to account for the sampled packets in the first and second records having been determined by sampling a fraction of packets in a packet stream for the flow; and

estimating the packet loss using the first and second counts of the sampled packets for the measurement interval.

2. The method of claim 1, wherein the estimated packet loss is represented by:

3. The method of claim 1, wherein estimating the packet loss comprises:

determining a ratio of the second count of the sampled packets from the second network element to the first count of the sampled packets from the first network element; and

subtracting the ratio from a value of one to determine an estimated packet loss for the flow between the first and second network elements.

4. The method of claim 1, wherein the flow corresponds to a transmission control protocol session, and the method further comprises:

including a transmission control protocol SYN packet from the first record in the first count if the first record includes a flow start time within the measurement interval, but otherwise not including the transmission control protocol SYN packet from the first record in the first count;

including a transmission control protocol FIN packet from the first record in the first count if the first record includes a flow end time within the measurement interval, but otherwise not including the transmission control protocol FIN packet from the first record in the first count;

including a transmission control protocol SYN packet from the second record in the second count if the second record includes a flow start time within the measurement interval, but otherwise not including the transmission control protocol SYN packet from the second record in the second count; and

including a transmission control protocol FIN packet from the second record in the second count if the second record includes a flow end time within the measurement interval, but otherwise not including the transmission control protocol FIN packet from the second record in the second count.

5. The method of claim 1, wherein the first record is part of a first set of records of sampled packets for the flow from the first network element, the second record is part of a second set of records of sampled packets for the flow from the second network element, and the method further comprises:

determining a first group of the first set of records and a second group of the second set of records that lie entirely within the measurement interval; and

determining the first and second counts of the sampled packets to be respective sums of the sample packets reported in the first and second groups of records that lie entirely within the measurement interval, the first and second counts to also include sampled SYN packets and FIN packets falling within the measurement interval but not included in the first and second groups of records.

6. The method of claim 1, wherein the first record is part of a first set of records of sampled packets for the flow from the first network element, the second record is part of a second set of records of sampled packets for the flow from the second network element, and the method further comprises:

determining the first count of the sampled packets from the first network element to be a sum of weighted numbers of sampled packets from records in the first set of records; and

determining the second count of the sampled packets from the second network element to be a sum of weighted numbers of sampled packets from records in the second set of records.

7. The method of claim 6, wherein a weighted number of sampled packets from a particular record in the first or second sets of records is determined by scaling the number of sampled packets from the particular record by a ratio of a first value to a second value, the first value corresponding to an overlap between a duration of the sampled packets in the particular record and the measurement interval, the second value corresponding to the duration of the sampled packets in the particular record.

8. A method for estimating one-way packet loss in a packet network, the method comprising:

receiving a first record of sampled packets for a flow from a first network element;

receiving a second record of sampled packets for the flow from a second network element communicating with the first network element;

associating sampled packets from the flow at the first and second network elements with a measurement interval; and

estimating packet loss using a count of the sampled packets associated with the measurement interval, wherein the estimated packet loss is represented by;

9. A method for estimating one-way packet loss in a packet network, the method comprising:

receiving a first record of sampled packets for a flow from a first network element;

receiving a second record of sampled packets for the flow from a second network element communicating with the first network element;

associating sampled packets from the flow at the first and second network elements with a measurement interval; and

estimating packet loss using a count of the sampled packets associated with the measurement interval, wherein the estimated packet loss is represented by;

10. A method for estimating one-way packet loss in a packet network, the method comprising:

receiving a first record of sampled packets for a flow from a first network element;

receiving a second record of sampled packets for the flow from a second network element communicating with the first network element;

associating sampled packets from the flow at the first and second network elements with a measurement interval; and

estimating packet loss using a count of the sampled packets associated with the measurement interval, wherein the estimated packet loss is represented by;

11. A machine-readable medium containing computer encoded instructions which, when executed by a processor, cause a device to at least:

receive a first record of sampled packets for a flow from a first network element;

receive a second record of sampled packets for the flow from a second network element in communication with the first network element;

determine, for a measurement interval, a first count of the sampled packets in the first record received from the first network element and a second count of the sampled packets in the second record received from the second network element, the first and second counts to account for the sampled packets in the first and second records having been determined by sampling a fraction of packets in a packet stream for the flow; and

estimate packet loss using the first and second counts of the sampled packets for the measurement interval.

12. The machine-readable medium of claim 11, wherein the estimated packet loss is represented by:

13. The machine-readable medium of claim 11, wherein the computer encoded instructions, when executed by the processor, further cause the device to:

determine a ratio of the second count of the sampled packets from the second network element to the first count of the sampled packets from the first network element; and

subtract the ratio from a value of one to determine an estimated packet loss for the flow between the first and second network elements.

14. The machine-readable medium of claim 11, wherein the computer encoded instructions, when executed by the processor, further cause the device to:

include a transmission control protocol SYN packet from the first record in the first count if the first record includes a flow start time within the measurement interval, but otherwise not include the transmission control protocol SYN packet from the first record in the first count;

include a transmission control protocol FIN packet from the first record in the first count if the first record includes a flow end time within the measurement interval, but otherwise not include the transmission control protocol FIN packet from the first record in the first count;

include a transmission control protocol SYN packet from the second record in the second count if the second record includes a flow start time within the measurement interval, but otherwise not include the transmission control protocol SYN packet from the second record in the second count; and

include a transmission control protocol FIN packet from the second record in the second count if the second record includes a flow end time within the measurement interval, but otherwise not include the transmission control protocol FIN packet from the second record in the second count.

15. The machine-readable medium of claim 11, wherein the first record is part of a first set of records of sampled packets for the flow from the first network element, the second record is part of a second set of records of sampled packets for the flow from the second network element, and the computer encoded instructions, when executed by the processor, further cause the device to:

determine a first group of the first set of records and a second group of the second set of records that lie entirely within the measurement interval; and

determine the first and second counts of the sampled packets to be respective sums of the sample packets reported in the first and second groups of records that lie entirely within the measurement interval, the first and second counts to also include sampled SYN packets and FIN packets falling within the measurement interval but not included in the first and second groups of records.

16. The machine-readable medium of claim 11, wherein the first record is part of a first set of records of sampled packets for the flow from the first network element, the second record is part of a second set of records of sampled packets for the flow from the second network element, and the computer encoded instructions, when executed by the processor, further cause the device to:

determine the first count of the sampled packets from the first network element to be a sum of weighted numbers of sampled packets from records in the first set of records; and

determine the second count of the sampled packets from the second network element to be a sum of weighted numbers of sampled packets from records in the second set of records.

17. The machine-readable medium of claim 16, wherein a weighted number of sampled packets from a particular record in the first or second sets of records is determined by scaling the number of sampled packets from the particular record by a ratio of a first value to a second value, the first value corresponding to an overlap between a duration of the sampled packets in the particular record and the measurement interval, the second value corresponding to the duration of the sampled packets in the particular record.

18. A machine-readable medium containing computer encoded instructions which, when executed by a processor, enable a device to estimate one-way packet loss in a packet network by at least:

receiving a first record of sampled packets for a flow from a first network element;

receiving a second record of sampled packets for the flow from a second network element communicating with the first network element;

associating sampled packets from the flow at the first and second network elements with a measurement interval; and

estimating packet loss using a count of the sampled packets associated with the measurement interval, wherein the estimated packet loss is represented by;

19. A machine-readable medium containing computer encoded instructions which, when executed by a processor, enable a device to estimate one-way packet loss in a packet network by at least:

receiving a first record of sampled packets for a flow from a first network element;

receiving a second record of sampled packets for the flow from a second network element communicating with the first network element;

associating sampled packets from the flow at the first and second network elements with a measurement interval; and

estimating packet loss using a count of the sampled packets associated with the measurement interval, wherein the estimated packet loss is represented by;

20. A machine-readable medium containing computer encoded instructions which, when executed by a processor, enable a device to estimate one-way packet loss in a packet network by at least:

receiving a first record of sampled packets for a flow from a first network element;

receiving a second record of sampled packets for the flow from a second network element communicating with the first network element;

associating sampled packets from the flow at the first and second network elements with a measurement interval; and

estimating packet loss using a count of the sampled packets associated with the measurement interval, wherein the estimated packet loss is represented by;