Method and apparatus of estimating available bandwidth on a packet network
First Claim
1. A method of estimating available bandwidth of a packet network comprising the steps of:
- determining the inter-packet intervals in a received train of packets that were injected into the network with known inter-packet intervals;
determining a variance of a distribution of sojourn times through the network of the packets in the received train of packets from the determined inter-packet intervals and the known inter-packet intervals; and
estimating the available bandwidth of the packet network from the determined variance;
wherein the step of determining a variance of a distribution of sojourn times comprises;
a) determining for each packet j in the received train of N packets the difference of sojourn times for packet j against all other packets in the received train by calculating the sum over each packet k of the difference between the inter-packet interval between packets j and k and the known inter-packet interval between packets j and k in the train of packets injected into the network;
b) determining the deviation of the sojourn time for each packet j from the mean sojourn time of the packets in the train by dividing the sum calculated in step a) for each packet j by N; and
c) determining the variance of the distribution of sojourn times of all the packets in the received train by calculating the average over N of the sum of the squares of the deviations determined in step b) of each packet j.
5 Assignments
0 Petitions
Accused Products
Abstract
By approximating a packet network, such as the Internet, by an M/M/1 queuing model, the available bandwidth of the network can determined from the variance of the distribution of the sojourn times of packets transmitted through the network. In order to determine the variance of the distribution of sojourn times, and thus the bandwidth of the packet network that is available for transport of packets from an input to an output, a probe train of N packets with known inter-packet intervals is injected from an input on a sending side of the network. At the receiving side of the network, the packet arrival times are measured and the inter-packet intervals of each pair of received packets in the received train are calculated and compared with the known inter-packet interval times of the corresponding input packets. The variance of the distribution of the sojourn times of the packets through the network can then calculated using these time differences even though the individual sojourn times of the packets through the network cannot be directly measured.
26 Citations
12 Claims
-
1. A method of estimating available bandwidth of a packet network comprising the steps of:
-
determining the inter-packet intervals in a received train of packets that were injected into the network with known inter-packet intervals; determining a variance of a distribution of sojourn times through the network of the packets in the received train of packets from the determined inter-packet intervals and the known inter-packet intervals; and estimating the available bandwidth of the packet network from the determined variance; wherein the step of determining a variance of a distribution of sojourn times comprises; a) determining for each packet j in the received train of N packets the difference of sojourn times for packet j against all other packets in the received train by calculating the sum over each packet k of the difference between the inter-packet interval between packets j and k and the known inter-packet interval between packets j and k in the train of packets injected into the network; b) determining the deviation of the sojourn time for each packet j from the mean sojourn time of the packets in the train by dividing the sum calculated in step a) for each packet j by N; and c) determining the variance of the distribution of sojourn times of all the packets in the received train by calculating the average over N of the sum of the squares of the deviations determined in step b) of each packet j. - View Dependent Claims (2, 3, 4)
-
-
5. Apparatus for estimating available bandwidth of a packet network comprising:
-
means for determining the inter-packet intervals in a received train of packets that were injected into the network with known inter-packet intervals; means for determining a variance of a distribution of sojourn times through the network of the packets in the received train of packets from the determined inter-packet intervals in the received train and the known inter-packet intervals; and means for estimating the available bandwidth of the packet network from the determined variance; wherein the means for determining a variance of sojourn times comprises; means for calculating for each packet j in the received train of N packets the sum over each packet k of the difference between the inter-packet interval between packets j and k and the known inter-packet interval between packets j and k in the train of packets injected into the network to determine the difference of sojourn times for packet j against all other packets in the received train; means for dividing by N the sum for each packet j of the calculated differences between inter-packet intervals in the output train and corresponding intervals in the input train to determining the deviation of the sojourn time for each packet j from the mean sojourn time; and means for determining the variance of the sojourn times for all the packets in the received train by calculating the average over N of the sum of the squares of the deviations determined for each packet j by the means for dividing. - View Dependent Claims (6, 7, 8)
-
-
9. A computer readable media tangibly embodying a program of instructions executable by a computer to perform a method, the method comprising the steps of:
-
determining the inter-packet intervals in a received train of packets that were injected into the network with known inter-packet intervals; determining a variance of a distribution of sojourn times through the network of the packets in the received train of packets from the determined inter-packet intervals and the known inter-packet intervals; and estimating the available bandwidth of the packet network from the determined variance; wherein in the method the step of determining a variance of sojourn times comprises; a) determining for each packet j in the received train of N packets the difference of sojourn times for packet j against all other packets in the received train by calculating the sum over each packet k of the difference between the inter-packet interval between packets j and k and the known inter-packet interval between packets j and k in the train of packets injected into the network; b) determining the deviation of the sojourn time for each packet j from the mean sojourn time of the packets in the train by dividing the sum calculated in step a) for each packet j by N; and c) determining the variance of the sojourn times of all the packets in the received train by calculating the average over N of the sum of the squares of the deviations determined in step b) of each packet j. - View Dependent Claims (10, 11, 12)
-
Specification