Multi-layered round robin routing for parallel servers |
| |
Authors: | Douglas G Down Rong Wu |
| |
Institution: | (1) Department of Computing and Software, McMaster University, 1280 Main Street West, Hamilton, ON, L8S 4L7, Canada |
| |
Abstract: | We study a system of several identical servers in parallel, where a routing decision must be made immediately on a job’s arrival.
Jobs arrive according to a Poisson process, with their processing times following a discrete distribution with finite support.
The processing time of a job is known on arrival and may be used in the routing decision. We propose a policy consisting of
multi-layered round robin routing followed by shortest remaining processing time scheduling at the servers. This policy is
shown to have a heavy traffic limit that is identical to one in which there is a single queue (no routing) and optimal heavy
traffic scheduling. In light traffic, we show that the performance of this policy is worse than round robin routing followed
by shortest remaining processing time scheduling. We also quantify the difference between round robin and multi-layered round
robin routing, which in turn yields insights on the relative importance of routing versus (local) scheduling in such systems.
AMS subject classifications: 68M20 · 60K25
(Work done while both authors were visitors at EURANDOM, P.O. Box 513, 5600 MB Eindhoven, The Netherlands.) |
| |
Keywords: | Parallel servers Round robin routing Heavy traffic Light traffic Shortest remaining processing time scheduling |
本文献已被 SpringerLink 等数据库收录! |
|