Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Adan, I.J.-B.F.: A Compensation Approach for Queueing Problems, vol. 104. Centrum voor Wiskunde en Informatica, Amsterdam (1994)
Adan, I.J.-B.F., Boxma, O.J., Resing, J.: Queueing models with multiple waiting lines. Queueing Syst. 37(1–3), 65–98 (2001)
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)
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)
Agarwal, R.P., Perera, K., Pinelas, S.: An Introduction to Complex Analysis. Springer, Berlin (2011)
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)
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)
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)
Boxma, O.J., Van Houtum, G.-J.: The compensation approach applied to a \(2\times 2\) switch. Probab. Eng. Inf. Sci. 7(04), 471–493 (1993)
Bruneel, H., Fiems, D., Walraevens, J., Wittevrongel, S.: Queueing models for the analysis of communication systems. TOP 22(2), 421–448 (2014)
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)
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)
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)
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)
Cohen, J.W.: Boundary value problems in queueing theory. Queueing Syst. 3(2), 97–128 (1988)
Cohen, J.W.: On the asymmetric clocked buffered switch. Queueing Syst. 30(3–4), 385–404 (1998)
Cohen, J.W., Boxma, O.J.: Boundary Value Problems in Queueing System Analysis, vol. 79 of Mathematics Studies. Elsevier Science Ltd., Amsterdam (1983)
Cooper, R.B.: Introduction to Queueing Theory, vol. 2. North-Holland, New York (1981)
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)
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)
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)
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)
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)
Fayolle, G., King, P.J.B., Mitrani, I.: The solution of certain two-dimensional Markov models. Adv. Appl. Probab. 14(2), 295–308 (1982)
Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)
Flatto, L.: Two parallel queues created by arrivals with two demands II. SIAM J. Appl. Math. 45(5), 861–878 (1985)
Flatto, L., Hahn, S.: Two parallel queues created by arrivals with two demands I. SIAM J. Appl. Math. 44(5), 1041–1053 (1984)
Forster, O., Gilligan, B.: Lectures on Riemann Surfaces, vol. 81. Springer, New York (1981)
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)
Gakhov, F.D.: Boundary Value Problems. Courier Corporation, North Chelmsford (1990)
Greene, D.H., Knuth, D.E.: Mathematics for the Analysis of Algorithms. Springer, Berlin (2007)
Guillemin, F.: Analysis of a non-work conserving generalized processor sharing queue. Preprint arXiv:1305.3536 (2013)
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)
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)
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)
Guillemin, F., Knessl, C., Van Leeuwaarden, J.: First response to letter of G. Fayolle and R. Iasnogorodski. Queueing Syst. 76(1), 109–110 (2014)
Guillemin, F., van Leeuwaarden, J.: Rare event asymptotics for a random walk in the quarter plane. Queueing Syst. 67(1), 1–32 (2011)
Henrici, P.: Applied and Computational Complex Analysis, Volume 3: Discrete Fourier Analysis, Cauchy Integrals, Construction of Conformal Maps, Univalent Functions. Wiley, New York (1993)
Houtum, V.G.-J.: New approaches for multi-dimensional queueing systems. Ph.D. thesis, Technische Universiteit Eindhoven (1995)
Kingman, J.F.C.: Two similar queues in parallel. Ann. Math. Stat. 32(4), 1314–1323 (1961)
Kleinrock, L.: Queueing Systems, Volume 1: Theory. Wiley-Interscience, New York (1975)
Li, H., Zhao, Y.Q.: Tail asymptotics for a generalized two-demand queueing model—a kernel method. Queueing Syst. 69(1), 77–100 (2011)
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)
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)
Morrison, J.A.: Processor sharing for two queues with vastly different rates. Queueing Syst. 57(1), 19–28 (2007)
Morrison, J.A.: Two queues with vastly different arrival rates and processor-sharing factors. Queueing Syst. 64(1), 49–67 (2010)
Muskhelishvili, N.I.: Singular Integral Equations: Boundary Problems of Function Theory and Their Application to Mathematical Physics. Courier Corporation, North Chelmsford (2008)
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)
Nassar, H.: Two-dimensional queueing model for a LAN gateway. WSEAS Trans. Commun. 5(9), 1585–1590 (2006)
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)
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)
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)
Nassar, H., Al-mahdi, H.: Delay analysis of a multimedia ATM multiplexer with homogeneous arrivals. J. Circuits Syst. Comput. 13(05), 999–1018 (2004)
Nassar, H., Al-mahdy, H.: A priority discrete queueing model for multimedia multiplexers. Math. Comput. Model. Dyn. Syst. 8(2), 199–211 (2002)
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)
Nassar, H.: El-hady, E-s: Closed form solution of a LAN gateway queueing model. In: Pardalos, P.M., Rassias, T.M. (eds.) Contributions in Mathematics and Engineering. In Honor of Constantin Caratheodory. Springer, Berlin (2016)
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)
Ponnusamy, S., Silverman, H.: Complex Variables with Applications. Birkhäuser, Basel (2006)
Resing, J., Örmeci, L.: A tandem queueing model with coupled processors. Oper. Res. Lett. 31(5), 383–389 (2003)
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)
Sidi, M., Segall, A.: Two interfering queues in packet-radio networks. IEEE Trans. Commun. 31(1), 123–129 (1983)
Takagi, H.: Queueing Analysis: A Foundation of Performance Evaluation, Volume 1: Vacation and Priority Systems. Elsevier Science Publication, New York (1991)
Van Leeuwaarden, J., Resing, J.: A tandem queue with coupled processors: computational issues. Queueing Syst. 51(1–2), 29–52 (2005)
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)
Walraevens, J.: Discrete-time queueing models with priorities. Ph.D. thesis, Ghent University (2004)
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)
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)
Wilf, H.S.: Generatingfunctionology. Elsevier, New York (2013)
Woodward, M.E.: Communication and Computer Networks: Modelling with discrete-time queues. Wiley-IEEE Computer Society Press, New York (1993)
Wright, P.E.: Two parallel processors with coupled inputs. Adv. Appl. Probab. 24(4), 986–1007 (1992)
Acknowledgements
El-sayed El-hady was a joint-scholarship holder. This scholarship was fully funded by the the Ministry of Higher Education and Scientific Research, Cairo, Egypt during the period January, 2013 till January, 2015. He was also getting a scholarship number \(2014/3/MIP-12\) funded by Innsbruck University, Austria.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
El-hady, Es., Brzdęk, J. & Nassar, H. On the structure and solutions of functional equations arising from queueing models. Aequat. Math. 91, 445–477 (2017). https://doi.org/10.1007/s00010-017-0471-1
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00010-017-0471-1