An algorithm for computing the mean response time of a single server queue with generalized on/off traffic arrivals

ABSTRACT

In this paper, an exact solution for the response time distribution of a single server, infinite capacity, discrete-time queue is presented. This queue is fed by a flexible discrete-time arrival process, which follows an on/off evolution. A workload variable is associated with each arrival instant, which may correspond to the service demand generated by a single arrival, or represent the number of simultaneous arrivals (bulk arrivals). Accordingly, the analysis focuses on two types of queues: (On/Off)/G/1 and (Batch-On/Off)/D/1. For both cases, a decomposition approach is carried out, which divides the problem into two contributions: the response time experienced by single bursts in isolation, and the increase on the response time caused by the unfinished work that propagates from burst to burst. Particularly, the solution for the unfinished work is derived from a Wiener-Hopf factorization of random walks, which was already used in the analysis of discrete GI/G/1 queues. Compared to other related works, the procedure proposed in this paper is exact, valid for any traffic intensity and has no constraints on the distributions of the input random variables characterizing the process: duration of on and off periods, and workload. From the general solution, an efficient and robust iterative algorithm for computing the expected response time of both queues is developed, which can provide results at any desired precision. This algorithm is numerically evaluated for different types of input distributions and proved against simulation.

REFERENCES

• 1: Alfa, A. S., Neuts, M. F., Modelling vehicular traffic using the Discrete Time Markovian Arrival Process, Transportation Science, Vol. 29, No. 2, May 1995.
• 2: Alfa, A., Breuer, L., An EM algorithm for Platoon Arrival Processes in discrete time, Research Report No. 02-07, Dept. of Mathematics and Computer Science, University of Trier, Germany.
• 3: Blondia, C., A discrete-time batch Markovian arrival process as B-ISDN traffic model, Belgian Journal of Operations Research, Statistics and Computer Science, vol. 32 (3,4).
• 4: Boettcher, A., Silbermann, B., On Large Truncated Toeplitz Matrices, Springer 1999.
• 5: Bruneel, H., Queueing behavior of statistical multiplexers with correlated inputs, IEEE Trans. on Communications, 36, 1339--1341, 1988.
• 6: Herwig Bruneel , Byung G. Kim, Discrete-Time Models for Communication Systems Including ATM, Kluwer Academic Publishers, Norwell, MA, 1992
• 7: Ralph L. Disney , Peter C. Kiessler, Traffic processes in queueing networks: a Markov renewal approach, Johns Hopkins University Press, Baltimore, MD, 1987
• 8: Frost, V. S., Melamed, B., Traffic modeling for telecommunications networks, IEEE Communications Magazine, March 1994.
• 9: Galmés, S., Puigjaner, R., Analysis of the (Batch-On/Off)/D/1 queue, Proc. of the Seventeenth International Teletraffic Congress, Salvador da Bahia, Brazil, 2001.
• 10: W. K. Grassman , J. L. Jain, Numerical solutions of the waiting time distribution and idle time distribution of the arithmetic GI/G/1 queue, Operations Research, v.37 n.1, p.141-150, Jan.-Feb. 1989 [doi>10.1287/opre.37.1.141]
• 11: Andreas Griewank, Evaluating derivatives: principles and techniques of algorithmic differentiation, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 12: Heffes, H., Lucantoni, D. M., A Markov modulated characterization of packetized voice and data traffic and related statistical multiplexer performance, IEEE JSAC, SAC-4, No. 6, 1986.
• 13: Johnson, Norman L., Kotz, S., Kemp Adrienne W., Univariate Discrete Distributions, Wiley 1993, Second Edition.
• 14: Kuehn, P., Reminder on queueing theory for ATM networks, First ATM Traffic Expert Symposium, Basel, Switzerland, 1995.
• 15: Li, S., Sheng, H., Discrete Queueing analysis of multi-media traffic with diversity of correlation and burstiness properties, Proc. of the IEEE INFOCOM'91.
• 16: Neuts, M. F., Chakravarthy, S., A single server queue with platooned arrivals and phase-type services, European Journal of Operational Research, 8: 379--389, 1981.
• 17: Sohraby, K., On the theory of general on-off sources with applications in high-speed networks, Proc. of the IEEE INFOCOM'93.
• 18: Sriram, K., Whitt, W., Characterizing superposition arrival processes in packet multiplexers for voice and data, IEEE Journal on Selected Areas in Communications, Vol. SAC-4, No. 6, September 1986.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: High-speed (e.g., FDDI, fiber channel, ATM); Access schemes
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes; Markov processes; Queueing theory

General Terms:
Algorithms, Performance, Theory

Keywords:
Markov chain, arrival process, queuing model, response time, steady-state