A survey on retrial queues.

*(English)*Zbl 0658.60124A systematized survey of the analytic results for retrival queues is given by discussing a generalized model A/B/s/m/O/H. Here, A and B describe the interarrival and service time distribution, respectively, s denotes the number of waiting positions in the queue, O is the capacity of an orbit for the retrying customers and \(H=\{H_ k\), \(k\geq 0\}\) denotes the loss model by which a customer joins to the orbit with probability \(1-H_ k\) after the k th unsuccessful retrial.

The survey concentrates an single-server models of type M/G/i/m/O/H. For \(m=1\), \(O=\infty\), \(H=NL=\{H_ k=1\), \(k\geq 0\}\), the number N of customers in the system, the waiting time w, the number \(\eta\) of retrials, the length L of busy periods, the number M of customers served in such periods, the server idle time i and the distribution \(\pi\) of time intervals between consecutive departures are examined. For M/M/1/m/O/H with finite m, O and \(H=GL=\{H_ k=\alpha \leq 1\), \(k\geq 0\}\) the exact values of state probabilities p(i,j), i,j\(\geq 0\), are derived, where i and j are the numbers of customers in the waiting room and in the orbit respectively. With \(O=\infty\) and \(H=NL\) an iterative procedure to approximate p(i,j) is reported.

In the case of batch arrivals the M/G/1 models are discussed. For the multi-server retrial queues only some major models, techniques dealing with the problems arising, and some main results are presented. Different full-availability and non-full-availability systems are reported. It is shown that the decomposition property, which is a common feature of queues with server vacations, is also true in retrial queues of the model M/G/s/m.

The survey concentrates an single-server models of type M/G/i/m/O/H. For \(m=1\), \(O=\infty\), \(H=NL=\{H_ k=1\), \(k\geq 0\}\), the number N of customers in the system, the waiting time w, the number \(\eta\) of retrials, the length L of busy periods, the number M of customers served in such periods, the server idle time i and the distribution \(\pi\) of time intervals between consecutive departures are examined. For M/M/1/m/O/H with finite m, O and \(H=GL=\{H_ k=\alpha \leq 1\), \(k\geq 0\}\) the exact values of state probabilities p(i,j), i,j\(\geq 0\), are derived, where i and j are the numbers of customers in the waiting room and in the orbit respectively. With \(O=\infty\) and \(H=NL\) an iterative procedure to approximate p(i,j) is reported.

In the case of batch arrivals the M/G/1 models are discussed. For the multi-server retrial queues only some major models, techniques dealing with the problems arising, and some main results are presented. Different full-availability and non-full-availability systems are reported. It is shown that the decomposition property, which is a common feature of queues with server vacations, is also true in retrial queues of the model M/G/s/m.

Reviewer: J.Tanko

##### MSC:

60K25 | Queueing theory (aspects of probability theory) |

90B22 | Queues and service in operations research |

##### Keywords:

imbedded Markov chain; stochastic decomposition; retrival queues; batch arrivals; multi-server retrial queues; server vacations
PDF
BibTeX
XML
Cite

\textit{T. Yang} and \textit{J. G. C. Templeton}, Queueing Syst. 2, No. 3, 201--233 (1987; Zbl 0658.60124)

Full Text:
DOI

##### References:

[1] | A.M. Aleksandrov, A queueing system with repeated orders, Engineering Cybernetics Rev. 12, 3(1974)1. |

[2] | W. Bux, Local-area subnetworks: A performance comparison, IEEE Trans. Comm. 29(1981)1465. · doi:10.1109/TCOM.1981.1094893 |

[3] | M.L. Chaudhry and J.G.C. Templeton,A First Course in Bulk Queues (Wiley, New York, 1983). · Zbl 0559.60073 |

[4] | Q.H. Choo and B. Conolly, New results in the theory of repeated orders queueing systems, J. Appl. Prob. 16(1979)631. · Zbl 0418.60088 · doi:10.2307/3213090 |

[5] | J.W. Cohen, Basic problems of telephone traffic theory and the influence of repeated calls, Philips Telecom. Rev. 18, 2(1957)49. |

[6] | N. Deul, Stationarity conditions for multi-server queueing systems with repeated calls, Elektr. Informationsverarbeit. Kybernet. 16(1980)607. · Zbl 0476.90027 |

[7] | B.T. Doshi, Queueing systems with vacations ?A survey, Queueing Systems 1(1986)29. · Zbl 0655.60089 · doi:10.1007/BF01149327 |

[8] | A. Elldin, Approach to the theoretical description of repeated call attempts, Ericsson Technics 23, 3(1967)345. |

[9] | G.I. Falin, Aggregate arrival of customers in one-line system with repeated calls, Ukrainian Math. J. 28(1976)437. · Zbl 0361.60086 · doi:10.1007/BF01101670 |

[10] | G.I. Falin, On the waiting time in a single-channel queueing system with secondary calls, Vestnik Moscow Univ. Ser. 15. Comput. Math. Cybernet. 4(1977)83. |

[11] | G.I. Falin, The output flow of a single-line queueing system when there are secondary orders, Engineering Cybernetics Rev. 16, 5(1978)64. · Zbl 0446.90034 |

[12] | G.I. Falin, A single-line system with secondary orders, Engineering Cybernetics Rev. 17, 2(1979)76. |

[13] | G.I. Falin, Not completely accessible schemes with allowance for repeated calls, Engineering Cybernetics Rev. 18, 5(1980)56. · Zbl 0497.90022 |

[14] | G.I. Falin, Communication systems with repeated calls, Prob. Inf. Trans. 16, 2(1980)83. · Zbl 0458.90024 |

[15] | G.I. Falin, Repeated calls in structurally complex systems, Engineering Cybernetics Rev. 18, 6(1980)46. · Zbl 0478.90020 |

[16] | G.I. Falin, Investigation of weakly loaded switching systems with repeated calls, Engineering Cybernetics Rev. 19, 3(1981)69. · Zbl 0512.90053 |

[17] | G.I. Falin, The influence of inhomogeneity of the composition of subscribers on the functioning of telephone systems with repeated calls, Engineering Cybernetics Rev. 21, 6(1983)21. · Zbl 0577.90030 |

[18] | G.I. Falin, On sufficient conditions for ergodicity of multichannel queueing systems with repeated calls, Adv. Appl. Prob. 16(1984)447. · Zbl 0535.60087 · doi:10.2307/1427079 |

[19] | G.I. Falin, Continuous approximation for a single-server system with an arbitrary service time under repeated calls, Engineering Cybernetics Rev. 22, 2(1984)66. · Zbl 0644.60099 |

[20] | G.I. Falin, On the waiting-time process in a single-line queue with repeated calls, J. Appl. Prob. 23(1986)185. · Zbl 0589.60077 · doi:10.2307/3214127 |

[21] | A.A. Fredericks and G.A. Reisner, Approximations to stochastic service systems with an application to a retrial model, Bell System Tech. J. 58, 3(1979)557. · Zbl 0402.90043 |

[22] | G. Gosztony, Comparison of calculated and simulated results for trunk group with repeated attempts,Proc 8th Int. Teletraffic Congress, I, Melbourne (1976)321/1-11. |

[23] | G. Gosztony, A generalrH? formula of call repetition: Validity and constraints,Proc. 11th Int. Teletraffic Congress (1985)1010-1016. |

[24] | B.S. Greenberg and R.W. Wolff, An upper bound on the performance of queues with returning customers, J. Appl. Prob. 24(1987)466. · Zbl 0626.60092 · doi:10.2307/3214270 |

[25] | O. Hashida and K. Kawashima, Buffer behavior with repeated calls, Electronics and Communication in Japan 62-B, 3(1979)27. |

[26] | H. Inamori, M. Sawai, T. Endo and K. Tanabe, An automatically repeated call model in NTT public facsimile,Proc. 11th Int. Teletraffic Congress (1985) 1017-1023. |

[27] | G.L. Jonin and Y.Y. Sedol, Investigation of telephone systems in the case of repeated calls, Latvian Mathematical Yearbook 7(1970)71. |

[28] | G.L. Jonin and N. Brezgunova, One-line system with repested calls in the case of ?-distributed occupation time, Latvian Mathematical Yearbook 11(1972)65. |

[29] | G.L. Jonin, The systems with repeated calls: models, measurements, and results,Proc. Third Int Seminar on Teletraffic Theory, Moscow (1984)197-208. |

[30] | J. Keilson, J. Cozzolino and H. Young, A service system with unfilled requests repeated, Oper. Res. 16(1968)1126. · Zbl 0165.52703 · doi:10.1287/opre.16.6.1126 |

[31] | F.P. Kelly, On auto-repeat facilities and telephone network performance, J.R. Statistical Society B48, 1(1986)123. · Zbl 0595.60088 |

[32] | A. Kharkevich et al., Approximate analysis of systems with repeated calls and multiphase service,Proc. 11th Int. Teletraffic Congress (1985)1029-1035. |

[33] | L. Kleinrock,Queueing Systems, Vol. I:Theory (Wiley, New York, 1975) ch. 5. · Zbl 0334.60045 |

[34] | A.G. de Kok, Algorithmic methods for single-server systems with repeated attempts, Statistica Neerlandica 38, 1(1984)23. · Zbl 0547.60098 |

[35] | J.N. Kornishev, Waiting positions for overloaded trunks, Elektrosviaz 7(1974)32. |

[36] | L. Kosten, On the influence of repeated calls in the theory of probabilities of blocking, De Ingenieur 59(1947)1. |

[37] | A. Kuczura, Loss systems with mixed renewal and Poisson inputs, Oper. Res. 21(1973)787. · Zbl 0278.90030 · doi:10.1287/opre.21.3.787 |

[38] | V.G. Kulkarni, Letter to the Editor, J. Appl. Prob. 19(1982)901. · doi:10.2307/3213849 |

[39] | V.G. Kulkarni, On queueing systems with retrials, J. Appl. Prob. 20(1983)380. · Zbl 0518.90023 · doi:10.2307/3213810 |

[40] | V.G. Kulkarni, A game theoretic model for two types of customers competing for service, Oper. Res. Lett. 2(1983)119. · Zbl 0523.60095 · doi:10.1016/0167-6377(83)90019-6 |

[41] | V.G. Kulkarni, Expected waiting times in a multiclass batch arrival retrial queue, J. Appl. Prob. 23(1986)144. · Zbl 0589.60073 · doi:10.2307/3214123 |

[42] | P. Le Gall, General telecommunications traffic without delay,Proc. 8th Int. Teletraffic Congress (1976)125/1-8. |

[43] | P. Le Gall, The repeated callmodel and the queue with impatience,Proc. Third Int. Seminar on Teletraffic Theory, Moscow (1984)278-289. |

[44] | J. Lubacz and J. Roberts, A new approach to the single-server repeated attempt system with balking,Proc.Third Int. Seminar on Teletraffic Theory, Moscow (1984)290-293. |

[45] | G.E. Ridout, A study of retrial queueing systems with buffers, M.A.Sc. Thesis, Department of Industrial Engineering, University of Toronto (1984). |

[46] | J. Riordan,Stochastic Service Systems (Wiley, New York, 1962). · Zbl 0106.33601 |

[47] | J.T. Runnenburg, On the use of method of collective marks in queueing theory, in:Proc. Symp. on Congestion Theory, ed. W.L. Smith and W.E. Wilkinson (The University of North Carolina Press, Chapel Hill, North Carolina, 1964)399-418. |

[48] | E.I. Skolny and G.I. Ialkapov, Systems with repeated calls and waiting positions,Information Systems and Their Analysis (Nauka, Moscow, 1982)23-37. |

[49] | M. Stastny, On the substitution of the basic retrial model for a complex loss model with retrials,Proc. Third Int. Seminar on Teletraffic Theory, Moscow (1984)395-399. |

[50] | S.N. Stepanov, Integral equilibrium relations of non-full-access systems with repeated calls and their applications, Prob. Inf. Trans. 16, 4(1980)88. · Zbl 0527.94001 |

[51] | S.N. Stepanov, Probabilistic characteristics of an incompletely accessible multi-phase service system with several types of repeated calls, Problems of Control and Information Theory 10(1981)387. · Zbl 0477.60086 |

[52] | S.N. Stepanov, Asymptotic formulae and estimations for probabilistic characteristics of full-available group with absolutely persistent subscribers, Problems of Control and Information Theory 12, 5(1983)361. · Zbl 0532.60097 |

[53] | S.N. Stepanov, Properties of probabilistic characteristics of a communication network with repeated calls, Prob. Inf. Trans. 19, 1(1983)69. · Zbl 0522.90026 |

[54] | S.N. Stepanov, Analysis of full-available group with repeated calls and waiting positions, Elektrosviaz 6(1983)9. |

[55] | S.N. Stepanov,Numerical Methods of Calculation for Systems with Repeated Calls (Nauka, Moscow, 1983). · Zbl 0517.90032 |

[56] | S.N. Stepanov, Probabilistic characteristics of an incompletely accessible service system with repeated calls for arbitrary values of subscriber persistent function, Problems of Control and Information Theory 13, 2(1984)69. · Zbl 0583.90037 |

[57] | S.N. Stepanov, Numerical calculation accuracy of communication models with repeated calls, Problems of Control and Information Theory 13, 6(1984)371. |

[58] | S.N. Stepanov, Estimation of characteristics of multilinear systems with repeated calls,Proc. Third Int. Seminar on Teletraffic Theory, Moscow (1984) 400-409. |

[59] | S.N. Stepanov and I.I. Tsitovich, The model of a full-available group with repeated calls and waiting positions in the case of extreme load, Problems of Control and Information Theory 14, 1(1985)25. · Zbl 0572.60090 |

[60] | R.I. Wilkinson, Theories for toll traffic engineering in the U.S.A., Bell System Tech. J. 35(1956)421. |

[61] | D.W. Sabo, Closure methods for the single-server retrial queue, M.Sc. Thesis, Department of Mathematics, University of British Columbia, Vancouver(1987). |

[62] | T. Hanschke, Explicit formulas for the characteristics of the M/M/2/2 queue with repeated attempts, J. Appl. Prob. 24(1987)486. · Zbl 0624.60110 · doi:10.2307/3214272 |

[63] | S.N. Stepanov, Increasing the efficiency of numerical methods for models with repeat calls, Prob. Inf. Trans. 22, 4(1987)313. |

[64] | B.S. Greenberg, M/G/1 queueing systems with returning customers, Working Paper 87/88-3-1, Department of Management Science and Information Systems, University of Texas at Austin (1987). |

[65] | G.I. Falin, Multichannel queueing systems with repeated calls under high intensity of repetition, Elektr. Informationsverarbeit. Kybernet. 23, 1(1987)37. · Zbl 0616.90020 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.