# US 2005/0232227 A1 · Method and apparatus for characterizing an end-to-end path of a packet-based network

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2005/0232227 A1
- Document ID: US20050232227A1
- Status: Published application
- Kind: A1
- Application number: 11/051,353
- Filed: 2005-02-04
- Published: 2005-10-20
- Earliest claimed: 2004-02-06
- Inventors: Loki Jorgenson; Robert Norris
- Web page: https://patentgrep.com/patent/US20050232227A1

## CPC

- H04L 41/14: Network analysis or design
- H04L 43/0864: Round trip delays
- H04L 43/091: Measuring contribution of individual network components to actual service level
- H04L 43/10: Active monitoring, e.g. heartbeat, ping or trace-route
- H04L 43/50: Testing arrangements
- H04L 47/10: Flow control; Congestion control
- H04L 47/115: {using a dedicated packet}
- H04L 47/18: {End to end}
- H04L 47/283: in response to processing delays, e.g. caused by jitter or round trip time [RTT]
- H04L 69/16: Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
- H04L 43/0858: {One way delays}
- H04L 43/0882: Utilisation of link capacity
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 2)

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

### Claim 4 (depends on 2)

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

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 5)

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.

### Claim 8 (depends on 1)

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.

### Claim 9 (depends on 1)

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.

### Claim 10 (depends on 1)

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.

### Claim 11 (depends on 10)

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.

### Claim 12 (depends on 10)

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.

### Claim 13 (depends on 1)

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.

### Claim 14 (depends on 13)

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

### Claim 15 (depends on 13)

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

### Claim 16 (depends on 13)

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

### Claim 17 (depends on 13)

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

### Claim 18 (depends on 14)

The method according to claim 14, wherein the one-way bitrate, Bmax is determined substantially as follows:
Bmax=(n*SL+SM)/(Λ1−Λ0)
where n is a number of load packets, SL is a size of one load packet, SM is a size of one marker packets, Λ1 is a minimum total-trip-time for the second marker packet and Λ0 is a minimum total-trip-time for the first marker packet.

### Claim 19 (depends on 16)

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.

### Claim 20 (depends on 18)

The method according to claim 18, wherein the one-way available bitrate, Bavail is determined substantially as follows:
Bavail=Bmax*[(t1−t0)/(t2−t0)]
where (t1-t0) 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 (t2-t0) is time between a trailing edge of the first marker packet and a last marker packet at the available bitrate.

### Claim 21 (depends on 1)

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.

### Claim 22 (depends on 21)

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.

### Claim 23 (depends on 21)

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.

### Claim 24 (depends on 1)

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

### Claim 25 (depends on 24)

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.

### Claim 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.

### Claim 27 (depends on 26)

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.

### Claim 28 (depends on 26)

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

### Claim 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.
