End-to-end estimation of the available bandwidth variation range

Abstract

The available bandwidth (avail-bw) of a network path is an important performance metric and its end-to-end estimation has recently received significant attention. Previous work focused on the estimation of the average avail-bw, ignoring the significant variability of this metric in different time scales. In this paper, we show how to estimate a given percentile of the avail-bw distribution at a user-specified time scale. If two estimated percentiles cover the bulk of the distribution (say 10% to 90%), the user can obtain a practical estimate for the avail-bw variation range. We present two estimation techniques. The first is iterative and non-parametric, meaning that it is more appropriate for very short time scales (typically less than 100ms), or in bottlenecks with limited flow multiplexing (where the avail-bw distribution may be non-Gaussian). The second technique is parametric, because it assumes that the avail-bw follows the Gaussian distribution, and it can produce an estimate faster because it is not iterative. The two techniques have been implemented in a measurement tool called Pathvar. Pathvar can track the avail-bw variation range within 10-20%, even under non-stationary conditions. Finally, we identify four factors that play a crucial role in the variation range of the avail-bw: traffic load, number of competing flows, rate of competing flows, and of course the measurement time scale.

References

1. A. Akella, S. Seshan, and A. Shaikh. An Empirical Evaluation of Wide-Area Internet Bottlenecks. In Proceedings of ACM/USENIX Internet Measurement Conference (IMC), 2003.
2. G. Bolch, S. Greiner, H. Meer, and K. S. Trivedi. Queueing Networks and Markov Chains. John Wiley and Sons, 1999.
3. N. Hu and P. Steenkiste. Evaluation and Characterization of Available Bandwidth Probing Techniques. IEEE Journal on Selected Areas in Communications, 21(6):879--894, Aug. 2003.
4. M. Jain and C. Dovrolis. Pathload: A Measurement Tool for End-to-End Available Bandwidth. In Proceedings of Passive and Active Measurements (PAM) Workshop, pages 14--25, Mar. 2002.
5. M. Jain and C. Dovrolis. End-to-End Available Bandwidth: Measurement Methodology, Dynamics, and Relation with TCP Throughput. IEEE/ACM Transactions on Networking, 11(4):537--549, Aug. 2003.
6. M. Jain and C. Dovrolis. Ten Fallacies and Pitfalls in End-to-End Available Bandwidth Estimation. In Proceedings of ACM/USENIX Internet Measurement Conference (IMC), Oct. 2004.
7. M. Jain and C. Dovrolis. End-to-end Estimation of the Available Bandwidth Variation Range (extended version). Technical report, Georgia Tech CERCS, 2005. www.cercs.gatech.edu/tech-reports/.
8. J. Kilpi and I. Norros. Testing the Gaussian Approximation of Aggregate Traffic. In Proceedings of ACM/USENIX Internet Measurement Workshop (IMW), Nov. 2002.
9. W. E. Leland, M. S. Taqqu, W. Willinger, and D. V. Wilson. On the Self-Similar Nature of Ethernet Traffic (Extended Version). IEEE/ACM Transactions on Networking, 2(1):1--15, Feb. 1994.
10. B. Melander, M. Bjorkman, and P. Gunningberg. A New End-to-End Probing and Analysis Method for Estimating Bandwidth Bottlenecks. In IEEE Global Internet Symposium, 2000.
11. NLANR MOAT. Passive Measurement and Analysis. http://pma.nlanr.net/PMA/.
12. K. Park and W. Willinger (editors). Self-Similar Network Traffic and Performance Evaluation. John Willey, 2000.
13. R. S. Prasad, M. Murray, C. Dovrolis, and K. Claffy. Bandwidth Estimation: Metrics, Measurement Techniques, and Tools. IEEE Network, Nov. 2003.
14. V. Ribeiro, M. Coates, R. Riedi, S. Sarvotham, B. Hendricks, and R. Baraniuk. Multifractal Cross-Traffic Estimation. In Proceedings ITC Specialist Seminar on IP Traffic Measurement, Modeling, and Management, Sept. 2000.
15. V. Ribeiro, R. Riedi, R. Baraniuk, J. Navratil, and L. Cottrell. pathChirp: Efficient Available Bandwidth Estimation for Network Paths. In Proceedings of Passive and Active Measurements (PAM) workshop, Apr. 2003.
16. J. Strauss, D. Katabi, and F. Kaashoek. A Measurement Study of Available Bandwidth Estimation Tools. In Proceedings of ACM/USENIX Internet Measurement Conference (IMC), 2003.
17. J. W. X. Tian and C. Ji. A Unified Framework for Understanding Network Traffic Using Independent Wavelet Models. In Proceedings of IEEE INFOCOM, June 2002.
18. M. Zukerman, T. D. Neame, and R. G. Addie. Internet Traffic Modeling and Future Technology Implications. In Proceedings of IEEE INFOCOM, 2003.

Index Terms

• Networks

  • Network services

    • Network monitoring