Generalized Processor Sharing With Heavy Tails


Predrag Jelenkovic (joint work with Sem Borst and Onno Boxma of CWI)

COMET Group, Columbia University

Abstract

We analyze the asymptotic behavior of long-tailed traffic flows under the Generalized Procesor Sharing (GPS) discipline. GPS-based scheduling algorithms, such as Weighted Fair Queueing, have emerged as important mechanisms for achieving differentiated quality-of-service in integrated networks. We prove that, in certain scenarios, a flow may be strongly affected by the activity of `heavier'-tailed flows, and inherit their traffic characteristics, causing induced burstiness. This phenomenon contrasts with a previous result which shows that, under certain conditions, an individual flow with long-tailed traffic characteristics is effectively served at a constant rate. The latter rate only depends on the traffic characteristics of the other flows through their average rate. In particular, the flow is then essentially immune from excessive activity of flows with `heavier'-tailed traffic characteristics. The stark contrast in qualitative behavior illustrates the crucial importance of selecting proper GPS weights in protecting individual flows.

Predrag Jelenkovic's home page