Exponential bounds with applications to call admission

ABSTRACT

In this paper, we develop a framework for computing upper and lower bounds of an exponential form for a large class of single resource systems with Markov additive inputs. Specifically, the bounds are on quantities such as backlog, queue length, and response time. Explicit or computable expressions for our bounds are given in the context of queuing theory and numerical comparisons with other bounds and exact results are presented. The paper concludes with two applications to admission control in multimedia systems.

REFERENCES

• 1: ABATE, J., CHOUDHURY, G. L., AND WHITT, W. 1994. Asymptotics for steady-state tail probabilities in structured Markov queueing models. Commun. Statist. Stochastic Models 10, 1, 99-143.
• 2: Joseph Abate , Ward Whitt, The Fourier-series method for inverting transforms of probability distributions, Queueing Systems: Theory and Applications, v.10 n.1-2, p.5-88, Jan. 1992 [doi>10.1007/BF01158520]
• 3: ANICK, D., MITRA, D., AND SONDHI, M.M. 1982. Stochastic theory of a data-handling system with multiple sources. Bell Syst. Tech. J. 61, 1871-1894.
• 4: D. Artiges , P. Nain, Upper and lower bounds for the multiplexing of multiclass Markovian on/off sources, Performance Evaluation, 27-28, p.673-698, Oct. 1996 [doi>10.1016/0166-5316(96)00035-1]
• 5: ASMUSSEN, S. 1987. Applied Probability and Queues. Wiley, New York.
• 6: ASMUSSEN, S. 1995. Stationary distributions via first passage times. Preprint. (Jan.).
• 7: Søren Asmussen , Tomasz Rolski, Risk theory in a periodic environment: the Crame´r-Lundberg approximation and Lundberg's inequality, Mathematics of Operations Research, v.19 n.2, p.410-433, May 1994 [doi>10.1287/moor.19.2.410]
• 8: BOLOT, J., AND VEGA GARCIA, A. 1996. Control mechanisms for packet audio in the internet. In Proceedings of INFOCOM '96 (San Francisco, Calif., Mar.) IEEE Computer Society Press, Los Alamitos, Calif., pp. 232-239.
• 9: BOROVKOV, A.A. 1976. Stochastic Processes in Queueing Theory. Springer-Verlag, New York.
• 10: BOROVKOV, A. A., AND FOSS, S.G. 1992. Stochastically recursive sequences and their generalizations. Sib. Adv. Math. 2, 16-81.
• 11: BOTVICH, D. D., AND DUFFIELD, N. G. 1995. Large deviations, the shape of the loss curve and economies of scale in large multiplexers. Que. Syst. 20, 293-320.
• 12: BREWER, J. W. 1978. Kronecker products and matrix calculus in system theory. IEEE Trans. Circuit Syst. 25, 9, 772-781.
• 13: CHANG, C.-S. 1994. Stability, queue length and delay of deterministic and stochastic queueing networks. IEEE Trans. Aut. Contr. 39, 5 (May), 913-931.
• 14: Cheng-Shang Chang , Jay Cheng, Computable exponential bounds for intree networks with routing, Proceedings of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies (Vol. 1)-Volume, p.197, April 02-06, 1995
• 15: Cheng-Shang Chang , Philip Heidelberger , Sandeep Juneja , Perwez Shahabuddin, Effective bandwidth and fast simulation of ATM intree networks, Performance Evaluation, v.20 n.1-3, p.45-65, May 1994
• 16: CHOUDHURY, G. L., LUCANTONI, D. M., AND WHITT, W. 1996. Squeezing the most out of ATM. IEEE Trans. Commun. 44, 2 (Feb.), 203-217.
• 17: COURCOUBETIS, C., FOUSKAS, G., AND WEBER, R. 1994. On the performance of an effective bandwidth formula. In Proceedings of ITC'14 (Antibes, June). J. Labetoulle, J. Roberts, eds. Elsevier, Amsterdam, The Netherlands, pp. 201-212.
• 18: COURCOUBETIS, C., AND WEBER, R. 1996. Buffer overflow asymptotics for a switch handling many traffic sources. J. Appl. Prob. 33, (Sept.), 886-903.
• 19: CRUZ, R.L. 1991a. A calculus for network delay. Part I: Network elements in isolation. IEEE Trans. Inf. Theory 37, 1 (Jan.), 114-131.
• 20: CRUZ, R. L. 1991b. A calculus for network delay. Part II: Network analysis. IEEE Trans. Inf. Theory 37, 1 (Jan.), 132-141.
• 21: DAN, A., SITARAM, D., AND SHAHABUDDIN, P. 1994. Scheduling policies for an on-demand video server with batching. IBM Res. Rep. RC 19381. IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y.
• 22: G. Veciana , C. Courcoubetis , J. Walrand, Decoupling Bandwidths for Networks: A Decomposition Approach to, University of California at Berkeley, Berkeley, CA, 1993
• 23: DUFFIELD, N. G. 1994. Exponential bounds for queues with Markovian arrivals. Que. Syst. 17, 413-430.
• 24: DUFFIELD, N. G., AND O'CONNELL, N. 1995. Large deviations and overflow probabilities for the general single-server queue. Math. Proc. Phil. Soc. 118, 363-374.
• 25: ELLIS, R.S. 1984. Large deviations for a general class of random vectors. Ann. Prob. 12, 1, 1-12.
• 26: ELLIS, R. S. 1985. Entropy, Large Deviations, and Statistical Mechanics. Springer-Verlag, New York.
• 27: ELWALID, A. I., HEYMAN, D., LAKSJMAN, T. V., MITRA, D., AND WEISS, A. 1995. Fundamental bounds and approximations for ATM multiplexers with applications to video teleconferencing. IEEE J. Select. Areas Cornrnun. 13, 6, 1004-1016.
• 28: Anwar I. Elwalid , Debasis Mitra, Effective bandwidth of general Markovian traffic sources and admission control of high speed networks, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.329-343, June 1993 [doi>10.1109/90.234855]
• 29: FERRARI, D., AND VERMA, D. 1990. A scheme for real-time channel establishment in wide-area networks. IEEE J. Select. Areas Commun. 8, 1 (Apr.), 368-379.
• 30: Wolfgang Fischer , Kathleen Meier-Hellstern, The Markov-modulated Poisson process (MMPP) cookbook, Performance Evaluation, v.18 n.2, p.149-171, Sept. 1993 [doi>10.1016/0166-5316(93)90035-S]
• 31: FREDERICK, R. 1993. nv. Manual Pages. Xerox Palo Alto Research Center, Palo Alto, Calif.
• 32: Erol Gelenbe , Xiaowen Mang , Raif Önvural, Diffusion based statistical call admission control in ATM, Performance Evaluation, 27-28, p.411-436, Oct. 1996 [doi>10.1016/0166-5316(96)00033-8]
• 33: R. J. Gibbens , P. J. Hunt, Effective bandwidths for the multi-type UAS channel, Queueing Systems: Theory and Applications, v.9 n.1-2, p.17-28, Oct. 1991 [doi>10.1007/BF01158790]
• 34: GLYNN, P. W., AND WHITT, W. 1994. Logarithmic asymptotics for steady-state tail probabilities in a single-server queue. In Studies in Applied Probability, J. Galambos and J. Gani, eds. J. Appl. Prob., Special vol. 31/t, 131-159.
• 35: GRAHAM, A. 1981. Kronecker Products and Matrix Calculus with Applications. Ellis Horwood, Chischester, England.
• 36: GUt#RIN, R., AHMADI, n., AND NAGHSHINEH, M. 1991. Equivalent capacity and its application to bandwidth allocation in high-speed networks. IEEE J. Select. Areas Cornrnun. 9, 968-981.
• 37: HEFFES, n., AND LUCANTONI, D. M. 1986. A Markov modulated characterization of packetized voice and data traffic and related statistical multiplexer performance. IEEE J. Select. Areas Commun. 6, 856-868.
• 38: Roger A. Horn , Charles R. Johnson, Matrix analysis, Cambridge University Press, New York, NY, 1985
• 39: I Iscoe , P Ney , E Nummelin, Large deviations of uniformly recurrent Markov additive processes, Advances in Applied Mathematics, v.6 n.4, p.373-412, December 1985 [doi>10.1016/0196-8858(85)90017-X]
• 40: JACOBSON, V., AND MCCANNE, S. 1994. vat. Manual pages. Lawrence Berkeley Laboratory, Berkeley, Calif.
• 41: JACOBSON, V., AND MCCANNE, S. 1995. Using the LBL Network Whiteboard. Lawrence Berkeley Laboratory, Berkeley, Calif.
• 42: F. P. Kelly, Effective bandwidths at multi-class queues, Queueing Systems: Theory and Applications, v.9 n.1-2, p.5-16, Oct. 1991 [doi>10.1007/BF01158789]
• 43: George Kesidis , Jean Walrand , Cheng-Shang Chang, Effective bandwidths for multiclass Markov fluids and other ATM sources, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.424-428, Aug. 1993 [doi>10.1109/90.251894]
• 44: KINGMAN, J. F. C. 1964. A Martingale inequality in the theory of queues. Camb. Phil. Soc. 59, 359-361.
• 45: KINGMAN, J. F.C. 1970. Inequalities in the theory of queues. J. Roy. Star. Soc., Ser. B 32, 102-110.
• 46: Jim Kurose, On computing per-session performance bounds in high-speed multi-hop computer networks, Proceedings of the 1992 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.128-139, June 01-05, 1992, Newport, Rhode Island, United States
• 47: LIU, Z., NAIN, P., AND TOWSLEY, D. 1997. On a generalization of Kingman's bounds. Preprint INRIA, BP93 06 902 Sophia Antipolis, France (available via http://www.inria.fr/mistral/personnel/ P hili ppe.N ain/r ese ar ch.h tml).
• 48: LIU, Z., NAIN, P., AND TOWSLEY, D. 1996. Bounds on finite horizon QoS metrics with application to call admission. In Proceedings of INFOCOM'96 (San Francisco, Calif., Mar.) IEEE Computer Society Press, Los Alamitos, Calif., pp. 1338-1345.
• 49: LIU, Z., NAIN, P., AND TOWSLEY, D. 1995. Bounds on the tail distribution of Markov-modulated stochastic Max-Plus systems. In Proceedings of the 34th IEEE Conference on Decision and Control (New Orleans, La., Dec.). IEEE Control Systems Society, Piscataway, N.J., pp. 1395-1399.
• 50: LOYNES, R.M. 1962. The stability of a queue with non-independent inter-arrival and service times. Proc. Cambridge Philos. Soc. 58, 497-520.
• 51: LUCANTONI, D. M., CHOUDHURY, G. L., AND WHITT, W. 1994. The transient BMAP/G/1 queue. Stoch. Models 10, 145-182.
• 52: Ramesh Nagarajan , James F. Kurose , Donald F. Towsley, Local Allocation of End-to-End Quality-of-Service in High-Speed Networks, Proceedings of the IFIP TC6 Task Group/WG6.4 International Workshop on Performance of Communication Systems: Modelling and Performance Evaluation of ATM Technology, p.99-118, January 25-27, 1993
• 53: NEUTS, M. F. 1981. Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. Johns Hopkins University Press, Baltimore, Md.
• 54: PARULEKAR, M., AND MAKOWSKI, A.M. 1996. Buffer overflow probabilities for a multiplexer with self-similar traffic. In Proceedings of INFOCOM'96 (San Francisco, Calif., Mar.). IEEE Computer Society Press, Los Alamitos, Calif., pp. 1452-1459.
• 55: Larry Press, The Internet and interactive television, Communications of the ACM, v.36 n.12, p.19-23, Dec. 1993 [doi>10.1145/163298.163352]
• 56: G J K Regterschot , J H A de Smit, The queue M/G/1 with Markov modulated arrivals and services, Mathematics of Operations Research, v.11 n.3, p.465-483, Aug. 1986 [doi>10.1287/moor.11.3.465]
• 57: Ross, S.M. 1974. Bounds on the delay distribution in GI/G/1 queues. J. Appl. Prob. 11,417-421.
• 58: SCHULZRINNE, H. 1992. Voice communication across the internet: A network voice terminal. Tech. Rep. Dept. of Computer Science, Univ. Massachusetts, Amherst Mass., July. (Available via anonymous ftp to gaia. cs. umass, edu in pub/nevot/nevot .ps. Z).
• 59: 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, 6, 1017-1027.
• 60: STOYAN, D. 1983. Comparison Methods for Queues and Other Stochastic Models. Wiley, Berlin, Germany.
• 61: WHITT, W. 1993. Tail probabilities with statistical multiplexing and effective bandwidths in multiclass queues. Telecommun. Syst. 2, 71-107.
• 62: Opher Yaron , Moshe Sidi, Performance and stability of communication networks via robust exponential bounds, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.372-385, June 1993 [doi>10.1109/90.234858]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.m MISCELLANEOUS
      Subjects: Queueing theory**

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Performance, Theory

Keywords:
Markov additive process, Markov chain, call admission control, effective bandwidth, ergodicity, exponential bound, large deviation principle, matrix analysis, queues, tail distribution