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.

By: Nikhil Bansal, David Gamarnik

Published in: RC23277 in 2004


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .