Packet loss service-level guarantee monitoring and claim validation systems and methods

• US 6,795,400 B1
• Filed: 11/30/1999
• Issued: 09/21/2004
• Est. Priority Date: 11/30/1999
• Status: Expired due to Term

• Current Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.), Raytheon BBN Technlogies Corp. (Rtx Corporation), Verizon Corporate Services Group Incorporated (Verizon Communications Inc.)
• Original Assignee: Genuity Inc. (Lumen Technologies, Inc.), BBNT Solutions LLC (Rtx Corporation), Verizon Corporate Services Group Incorporated (Verizon Communications Inc.)
• Inventors: Schick, Irvin C.
• Primary Examiner(s): Yao, Kwang Bin
• Application Number:
  US09/450,549
• Time in Patent Office: 1,757 Days
• Field of Search: 370/229, 370/230, 370/231, 370/235, 370/236, 370/236.1, 370/236.2, 370/237, 370/238, 370/238.1, 370/248, 370/241, 370/252, 370/253, 370/395.2, 370/395.41, 370/395.42, 370/395.43, 709/223, 709/224, 709/238, 709/240, 709/241, 709/242
• US Class Current: 370/236
• CPC Class Codes: H04L 41/5003 Managing SLA; Interaction between SLA and QoS
• 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 41/5061 characterised by the interaction between service providers and their network customers, e.g. customer relationship management
• CPC Class Codes: H04L 41/5067 Customer-centric QoS measurements
• CPC Class Codes: H04L 43/062 related to network traffic
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/2425 for supporting services specification, e.g. SLA
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames

Abstract

A system monitors performance in a network (130) having several routers (210). The system determines a roundtrip path in the network (130) between a source and a destination, identifies routers (210) located on the path, collects performance data from the identified routers (210), and compares the performance data to at least one performance criteria to determine compliance with a service-level guarantee.

Claims

1. A computer-implemented method for monitoring performance in a network having a plurality of routers, comprising:

determining a path in the network between a source and a destination;

identifying routers located on the path;

collecting performance data from the identified routers; and

comparing the performance data to at least one performance criteria to determine compliance with a service-level guarantee.

2. The method of claim 1, wherein the determining includes:

receiving at least one traceroute, and

identifying the path from the traceroute.

3. The method of claim 1, further comprising:

performing first and second source-routed traceroutes between the source and the destination.

4. The method of claim 3, wherein the determining includes:

parsing the first traceroute to identify a first path from the source to the destination, and

parsing the second traceroute to identify a second path from the destination to the source.

5. The method of claim 4, wherein the determining further includes:

discarding portions of the first and second paths located outside the network.

6. The method of claim 1, wherein the determining includes:

identifying a first path from the source to the destination, and

identifying a second path from the destination to the source.

7. The method of claim 1, wherein the collecting includes:

obtaining performance data gathered by the identified routers over a plurality of periods.

8. The method of claim 7, wherein the collecting further includes:

partitioning time into a plurality of intervals of fixed duration,

determining an amount of overlap between the periods and the intervals, and

weighting the performance data based on the amount of overlap of the corresponding period.

9. The method of claim 1, wherein the comparing includes:

combining the performance data from each of the identified routers to obtain path performance data, and

using the path performance data in the comparison with the at least one performance criteria.

10. The method of claim 1, wherein the at least one performance criteria includes a packet threshold identifying a minimum packet rate requirement for each of the identified routers for compliance with the service-level guarantee.

11. The method of claim 1, wherein the at least one performance criteria includes a drop guarantee identifying a minimum packet loss rate permitted by each of the identified routers for compliance with the service-level guarantee.

12. The method of claim 1, wherein the at least one performance criteria includes an interval parameter identifying a duration of intervals over which a packet drop rate must be lower than a minimum packet loss rate for compliance with the service-level guarantee.

13. The method of claim 1, wherein the service-level guarantee relates to packet loss;

and

wherein the collecting includes;

obtaining packet loss statistics from the identified routers including at least one of byte rate, packet rate, a number of packet discards by the identified routers, and a number of packet drops by the identified routers.

14. A system for monitoring performance in a network having a plurality of routers, comprising:

means for determining a path in the network between a source and a destination;

means for identifying routers located on the path;

means for collecting performance data from the identified routers; and

means for comparing the performance data to at least one performance criteria to determine compliance with a service-level guarantee.

15. A system that monitors performance in a network having a plurality of routers, comprising:

a pre-processor that determines a path in the network between a source and a destination and identifies routers located on the path;

a data collector that obtains performance data from the identified routers; and

a post-processor that compares the performance data to at least one performance criteria to determine compliance with a service-level guarantee.

16. The system of claim 15, wherein when determining the path, the pre-processor is configured to receive at least one traceroute and identify the path from the traceroute.

17. The system of claim 15, further comprising:

a server that performs first and second source-routed traceroutes between the source and the destination.

18. The system of claim 17, wherein when determining the path, the pre-processor is further configured to parse the first traceroute to identify a first path from the source to the destination, and parse the second traceroute to identify a second path from the destination to the source.

19. The system of claim 18, wherein when determining the path, the pre-processor is further configured to discard portions of the first and second paths located outside the network.

20. The system of claim 15, wherein when determining the path, the pre-processor is configured to identify a first path from the source to the destination and a second path from the destination to the source.

21. The system of claim 15, wherein when obtaining performance data, the data collector is configured to collect performance data gathered by the identified routers over a plurality of periods.

22. The system of claim 21, wherein when obtaining performance data, the data collector is further configured to partition time into a plurality of intervals of fixed duration, determine an amount of overlap between the periods and the intervals, and weight the performance data based on the amount of overlap of the corresponding period.

23. The system of claim 15, wherein when comparing the performance data, the post-processor is configured to combine the performance data from each of the identified routers to obtain path performance data, and use the path performance data in the comparison with the at least one performance criteria.

24. The system of claim 15, wherein the at least one performance criteria includes a packet threshold identifying a minimum packet rate requirement for each of the identified routers for compliance with the service-level guarantee.

25. The system of claim 15, wherein the at least one performance criteria includes a drop guarantee identifying a minimum packet loss rate permitted by each of the identified routers for compliance with the service-level guarantee.

26. The system of claim 15, wherein the at least one performance criteria includes an interval parameter identifying a duration of intervals over which a packet drop rate must be lower than a minimum packet loss rate for compliance with the service-level guarantee.

27. The system of claim 15, wherein the service-level guarantee relates to packet loss;

and

wherein when obtaining performance data, the data collector is configured to collect packet loss statistics from the identified routers including at least one of byte rate, packet rate, a number of packet discards by the identified routers, and a number of packet drops by the identified routers.

28. A computer-readable medium containing instructions for controlling a computer to perform a method for monitoring performance in a network having a plurality of routers, the method comprising:

determining a path in the network between a source and a destination;

identifying routers located on the path;

collecting performance data from the identified routers; and

comparing the performance data to at least one performance criteria to determine compliance with a service-level guarantee.

29. A computer-implemented method that validates customer claims relating to performance in a network having a plurality of routers, comprising:

receiving one of the customer claims, the claim identifying a path in the network between a source and a destination and a time interval for which degraded performance was experienced;

identifying routers located on the path;

collecting performance data from the identified routers for a plurality of periods, at least some of the periods overlapping the time interval;

weighting the performance data based on an amount of overlap of the corresponding period with the time interval;

combining the weighted performance data for each of the identified routers to obtain path performance data; and

determining compliance with a service-level guarantee based on the path performance data.

30. The method of claim 29, wherein the determining includes:

comparing the path performance data to a set of performance criteria to determine compliance with the service-level guarantee.

31. A system that validates customer claims relating to performance in a network having a plurality of routers, each of the claims identifying a path in the network between a source and a destination and a time interval for which degraded performance was experienced, the system comprising:

a memory that stores instructions; and

a processor that executes the instructions stored in the memory to identify routers located on the path, collect performance data from the identified routers for a plurality of periods, at least some of the periods overlapping the time interval, weight the performance data based on an amount of overlap of the corresponding period with the time interval, combine the weighted performance data for each of the identified routers to obtain path performance data, and determine compliance with a service-level guarantee based on the path performance data.

32. A computer-readable medium that stores instructions executable by a computer to perform a method for validating customer claims relating to performance in a network having a plurality of routers, each of the claims identifying a path in the network between a source and a destination and a time interval for which degraded performance was experienced, the method comprising:

identifying routers located on the path;

collecting performance data from the identified routers for a plurality of periods, at least some of the periods overlapping the time interval;

weighting the performance data based on an amount of overlap of the corresponding period with the time interval;

combining the weighted performance data for each of the identified routers to obtain path performance data; and

determining compliance with a service-level guarantee based on the path performance data.

33. A method of validating a claim relating to a service-level guarantee, comprising:

receiving the claim from a customer, the claim identifying a first path in a network from a source to a destination, a second path from the destination to the source, and a time interval for which degraded performance was experienced in the network; and

validating the claim by collecting performance data reflecting performance of communication along the first and second paths and determining compliance with the service-level guarantee based on the collected performance data.