Abstract
We study how the average performance of a system degrades as the load nears its peak capacity. We restrict our attention to the performance measures of average sojourn time and the large deviation rates of buffer overflow probabilities. We first show that for certain queueing systems, the average sojourn time of requests depends much more weakly on the load ρ than the commonly observed 1/(1-ρ) dependence for most queueing policies. For example, we show that for an M/G/1 system under the preemptive Shortest Job First (pSJF) policy, the average sojourn time varies as log (1/(1-ρ)) with load for a certain class of distributions. We observe that such results hold even for more restricted policies. We give some examples of non-preemptive policies and policies that do not use the knowledge of job sizes while scheduling, where the dependence of average sojourn time on load is significantly better than 1/(1-ρ). Similar results hold even for very simple non-preemptive threshold based policies that partition all the jobs into two job classes based on a fixed threshold and do FIFO within each class. Finally we study the large deviations rate of the queue length under a simple dedicated partition-based policy. © Springer Science + Business Media, LLC 2006.