Asymptotic regimes and approximations for Discriminatory Processor Sharing

Rudesindo Nunez-Queija

CWI Amsterdam, The Netherlands


The Discriminatory Processor Sharing (DPS) model was originally introduced by Kleinrock in 1967 as a multi-class extension of the ordinary (egalitarian) Processor Sharing (PS) model. The adoption of PS as a modeling abstraction of TCP bandwidth sharing Massoulie & Roberts [1999] triggered a renewed interest in the analysis of PS models. The PS discipline assumes a perfectly egalitarian distribution of the bandwidth among all active flows. Because of TCP's distributed nature, however, the actual shares of flows sharing a common (bottleneck) link may show strong asymmetry. The DPS discipline provides a natural approach for modeling the flow-level performance of such heterogeneous TCP flows. The service capacity is shared among all users according to fixed class-dependent weight factors. When all weight factors are equal, the DPS discipline reduces to the egalitarian PS policy. The analysis of the DPS discipline is extremely difficult compared to that of ordinary PS. Most notably, the simple geometric queue length distribution for the standard PS discipline does not have any counterpart for DPS. Fayolle, Mitrani & Iasnogorodski [1980] obtained the conditional mean sojourn times as the solution of a system of integro-differential equations. For the case of exponentially distributed service requirements, they derived closed-form expressions and also determined the unconditional mean sojourn times from a system of linear equations. For exponentially distributed service requirements, Rege & Sengupta [1996] extended this result and obtained higher moments of the queue length distribution as solutions of linear equations. Rege & Sengupta also proved a heavy-traffic limit theorem under the same assumptions. In this talk we extend these results to phase-type distributions. In addition, we use the theory of nearly-completely decomposable Markov Chains to study DPS, assuming a strict separation of time scales among the different user classes.

This is a joint work with Gijs van Kessel and Sem Borst.

[Rudesindo Nunez-Queija]
[CWI Amsterdam, The Netherlands]