MR-BART: multi-rate available bandwidth estimation in real-time

ABSTRACT

In this paper, we propose an efficient method to estimate the end-to-end Available Bandwidth (AB) of a network path. This method employs multi-rate (MR) probe packet sequences with Kalman filtering. Our proposed method is an extension of the Bandwidth Available in Real Time (BART) method, so that the probe packet sequences are injected into the network path of interest. Using this technique, the probing rate within each probing sequence is varied. We show that by a marginal addition to the computation complexity compared to the conventional BART technique, the proposed method converges faster than that of BART and achieves a more accurate estimation. In addition, this method is more robust against inappropriate initial value of Kalman filter than the conventional BART method. Furthermore, we obtain the estimation error of MR-BART based on the parameters of the probe packet sequences.

REFERENCES

• 1: Prasad, R., Murray, M., Dovrolis, C., Claffy, K. 2003. Bandwidth estimation: metrics, measurement techniques, and tools. IEEE Network, 17 (Nov. 2003), 27--35.
• 2: Garcia, E., Viamonte, D., Vidal, R., Paradells, J. 2007. Achievable bandwidths estimation for stations in multi-rate IEEE 802.11 WLAN cells. in Proc. IEEE Inernat. Symp. On a World of Wireless, Mobile and Multimedia Networks (WoWMoM 2007), 1--8.
• 3: Melander, B., Bjorkman, M., Gunningberg, P. 2000. A new end-to-end probing and analysis method for estimating bandwidth bottlenecks. in Proc. IEEE Globecomm'00, San Francisco, 1(USA, Nov. 2000), 415--420.
• 4: Jain, M., Dovrolis, C. 2002. Pathload: a measurement tool for end-to-end available bandwidth. in Proc. Passive and Active Measurement workshop, (Mar. 2002), 14--25.
• 5: Ribeiro, V., Baraniuk, R., Navratil, J., Cottrell, L. 2003. pathChirp: efficient available bandwidth estimation for network paths. in Proc. Passive and Active Measurement workshop, (Apr. 2003).
• 6: Ekelin, S., Nilsson, M., Hartikainen, E., Johnsson, A., Mangs, J., Melander, B., Bjorkman, M. 2006. Real-time measurement of end-to-end available bandwidth using Kalman filtering. in Proc. of the IEEE/IFIP Network Operations and Management Symposium, (Vancouver, Canada, Apr. 2006), 73--84.
• 7: Xiliang Liu , Kaliappa Ravindran , Dmitri Loguinov, A queueing-theoretic foundation of available bandwidth estimation: single-hop analysis, IEEE/ACM Transactions on Networking (TON), v.15 n.4, p.918-931, August 2007 [doi>10.1109/TNET.2007.896235]
• 8: Mohinder S. Grewal , Angus P. Andrews, Kalman filtering: theory and practice, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 9: Tyrone E. Duncan , Yaozhong Hu , Bozenna Pasik-Duncan, Stochastic Calculus for Fractional Brownian Motion I. Theory, SIAM Journal on Control and Optimization, v.38 n.2, p.582-612, Jan. 2000 [doi>10.1137/S036301299834171X]
• 10: Mikosch, T., Resnick, S., Rootzen, H., Stegeman, A. 2002. Is Network Traffic Approximated by Stable Lévy Motion or Fractional Brownian Motion? The Annals of Applied Probability, 12 No. 1 (Feb., 2002), 23--68.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.0 General

Additional Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.3 Software Management

General Terms:
Management, Measurement

Keywords:
Kalman filter, available bandwidth, network path, probing sequence