Bridges and networks: Exact asymptotics

• 成果类型: Article
• 署名作者: Foley, RD; McDonald, DR
• 署名单位: University System of Georgia; Georgia Institute of Technology; University of Ottawa
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/105051604000000675
• 发表日期: 2005
• 页码: 542-586
• 关键词: limit-theorem; markov-chains; random-walk; parallel; queues

摘要

We extend the Markov additive methodology developed in [Ann. Appl. Probab. 9 (1999) 110-145, Ann. Appl. Probab. 11 (2001) 596-607] to obtain the sharp asymptotics of the steady state probability of a queueing network when one of the nodes gets large. We focus on a new phenomenon we call a bridge. The bridge cases occur when the Markovian part of the twisted Markov additive process is one null recurrent or one transient, while the jitter cases treated in [Ann. Appl. Probab. 9 (1999) 110-145, Ann. Appl. Probab. 11 (2001) 596-607] occur when the Markovian part is (one) positive recurrent. The asymptotics of the steady state is an exponential times a polynomial term in the bridge case, but is purely exponential in the jitter case. We apply this theory to a modified, stable, two node Jackson network where server two helps server one when server two is idle. We derive the sharp asymptotics of the steady state distribution of the number of customers queued at each node as the number of customers queued at the server one grows large. In so doing we get an intuitive understanding of the companion paper [Ann. Appl. Probab. 15 (2005) 519-541] which gives a large deviation analysis of this problem using the flat boundary theory in the book by Shwartz and Weiss. Unlike the (unsealed) large deviation path of a Jackson network which jitters along the boundary, the unscaled large deviation path of the modified network tries to avoid the boundary where server two helps server one (and forms a bridge). In the fluid limit this bridge does collapse to a straight line, but the proportion of time spent on the flat boundary tends to zero. This bridge phenomenon is ubiquitous. We also treated the bathroom problem described in the Shwartz and Weiss book and found the bridge case is present. Here we derive the sharp asymptotics of the steady state of the bridge case and we obtain the results consistent with those obtained in [SIAM J. Appl. Math. (1984) 44 1041-1053] using complex variable methods.