Method and apparatus for characterizing an end-to-end path of a packet-based network

• US 20050232227A1
• Filed: 02/04/2005
• Published: 10/20/2005
• Est. Priority Date: 02/06/2004
• Status: Abandoned Application

• Current Assignee: AppNeta
• Original Assignee: AppNeta
• Inventors: Jorgenson, Loki, Norris, Robert Christopher
• Application Number:
  US11/051,353
• Publication Number:
  US 20050232227A1
• Time in Patent Office: Days
• US Class Current: 370/351
• CPC Class Codes: H04L 41/14 Network analysis or design
• CPC Class Codes: H04L 43/0858 One way delays
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 43/091 Measuring contribution of individual network components to actual service level
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 43/50 Testing arrangements
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/115 using a dedicated packet
• CPC Class Codes: H04L 47/18 End to end
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]

Abstract

The present invention provides a method and apparatus for characterising a path between a source host and a destination host, including characterisation of each segment of the network path between the source host and destination host. The present invention comprises a first stage of data collection, wherein sampling of a network path is enabled by means of sending and receiving specific predetermined ordered groups of packets that can vary in size, number and protocol, wherein all packets are sent from the source host and addressed to the destination host. These ordered groups of packets include strategically arranged marker packets and load packets, wherein the load packets are typically expired at a predetermined node between the source host and destination host, and the marker packets complete their journey to the destination. After expiry of the load packets of a particular ordered group of packets, the marker packets associated therewith provide a means for capturing information relating to network characteristics up to the expiry of these load packets. Subsequent analysis of the collected information enables the characterisation of each segment along a network path between the source host and destination host. The present invention can incorporate a further analysis of the collected information performing a correlation between the characteristics of the ordered groups of packets and the collected information, thereby enabling a means for the adjustment of the characteristics of the ordered groups of packets used during sampling that can result in an optimisation of the sampling and characterisation of the network path.

Claims

1. A method for characterizing an end-to-end path of a packet-based network, said end-to-end path including two or more nodes, said method comprising the steps of:

a) generating one or more ordered groups of packets each including two or more marker packets and one or more load packets, all of said packets being configured to travel along a common end-to-end path defined by a source host and a destination host, wherein said one or more load packets are configured to traverse the end-to-end path to a predetermined node, said predetermined node being any node along the end-to-end path;

b) transmitting said one or more ordered groups of packets from said source host along said common end-to-end path;

c) collecting data relating to the transmission of said one or more ordered groups of packets; and

d) analysing said data thereby developing characteristics of the end-to-end path.

2. The method according to claim 1, wherein said step of collecting data is performed at a sink host.

3. The method according to claim 2, wherein said sink host is the source host.

4. The method according to claim 2, wherein said sink host is a node outside of the end-to-end path.

5. The method according to claim 1, wherein the step of generating the one or more ordered groups of packets comprises configuring said one or more load packets with a time-to-live value.

6. The method according to claim 1, wherein the step of generating the one or more ordered groups of packets comprises configuring said one or more load packets to cause a Port Unreachable response from the predetermined node.

7. The method according to claim 5, wherein said end-to-end path comprises one or more target hosts located between the source host and the destination host, and said time-to-live value is set for the one or more loads to expire at one of the one or more target hosts.

8. The method according to claim 1, wherein said step of generating the one or more ordered groups of packets comprises configuring said one or more load packets and said two or more marker packets using a protocol selected from the group comprising ICMP, UDP and TCP.

9. The method according to claim 1, wherein the step of generating the one or more ordered groups of packets comprises configuring said two or more marker packets with a time-to-live value in order that said two or more marker packets expire prior to reaching said destination host, wherein expiry of said two or more marker packets occurs subsequent to said marker packets traversing the predetermined node.

10. The method according to claim 1, wherein the step of collecting data comprises collection of time data relating to transmission of the one or more ordered groups of packets from the source host and reception of replies to the ordered group of packets at a sink host.

11. The method according to claim 10, wherein the step of collecting data is performed until a statistical significant amount of time data has been collected.

12. The method according to claim 10, wherein the step of analysing said data comprises evaluating one or more of total trip time, minimum total trip time, maximum total trip time, mean total trip time, standard deviation of total trip time and loss rate for one or more of the two or more marker packets and the one or more load packets.

13. The method according to claim 1, wherein said one or more ordered groups of packets comprise a first marker packet followed by one or more load packets followed by a second marker packet.

14. The method according to claim 13, wherein the step of analysing said data comprises determining a one-way bitrate.

15. The method according to claim 13, wherein the step of analysing said data comprises determining a one-way propagation delay.

16. The method according to claim 13, wherein the step of analysing said data comprises determining a one-way delay variation.

17. The method according to claim 13, wherein the step of analysing said data comprises determining a one-way available bitrate.

18. The method according to claim 14, wherein the one-way bitrate, B_max is determined substantially as follows:

B_max=(n*S_L+S_M)/(Λ

₁−

Λ

₀)

where n is a number of load packets, S_L is a size of one load packet, S_M is a size of one marker packets, Λ

₁ is a minimum total-trip-time for the second marker packet and Λ

₀ is a minimum total-trip-time for the first marker packet.

19. The method according to claim 16, wherein the one-way delay variation is determined substantially by evaluating a coefficient of variation of a standard deviation and a mean of a total-trip-time for either a first load packet or a last load packet.

20. The method according to claim 18, wherein the one-way available bitrate, B_avail is determined substantially as follows:

B_avail=B_max*[(t₁−

t₀)/(t₂−

t₀)]

where (t₁-t₀) is time between a trailing edge of the first marker packet and a trailing edge of a last marker packet at the maximum bitrate and (t₂-t₀) is time between a trailing edge of the first marker packet and a last marker packet at the available bitrate.

21. The method according to claim 1, wherein the step of modifying includes determining one or more indicators, and modifying one or more parameters of said one or more ordered groups of packets based on said one or more indicators.

22. The method according to claim 21, wherein step of modifying said parameters is selected from the group comprising changing number of load packets, changing load packet size, changing marker packet size, ramping marker packet sizes, ramping load packet sizes, changing load packet protocol, changing marker packet protocol and changing the destination host.

23. The method according to claim 21, wherein the step of modifying parameters is performed in an iterative manner in order to obtain an optimised sampling procedure.

24. The method according to claim 1, further comprising the step of evaluating convergence of data collected.

25. The method according to claim 24, wherein the step of evaluating convergence comprises the steps of percent change function evaluation, binary string function evaluation, entropy encoding, entropy analysis function evaluation and evaluation of stability of a convergence indicator.

26. An apparatus for characterizing an end-to-end path of a packet-based network, said apparatus comprising:

a) means for generating one or more ordered groups of packets each including two or more marker packets and one or more load packets, all of said packets being configured to travel along a common end-to-end path defined by a source host and a destination host, wherein said one or more load packets are configured to traverse the end-to-end path to a predetermined node, said predetermined node being any node along the end-to-end path;

b) means for transmitting said one or more ordered groups of packets from said source host along said common end-to-end path;

c) means for collecting data relating to the transmission of said one or more ordered groups of packets; and

d) means for analysing said data thereby developing characteristics of the end-to-end path.

27. The apparatus according to claim 26 further comprising a means for adaptively modifying generation of the one or more ordered groups of packets based on collected data, said means for adaptively modifying for optimizing characterization of the end-to-end path.

28. The apparatus according to claim 26 further comprising a means for evaluating convergence of data collected.

29. A computer program product comprising a computer readable medium having a computer program recorded thereon for performing a method for characterizing an end-to-end path of a packet-based network comprising the steps of:

a) generating one or more ordered groups of packets each including two or more marker packets and one or more load packets, all of said packets being configured to travel along a common end-to-end path defined by a source host and a destination host, wherein said one or more load packets are configured to traverse the end-to-end path to a predetermined node, said predetermined node being any node along the end-to-end path;

b) transmitting said one or more ordered groups of packets from said source host along said common end-to-end path;

c) collecting data relating to the transmission of said one or more ordered groups of packets; and

d) analysing said data thereby developing characteristics of the end-to-end path.