Bandwidth estimation in broadband access networks
AssigneeMicrosoft Corporation
InventorsVenkata Padmanabhan, Jitendra Padhye
Life of this patent
Estimating the term…
Abstract
Measurement systems according to embodiments of the invention allow accurate bandwidth estimation even in non-FIFO scheduling and frame-level contention environments. In an embodiment of the invention, the approximate fraction of time that a link is idle is found by probing for idle periods (“gaps”). The fraction of idle time is then multiplied by the capacity to obtain an estimate of the available bandwidth. Gap time is estimated in an embodiment of the invention fraction by gathering samples of one-way delay (OWD) over the link in question. After the OWD is normalized and plotted, the knee in the cumulative distribution function (CDF) of OWD samples is used to identify the fraction of time that the channel is idle.
Claims20
A method of measuring available bandwidth over a network path between a source machine and a destination machine, the method comprising:
- sending a series of probes, each containing a local timestamp;
- recording a respective destination time stamp for each probe indicating the time at which the probe was received at the destination device;
- computing a set of one way delays by differencing the local timestamp and the destination time stamp to compute the respective one way delay experienced by each probe over the network path;
- and
- calculating an estimate of bandwidth available on the network path based on the set of one way delays.
A computer-readable medium having thereon computer-readable instructions for performing a method of measuring available bandwidth over a network path between a source machine and a destination machine, the instructions comprising instructions for:
- sending a series of probes, each containing a local timestamp;
- computing a set of respective round trip times experienced by each probe over the network path;
- and
- calculating an estimate of bandwidth available on the network path based on the set of respective round trip times.
A method of measuring available bandwidth over a network path between a source machine and a destination machine, the method comprising:
- sending a series of probe groups, each probe group containing a plurality of packets, each packet having a local timestamp;
- receiving a respective destination time stamp for each packet indicating the time at which the packet was received at the destination machine;
- computing a set of one way delays by differencing the local timestamp and the destination time stamp to compute the respective one way delay experienced by each packet over the network path;
- for each probe group, identifying a maximum one way delay experienced by one of the probe group packets, wherein the maximum one way delay is greater than all other one way delays experienced by packets in the group, to identify a set of maximum one way delays comprising the maximum one way delay for each probe group;
- and
- calculating an estimate of bandwidth available on the network path based on the set of maximum one way delays.
The method according to claim 19, wherein calculating an estimate of bandwidth available on the network path based on the set of maximum one way delays comprises:
- forming the cumulative distribution function for the set of maximum one way delays;
- identifying a point in the cumulative distribution function wherein the point separates a first region of the cumulative distribution function having a first slope from a second region of the cumulative distribution function having a second slope that is lower than the first slope;
- and
- calculating an estimate of bandwidth available on the network path based on the delay value at the point.
Dependencies are inferred from the claim text.