Hostname: page-component-848d4c4894-xm8r8 Total loading time: 0 Render date: 2024-06-25T06:54:17.506Z Has data issue: false hasContentIssue false
  • English
  • Français

Exponential upper bounds via martingales for multiplexers with Markovian arrivals

Part of: Special processes Computer system organization Operations research and management science

Published online by Cambridge University Press:  14 July 2016

E. Buffet  and
N. G. Duffield
E. Buffet*
Affiliation:
Dublin City University
N. G. Duffield*
Affiliation:
Dublin City University
*
∗Postal address: School of Mathematical Sciences, Dublin City University, Dublin 9, Ireland.
∗Postal address: School of Mathematical Sciences, Dublin City University, Dublin 9, Ireland.
Get access Rights & Permissions [Opens in a new window]

Abstract

We obtain explicit upper bounds in closed form for the queue length in a slotted time FCFS queue in which the service requirement is a sum of independent Markov processes on the state space {0, 1}, with integral service rate. The bound is of the form [queue length for any where c < 1 and y > 1 are given explicitly in terms of the parameters of the model. The model can be viewed as an approximation for the burst-level component of the queue in an ATM multiplexer. We obtain heavy traffic bounds for the mean queue length and show that for typical parameters this far exceeds the mean queue length for independent arrivals at the same load. We compare our results on the mean queue length with an analytic expression for the case of unit service rate, and compare our results on the full distribution with computer simulations.

Keywords

QUEUEING THEORYATM MULTIPLEXERSHEAVY TRAFFIC LIMIT68M20

MSC classification

Primary: 60K25: Queueing theory
Secondary: 68M20: Performance evaluation; queueing; scheduling 90B22: Queues and service
Type
Research Article
Information
Journal of Applied Probability , Volume 31 , Issue 4 , December 1994 , pp. 1049 - 1060
Copyright
Copyright © Applied Probability Trust 1994 

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.)

Footnotes

The authors are also affiliated to the School of Theoretical Physics, Dublin Institute for Advanced Studies, 10 Burlington Road, Dublin 4, Ireland.

References

[1] Anick, D., Mitra, D. and Sondhi, M. M. (1982) Stochastic theory of a data-handling system with multiple sources. Bell. Syst. Tech. J. 61, 1872–1894.CrossRefGoogle Scholar
[2] Baiocchi, A., Belafri Melazzi, N., Listanti, M., Roveri, A. and Winkler, R. (1991) Loss performance analysis of an ATM multiplexer loaded with high speed on-off sources. IEEE J. Select. Areas Commun. 9, 388–393.CrossRefGoogle Scholar
[3] Corry, D. M., Duffield, N. G. and Curran, T. (1992) Sub-burst mode queueing in an ATM voice multiplexer. Proc. 9th IEE Teletraffic Symposium, Guildford. Google Scholar
[4] Gibbens, R. J. and Hunt, P. J. (1991) Effective bandwidths for the multi-type UAS channel. Queueing Systems 9, 17–28.Google Scholar
[5] Grandell, J. (1991) Aspects of Risk Theory. Springer-Verlag, New York.Google Scholar
[6] Heffes, H. and Lucantoni, D. M. (1991) A Markov modulated characterization of packetized voice and data traffic and related statistical multiplexer performance. IEEE J. Select. Areas Commun. 4, 856–868.Google Scholar
[7] Hui, J. Y. (1988) Resource allocation for broadband networks. IEEE J. Select. Areas Commun. 6, 1598–1608.Google Scholar
[8] Kingman, J. F. C. (1964) A martingale inequality in the theory of queues. Proc. Camb. Phil. Soc. 59, 359–361.Google Scholar
[9] Kingman, J. F. C. (1970) Inequalities in the theory of queues. J . R. Statist. Soc. 32, 102–110.Google Scholar
[10] Kosten, L. (1988) Stochastic theory of data handling systems with groups of multiple sources. Proc. 2nd Internat. Symp. on the Performance of Computer Communication Systems, ed. Rudin, H. and Bux, W., North-Holland, Amsterdam.Google Scholar
[11] Loynes, R. M. (1962) The stability of a queue with non-independent inter-arrival and service times. Proc. Camb. Phil. Soc. 58, 497–520.Google Scholar
[12] Neuts, M. F. (1990) On Viterbi's formula for the mean delay in a queue of data packets. Commun. Statist .-Stoch. Models 6, 87–98.CrossRefGoogle Scholar
[13] Neveu, J. (1975) Discrete-Parameter Martingales. North-Holland, Amsterdam.Google Scholar
[14] Norros, I., Roberts, J. W., Simonian, A. and Virtamo, J. T. (1991) The superposition of variable bit rate sources in an ATM multiplexer. IEEE J. Select. Areas Commun. 9, 378–387.Google Scholar
[15] Sriram, K. and Whitt, W. (1986) Characterizing superposition arrival processes in packet multiplexers for voice data. IEEE J. Select. Areas Commun. 4, 833–846.Google Scholar
[16] Viterbi, A. M. (1986) Approximation analysis of time synchronous packet networks. IEEE J. Select. Areas Commun. 4, 879–890.Google Scholar
[17] Wichmann, B. A. and Hill, I. D. (1982) An efficient and portable pseudo-random number generator. Appl. Statist. 31, 188–190.CrossRefGoogle Scholar