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: Aditya Akella , Srinivasan Seshan , Anees Shaikh, An empirical evaluation of wide-area internet bottlenecks, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948219]
• 2: Gunter Bolch , Stefan Greiner , Hermann de Meer , Kishor Shridharbhai Trivedi, Queueing Networks and Markov Chains, Wiley-Interscience, 2005
• 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: Manish Jain , Constantinos Dovrolis, End-to-end available bandwidth: measurement methodology, dynamics, and relation with TCP throughput, IEEE/ACM Transactions on Networking (TON), v.11 n.4, p.537-549, August 2003 [doi>10.1109/TNET.2003.815304]
• 6: Manish Jain , Constantinos Dovrolis, Ten fallacies and pitfalls on end-to-end available bandwidth estimation, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028825]
• 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: Jorma Kilpi , Ilkka Norros, Testing the Gaussian approximation of aggregate traffic, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637207]
• 9: Will E. Leland , Murad S. Taqqu , Walter Willinger , Daniel V. Wilson, On the self-similar nature of Ethernet traffic (extended version), IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.1-15, Feb. 1994 [doi>10.1109/90.282603]
• 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: Kihong Park , Walter Willinger, Self-Similar Network Traffic and Performance Evaluation, John Wiley & Sons, Inc., New York, NY, 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: Jacob Strauss , Dina Katabi , Frans Kaashoek, A measurement study of available bandwidth estimation tools, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948211]
• 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

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

General Terms:
Measurement, Performance

Keywords:
active measurement, bandwidth estimation, network measurement tools, pathvar, traffic variability