Handling Load with Less Stress

In this work we study how the average performance of a system degrades as the load nears its peaks capacity. We restrict our attention to the performance measures of average sojourn time and the large deviation rates of buffer overflow probabilities. While it is common knowledge that the average sojourn time in an M/M/1 system under FIFO varies as 1/1(1-p) with the load p, we show that it could be substantially better for other queueing systems. For example, we show that for an M/G/1 system where the job sizes have the Pareto distribution with < 2, the average sojourn time under the policy Shortest job first (SJF) varies only as log(1/(1 - p)) with load, which is an exponential improvement over the 1/(1 - p) dependence. We investigate this phenomenon further for other distributions and other policies.

We then study how much performance improvement can be obtained by policies which are more restricted. We first consider "blind" scheduling policies in M/G/1 type queueing systems, where a "blind" scheduling policy is one that has no knowledge of the sizes of jobs in hand and is thus restricted (for example, it cannot schedule jobs in the SJF fashion). We show that a logarithmic dependence on 1/(1 - p) is possible even for blind policies. Next, we consider even more restricted policies (that we call threshold based policies). Threshold based policies allow the jobs to be partitioned into two job classes, but cannot reorder jobs within a class and are essentially like FIFO. We show that these policies can also outperform the naive FIFO significantly. Finally we study these policies in the regime of large deviations rates asymptotics.