Network Tomography Using Close-Spaced Unicast Packets

• US 20020116154A1
• Filed: 09/14/2001
• Published: 08/22/2002
• Est. Priority Date: 09/15/2000
• Status: Active Grant

• Current Assignee: Rice University
• Original Assignee: Rice University
• Inventors: Coates, Mark J., Nowak, Robert D.
• Granted Patent: US 6,839,754 B2
• Time in Patent Office: Days
• US Class Current: 702/186
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• 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 43/0852 Delays
• CPC Class Codes: H04L 43/091 Measuring contribution of individual network components to actual service level
• CPC Class Codes: H04L 43/50 Testing arrangements

Abstract

This work discloses a unicast, end-to-end network performance measurement process which is capable of determining internal network losses, delays, and probability mass functions for these characteristics. The process is based on using groups of closely-spaced communications packets to determine the information necessary for inferring the performance characteristics of communications links internal to the network. Computationally efficient estimation algorithms are provided.

Claims

1. A method of determining network performance, wherein the method includes:

sending a set of unicast communications packets from a source through the network to multiple receivers;

receiving from each of the multiple receivers receipt information indicating those communications packets which have been successfully received by that receiver; and

determining a performance characteristic for each of multiple communications links in the network solely from the receipt information.

2. The method of claim 1, wherein the set of unicast communications packets includes multiple groups of communications packets.

3. The method of claim 2, wherein the groups are separated by at least a minimum time, wherein the communications packets within the groups are separated by no more than a maximum time, and wherein the maximum time is substantially less than the minimum time.

4. The method of claim 2, wherein each group is a packet pair separated by less than a maximum time.

5. The method of claim 4, wherein at least one of the packet pair s includes packets going to different receivers.

6. The method of claim 4, wherein at least one of the packet pairs includes packets going to the same receiver.

7. The method of claim 2, wherein the set of unicast communications packets further includes multiple isolated communications packets.

8. The method of claim 7, wherein the isolated communications packets and the groups are separated from other isolated communications packets and groups by at least some minimum time which is at least twice a maximum time separation for communications packets in the groups.

9. The method of claim 7, wherein the performance characteristic is an unconditional packet loss rate.

10. The method of claim 9, wherein said determining a performance characteristic includes:

computing a conditional packet success rate of packets in the groups for the multiple communications links.

11. The method of claim 7, wherein the performance characteristic is an unconditional packet success probability estimate and a confidence measure of the success probability estimate.

12. The method of claim 7, wherein the performance characteristic is average packet delay, and the receipt information indicates an end-to-end travel time of the communications packets.

13. The method of claim 7, wherein the performance characteristic is a packet delay probability mass function, and the receipt information indicates an end-to-end travel time of the communications packets.

15. The method of claim 11, wherein the closely-spaced communications packets in each set have a conditional packet success rate of substantially unity.

16. The method of claim 11, wherein the multiple sets are transmitted in a manner that avoids correlation of performance conditions.

18. The computer of claim 17, wherein the set of unicast communications packets consists of multiple isolated packets and multiple back-to-back packet pairs, wherein the isolated packets and packet pairs are separated from other isolated packets and packet pairs by at least a minimum time spacing value between 100 μ

s and 100 ms.

19. The computer of claim 17, wherein the performance characteristic is one of a set of characteristics consisting of an unconditional packet loss rate and an average packet delay.

20. The computer of claim 17, wherein the performance measurement is one of a set of characteristics consisting of an unconditional packet success posterior probability density function, and a packet delay probability mass function.

14. A method of determining network performance, wherein the method includes:

sending multiple sets of closely-spaced communications packets from a source through the network to multiple receivers;

receiving from each of the multiple receivers receipt information indicating those communications packets which have been successfully received by that receiver; and

determining a performance characteristic for each of multiple communications links in the network from the receipt information.

17. A source computer configured to execute network performance determination software, wherein the software comprises:

a topology component configured to determine a tree structure of network communications paths from the source computer to multiple receivers;

a probe component configured to create a first log to track a set of unicast communications packets transmitted from the source computer to the multiple receivers;

a gathering component configured to create a second log to track end-to-end measurement information received from the multiple receivers regarding those communications packets which have been successfully received by the multiple receivers; and

an estimation component configured to process the first and second logs to determine a performance characteristic for each communications link identified in the tree structure.