Hostname: page-component-848d4c4894-75dct Total loading time: 0 Render date: 2024-05-17T07:24:43.924Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic results for multiplexing subexponential on-off processes

Part of: Special processes

Published online by Cambridge University Press:  01 July 2016

Predrag R. Jelenković  and
Aurel A. Lazar
Predrag R. Jelenković*
Affiliation:
Columbia University
Aurel A. Lazar*
Affiliation:
Columbia University
*
∗ Postal address: Department of Electrical Engineering and Center for Telecommunications Research, Columbia University, New York, NY 10027, USA.
∗ Postal address: Department of Electrical Engineering and Center for Telecommunications Research, Columbia University, New York, NY 10027, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

Consider an aggregate arrival process AN obtained by multiplexing N on-off processes with exponential off periods of rate λ and subexponential on periods τon. As N goes to infinity, with λN → Λ, AN approaches an M/G/∞ type process. Both for finite and infinite N, we obtain the asymptotic characterization of the arrival process activity period.

Using these results we investigate a fluid queue with the limiting M/G/∞ arrival process At∞ and capacity c. When on periods are regularly varying (with non-integer exponent), we derive a precise asymptotic behavior of the queue length random variable QtP observed at the beginning of the arrival process activity periods

where ρ = 𝔼At∞ < c; r (c ≤ r) is the rate at which the fluid is arriving during an on period. The asymptotic (time average) queue distribution lower bound is obtained under more general assumptions regarding on periods than regular variation.

In addition, we analyse a queueing system in which one on-off process, whose on period belongs to a subclass of subexponential distributions, is multiplexed with independent exponential processes with aggregate expected rate 𝔼et. This system is shown to be asymptotically equivalent to the same queueing system with the exponential arrival processes being replaced by their total mean value 𝔼et.

Keywords

Non-Cramér type conditionssubexponential distributionslong-tailed distributionslong-range dependencynetwork multiplexerfluid flow queueM/G/∞ queue

MSC classification

Secondary: 60K25: Queueing theory
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 31 , Issue 2 , June 1999 , pp. 394 - 421
Copyright
Copyright © Applied Probability Trust 1999 

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

Abate, J., Choudhury, G. L. and Whitt, W. (1994). Waiting-time tail probabilities in queues with long-tail service-time distributions. Queueing Systems 16, 311–338.CrossRefGoogle Scholar
Anantharam, V. (1995). On the sojourn time of sessions at an ATM buffer with long-range dependent input traffic. Proc. 34th IEEE CDC. IEEE Control Systems Society, New York.Google Scholar
Anick, D., Mitra, D. and Sondhi, M. M. (1982). Stochastic theory of a data handling system with multiple sources. Bell Syst. Techn. J. 61, 1871–1894.CrossRefGoogle Scholar
Asmussen, S. (1987). Applied Probability and Queues. Wiley, New York Google Scholar
Asmussen, S. (1996). Rare events in the presence of heavy tails. In Stochastic Networks: Stability and Rare Events, eds. Glasserman, P., Sigman, K. and Yao, D. D. (Lecture Notes in Statist. 117). Springer, New York.Google Scholar
Asmussen, S., Henriksen, L. F. and Klüppelberg, C. (1994). Large claims approximations for risk processes in a Markovian environment. Stoch. Proc. Appl. 54, 29–43.Google Scholar
Asmussen, S., Schmidli, H. and Schmidt, V. (1997). Tail probabilities for non-standard risk and queueing processes with subexponential jumps. Adv. Appl. Prob 31, 422–447.Google Scholar
Athreya, K. B. and Ney, P. E. (1972). Branching Processes. Springer, New York.Google Scholar
Baccelli, F. and Bremaud, P. (1994). Elements of Queueing Theory: Palm-Martingale Calculus and Stochastic Recurrence. Springer, New York.Google Scholar
Bingham, N. H. and Doney, R. A. (1974). Asymptotic properties of super-critical branching processes I: the Galton–Watson process. Adv. Appl. Prob. 6, 711–731.Google Scholar
Bingham, N. H., Goldie, C. M. and Teugels, J. L. (1987). Regular Variation. CUP, Cambridge.Google Scholar
Boxma, O. J. (1996). Fluid queues and regular variation. Perf. Eval. 27&28, 699–712.Google Scholar
Boxma, O. J. (1997). Regular variation in a multi-source fluid queue. In Teletraffic contributions for the Information Age, Vol. 2 (Proc. ITC 15), ed. Ramaswami, V., Wirth, P. E.. Elsevier, New York, pp. 391–402.Google Scholar
Chistyakov, V. P. (1964). A theorem on sums of independent positive random variables and its application to branching random processes. Theory Prob. Appl. 9, 640–648.Google Scholar
Choudhury, G. L. and Whitt, W. (1997). Long-tail buffer-content distributions in broadband networks. Perf. Eval. 30, 177–190.Google Scholar
Cinlar, E. (1972). Superposition of point processes. In Stochastic Point Processes: Statistical Analysis, Theory and Application, ed. Lewis, P. A. W.. Wiley, New York, pp. 594–606.Google Scholar
Cinlar, E. (1975). Introduction to Stochastic Processes. Prentice-Hall, Engleton Cliffs, NJ.Google Scholar
Cline, D. B. H. (1986). Convolution tails, product tails and domains of attraction. Prob. Theory Rel. Fields 72, 529–557.CrossRefGoogle Scholar
Cline, D. B. H. (1994). Intermediate regular and π variation. Proc. London Math. Soc. 68, 594–616.Google Scholar
Cohen, J. W. (1973). Some results on regular variation for distributions in queueing and fluctuation theory. J. Appl. Prob. 10, 343–353.CrossRefGoogle Scholar
Cohen, J. W. (1974). Superimposed renewal processes and storage with gradual input. Stoch. Proc. Appl. 2, 31–58.CrossRefGoogle Scholar
Cohen, J. W. (1994). On the effective bandwidth in buffer design for the multi-server channels. Technical report, CWI Report BS-R9406, NL-1090 GB, Amsterdam, The Netherlends.Google Scholar
Cox, D. R. and Smith, W. L. (1954). On the superposition of renewal processes. Biometrika 41, 91–99.CrossRefGoogle Scholar
Duffield, N. G. and O'Connell, N. (1995). Large deviations and overflow probabilities for the general single-server queue with applications. Math. Proc. Camb. Phil. Soc. 118, 363–374.Google Scholar
Elwalid, A., Heyman, D., Lakshman, T. V., Mitra, D. and Weiss, A. (1995). Fundamental bounds and approximations for ATM multiplexers with applications to video teleconferencing. IEEE J. Sel. Areas Commun. 13, 1004–1016.Google Scholar
Embrechts, P., Goldie, C. M. and Veraverbeke, N. (1979). Subexponentiality and infinite divisibility. Z. Wahrscheinlichkeitsth. 49, 335–347.CrossRefGoogle Scholar
Glynn, P. V. and Whitt, W. (1994). Logarithmic asymptotics for steady-state tail probabilities in a single-server queue. In Studies in Applied Probability, eds. Galambos, J. and Gani, J. (J. Appl. Prob. 31A). Applied Probability Trust, Sheffield, England, pp. 131–156.Google Scholar
Heath, D., Resnick, S. and Samorodnitsky, G. (1998). Heavy tails and long range dependence in on/off processes and associated fluid models. Math. Operat. Res. 23, 145–165.Google Scholar
Heyman, D. P. and Lakshman, T. V. (1996). Source models for VBR broadcast-video traffic. IEEE/ACM Trans. Networking 4, 40–48.Google Scholar
Jelenković, P. R. and Lazar, A. A. (1996). Multiple time scale and subexponential asymptotic behavior of a network multiplexer. In Stochastic Networks: Stability and Rare Events, eds. Glasserman, P., Sigman, K. and Yao, D. D.. (Lecture Notes in Statist. 117). Springer, New York, pp. 215–235.Google Scholar
Jelenković, P. R. and Lazar, A. A. (1996). Multiplexing on-off sources with subexponential on periods. CTR Technical Report CU/CTR/TR 457-96-23, Columbia University, New York. (www: http://www.ctr.columbia.edu/comet/publications.)Google Scholar
Jelenković, P. R. and Lazar, A. A. (1997). Multiplexing on-off sources with subexponential on periods: Part I. In Proc. INFOCOM'97. IEEE Computer Society, New York.Google Scholar
Jelenković, P. R. and Lazar, A. A. (1997). Multiplexing on-off sources with subexponential on periods: Part II. In Teletraffic contributions for the Information Age, Vol. 2 (Proc. ITC 15), ed. Ramaswami, V., Wirth, P. E.. Elsevier, New York, pp. 965–974.Google Scholar
Jelenković, P. R. and Lazar, A. A. (1998). Subexponential asymptotics of a Markov-modulated random walk with queueing applications. J. Appl. Prob. 35, 325–347.Google Scholar
Jelenković, P. R., Lazar, A. A. and Semret, N. (1996). Multiple time scales and subexponentiality in MPEG video streams. In Broadband communications: global infrastructure for the information age (Proc. Internat. IFIP-IEEE Conference on Broadband Communications), ed. Mason, L. and Casaca, A.. Chapman and Hall, London.Google Scholar
Jelenković, P. R., Lazar, A. A. and Semret, N. (1997). The effect of multiple time scales and subexponentiality of MPEG video streams on queueing behavior. IEEE J. Sel. Areas Commun. 15, 1052–1071.Google Scholar
Karamata, J. (1930). Sur un mode de croissance régulière des fonctions. Mathematica (Cluj) 4, 38–53.Google Scholar
Kella, O. and Whitt, W. (1992). A storage model with a two-state random environment. Operat. Res. 40, 257–262.Google Scholar
Klüppelberg, C., (1988). Subexponential distributions and integrated tails. J. Appl. Prob. 25, 132–141.CrossRefGoogle Scholar
Klüppelberg, C., (1989). Subexponential distributions and characterizations of related classes. Prob. Theory Rel. Fields 82, 259–269.Google Scholar
Leland, W. E., Taqqu, M. S., Willinger, W. and Wilson, D. V. (1993). On the self-similar nature of Ethernet traffic. In SIGCOMM'93, Assoc. for Computing Machinery, New York, pp. 183–193.Google Scholar
Likhanov, N., Tsybakov, B. and Georganas, N. D. (1995). Analysis of an ATM buffer with self-similar (‘fractal’) input traffic. In INFOCOM'95, IEEE Computer Society, New York, pp. 985–991.Google Scholar
Loynes, R. M. (1968). The stability of a queue with non-independent inter-arrival and service times. Proc. Camb. Phil. Soc. 58, 497–520.Google Scholar
Norros, I. (1994). A storage model with self-similar input. Queueing Systems 16, 387–396.Google Scholar
Pakes, A. G. (1975). On the tails of waiting-time distribution. J. Appl. Prob. 12, 555–564.Google Scholar
Parulekar, M. and Makowski, A. M. (1996). Tail probabilitites for a multiplexer with self-similar traffic. In INFOCOM'96, IEEE Computer Society, New York.Google Scholar
Parulekar, M. and Makowski, A. M. (1997). Tail probabilitites for M/G/∞ input processes (I): preliminary asymptotics. Queueing Systems 27, 271–296.Google Scholar
Resnick, S. and Samorodnitsky, G. (1997). Performance decay in a single server queueing model with long range dependence. Operat. Res. 45, 235–243.Google Scholar
Rolski, T., Schlegel, S. and Schmidt, V. (1999). Asymptotics of palm-stationary buffer content distribution in fluid flow queues. Adv. Appl. Prob. 31, 235–253.Google Scholar
Rubinovitch, M. (1973). The output of a buffered data communication system. Stoch. Proc. Appl. 1, 375–380.CrossRefGoogle Scholar
Ryu, B. K. and Lowen, S. B. (1996). Point process approaches to the modeling and analysis of self-similar traffic - part I: Model construction. In INFOCOM'96, IEEE Computer Society, New York.Google Scholar
Weiss, A. and Shwartz, A. (1995). Large Deviations for Performance Analysis: Queues, Communications, and Computing. Chapman & Hall, New York.Google Scholar
Willekens, E. and Teugels, J. L. (1992). Asymptotic expansion for waiting time probabilities in an M/G/1 queue with long-tailed service time. Queueing Systems 10, 295–312.Google Scholar