On the large deviations behavior of acyclic networks of G/G/1 queues

• 成果类型: Article
• 署名作者: Bertsimas, D; Paschalidis, IC; Tsitsiklis, JN
• 署名单位: Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Boston University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• 发表日期: 1998
• 页码: 1027-1069
• 关键词: intree networks; delay; calculus

摘要

We consider a single class, acyclic network of G/G/1 queues. We impose some mild assumptions on the service and external arrival processes and we characterize the large deviations behavior of all the processes resulting from various operations in the network. For the network model that we are considering, these operations are passing-through-a-single-server-queue (the process resulting from this operation being the departure process), superposition of independent processes and deterministic splitting of a process into a number of processes; We also characterize the large deviations behavior of the waiting time and the queue length observed by a typical customer in a single server queue. We prove that the assumptions imposed on the external arrival processes are preserved by these operations, and we show how to apply inductively these results to obtain the large deviations behavior of the waiting time and the queue length in all the queues of the network. Our results indicate how these large deviations occur, by concretely characterizing the most likely path that leads to them.