Web users are notoriously impatient, willing to wait only a few seconds
before aborting a pending web request. This behavior unnecessarily taxes web
server resources, which are dedicated to a connection that ultimately does not
complete. While this is not as problematic at well-provisioned or
lightly-trafficked web servers, where all incoming requests can be serviced with
little or no queuing time required, such behavior is extremely detrimental to
poorly-provisioned or very busy web servers, where server deadlock may occur and
no users are adequately served.
In this work, we analytically derive, using queuing models, a service
ordering for web servers that is useful under these extreme conditions and that
takes into account the impatience of web users. The ordering is based on a
revenue generation model that assumes a web server earns some amount from
processing a user request to completion. This amount diminishes exponentially
with the time spent in queue and in service at the web server. In such cases, a
greedy algorithm maximizes server revenue and outperforms "fair" algorithms such
a first-in-first-out by several orders of magnitude when server load is high.
These performance gains continue even when the server passes into an overload
situation, allowing the web server to operate even when completely saturated.
These results are verified both analytically and via simulation, and have been
shown to be useful for general Markovian queuing systems as well.
An Optimal Service Ordering for a World
Wide Web Server (with A.C. Dalal), ACM Performance Evaluation Reviews,
vol. 29 no. 2, September 2001, pp. 8-13.
Optimal Scheduling in a Queue with
Differentiated Impatient Users (with A.C. Dalal), Performance
Evaluation, vol. 59 no. 1, January 2005, pp. 73-84.
Portions of this work were supported by NSF.
Any opinions, findings, conclusions or recommendations expressed in this
material are those of the author(s) and do not necessarily reflect the views of
the National Science Foundation or IEEE. This material is presented to ensure
timely dissemination of scholarly and technical work. Copyright and all rights
therein are retained by authors or by other copyright holders. All persons
copying this information are expected to adhere to the terms and constraints
invoked by each author's copyright. One print or electronic copy may be made for
personal use only. Permission must be obtained from the copyright holder for
systematic or multiple reproduction, distribution to multiple locations via
electronic or other means, duplication of any material in these papers for a fee
or for commercial purposes, modification of the content of these papers,
reprinting or republishing of this material for advertising or promotional
purposes or for creating new collective works for resale or redistribution to
servers or lists, and to reuse any copyrighted component of this work in other