Large Deviations and the Generalized Processor Sharing Scheduling for a Multiple-Queue System

this paper, we study the asymptotic decay rate of the queue length tail distributions for the sessions sharing a GPS server. The bandwidth sharing mechanism introduced by the GPS scheduling discipline makes understanding of its behavior a challenging task. In the special case where there are only two sessions sharing a two-queue GPS server, an exact analysis of the asymptotic decay rate of the queue length tail distributions for the two sessions is possible, and is presented in an earlier paper of ours [15] (see also [7]). When more than two sessions share a multiple GPS server, an exact analysis of the bandwidth sharing dynamics among the sessions becomes significantly more complex. In order to circumvent this difficulty, we take the decomposition approach devised in [17]. We introduce a key concept partial feasible sets which provides an avenue to capture the asymptotic bandwidth sharing dynamics among the sessions in the GPS system. With the help of this concept, we apply th