Workload analysis of a two-queue fluid Polling model. (English) Zbl 1517.60118
Summary: In this paper, we analyze a two-queue random time-limited Markov-modulated polling model. In the first part of the paper, we investigate the fluid version: fluid arrives at the two queues as two independent flows with deterministic rate. There is a single server that serves both queues at constant speeds. The server spends an exponentially distributed amount of time in each queue. After the completion of such a visit time to one queue, the server instantly switches to the other queue, i.e., there is no switch-over time.
For this model, we first derive the Laplace-Stieltjes transform (LST) of the stationary marginal fluid content/workload at each queue. Subsequently, we derive a functional equation for the LST of the two-dimensional workload distribution that leads to a Riemann-Hilbert boundary value problem (BVP). After taking a heavy-traffic limit, and restricting ourselves to the symmetric case, the BVP simplifies and can be solved explicitly.
In the second part of the paper, allowing for more general (Lévy) input processes and server switching policies, we investigate the transient process limit of the joint workload in heavy traffic. Again solving a BVP, we determine the stationary distribution of the limiting process. We show that, in the symmetric case, this distribution coincides with our earlier solution of the BVP, implying that in this case the two limits (stationarity and heavy traffic) commute.
For this model, we first derive the Laplace-Stieltjes transform (LST) of the stationary marginal fluid content/workload at each queue. Subsequently, we derive a functional equation for the LST of the two-dimensional workload distribution that leads to a Riemann-Hilbert boundary value problem (BVP). After taking a heavy-traffic limit, and restricting ourselves to the symmetric case, the BVP simplifies and can be solved explicitly.
In the second part of the paper, allowing for more general (Lévy) input processes and server switching policies, we investigate the transient process limit of the joint workload in heavy traffic. Again solving a BVP, we determine the stationary distribution of the limiting process. We show that, in the symmetric case, this distribution coincides with our earlier solution of the BVP, implying that in this case the two limits (stationarity and heavy traffic) commute.
MSC:
| 60K25 | Queueing theory (aspects of probability theory) |
| 90B22 | Queues and service in operations research |
| 60K37 | Processes in random environments |
| 60G51 | Processes with independent increments; Lévy processes |
Keywords:
polling model; fluid queue; Lévy process; heavy-traffic limit; workload analysis; boundary value problemReferences:
| [1] | Abate, J. and Whitt, W. (2006). A unified framework for numerically inverting Laplace transforms. INFORMS J. Computing18, 408-421. · Zbl 1241.65114 |
| [2] | Adan, I. J. B. F., Boxma, O. J. and Resing, J. A. C. (2001). Queueing models with multiple waiting lines. Queueing Systems37, 65-98. · Zbl 0974.60079 |
| [3] | Adan, I. J. B. F., Kulkarni, V. G., Lee, N. and Lefeber, E. (2018). Optimal routeing in two-queue polling systems. J. Appl. Prob.55, 944-967. · Zbl 1402.60117 |
| [4] | Akhiezer, N. I. (1990). Elements of the Theory of Elliptic Functions. American Mathematical Society, Providence, RI. · Zbl 0694.33001 |
| [5] | Al Hanbali, A., De Haan, R., Boucherie, R. J. and Van Ommeren, J. C. W. (2012). Time-limited polling systems with batch arrivals and phase-type service times. Ann. Operat. Res.198, 57-82. · Zbl 1259.90021 |
| [6] | Asmussen, S. (1992). Queueing simulation in heavy-traffic. Math. Operat. Res.17, 84-111. · Zbl 0754.60101 |
| [7] | Asmussen, S. (2003). Applied Probability and Queues. Springer, New York. · Zbl 1029.60001 |
| [8] | Biane, P., Pitman, J. and Yor, M. (2001). Probability laws related to the Jacobi theta and Riemann zeta functions, and Brownian excursions. Bull. Amer. Math. Soc.38, 435-465. · Zbl 1040.11061 |
| [9] | Bieberbach, L. (2000). Conformal Mapping. American Mathematical Society, Providence, RI. · Zbl 0050.08401 |
| [10] | Bladt, M. and Nielsen, B. F. (2010). On the construction of bivariate exponential distributions with an arbitrary correlation coefficient. Stoch. Models26, 295-308. · Zbl 1197.60005 |
| [11] | Boon, M. A. A., Van Der Mei, R. D. and Winands, E. M. M. (2011). Applications of polling systems. Surveys Operat. Res. Manag. Sci.16, 67-82. |
| [12] | Borst, S. C. and Boxma, O. J. (2018). Polling: past, present, and perspective. TOP26, 335-369. · Zbl 1401.60166 |
| [13] | Boxma, O. J., Ivanovs, J., Kosinski, K. M. and Mandjes, M. R. H. (2011). Lévy-driven polling systems and continuous-state branching processes. Stoch. Systems1, 411-436. · Zbl 1291.60185 |
| [14] | Boxma, O. J. and Van Houtum, G. J. (1993). The compensation approach applied to a \(2 \times 2\) switch. Prob. Eng. Inf. Sci.7, 471-493. |
| [15] | Boxma, O. J. and Zwart, A. P. (2018). Fluid flow models in performance analysis. Comput. Commun.131, 22-25. |
| [16] | Brown, J. W. and Churchill, R. V. (2009). Complex Variables and Applications. McGraw-Hill, New York. |
| [17] | Chen, H. and Yao, D. D. (1992). A fluid model for systems with random disruptions. Operat. Res.40, S239-S247. · Zbl 0754.60107 |
| [18] | Choudhury, G. L., Lucantoni, D. M. and Whitt, W. (1994). Multidimensional transform inversion with applications to the transient M/G/1 queue. Ann. Appl. Prob.4, 719-740. · Zbl 0808.65140 |
| [19] | Ciesielski, Z. and Taylor, S. J. (1962). First passage times and sojourn times for Brownian motion in space and the exact Hausdorff measure of the sample path. Trans. Amer. Math. Soc.103, 434-450. · Zbl 0121.13003 |
| [20] | Coffman, E. G. Jr, Fayolle, G. and Mitrani, I. (1988). Two queues with alternating service periods. In Performance ’87, eds P.-J. Courtois and G. Latouche, North-Holland, Amsterdam, pp. 227-239. |
| [21] | Cohen, J. W. and Boxma, O. J. (2000). Boundary Value Problems in Queueing System Analysis. North-Holland, Amsterdam. · Zbl 0515.60092 |
| [22] | Czerniak, O. and Yechiali, U. (2009). Fluid polling systems. Queueing Systems63, 401-435. · Zbl 1209.90108 |
| [23] | Den Iseger, P., Gruntjes, P. and Mandjes, M. R. H. (2013). A Wiener-Hopf based approach to numerical computations in fluctuation theory for Lévy processes. Math. Meth. Operat. Res.78, 101-118. · Zbl 1281.60045 |
| [24] | Fayolle, G. and Iasnogorodski, R. (1979). Two coupled processors: the reduction to a Riemann-Hilbert problem. Z. Wahrscheinlichkeitsth.47, 325-351. · Zbl 0395.68032 |
| [25] | Feller, W. (1966). An Introduction to Probability Theory and Its Applications, Vol. II. John Wiley, New York. · Zbl 0138.10207 |
| [26] | Gamarnik, D. and Zeevi, A. (2006). Validity of heavy traffic steady-state approximation in generalized Jackson networks. Ann. Appl. Prob.16, 56-90. · Zbl 1094.60052 |
| [27] | Glynn, P. W. and Whitt, W. (1993). Limit theorems for cumulative processes. Stoch. Process. Appl.47, 299-314. · Zbl 0779.60021 |
| [28] | Glynn, P. W. and Whitt, W. (2002). Necessary conditions in limit theorems for cumulative processes. Stoch. Process. Appl.98, 199-209. · Zbl 1059.60025 |
| [29] | Hew, P. C. (2017). Asymptotic distribution of rewards accumulated by alternating renewal processes. Statist. Prob. Lett.129, 355-359. · Zbl 1457.62071 |
| [30] | Hirschman, I. I. and Widder, D. V. (1955). The Convolution Transform. Princeton University Press. · Zbl 0039.33202 |
| [31] | Kella, O. (1993). Parallel and tandem fluid networks with dependent Lévy inputs. Ann. Appl. Prob.3, 682-695. · Zbl 0780.60072 |
| [32] | Kella, O. and Whitt, W. (1992). A storage model with a two-state random environment. Operat. Res.40, S257-S262. · Zbl 0825.90344 |
| [33] | Kella, O. and Whitt, W. (1992). Useful martingales for stochastic storage processes with Lévy input. J. Appl. Prob.29, 396-403. · Zbl 0761.60065 |
| [34] | Kent, J. (1978). Some probabilistic interpretations of Bessel functions. J. Appl. Prob.6, 760-770. · Zbl 0402.60080 |
| [35] | Kingman, J. F. C. (1961). The single server queue in heavy traffic. Math. Proc. Camb. Phil. Soc. 57, 902-904. · Zbl 0114.11703 |
| [36] | Koops, D. T., Boxma, O. J. and Mandjes, M. R. H. (2016). A tandem fluid network with Lévy input in heavy traffic. Queueing Systems84, 355-379. · Zbl 1386.60307 |
| [37] | Kulkarni, V. G. (1997). Fluid models for single-buffer systems. In Frontiers in Queueing, ed. J. H. Dshalalow, CRC Press, Boca Raton, FL, pp. 321-338. · Zbl 0871.60079 |
| [38] | Remerova, M., Foss, S. G. and Zwart, A. P. (2014). Random fluid limit of an overloaded polling model. Adv. Appl. Prob.46, 76-101. · Zbl 1292.60093 |
| [39] | Saxena, M., Boxma, O. J., Kapodistria, S. and Núñez-Queija, R. (2017). Two queues with random time-limited polling. Prob. Math. Statist.37, 257-289. · Zbl 1403.90251 |
| [40] | Saxena, M., Kapodistria, S. and Núñez-Queija, R. (2019). Perturbation analysis of two queues with random time-limited polling. In Proc. 14th International Conference on Queueing Theory and Network Applications (QTNA2019), Centrum Wiskunde en Informatica, Amsterdam. · Zbl 1403.90251 |
| [41] | Takács, L. (1959). On a sojourn time problem in the theory of stochastic processes. Trans. Amer. Math. Soc.93, 531-540. · Zbl 0092.33701 |
| [42] | Zhang, J. and Zwart, A. P. (2008). Steady state approximations of limited processor sharing queues in heavy traffic. Queueing Systems60, 227-246. · Zbl 1156.90337 |
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.
