Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-24T19:10:17.283Z Has data issue: false hasContentIssue false
  • English
  • Français

Distribution-free confidence intervals for measurement of effective bandwidth

Part of: Stochastic processes Stochastic systems and control

Published online by Cambridge University Press:  14 July 2016

László Györfi ,
András Rácz ,
Ken Duffy ,
John T. Lewis  and
Fergal Toomey
László Györfi*
Affiliation:
Technical University of Budapest
András Rácz*
Affiliation:
Technical University of Budapest
Ken Duffy*
Affiliation:
Dublin Institute for Advanced Studies
John T. Lewis*
Affiliation:
Dublin Institute for Advanced Studies
Fergal Toomey*
Affiliation:
Dublin Institute for Advanced Studies
*
∗Postal address: Department of Computer Science and Information Theory, Technical University of Budapest, 1521 Stoczek u. 2, Budapest, Hungary
∗Postal address: Department of Computer Science and Information Theory, Technical University of Budapest, 1521 Stoczek u. 2, Budapest, Hungary
∗∗Postal address: Dublin Institute for Advanced Studies, 10 Burlington Road, Dublin 4, Ireland
∗∗Postal address: Dublin Institute for Advanced Studies, 10 Burlington Road, Dublin 4, Ireland
∗∗Postal address: Dublin Institute for Advanced Studies, 10 Burlington Road, Dublin 4, Ireland
Get access Rights & Permissions [Opens in a new window]

Abstract

Hoeffding's inequality can be used in conjunction with the declared parameters of a traffic source, such as its peak rate, to obtain confidence intervals for measurements of the traffic's effective bandwidth. We describe a variety of interval-estimation procedures based on this idea, designed to provide differing degrees of robustness against non-stationarity. We also discuss how to compute confidence intervals for the effective bandwidth of an aggregate of traffic sources.

Keywords

Effective bandwidthconfidence intervalsHoeffding's inequalitylarge deviations

MSC classification

Primary: 60G35: Signal detection and filtering
Secondary: 60G50: Sums of independent random variables; random walks 93E10: Estimation and detection
Type
Research Papers
Information
Journal of Applied Probability , Volume 37 , Issue 1 , March 2000 , pp. 224 - 235
Copyright
Copyright © 2000 by The Applied Probability Trust 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bottvich, D. D., and Duffield, N. G. (1996). Large deviations, the shape of the loss curve, and economies of scale in large multiplexers. Queueing Systems 20, 293–320.Google Scholar
Brandt, A. (1986). The stochastic equation Y_n+1=A_nY_n+B_n with stationary coefficients. Adv. Appl. Prob. 18, 69–86.Google Scholar
Courcoubetis, C., and Weber, R. (1996). Buffer overflow asymptotics for a switch handling many traffic sources. J. Appl. Prob. 33, 886–903.Google Scholar
Courcoubetis, C., Kelly, F. P., and Weber, R. (1997). Measurement-based charging in communications networks. Unpublished manuscript.Google Scholar
de Veciana, G., Kesidis, G., and Walrand, J. (1995). Resource management in wide-area ATM networks using effective bandwidths. IEEE J. Sel. Areas Commun. 13, 1081–1090.Google Scholar
Devroye, L., Györfi, L., and Lugosi, G. (1996). A Probabilistic Theory of Pattern Recognition. Springer, New York.Google Scholar
Duffield, N. G., Lewis, J. T., O'Connell, N., Russell, R., and Toomey, F. (1995). Entropy of ATM traffic streams: a tool for estimating QoS parameters. IEEE J. Sel. Areas Commun. 13, 981–990.Google Scholar
Floyd, S. (1996). Comments on measurement-based admissions control for controlled-load services. Tech. Rept. ICSI. Available at http://www.aciri.org/floyd/.Google Scholar
Gibbens, R. J. (1996). Traffic characterisation and effective bandwidths for broadband network traces. In Stochastic Networks: Theory and Applications, eds. Kelly, F. P., Zachary, S. and Ziedins, I. B. Oxford University Press, pp. 169–179.Google Scholar
Gibbens, R. J., and Kelly, F. P. (1997). Measurement-based connection admission control. In Teletraffic Contributions for the Information Age: Proc. 15th International Teletraffic Conference, eds. Ramaswami, V. and Wirth, P. E. Elsevier, Amsterdam.Google Scholar
Grossglauser, M., and Tse, D. (1997). A framework for robust measurement-based admission control. In Proc. ACM SIGCOMM '97. ACM, New York.Google Scholar
Györfi, L., and Walk, H. (1996). On the averaged stochastic approximation for linear regression. SIAM J. Contr. Opt. 34, 31–61.Google Scholar
Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. J. Amer. Statist. Soc. 58, 13–30.Google Scholar
Kelly, F. P. (1996). Notes on effective bandwidths. In Stochastic Networks: Theory and Applications, eds. Kelly, F. P., Zachary, S. and Ziedins, I. B. Oxford University Press, pp. 141–168.CrossRefGoogle Scholar
Kushner, H. J., and Shwartz, A. (1984). Weak convergence and asymptotic properties of adaptive filters with constant gains. IEEE Trans. Inform. Theory IT30, 177–182.Google Scholar
Lewis, J. T., Russell, R., Toomey, F., McGurk, B., Crosby, S., and Leslie, I. (1998). Practical connection admission control for ATM networks based on on-line measurements. Computer Communications 21, 1585–1596.Google Scholar
Pflug, G. Ch. (1986). Stochastic minimization with constant step-size: asymptotic laws. SIAM J. Contr. Opt. 24, 655–660.Google Scholar
Simonian, A., and Guibert, J. (1995). Large deviations approximation for fluid queues fed by a large number of on/off sources. IEEE J. Sel. Areas Commun. 13, 1017–1027.Google Scholar
Vervaat, W. (1979). On a stochastic difference equation and a representation of non-negative infinitely-divisble random variables. Adv. Appl. Prob. 11, 750–783.Google Scholar