Ten fallacies and pitfalls on end-to-end available bandwidth estimation

ABSTRACT

The area of available bandwidth (avail-bw) estimation has attracted significant interest recently, with several estimation techniques and tools developed during the last 2-3 years. Unfortunately, some key issues regarding the avail-bw definition, estimation, and validation remain vague or misinterpreted. In this note, we first review the previous work in the area and classify the existing techniques in two classes: direct probing and iterative probing. We then identify ten misconceptions, in the form of fallacies or pitfalls, that we consider as most important. Some misconceptions relate to basic statistics, such as the impact of the population variance on the sample mean, the variability of the avail-bw in different time scales, and the effect of the probing duration. Other misconceptions relate to the queueing model underlying these estimation techniques. For instance, ignoring that traffic burstiness or the presence of multiple bottlenecks can cause significant underestimation errors. Our objective is not to debunk previous work or to claim that some estimation techniques are better than others, but to clarify a number of important issues that cover the entire area of avail-bw estimation so that this important metric can be better understood and put in practical use.

REFERENCES

• 1: 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.
• 2: 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.
• 3: 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]
• 4: N. Hu and P. Steenkiste, " Evaluation and Characterization of Available Bandwidth Probing Techniques," IEEE Journal on Selected Areas in Communications, vol. 21, no. 6, pp. 879--894, Aug. 2003.
• 5: 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.
• 6: 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]
• 7: 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]
• 8: Kihong Park , Walter Willinger, Self-Similar Network Traffic and Performance Evaluation, John Wiley & Sons, Inc., New York, NY, 2000
• 9: B. Melander, M. Bjorkman, and P. Gunningberg, " Regression-Based Available Bandwidth Measurements," in International Symposium on Performance Evaluation of Computer and Telecommunications Systems, 2002.
• 10: A. Pasztor, Accurate Active Measurement in the Internet and its Applications, Ph.D. thesis, Department of Electrical and Electronic Engineering, The University of Melbourne, Feb. 2003.
• 11: Robert L. Carter , Mark E. Crovella, Measuring bottleneck link speed in packet-switched networks, Performance Evaluation, 27-28, p.297-318, Oct. 1996 [doi>10.1016/0166-5316(96)00036-3]
• 12: Xiliang Liu , Kaliappa Ravindran , Benyuan Liu , Dmitri Loguinov, Single-hop probing asymptotics in available bandwidth estimation: sample-path analysis, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028831]
• 13: F. Kelly, Stochastic Networks: Theory and Applications, chapter Notes on effective bandwidths, pp. 141--168, Oxford University Press, 1996.
• 14: M. Jain, R. S. Prasad, and C. Dovrolis, " The TCP Bandwidth-Delay Product Revisited: Network Buffering, Cross Traffic, and Socket Buffer Auto-Sizing," Tech. Rep. GIT-CERCS-03-02, Georgia Tech, Feb. 2003, Available at http://www.cercs.gatech.edu/tech-reports/.

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 measurements, available bandwidth, bandwidth estimation, measurement tools, packet pairs and trains