Proceedings of IEEE Information Communications Conference (INFOCOM 2002)

Abstract

We investigate the distribution of the waiting time V in an M/G/1 processor sharing queue with traffic intensity /spl rho/ < 1. This queue represents a baseline model for evaluating efficient and fair network resource sharing algorithms, e.g. TCP flow control. When the distribution of job size B belongs to a class of subexponential distributions with tails heavier than e/sup -/spl radic/x/, it is shown that as x/spl rarr//spl infin/ P[V > x] = P[B > (1 - /spl rho/)x](1 + o(1)) Furthermore, we demonstrate that the preceding relationship does not hold if the job distribution has a lighter tail than e/sup -/spl radic/x/. This result provides a new tool for analyzing network congestion points with moderately heavy-tailed characteristics, e.g. log normal distributions, that have been recently empirically discovered in Web traffic. The accuracy of our approximation is confirmed with simulation experiments.

Related Articles