Serve the shortest queue and Walsh Brownian motion.

*(English)*Zbl 1409.60037Summary: We study a single server Markovian queueing model with \(N\) customer classes in which priority is given to the shortest queue. Under critical load condition, we establish in the form of a Walsh Brownian motion (WBM) living in the union of the \(N\) nonnegative coordinate axes in \(\mathbb{R}^N\) and a linear transformation thereof. This reveals the following asymptotic behavior. Each time that queues begin to build starting from an empty system, one of them becomes dominant in the sense that it contains nearly all the workload in the system, and it remains so until the system becomes (nearly) empty again. The radial part of the WBM, given as a reflected Brownian motion (RBM) on the half-line, captures the total workload asymptotics, whereas its angular distribution expresses how likely it is for each class to become dominant on excursions.

As a heavy traffic result, it is nonstandard in three ways: (i) In the terminology of J. M. Harrison [in: Stochastic networks. Proceedings of a workshop of the 1993-94 IMA program on emerging applications of probability. New York, NY: Springer-Verlag. 1–20 (1995; Zbl 0838.90045)], it is unconventional, in that the limit is not RBM. (ii) It does not constitute an invariance principle, in that the limit law (specifically, the angular distribution) is not determined solely by the first two moments of the data, and is sensitive even to tie breaking rules. (iii) The proof method does not fully characterize the limit law (specifically, it gives no information on the angular distribution).

As a heavy traffic result, it is nonstandard in three ways: (i) In the terminology of J. M. Harrison [in: Stochastic networks. Proceedings of a workshop of the 1993-94 IMA program on emerging applications of probability. New York, NY: Springer-Verlag. 1–20 (1995; Zbl 0838.90045)], it is unconventional, in that the limit is not RBM. (ii) It does not constitute an invariance principle, in that the limit law (specifically, the angular distribution) is not determined solely by the first two moments of the data, and is sensitive even to tie breaking rules. (iii) The proof method does not fully characterize the limit law (specifically, it gives no information on the angular distribution).

##### MSC:

60F05 | Central limit and other weak theorems |

93E03 | Stochastic systems in control theory (general) |

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

60J65 | Brownian motion |

60J70 | Applications of Brownian motions and diffusion theory (population genetics, absorption problems, etc.) |

PDF
BibTeX
XML
Cite

\textit{R. Atar} and \textit{A. Cohen}, Ann. Appl. Probab. 29, No. 1, 613--651 (2019; Zbl 1409.60037)

**OpenURL**

##### References:

[1] | Barlow, M., Pitman, J. and Yor, M. (1989). On Walsh’s Brownian motions. In Séminaire de Probabilités, XXIII. Lecture Notes in Math.1372 275–293. Springer, Berlin. · Zbl 0747.60072 |

[2] | Baxter, J. R. and Chacon, R. V. (1984). The equivalence of diffusions on networks to Brownian motion. In Conference in Modern Analysis and Probability (New Haven, Conn., 1982). Contemp. Math.26 33–48. Amer. Math. Soc., Providence, RI. · Zbl 0546.60080 |

[3] | Benameur, N., Guillemin, F. and Muscariello, L. (2013). Latency reduction in home access gateways with shortest queue first. In Proc. ISOC Workshop on Reducing Internet Latency. |

[4] | Billingsley, P. (1999). Convergence of Probability Measures, 2nd ed. Wiley, New York. · Zbl 0944.60003 |

[5] | Bonald, T., Muscariello, L. and Ostallo, N. (2011). Self-prioritization of audio and video traffic. In IEEE International Conference on Communications (ICC) 1–6. IEEE, New York. |

[6] | Carofiglio, G. and Muscariello, L. (2010). On the impact of TCP and per-flow scheduling on Internet performance. In INFOCOM, 2010 Proceedings IEEE 1–9. IEEE, New York. |

[7] | Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes: Characterization and Convergence. Wiley, New York. · Zbl 0592.60049 |

[8] | Guillemin, F. and Simonian, A. (2013). Analysis of the shortest queue first service discipline with two classes. In Proceedings of the 7th International Conference on Performance Evaluation Methodologies and Tools 1–10. ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering), Portland. · Zbl 1309.60087 |

[9] | Guillemin, F. and Simonian, A. (2014). Stationary analysis of the shortest queue first service policy. Queueing Syst.77 393–426. · Zbl 1309.60087 |

[10] | Guillemin, F. and Simonian, A. (2017). Stationary analysis of the “shortest queue first” service policy: The asymmetric case. Stoch. Models33 256–296. · Zbl 1370.60168 |

[11] | Hajri, H. (2012). Discrete approximations to solution flows of Tanaka’s SDE related to Walsh Brownian motion. In Séminaire de Probabilités XLIV. Lecture Notes in Math.2046 167–190. Springer, Heidelberg. · Zbl 1261.60054 |

[12] | Harrison, J. M. (1995). Balanced fluid models of multiclass queueing networks: A heavy traffic conjecture. In Stochastic Networks. IMA Vol. Math. Appl.71 1–20. Springer, New York. · Zbl 0838.90045 |

[13] | Harrison, J. M. and Shepp, L. A. (1981). On skew Brownian motion. Ann. Probab.9 309–313. · Zbl 0462.60076 |

[14] | Harrison, J. M. and Williams, R. J. (1996). A multiclass closed queueing network with unconventional heavy traffic behavior. Ann. Appl. Probab.6 1–47. · Zbl 0865.60078 |

[15] | Hu, Q., Wang, Y. and Yang, X. (2012). The hitting time density for a reflected Brownian motion. Comput. Econ.40 1–18. · Zbl 1282.60080 |

[16] | Ichiba, T., Karatzas, I., Prokaj, V. and Yan, M. (2018). Stochastic integral equations for Walsh semimartingales. Ann. Inst. Henri Poincaré Probab. Stat.54 726–756. · Zbl 1391.60090 |

[17] | Kruk, Ł. (2011). An open queueing network with asymptotically stable fluid model and unconventional heavy traffic behavior. Math. Oper. Res.36 538–551. · Zbl 1242.60094 |

[18] | Lambert, A. and Simatos, F. (2014). The weak convergence of regenerative processes using some excursion path decompositions. Ann. Inst. Henri Poincaré Probab. Stat.50 492–511. · Zbl 1291.60179 |

[19] | Nasser, N., Al-Manthari, B. and Hassanein, H. (2005). A performance comparison of class-based scheduling algorithms in future UMTS access. In IPCCC 2005. 24th IEEE International 437–441. IEEE, New York. |

[20] | Plambeck, E., Kumar, S. and Harrison, J. M. (2001). A multiclass queue in heavy traffic with throughput time constraints: Asymptotically optimal dynamic controls. Queueing Syst.39 23–54. · Zbl 1002.90015 |

[21] | Protter, P. E. (2004). Stochastic Integration and Differential Equations: Stochastic Modelling and Applied Probability, 2nd ed. Applications of Mathematics (New York) 21. Springer, Berlin. · Zbl 1041.60005 |

[22] | Rogers, L. C. G. (1983). Itô excursion theory via resolvents. Z. Wahrsch. Verw. Gebiete63 237–255. · Zbl 0528.60073 |

[23] | Salisbury, T. S. (1986). Construction of right processes from excursions. Probab. Theory Related Fields73 351–367. · Zbl 0587.60068 |

[24] | Tsirelson, B. (1997). Triple points: From non-Brownian filtrations to harmonic measures. Geom. Funct. Anal.7 1096–1142. · Zbl 0902.31004 |

[25] | Varopoulos, N. T. (1985). Long range estimates for Markov chains. Bull. Sci. Math. (2) 109 225–252. · Zbl 0583.60063 |

[26] | Walsh, J. B. (1978). A diffusion with a discontinuous local time. Astérisque52 37–45. |

[27] | Whitt, W. (1971). Weak convergence theorems for priority queues: Preemptive-resume discipline. J. Appl. Probab.8 74–94. · Zbl 0215.53801 |

[28] | Williams, R. · Zbl 0855.60083 |

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.