zbMATH — the first resource for mathematics

Boundary value problems in queueing theory. (English) Zbl 0662.60098
Certain types of random walks on \(\{0,1,2,...\}^ 2\) lead to the study of functional equations which can be transformed into Riemann boundary value problems. The author starts by outlining this procedure as well as the solution of the boundary value problem. He continues by illustrating this techniques with a typical random walk example and further shows that the corresponding functional equation can also be studied in terms of a Riemann-Hilbert boundary value problem or - yet another alternative - a Fredholm integral equation. A discussion of the application to queueing models with a “two-dimensional” state space and an extensive list of references is included.
Reviewer: R.Schaßberger

60K25 Queueing theory (aspects of probability theory)
60G50 Sums of independent random variables; random walks
45B05 Fredholm integral equations
Full Text: DOI
[1] J.P.C. Blanc, Asymptotic analysis of a queueing system with a two-dimensional state space, J. Appl. Prob. 21 (1984) 870–886. · Zbl 0554.60086
[2] J.P.C. Blanc, The relaxation time of two queueing systems in series, Stoch. Models 1 (1985) 1–16. · Zbl 0554.60091
[3] J.P.C. Blanc, A numerical study of a coupled processor model, report 87-01, Dept. Math. Univ. Limburg, Neth. 1987.
[4] J.P.C. Blanc and E.A. Van Doorn, Relaxation times for queueing systems, in:Proc. C.W.I. Symposium Mathematics and Computer Science, ed. J.W. Bakker, M. Hazewinkel and J.K. Lenstra, C.W.I. Monograph (North-Holland Publ. Co., Amsterdam, 1984) p. 139–162. · Zbl 0597.60097
[5] J.P.C. Blanc, Iasnogoradski and Ph. Nain, Analysis of the M/G/1-/M/1 queueing model, Report INRIA, Center de Sophia Antipolis, 1986.
[6] O.J. Boxma, Two symmetric queues with alternating service and switching times, In:Performance ’84, ed. E. Gelenbe (North-Holland Publ. Co., Amsterdam, 1984) p. 409–431.
[7] O.J. Boxma, Models of two queues: a few new views, In:Teletraffic Analysis and Comp. Perf. Evaluation, ed. O.J. Boxma, J.W. Cohen and H.C. Tijms (North-Holland Publ. Co., Amsterdam, 1986) p. 75–98.
[8] M.A. Brun and G. Fayolle, The distribution of the resequencing time in a simple fork-join system, In:Appl. Math., Perf., Reliab. Models Comp. Comm. Syst., ed. G. Iazeolla, F.J. Courtois and O.J. Boxma (North-Holland Publ. Co. Amsterdam, 1987) p. 203–212.
[9] E.G. Coffman, G. Fayolle and I. Mitrani, Analysis of sojourn times in a tandem queue with overtaking; reduction to a boundary value problem, Stochastic Models 2 (1986) 43–65. · Zbl 0595.60091
[10] E.G. Coffman, G. Fayolle and I. Mitrani, Two queues with alternating service periods, Report A.T. & T Bell Labs. Murray Hill, 1987, to appear in:Proc. Performance ’87, ed. P.J. Courtois and G. Latouche.
[11] J.W. Cohen,The Single Server Queue (North-Holland Publ. Co., Amsterdam, 1982) revised edition. · Zbl 0481.60003
[12] J.W. Cohen, The Wiener-Hopf technique in applied probability, In:Perspectives in Probability and Statistics, ed. J. Gani (Academic Press, London, 1975) p. 145–156. · Zbl 0334.60030
[13] J.W. Cohen, A two-queue, one-server model with priority for the longer queue, Queueing Systems Theor. Appl. 2 (1987) 261–284. · Zbl 0655.60090
[14] J.W. Cohen, A queueing system with semi-exhaustive alternating service, To appear in:Performance ’87, ed. P.J. Courtois and G. Latouche.
[15] J.W. Cohen, On a functional relation in three complex variables, preprint 359, Math. Inst., Univ. Utrecht, 1984.
[16] J.W. Cohen, On the analysis of parallel independent processors, preprint 374, Math. Inst., Univ. Utrecht, 1985.
[17] J.W. Cohen, On entrance time distributions for two-dimensional random walks, in:Proc. Appl. Math. & Perf. Reliability Models of Compl. Commun. Syst., ed. G. Iazeolla, P.J. Courtois and O.J. Boxma (North-Holland Publ. Co., Amsterdam, 1987) p. 25–42.
[18] J.W. Cohen, On entrance times of a homogeneousN-dimensional random walk: an identity, to appear in:A Celebration of Probability, 1988, ed. J. Gani.
[19] J.W. Cohen and O.J. Boxma,Boundary Value Problems in Queueing System Analysis (North-Holland Publ. Co., Amsterdam, 1983); Russian edition (Mir, Moscow, 1987). · Zbl 0515.60092
[20] H. Cramer, On some questions connected with mathematical risk, Univ. of California, Publ. in Statist. 2 (1954) 99.
[21] M. Eisenberg, Two queues with alternating service, SIAM Journ. Appl. Math. 36 (1979) 287–303. · Zbl 0405.90032
[22] G. Fayolle, On functional equations of one and two variables arising in the analysis of stochastic models, In:Math. Comp. Perform/Reliability, ed. G. Iazeolla, P.J. Courtois and A. Hordijk (North-Holland Publ. Co. Amsterdam, 1984) p. 55–75.
[23] G. Fayolle, A simple telephone exchange with delayed feedback, In:Teletraffic Analysis and Comp. Perf. Evaluation, ed. O.J. Boxma, J.W. Cohen and H.C. Tijms (North-Holland Publ. Co., Amsterdam, 1986) p. 245–254.
[24] G. Fayolle and R. Iasnogorodski, Two coupled processors: the reduction to a Riemann-Hilbert problem, Z. Wahrsch. Verw. Gebiete 47 (1979) 325–351. · Zbl 0395.68032
[25] G. Fayolle, R. Iasnogorodski and I. Mitrani, The distribution of sojourn times in a queueing network with overtaking: reduction to a boundary value problem, inPerformance ’83, ed. A.K. Agrawala and S.K. Tripathi (North-Holland Publ. Co., Amsterdam, 1983) p. 477–486.
[26] G. Fayolle, P.J.B. King and I. Mitrani, The solution of certain two-dimensional Markov models, Adv. Appl. Prob. 14 (1982) 295–308. · Zbl 0495.60087
[27] L. Flatto and S. Hahn, Two parallel queues created by arrivals with two demands, I&II, SIAM J. Appl. Math. 44 (1984) 1041–1054; 45 (1985) 861–878; erratum 45 (1985) 168. · Zbl 0554.90041
[28] G.J. Foschini, Equilibrium for diffusion models of pairs of communicating computers-symmetric case, IEEE Transactions, IT 28 (1982) 273–284. · Zbl 0476.68030
[29] F.D. Gakhov,Boundary Value Problems (Pergamon Press, Oxford, 1966). · Zbl 0141.08001
[30] S.J. de Klein, Fredholm integral equation in queueing systems analysis, doctoral thesis, Math. Inst., Univ. of Utrecht, 1988.
[31] V.A. Malysev, Classification of two-dimensional positive random walks and almost linear semi-martingales, Dokl. Akad. Nauk. SSSR 202 (1972) 136–139.
[32] E. Meister,Randwertaufgaben der Funktionentheorie (Teubner, Stuttgart, 1983).
[33] I. Mitrani, Response time problems in communication networks, J.R. Statist. Soc. B 47 (1985) 396–406. · Zbl 0611.68011
[34] N.I. Mushkelishvili,Singular Integral Equations (Noordhoff, Groningen, 1953).
[35] Ph. Nain, On a generalisation of the preemptive resume priority, Adv. Appl. Prob. 18 (1986) 255–273. · Zbl 0589.60079
[36] Ph. Nain, Applications des Méthodes Analytiques à la Modelisation des Systèmes Informatiques, Doctoral Thesis, Univ. Pierre et Marie Curie-Paris 6, Paris, 1987.
[37] Ph. Nain and K. Ross, Optimal priority assignment with hard constraint, Report INRIA, Centre de Sophia Antipolis, 1985. · Zbl 0625.90031
[38] Ph. Nain, Analysis of a two-node ALOHA-network with infinite capacity buffers, in:Computer Networking and Performance Evaluation, ed. T. Hasegawa, H. Takagi, Y. Takahashi (North-Holland, Amsterdam, 1986) p. 49–64.
[39] Z. Nehari,Conformal Mapping (Dover Publ., New York, 1975).
[40] H. Nauta, A queueing model-transport of items to one saerver, preprint 388, Math. Inst. Univ. of Utrecht, 1985.
[41] F. Pollaczek,Théorie Analytique des Problèmes Stochastiques Relatifs à un Groupe de Ligues Téléphoniques avec Dispositif d’Attente (Gauthier Villars, Paris, 1961). · Zbl 0103.11602
[42] J.H.A. de Smit, The single server semi-Markov queue, Stoch. Proc. Appl. 22 (1986) 37–50. · Zbl 0606.60086
[43] H. Takagi, Analysis of Polling Systems (MIT Press Cambridge, Massachusetts, 1986). · Zbl 0647.01001
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.