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

'Research supported by a Presidential Young Investigator award DDM-9158118 with matching funds from Draper Laboratory, and by the ARO under grant DAAL-03-92-G-0115. We consider a single class, acyclic network of G/G/1 queues. We impose some mild assump-tions on the service and external arrival processes and we characterize the large deviations behaviour of all the processes resulting from various operations in the network. For the net-work 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 Bernoulli splitting of a process to a number of processes. We also characterize the large deviations behaviour 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 inductively apply these results to obtain the large deviations behaviour of the wait-ing 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