Methods and systems for estimating network available bandwidth using packet pairs and spatial filtering

• US 8,068,436 B2
• Filed: 10/15/2003
• Issued: 11/29/2011
• Est. Priority Date: 10/15/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rui, Yong, Vega-Garcia, Andres
• Primary Examiner(s): Harper; Kevin C
• Assistant Examiner(s): MURPHY, RHONDA L
• Application Number:
  US10/686,160
• Publication Number:
  US 20050083849A1
• Time in Patent Office: 2,967 Days
• Field of Search: None
• US Class Current: 370/252
• CPC Class Codes: H04L 43/022 by sampling
• CPC Class Codes: H04L 43/045 for graphical visualisation of monitoring data
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity

Abstract

Estimation of available bandwidth on a network uses packet pairs and spatially filtering. Packet pairs are transmitted over the network. The dispersion of the packet pairs is used to generate samples of the available bandwidth, which are then classified into bins to generate a histogram. The bins can have uniform bin widths, and the histogram data can be aged so that older samples are given less weight in the estimation. The histogram data is then spatially filtered. Kernel density algorithms can be used to spatially filter the histogram data. The network available bandwidth is estimated using the spatially filtered histogram data. Alternatively, the spatially filtered histogram data can be temporally filtered before the available bandwidth is estimated.

Claims

1. A method, comprising:

generating histogram data using packet pairs received from a data source via a network, the histogram data including bandwidth samples derived from the received packet pairs, the histogram data being associated with a plurality of bins of a histogram;

spatially filtering the histogram data, the spatial filtering including;

averaging values of samples in each bin of the plurality of bins to form a bin average for each bin;

forming smoothed bin counts for the plurality of bins by calculating, for each bin, a weighted average of a bin count of that bin and of bin count(s) of adjacent bin(s), the bin counts being weighted utilizing normalized scaling factors; and

forming a smoothed bin average for a bin in the plurality of bins having a highest smoothed bin count by calculating, for the bin in the plurality of bins having the highest smoothed bin count, a weighted average of a bin average of that bin and of bin average(s) of adjacent bin(s), the bin averages utilizing normalized scaling factors; and

estimating bandwidth available on the network using the spatially filtered histogram data.

2. The method of claim 1, wherein the packet pairs are interspersed in a real-time data stream.

3. The method of claim 1, wherein generating histogram data comprises:

receiving a packet pair transmitted by the data source via the network;

deriving a bandwidth sample from dispersion in the received packet pair; and

classifying the sample into a bin of the plurality of bins.

4. The method of claim 1, wherein the plurality of bins are of uniform bin width.

5. The method of claim 1, wherein the plurality of bins are organized into a hierarchical structure.

6. The method of claim 1, wherein spatially filtering histogram data comprises providing compensation for a bin having a different number of bins used in the spatial filtering on one side than its other side.

7. The method of claim 1, wherein a kernel density estimation algorithm is used to determine normalized scaling factors.

8. The method of claim 7, wherein the kernel density estimation algorithm includes using a linear kernel.

9. The method of claim 7, wherein the kernel density estimation algorithm includes a Gaussian kernel algorithm.

10. The method of claim 1, further comprising selectively spatially filtering lower level bins of the bin having the highest smoothed bin count.

11. The method of claim 1, wherein estimating bandwidth available on the network comprises selecting the smoothed bin average of the bin of the plurality of bins having the highest smoothed bin count.

12. The method of claim 11, wherein estimating bandwidth available on the network further comprises temporally filtering the selected smoothed bin average.

13. The method of claim 12, wherein temporally filtering the selected smoothed bin average comprises calculating a weighted average of the selected smoothed bin average and a previous estimation of the bandwidth available on the network.

14. A computer storage medium comprising computer-executable instructions stored on the computer-readable storage medium and configured to perform operations comprising:

generating histogram data using packet pairs received from a data source via a network, the histogram data including bandwidth samples derived from received packet pairs, and the histogram data being associated with a plurality of bins of a histogram;

spatially filtering the histogram data, the spatial filtering including;

averaging values of samples in each bin of the plurality of bins to form a bin average for each bin;

forming smoothed bin counts for the plurality of bins by calculating, for each bin, a weighted average of a bin count of that bin and of bin count(s) of adjacent bin(s), the bin counts being weighted utilizing normalized scaling factors; and

forming a smoothed bin average for a bin in the plurality of bins having a highest smoothed bin count by calculating, for the bin in the plurality of bins having the highest smoothed bin count, a weighted average of a bin average of that bin and of bin average(s) of adjacent bin(s), the bin averages utilizing normalized scaling factors; and

estimating bandwidth available on the network using the spatially filtered histogram data.

15. The computer storage medium of claim 14, wherein the packet pairs are interspersed in a real-time data stream.

16. The computer storage medium of claim 14, wherein generating histogram data comprises:

receiving a packet pair transmitted by the data source via the network;

deriving a bandwidth sample from dispersion in the received packet pair; and

classifying the sample into a bin of the plurality of bins.

17. The computer storage medium of claim 14, wherein the plurality of bins have uniform bin widths.

18. The computer storage medium of claim 14, wherein the plurality of bins are organized into a hierarchical structure.

19. The computer storage medium of claim 14, wherein spatially filtering histogram data comprises providing compensation for a bin having a different number of bins used in the spatial filtering on one side than its other side.

20. The computer storage medium of claim 14, wherein a kernel density estimation algorithm is used to determine normalized scaling factors.

21. The computer storage medium of claim 20, wherein the kernel density estimation algorithm includes using a linear kernel.

22. The computer storage medium of claim 20, wherein the kernel density estimation algorithm includes using a Gaussian kernel.

23. The computer storage medium of claim 14, further comprising selectively spatially filtering lower level bins of the bin of the plurality of bins having the highest smoothed bin count.

24. The computer storage medium of claim 14, wherein estimating bandwidth available on the network comprises selecting the smoothed bin average of the bin of the plurality of bins having the largest smoothed bin.

25. The computer storage medium of claim 24, wherein estimating bandwidth available on the network further comprises temporally filtering the selected smoothed bin average.

26. The computer storage medium of claim 25, wherein temporally filtering the selected bin average comprises calculating a weighted average of the selected smoothed bin average and a previous estimation of the bandwidth available on the network.

27. A system, comprising:

a processor;

a network interface coupled to the processor to receive data from a data source coupled to a network; and

a bandwidth estimator operated by the processor to estimate available bandwidth on the network, the bandwidth estimator including;

a histogram generator to generate histogram data derived from packet pairs the sent by the data source and received via the network interface, the histogram data including bandwidth samples contained in one or more bins of a plurality of bins; and

a spatial filter to filter histogram data from the histogram generator, wherein the spatial filter is to filter the histogram data by;

averaging values of samples in each bin of the plurality of bins to form a bin average for each bin;

forming smoothed bin counts for the plurality of bins by calculating, for each bin, a weighted average of a bin count of that bin and of bin count(s) of adjacent bin(s), the bin counts being weighted utilizing normalized scaling factors; and

forming a smoothed bin average for a bin in the plurality of bins having a highest smoothed bin count by calculating, for the bin in the plurality of bins having the highest smoothed bin count, a weighted average of a bin average of that bin and of bin average(s) of adjacent bin(s), the bin averages utilizing normalized scaling factors.

28. The system of claim 27, wherein the histogram data has a hierarchical structure.

29. The system of claim 27, wherein the packet pairs conform to a Real-time Transport Control Protocol (RTCP) and are interspersed in a data stream conforming to a Real-time Transport Protocol (RTP).

30. The system of claim 27, wherein the bandwidth estimator estimates the available bandwidth on the network as a function of the smoothed bin count and the smoothed bin average of the bin having the highest smoothed bin count.

31. The system of claim 27, wherein the spatial filter is further to calculate the smoothed bin average using a compensation factor when the bin having the highest smoothed bin count has only one adjacent bin.

32. The system of claim 27, wherein weights used in weighted averages are determined using a kernel density algorithm.

33. The system of claim 32, wherein the kernel density algorithm comprises a linear kernel density algorithm.

34. The system of claim 32, wherein the kernel density algorithm comprises a Gaussian kernel density algorithm.

35. The system of claim 32, wherein the bandwidth estimator further comprises a temporal filter.

36. The system of claim 35, wherein the temporal filter is to calculate a weighted average of the smoothed bin average and a previous estimation of the bandwidth available on the network.

37. A computer storage medium comprising a plurality of executable instructions configured to program a computing device to implement components including:

a bandwidth estimator to estimate available bandwidth on a network, the bandwidth estimator including;

a histogram generator to generate histogram data derived from packet pairs the sent by a data source over the network, the histogram data including bandwidth samples contained in one or more bins of a plurality of bins; and

a spatial filter to filter histogram data from the histogram generator, wherein the spatial filter is to filter the histogram data by;

averaging values of samples in each bin of the plurality of bins to form a bin average for each bin;

forming smoothed bin counts for the plurality of bins by calculating, for each bin, a weighted average of a bin count of that bin and of bin count(s) of adjacent bin(s), the bin counts being weighted utilizing normalized scaling factors; and

forming a smoothed bin average for a bin in the plurality of bins having a highest smoothed bin count by calculating, for the bin in the plurality of bins having the highest smoothed bin count, a weighted average of a bin average of that bin and of bin average(s) of adjacent bin(s), the bin averages utilizing normalized scaling factors.

38. The computer storage medium of claim 37, wherein the histogram data has a hierarchical structure.

39. The computer storage medium of claim 37, wherein the packet pairs conform with a Real-time Transport Control Protocol (RTCP) and are interspersed in a data stream conforming with a Real-time Transport Protocol (RTP).

40. The computer storage medium of claim 37, wherein the bandwidth estimator is to estimate the available bandwidth on the network as a function of the smoothed bin count and the smoothed bin average of the bin having the highest smoothed bin count.

41. The computer storage medium of claim 37, wherein the spatial filter is further to calculate the smoothed bin average using a compensation factor when the bin having the highest smoothed bin count has only one adjacent bin.

42. The computer storage medium of claim 37, wherein weights used in weighted averages are determined using a kernel density algorithm.

43. The computer storage medium of claim 42, wherein the kernel density algorithm comprises a linear kernel density algorithm.

44. The computer storage medium of claim 42, wherein the kernel density algorithm comprises a Gaussian kernel density algorithm.

45. The computer storage medium of claim 37, wherein the bandwidth estimator further comprises a temporal filter.

46. The computer storage medium of claim 45, wherein the temporal filter is to calculate a weighted average of the smoothed bin average and a previous estimation of the bandwidth available on the network.

47. A system, comprising:

means for receiving data from a data source coupled to a network;

means for generating histogram data from packet pairs the sent by the data source and received via the means for receiving, the histogram data including bandwidth samples contained in one or more bins of a plurality of bins; and

means for spatially filtering histogram data generated by the means for generating, wherein the means for spatially filtering;

averages values of samples in each bin of the plurality of bins to form a bin average for each bin;

forms smoothed bin counts for the plurality of bins by calculating, for each bin, a weighted average of a bin count of that bin and of bin count(s) of adjacent bin(s), the bin counts being weighted utilizing normalized scaling factors; and

forms a smoothed bin average for a bin in the plurality of bins having a highest smoothed bin count by calculating, for the bin in the plurality of bins having the highest smoothed bin count, a weighted average of a bin average of that bin and of bin average(s) of adjacent bin(s), the bin averages utilizing normalized scaling factors.

48. The system of claim 47, wherein the histogram data has a hierarchical structure.

49. The system of claim 47, wherein the packet pairs conform with a Real-time Transport Control Protocol (RTCP) and are interspersed in a data stream conforming with a Real-time Transport Protocol (RTP).

50. The system of claim 47, wherein the means for spatially filtering is also for calculating the smoothed bin average using a compensation factor when the bin having the highest in count has only one adjacent bin.

51. The system of claim 47, wherein weights used in weighted averages are determined using a kernel density algorithm.

52. The system of claim 47, further comprising means for temporally filtering the spatially filtered data.

53. The system of claim 52, wherein the means for temporally filtering calculates a weighted average of the smoothed bin average and a previous estimation of the bandwidth available on the network.