Copyright © (2004) by Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distrubuted for profit or commericial advantage. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.
In this paper we consider the fundamental problem of routing customers among multiple distributed parallel queues to minimize an objective function based on equilibrium sojourn times, which arises in a wide variety of distributed computer systems, networks and applications. We derive optimal solutions to this theoretical scheduling problem under general assumptions for the arrival and service processes through stochastic-process limits. Our analysis extends previous studies by providing explicit solutions for the optimal scheduling problem and by considering general single-server queues, including correlated arrivals, under both first-come first-serve and processor-sharing queueing disciplines. In addition, we derive bounds for the variance of customer waiting times and exploit these results in order to obtain optimal solutions to the scheduling problem of interest based on equilibrium sojourn times subject to constraints on the waiting time variance, which have been ignored in previous studies. This collection of results allow us to cover risk factors and incorporate risk management within the context of our optimal scheduling problem. Numerical experiments with data from a real Web server system demonstrate the potential benefits of our theoretical results and methods in practice.
By: Xin Guo; Yingdong Lu; Mark S. Squillante
Published in: ACM SIGMETRICS Performance Evaluation Review, volume 32, (no 2), pages 53-4 in 2004
LIMITED DISTRIBUTION NOTICE:
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 .