×

On the structure and solutions of functional equations arising from queueing models. (English) Zbl 1441.39022

Summary: It is a survey on functional equations of a certain type, for functions in two complex variables, which often arise in queueing models. They share a common pattern despite their apparently different forms. In particular, they invariably characterize the probability generating function of the bivariate distribution characterizing a two-queue system and their forms depend on the composition of the underlying system. Unfortunately, there is no general methodology of solving them, but rather various ad-hoc techniques depending on the nature of a particular equation; most of the techniques involve advanced complex analysis tools. Also, the known solutions to particular cases of this type of equations are in general of quite involved forms and therefore it is very difficult to apply them practically. So, it is clear that the issues connected with finding useful descriptions of solutions to these equations create a huge area of research with numerous open problems. The aim of this article is to stimulate a methodical study of this area. To this end we provide a survey of the queueing literature with such two-place functional equations. We also present several observations obtained while preparing it. We hope that in this way we will make it easier to take some steps forward on the road towards a (more or less) general solving theory for this interesting class of equations.

MSC:

39B32 Functional equations for complex functions
05A15 Exact enumeration problems, generating functions
30D05 Functional equations in the complex plane, iteration and composition of analytic functions of one complex variable
30E25 Boundary value problems in the complex plane
60K25 Queueing theory (aspects of probability theory)
65Q20 Numerical methods for functional equations
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adan, I.J.-B.F.: A Compensation Approach for Queueing Problems, vol. 104. Centrum voor Wiskunde en Informatica, Amsterdam (1994) · Zbl 0819.60081
[2] Adan, I.J.-B.F., Boxma, O.J., Resing, J.: Queueing models with multiple waiting lines. Queueing Syst. 37(1-3), 65-98 (2001) · Zbl 0974.60079 · doi:10.1023/A:1011040100856
[3] Adan, I.J.-B.F., Van Houtum, G.-J., Wessels, J., Zijm, W.: A compensation procedure for multiprogramming queues. OR Spectr. 15(2), 95-106 (1993) · Zbl 0776.68022 · doi:10.1007/BF01720521
[4] Adan, I.J.-B.F., Wessels, J., Zijm, W.H.M.: A compensation approach for two-dimensional Markov processes. Adv. Appl. Probab. 25(4), 783-817 (1993) · Zbl 0798.60081 · doi:10.1017/S0001867800025751
[5] Agarwal, R.P., Perera, K., Pinelas, S.: An Introduction to Complex Analysis. Springer, Berlin (2011) · Zbl 1230.30001 · doi:10.1007/978-1-4614-0195-7
[6] Ahlfors, L.V.: Complex Analysis: An Introduction to The Theory of Analytic Functions of One Complex Variable, vol. 3 of International Series in Pure & Applied Mathematics. McGraw-Hill Book Company, New York (1966)
[7] Blanc, J.P.C.: Application of the Theory of Boundary Value Problems in the Analysis of a Queueing Model with Paired Services, vol. 153 of Mathematisch Centrum Amsterdam: Mathematical Centre Tracts. Mathematisch Centrum (1982) · Zbl 0508.60075
[8] Boxma, O.J., Groenendijk, W.P.: Two queues with alternating service and switching times. In: Queueing Theory and its Applications. CWI Monograph, vol. 7, pp. 261-282. North-Holland, Amsterdam (1988) · Zbl 1095.90527
[9] Boxma, O.J., Van Houtum, G.-J.: The compensation approach applied to a \[2\times 22\]×2 switch. Probab. Eng. Inf. Sci. 7(04), 471-493 (1993) · Zbl 0814.68072 · doi:10.1017/S0269964800003089
[10] Bruneel, H., Fiems, D., Walraevens, J., Wittevrongel, S.: Queueing models for the analysis of communication systems. TOP 22(2), 421-448 (2014) · Zbl 1303.60083 · doi:10.1007/s11750-014-0330-3
[11] Bruneel, H., Mélange, W., Steyaert, B., Claeys, D., Walraevens, J.: A two-class discrete-time queueing model with two dedicated servers and global FCFS service discipline. Eur. J. Oper. Res. 223(1), 123-132 (2012) · Zbl 1253.90071 · doi:10.1016/j.ejor.2012.06.031
[12] Bruneel, H., Rogiest, W., Walraevens, J., Wittevrongel, S.: Analysis of a discrete-time queue with general independent arrivals, general service demands and fixed service capacity. Math. Methods Oper. Res. 82(3), 285-315 (2015) · Zbl 1334.90030 · doi:10.1007/s00186-015-0515-z
[13] Bruneel, H., Wittevrongel, S., Claeys, D., Walraevens, J.: Discrete-time queues with variable service capacity: a basic model and its analysis. Ann. Oper. Res. 239(2), 359-380 (2016) · Zbl 1338.90123
[14] Brzdęk, J., El-hady, E.-S., Förg-Rob, W., Leśniak, Z.: A note on solutions of a functional equation arising in a queueing model for a LAN gateway. Aequ. Math. 90(4), 671-681 (2016) · Zbl 1345.30030 · doi:10.1007/s00010-016-0421-3
[15] Cohen, J.W.: Boundary value problems in queueing theory. Queueing Syst. 3(2), 97-128 (1988) · Zbl 0662.60098 · doi:10.1007/BF01189045
[16] Cohen, J.W.: On the asymmetric clocked buffered switch. Queueing Syst. 30(3-4), 385-404 (1998) · Zbl 0919.90062 · doi:10.1023/A:1019133525165
[17] Cohen, J.W., Boxma, O.J.: Boundary Value Problems in Queueing System Analysis, vol. 79 of Mathematics Studies. Elsevier Science Ltd., Amsterdam (1983) · Zbl 0515.60092
[18] Cooper, R.B.: Introduction to Queueing Theory, vol. 2. North-Holland, New York (1981) · Zbl 0467.60001
[19] Dautray, R., Lions, J.-L.: Mathematical Analysis and Numerical Methods for Science and Technology, vol. 4 of Integral Equations and Numerical Methods. Springer, Berlin (2000) · Zbl 0951.74001 · doi:10.1007/978-3-642-58090-1
[20] Fayolle, G.: On functional equations for one or two complex variables arising in the analysis of stochastic models. In: Proceedings of the International Workshop on Computer Performance and Reliability. North-Holland Publishing Company, pp. 55-75 (1983) · Zbl 1334.60199
[21] Fayolle, G., Iasnogorodski, R.: Two coupled processors: the reduction to a Riemann-Hilbert problem. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 47(3), 325-351 (1979) · Zbl 0395.68032 · doi:10.1007/BF00535168
[22] Fayolle, G., Iasnogorodski, R., Malyshev, V.A.: Random Walks in the Quarter-Plane: Algebraic Methods, Boundary Value Problems and Applications, vol. 40 of Stochastic Modelling and Applied Probability. Springer, Berlin (1999) · Zbl 0932.60002 · doi:10.1007/978-3-642-60001-2
[23] Fayolle, G., King, P.J.B., Mitrani, I.: The solution of certain two-dimensional Markov models. ACM Sigmetr. Perform. Eval. Rev. 9(2), 283-289 (1980) · Zbl 0495.60087 · doi:10.1145/1009375.806175
[24] Fayolle, G., King, P.J.B., Mitrani, I.: The solution of certain two-dimensional Markov models. Adv. Appl. Probab. 14(2), 295-308 (1982) · Zbl 0495.60087 · doi:10.1017/S0001867800020450
[25] Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009) · Zbl 1165.05001 · doi:10.1017/CBO9780511801655
[26] Flatto, L.: Two parallel queues created by arrivals with two demands II. SIAM J. Appl. Math. 45(5), 861-878 (1985) · Zbl 0579.90033 · doi:10.1137/0145052
[27] Flatto, L., Hahn, S.: Two parallel queues created by arrivals with two demands I. SIAM J. Appl. Math. 44(5), 1041-1053 (1984) · Zbl 0554.90041 · doi:10.1137/0144074
[28] Forster, O., Gilligan, B.: Lectures on Riemann Surfaces, vol. 81. Springer, New York (1981) · Zbl 0475.30002 · doi:10.1007/978-1-4612-5961-9
[29] Fricker, C., Guillemin, F., Robert, P., Thompson, G.: Analysis of an offloading scheme for data centers in the framework of fog computing. arXiv:1507.05746 (2015)
[30] Gakhov, F.D.: Boundary Value Problems. Courier Corporation, North Chelmsford (1990) · Zbl 0830.30026
[31] Greene, D.H., Knuth, D.E.: Mathematics for the Analysis of Algorithms. Springer, Berlin (2007) · Zbl 1151.68750
[32] Guillemin, F.: Analysis of a non-work conserving generalized processor sharing queue. Preprint arXiv:1305.3536 (2013)
[33] Guillemin, F., Knessl, C., Van Leeuwaarden, J.: Wireless multihop networks with stealing: large buffer asymptotics via the ray method. SIAM J. Appl. Math. 71(4), 1220-1240 (2011) · Zbl 1238.60102 · doi:10.1137/100808629
[34] Guillemin, F., Knessl, C., van Leeuwaarden, J.: Wireless three-hop networks with stealing II: exact solutions through boundary value problems. Queueing Syst. 74(2-3), 235-272 (2013) · Zbl 1266.90074 · doi:10.1007/s11134-012-9332-8
[35] Guillemin, F., Knessl, C., van Leeuwaarden, J.: Erratum to: Wireless three-hop networks with stealing II: exact solutions through boundary value problems. Queueing Syst. 78(2), 189-195 (2014) · Zbl 1299.90098 · doi:10.1007/s11134-014-9418-6
[36] Guillemin, F., Knessl, C., Van Leeuwaarden, J.: First response to letter of G. Fayolle and R. Iasnogorodski. Queueing Syst. 76(1), 109-110 (2014) · Zbl 1303.90029 · doi:10.1007/s11134-013-9391-5
[37] Guillemin, F., van Leeuwaarden, J.: Rare event asymptotics for a random walk in the quarter plane. Queueing Syst. 67(1), 1-32 (2011) · Zbl 1210.60100 · doi:10.1007/s11134-010-9197-7
[38] Henrici, P.: Applied and Computational Complex Analysis, Volume 3: Discrete Fourier Analysis, Cauchy Integrals, Construction of Conformal Maps, Univalent Functions. Wiley, New York (1993) · Zbl 1107.30300
[39] Houtum, V.G.-J.: New approaches for multi-dimensional queueing systems. Ph.D. thesis, Technische Universiteit Eindhoven (1995) · Zbl 0822.90064
[40] Kingman, J.F.C.: Two similar queues in parallel. Ann. Math. Stat. 32(4), 1314-1323 (1961) · Zbl 0104.36901 · doi:10.1214/aoms/1177704869
[41] Kleinrock, L.: Queueing Systems, Volume 1: Theory. Wiley-Interscience, New York (1975) · Zbl 0334.60045
[42] Li, H., Zhao, Y.Q.: Tail asymptotics for a generalized two-demand queueing model—a kernel method. Queueing Syst. 69(1), 77-100 (2011) · Zbl 1235.60132 · doi:10.1007/s11134-011-9227-0
[43] Lopatatzidis, S., De Bock, J., de Cooman, G., De Vuyst, S., Walraevens, J.: Robust queueing theory: an initial study using imprecise probabilities. Queueing Syst. 82(1), 75-101 (2015) · Zbl 1334.60199
[44] Maertens, T., Walraevens, J., Moeneclaey, M., Bruneel, H.: Performance analysis of a discrete-time queueing system with priority jumps. AEU-Int. J. Electron. Commun. 63(10), 853-858 (2009) · doi:10.1016/j.aeue.2008.07.004
[45] Morrison, J.A.: Processor sharing for two queues with vastly different rates. Queueing Syst. 57(1), 19-28 (2007) · Zbl 1128.60081 · doi:10.1007/s11134-007-9043-8
[46] Morrison, J.A.: Two queues with vastly different arrival rates and processor-sharing factors. Queueing Syst. 64(1), 49-67 (2010) · Zbl 1181.90076 · doi:10.1007/s11134-009-9126-9
[47] Muskhelishvili, N.I.: Singular Integral Equations: Boundary Problems of Function Theory and Their Application to Mathematical Physics. Courier Corporation, North Chelmsford (2008)
[48] Nada, F.A.: Performance analysis of multiserver ATM buffers routing multimedia traffics with geometric service time. Automatika: Časopis za Automatiku, Mjerenje, Elektroniku, Računarstvo i Komunikacije 51(3), 293-301 (2010)
[49] Nassar, H.: Two-dimensional queueing model for a LAN gateway. WSEAS Trans. Commun. 5(9), 1585-1590 (2006)
[50] Nassar, H.: Two-dimensional queueing model for a LAN gateway. In: Proceedings of the 10th WSEAS International Conference on Communications, Vouliagmeni (Greece) pp. 425-430 (2006) · Zbl 1309.90020
[51] Nassar, H., Ahmed, M.A.: Performance analysis of an ATM buffered switch transmitting two-class traffic over unreliable channels. AEU-Int. J. Electron. Commun. 57(3), 190-200 (2003) · doi:10.1078/1434-8411-54100161
[52] Nassar, H., Al-mahdi, H.: Queueing analysis of an ATM multimedia multiplexer with non-pre-emptive priority. IEE Proc. Commun. 150(3), 189-196 (2003) · doi:10.1049/ip-com:20030218
[53] Nassar, H., Al-mahdi, H.: Delay analysis of a multimedia ATM multiplexer with homogeneous arrivals. J. Circuits Syst. Comput. 13(05), 999-1018 (2004) · doi:10.1142/S0218126604001842
[54] Nassar, H., Al-mahdy, H.: A priority discrete queueing model for multimedia multiplexers. Math. Comput. Model. Dyn. Syst. 8(2), 199-211 (2002) · Zbl 1090.90508 · doi:10.1076/mcmd.8.2.199.8590
[55] Nassar, H., Carpinelli, J., Nada, F.A.: Queueing analysis of an ATM multichannel switch routing two-class multimedia traffic with two service rates. IEICE Trans. Commun. 87(6), 1505-1513 (2004)
[56] Nassar, H.; Pardalos, PM (ed.); Rassias, TM (ed.), El-hady, E-s: Closed form solution of a LAN gateway queueing model (2016), Berlin · Zbl 1370.90092
[57] Nassar, H., Fouad, Y.: Analysis of two-class discrete packet queues with homogenous arrivals and prioritized service. Commun. Inf. Syst. 3(2), 101-117 (2003) · Zbl 1095.90527
[58] Ponnusamy, S., Silverman, H.: Complex Variables with Applications. Birkhäuser, Basel (2006) · Zbl 1121.30001
[59] Resing, J., Örmeci, L.: A tandem queueing model with coupled processors. Oper. Res. Lett. 31(5), 383-389 (2003) · Zbl 1033.90017 · doi:10.1016/S0167-6377(03)00046-4
[60] Rogiest, W., Laevens, K., Walraevens, J., Bruneel, H.: Random-order-of-service for heterogeneous customers: waiting time analysis. Ann. Oper. Res. 226(1), 527-550 (2015) · Zbl 1309.90020 · doi:10.1007/s10479-014-1721-4
[61] Sidi, M., Segall, A.: Two interfering queues in packet-radio networks. IEEE Trans. Commun. 31(1), 123-129 (1983) · doi:10.1109/TCOM.1983.1095740
[62] Takagi, H.: Queueing Analysis: A Foundation of Performance Evaluation, Volume 1: Vacation and Priority Systems. Elsevier Science Publication, New York (1991) · Zbl 0744.60114
[63] Van Leeuwaarden, J., Resing, J.: A tandem queue with coupled processors: computational issues. Queueing Syst. 51(1-2), 29-52 (2005) · Zbl 1094.60065 · doi:10.1007/s11134-005-1683-y
[64] Vanlerberghe, J., Walraevens, J., Maertens, T., De Vuyst, S., Bruneel, H.: On generalized processor sharing and objective functions: Analytical framework. In: Computer Performance Engineering, vol. 9272 of Lecture Notes in Computer Science. Springer International Publishing, pp. 96-111 (2015) · Zbl 0579.90033
[65] Walraevens, J.: Discrete-time queueing models with priorities. Ph.D. thesis, Ghent University (2004)
[66] Walraevens, J., Bruneel, H., Claeys, D., Wittevrongel, S.: The discrete-time queue with geometrically distributed service capacities revisited. In: Analytical and Stochastic Modeling Techniques and Applications. Springer, pp. 443-456 (2013) · Zbl 1395.90124
[67] Walraevens, J., Steyaert, B., Bruneel, H.: Performance analysis of a single-server ATM queue with a priority scheduling. Comput. Oper. Res. 30(12), 1807-1829 (2003) · Zbl 1047.90024 · doi:10.1016/S0305-0548(02)00108-9
[68] Wilf, H.S.: Generatingfunctionology. Elsevier, New York (2013) · Zbl 1092.05001
[69] Woodward, M.E.: Communication and Computer Networks: Modelling with discrete-time queues. Wiley-IEEE Computer Society Press, New York (1993) · Zbl 0825.68173
[70] Wright, P.E.: Two parallel processors with coupled inputs. Adv. Appl. Probab. 24(4), 986-1007 (1992) · Zbl 0760.60093 · doi:10.1017/S0001867800025040
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.