A survey of retrial queues.

*(English)*Zbl 0709.60097This survey of results on retrial queues supplements the recent surveys by the author [Optimization 17, 649-667 (1986; Zbl 0618.90033)] and T. Yang and J. G. C. Templeton [Queueing Syst. 2, No.3, 201-233 (1987; Zbl 0658.60124); Correction in ibid. 4, 94 (1989)].

Author’s abstract: We concentrate on Markovian single and multi-channel systems. For the single channel case we consider the main model as well as models with batch arrivals, multiclasses, customer impatience, double connection, control devices, two-way communication and buffers. The stochastic processes arising from these models are considered in the stationary as well as the nonstationary regime. For multi-channel queues we survey numerical investigations of stationary distributions, limit theorems for high and low retrial intensities, and heavy and light traffic behaviour.

Author’s abstract: We concentrate on Markovian single and multi-channel systems. For the single channel case we consider the main model as well as models with batch arrivals, multiclasses, customer impatience, double connection, control devices, two-way communication and buffers. The stochastic processes arising from these models are considered in the stationary as well as the nonstationary regime. For multi-channel queues we survey numerical investigations of stationary distributions, limit theorems for high and low retrial intensities, and heavy and light traffic behaviour.

Reviewer: E.A.van Doorn

##### MSC:

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

90B22 | Queues and service in operations research |

##### Keywords:

retrial queues; stationary as well as the nonstationary regime; retrial intensities; heavy and light traffic behaviour
Full Text:
DOI

##### References:

[1] | A.M. Aleksandrov, A queueing system with repeated orders, Eng. Cybernet. Rev. 12 (3) (1974) 1-4. |

[2] | Q.H. Choo, The interaction of theory and simulation in queueing analysis, Ph.D. Thesis, Chelsea College, University of London (1978). |

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

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

[5] | B.W. Conolly, Letter to the Editor, J. Appl. Probab. 19 (1982) 904-905. |

[6] | B.N. Dimitrov and P.R. Ruskov, A discrete model of a single-line queue with repeated calls, in:Proc. 14th Spring Conf. of the Union of Bulgarian Mathematicians, Sunny Beach, April 6-9, 1985 (Sofia, Bulgarian Academy of Science, (1985) (in Russian). · Zbl 0585.90037 |

[7] | A.N. Dudin, On a queue with repeated calls and changing operating conditions, Paper #293-85, All-Union Institute for Scientific and Technical Information, Moscow (1985) (in Russian). |

[8] | G.I. Falin, Multi-phase servicing in a single-channel system for automation of experiments with repeated calls, in:Problems of Automation of Scientific Investigations in Radio Engineering and Electronics (USSR Academy of Science, Moscow, 1975). |

[9] | G.I. Falin, Aggregate arrival of customers in one-line system with repeated calls, Ukrainian Math. J. 28 (1976) 437-440. · 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-87. |

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

[12] | G.I. Falin, Model of coupled switching in the presence of recurrent calls, Eng. Cybernet. Rev. 17 (1) (1979) 53-59. · Zbl 0438.94039 |

[13] | G.I. Falin, A single-line system with secondary orders, Eng. Cybernet. Rev. 17 (2) (1979) 76-83. · Zbl 0437.60073 |

[14] | G.I. Falin, Effect of the recurrent calls on output flow of a single channel system of mass service, Eng. Cybernet. Rev. 17 (4) (1979) 99-103. · Zbl 0437.60074 |

[15] | G.I. Falin, AnM/M/1 queue with repeated calls in the presence of persistence function, Paper #1606-80, All-Union Institute for Scientific and Technical Information, Moscow (1980) (in Russian). |

[16] | G.I. Falin, AnM/G/1 system with repeated calls in heavy traffic, Vestnik Moscow Univ. Ser. 1, Math. Mech. 6 (1980) 48-50. · Zbl 0512.60091 |

[17] | G.I. Falin, Computation of a traffic of a telephone used by many subscribers, Vestnik Moscow Univ. Ser. 15, Comput. Math. Cybernet. 2 (1981) 59-62. |

[18] | G.I. Falin, Functioning under nonsteady conditions of a single-channel system with group arrival of requests and repeated calls, Ukrainian Math. J. 33 (1981) 429-432. · Zbl 0476.60088 · doi:10.1007/BF01085753 |

[19] | G.I. Falin, The influence of inhomogeneity of the composition of subscribers on the functioning of telephone systems with repeated calls, Eng. Cybernet. Rev. 21 (6) (1983) 21-25. · Zbl 0577.90030 |

[20] | G.I. Falin, Asymptotic properties of the number of demands distribution in anM/G/1/? queueing system with repeated calls, Paper #5418-83, All-Union Institute for Scientific and Technical Information, Moscow (1983) (in Russian). |

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

[22] | G.I. Falin, Quasi-input process in theM/G/1/? queue, Adv. Appl. Probab. 16 (1984) 695-696. · Zbl 0544.60086 · doi:10.2307/1427298 |

[23] | G.I. Falin, A probabilistic model for investigation of load of subscriber’s lines with waiting places, in:Probability Theory, Stochastic Processes and Functional Analysis (Moscow State University, Moscow, 1985). |

[24] | G.I. Falin and Yu.I. Sukharev, On single-line queues with double connections, Paper #6582-85, All-Union Institute for Scientific and Technical Information, Moscow (1985)(in Russian). |

[25] | G.I. Falin, On waiting time process in single-line queues with repeated calls, J. Appl. Probab. 23 (1986) 185-192. · Zbl 0589.60077 · doi:10.2307/3214127 |

[26] | G.I. Falin, On ergodicity of multichannel queueing systems with repeated calls, Sov. J. Comput. Syst. Sci. 25 (1) (1987) 60-65. · Zbl 0655.60094 |

[27] | G.I. Falin, Single-line repeated orders queueing systems, Mathematische Operationsforschung und Statistik, Optimization 5 (1986) 649-667. · Zbl 0618.90033 |

[28] | G.I. Falin, Estimations of error in approximation of countable Markov chains associated with models of repeated calls, Vestnik Moscov. Univ. Ser. 1, Math. Mech. 2 (1987) 12-15. · Zbl 0625.60113 |

[29] | G.I. Falin, On a multiclass batch arrival retrial queue, Adv. Appl. Probab. 20 (1988) 483-487. · Zbl 0672.60089 · doi:10.2307/1427403 |

[30] | G.I. Falin, On the quasi-input process for theM/G/1/? queueing system, Ukrainian Math. J. 40 (1988) 226-229. · Zbl 0664.90033 · doi:10.1007/BF01056485 |

[31] | G.I. Falin, On virtual waiting time in retrial queues, Vestnik Moscow Univ. Ser. 1, Math. Mech., to appear. · Zbl 0743.60096 |

[32] | G. Fayolle, A simple telephone exchange with delayed feedbacks, in:Teletraffic Analysis and Computer Performance Evaluation, eds. O.J. Boxma, J.W. Cohen and H.C. Tijms (Elsevier Science, 1986). |

[33] | B.S. Greenberg, Queueing systems with returning customers and the optimal order of tandem queues, Ph.D. Thesis, University of California, Berkeley (1986). |

[34] | B.S. Greenberg,M/G/1 queueing systems with returning customers, J. Appl. Probab. 26 (1989) 152. · Zbl 0672.60094 · doi:10.2307/3214325 |

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

[36] | S.A. Greeschechkin, Branching processes and queues with repeated calls or random service, Theory of Probability and its Applications, to appear. |

[37] | T. Hanschke, A model for planning switching networks, in:Operations Research Proceedings 1984 (Springer, Berlin/Heidelberg, 1985). · Zbl 0557.90028 |

[38] | T. Hanschke, TheM/G/1/1 queue with repeated attempts and different types of feedback effects, OR Spektrum 7 (1985) 209-215. · Zbl 0572.60093 · doi:10.1007/BF01720172 |

[39] | T. Hanschke, A computational procedure for the variance of the waiting time in theM/M/1/1 queue with repeated calls, in:Operations Research Proceedings 1985 (Springer, Berlin/Heidelberg, 1986). · Zbl 0572.60093 |

[40] | I.I. Homitchkov, A model of a route of a circuit switching network with repeated calls, in:Mathematics and Software for Systems of Automatic Design of Networks (Mari State University, Oshkar-Ola, 1985)(in Russian). |

[41] | I.I. Homitchkov, Generating functions of state probabilities of a single-line queue with repeated calls, Vestnik Beloruss. Univ. Ser. 1, 1 (1987) 51-55 (in Russian). |

[42] | I.I. Homitchkov, A model of local area computer network with random multiple access, Automatics and Telemechanics 1 (1987) 58-62 (in Russian). |

[43] | I.I. Homitchkov, Single-line queue with repeated calls and Cox input process of second order, Vestnik Belorus. Univ. 1 (1988) 70-71 (in Russian). |

[44] | I.I. Homitchkov, Computing the characteristics of a queueing system with repeated units and twin connections, Automatics and Telemechanics 4 (1988) 77-84 (in Russian). |

[45] | J.J. Hunter, The non-renewal nature of the quasi-input process in theM/G/1/? queue, J. Appl. Probab. 23 (1986) 803-811. · Zbl 0624.60109 · doi:10.2307/3214017 |

[46] | G.L. Jonin and J.J. Sedol, Investigation of telephone systems with repeated calls, Latvian Math. Yearbook 7 (1970) 71-83. |

[47] | G.L. Jonin and J.J. Sedol,Tables of Probabilistic Characteristics of Fully Available Trunk Groups in the Case of Repeated Calls (Moscow, 1970). |

[48] | G.L. Jonin and J.J. Sedol, Telephone systems with repeated calls,Proc. 6th Int. Teletraffic Congress (1970) pp. 435/1-435/5. |

[49] | G.L. Jonin, A single-line system with repeated calls, in:Scientific and Technical Conf. for Problems of Information Networks and Automatic Switching, Thesis of Reports (Moscow, 1971). |

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

[51] | G.L. Jonin, J.J. Sedol and A.V. Kibild, General queueing model with repeated calls, in:Information Networks and Automatic Switching, 3rd All-Union Scientific and Technical Conference, Thesis of Reports (Moscow, 1975)(in Russian). |

[52] | G.L. Jonin, An investigation of single-line queues with repeated calls under independent discrete check of channel state, Latvian Math. Yearbook 24 (1980) 204-209. |

[53] | G.L. Jonin, An investigation of single-line queues with repeated calls under service without interruption and with independent discrete check of channel state, in:Models of Information Networks and Switching Systems (Moscow, 1982). |

[54] | G.L. Jonin, Determination of probabilistic characteristics of single-line queues with double connections and repeated calls, in:Models of Systems of Distribution of Information and Its Analysis (Moscow, 1982). |

[55] | V.A. Kapyrin, A study of the stationary characteristics of a queueing system with recurring demands, Cybernetics 13 (1977) 584-590. · Zbl 0368.60111 |

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

[57] | A.G. de Kok, Computational methods for single server systems with repeated attempts, Report #89, Interfaculteit der Actuariële Wetenschappen en Econometrie, Amsterdam (1982). |

[58] | A.G. de Kok, Algorithmic methods for single server systems with repeated attempts, Statistica Neerlandica 38 (1984) 23-32. · Zbl 0547.60098 · doi:10.1111/j.1467-9574.1984.tb01094.x |

[59] | Y.N. Kornishov, Calculation of coupled switching, Trudy Utchebnih Institutov Svyasi 37 (1968) 96-104 (in Russian). |

[60] | Y.N. Kornishov, Repeated calls in a trunk-line, Elektrosvyaz 1 (1974) 35-41 (in Russian). |

[61] | Y.N. Kornishov, A single-line queue with repeated calls and advance service, Izv. ANSSSR. Tekhn. Kibernetika 2 (1977) 83-88 (in Russian). |

[62] | Y.N. Kornishov and A.M. Zelinskiy, Analysis of subscriber’s line states, in:Information Networks and its Analysis (Moscow, 1978) (in Russian). |

[63] | Y.N. Kornishov, A single-line queue with heterogeneity repeated calls, in:Teletraffic Theory and Networks with Controlled Elements (Moscow, 1980)(in Russian). |

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

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

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

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

[68] | J. Lubacz and J. Roberts, A new approach to the single server repeat attempts system with balking,Proc. 3rd Int. Seminar on Teletraffic Theory, Moscow (1984) pp. 290-293. |

[69] | B. Pourbabai, Analysis of aG/M/K/0 queueing system with heterogeneous servers and retrials, Int. J. Syst. Sci. 18 (1987) 985-992. · Zbl 0611.90050 · doi:10.1080/00207728708964025 |

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

[71] | P. Ruskov, K. Yanev, B. Dimitrov and K. Boyanov, A model for investigating local area computer networks, Control Systems and Machines 5 (1984) 37-40. |

[72] | S.N. Stepanov, Moments of overload traffic for single-line queues with repeated calls, Izv. AN SSSR. Tekhn. Kibernetika 1 (1977) 88-93. |

[73] | S.N. Stepanov, The correlation function of a single-line queue with repeated attempts and its application to load measurement, in:Methods and Structures of Teletraffic Systems (Moscow, 1979)(in Russian). |

[74] | Yu.I. Sukcharev, Calculation of probabilistic characteristics ofM/G/1/? queues with repeated calls in the presence of network blocking, Paper #6258-84, All-Union Institute for Scientific and Technical Information, Moscow (1984)(in Russian). |

[75] | T. Yang and J.G.C. Templeton, A survey on retrial queues, Queueing Systems 2 (1987) 203-233. · Zbl 0658.60124 · doi:10.1007/BF01158899 |

[76] | A.M. Zelinskiy and Y.N. Kornishov, Equivalent models of a system with repeated calls, Trudy Utchebnih. Institutov Svyazi 80 (1976) 37-42 (in Russian). |

[77] | A.M. Zelinskiy and Y.N. Kornishov, Two models of a system with repeated calls, Elektrosvyaz 1 (1978) 60-63 (in Russian). |

[78] | G. Bretschneider, Repeated calls with limited repetition probability,Proc. 6th Int. Teletraffic Congress, Munich (1970) pp. 431/1-434/5. |

[79] | N. Deul, Stationary conditions for multiserver queueing systems with repeated calls, Elektronische Informationsverarbeitung und Kybernetik 10-12 (16) (1980) 607-613. · Zbl 0476.90027 |

[80] | A. Elldin, Approach to the theoretical description of repeated call attempts, Ericsson Technics 23 (3) (1967) 346-407. |

[81] | G.I. Falin, Not completely accessible schemes with allowance for repeated calls, Eng. Cybernet. Rev. 18 (5) (1980) 56-63. · Zbl 0497.90022 |

[82] | G.I. Falin, Switching systems with allowance for repeated calls, Probl. Inform. Transmission 16(1980) 145-151. · Zbl 0458.90024 |

[83] | G.I. Falin, Repeated calls in structurally complex systems, Eng. Cybernet. Rev. 18 (6) (1980) 46-51. · Zbl 0478.90020 |

[84] | G.I. Falin, Investigation of weakly loaded switching systems with repeated calls, Eng. Cybernet. Rev. 19 (3) (1981) 69-73. · Zbl 0512.90053 |

[85] | G.I. Falin, State consolidation in symmetrical partially accessible circuits, Probl. Control Inform. Theory 11 (1982) 3-12. · Zbl 0483.90043 |

[86] | G.I. Falin, Calculation of probabilistic characteristics of a multi-channel queue with repeated calls, Vestnik Mosk. Univ. Ser. 15, Vychisl. Mat. Cybernet. 1 (1983) 35-41. |

[87] | G.I. Falin, On the accuracy of a numerical method of calculation of characteristics of systems with repeated calls, Elektrosvyaz 8 (1983) 35-36. |

[88] | G.I. Falin, On sufficient conditions for ergodicity of multi-channel queueing systems with repeated calls, Adv. Appl. Probab. 16 (1984) 447-448. · Zbl 0535.60087 · doi:10.2307/1427079 |

[89] | G.I. Falin, Double-channel queueing system with repeated calls, Paper #4221-84, All-Union Institute for Scientific and Technical Information, Moscow (1984). |

[90] | G.I. Falin, Multilinear completely accessible systems with repeated calls in heavy traffic, Vestnik Moskov Univ. Ser. 15, Vychisl. Mat. Kibernet. 3 (1984) 66-69. · Zbl 0561.90037 |

[91] | G.I. Falin, Asymptotic investigation of fully available switching systems with high repetition intensity of blocked calls, Mosc. Univ. Math. Bull. 39 (6) (1984) 72-77 [Transl. from Vestn. Mosc. Univ. Ser. 1, no. 6 (1984) 49-53]. · Zbl 0572.60089 |

[92] | G.I. Falin, Limit theorems for queueing systems with repeated calls,4th Int. Vilnius Conf. on Probability Theory and Mathematical Statistics, Abstracts of Communications, Vol. 3, Vilnius, USSR (1985). |

[93] | G.I. Falin, On heavily loaded systems with repeated calls, Sov. J. Comput. Syst. Sci. 24 (4) (1986) 124-128 [Transi, from Izv. Akad. Nauk SSSR. Tekn. Kibern. (1986) 180-184]. · Zbl 0619.60090 |

[94] | G.I. Falin, Multichannel queueing systems with repeated calls under high intensity of repetition, J. Inform. Processing Cybernet. 1 (1987) 37-47. · Zbl 0616.90020 |

[95] | G.I. Falin, Comparability of migration processes, Probab. Theory Appl. 2 (1986) 392-396. · Zbl 0649.60087 |

[96] | G.I. Falin and Yu.I. Suharev, Singular perturbed equations and asymptotic investigation of stationary characteristics of retrial queues, Vestnik Moskow Univ. Ser. 1, Math. Mech. 5 (1988) 7-10. |

[97] | G.I. Falin, Theorems of ergodicity and stability for retrial queues, Ukrainian Math. J., to appear. |

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

[99] | T. Hanschke, Die von Bretschneider, Cohen und Schwartzbart/Puri entwickelte Warteschlangenmodelle mit wiederholten Versuchen: eine Methode zur Berechnung der ergodischen Projektion ihrer Markovschen Warteprozesse und die Simulation der Wartezeiten, Fakultät für Mathematik der Universität Karlsruhe (1978). |

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

[101] | G.L. Jonin and J.J. Sedol, Full-availability groups with repeated calls and time of advanced service,Proc. 7th Int. Teletraffic Congress, Stockholm (1973) pp. 137/1-137/4. |

[102] | Yu.N. Kornishov, Waiting positions for overloading trunks, Elektrosvyaz 7 (1974) 32-39. |

[103] | C.E.M. Pearce, On the problem of re-attempted calls in teletraffic, Commun. Statist.-Stochastic Models 3 (3) (1987) 393-407. · Zbl 0641.90041 · doi:10.1080/15326348708807063 |

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

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

[106] | S. Stepanov, Optimal calculation of characteristics of models with repeated calls,Proc. 12th Int. Teletraffic Congress, Torino (1988). |

[107] | R.I. Wilkinson, Theories for toll traffic engineering in the USA, Bell Syst. Techn. J. 35 (2) (1956) 421-507. |

[108] | R. Wilkinson and R. Radnik, Customers’ retrials in toll circuit operation,IEEE Int. Conf. on Communications (1968). |

[109] | R.W. Wolff,Stochastic Modeling and the Theory of Queues (Prentice-Hall, Englewood Cliffs, NJ, 1989). · Zbl 0701.60083 |

[110] | A.M. Zelinskiy and Yu.N. Kornishev, Two models of a system with repeated calls, Elektrosvyaz 1 (1978) 60-63. |

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.