Class-Dependent Assignment in Cluster-based Servers
Authors: Victoria Ungureanu, Phillip G. Bradford, Michael Katehakis, Benjamin Melamed
ABSTRACT
A cluster-based server consists of a front-end dispatcher and several
back-end servers. The dispatcher receives incoming requests, and then
assigns them to back-end servers for processing. Our goal is to
devise an assignment policy that has good response time performance,
and is practical to implement in that the amount of information
used by the dispatcher is relatively small, so that the attendant
computation and communication overheads are low. In contrast to
extant assignment policies that apply the same assignment policy to all
incoming jobs, our approach calls for the dispatcher to
classify incoming jobs as long or short, and then use class-dependent
assignment policies. Specifically, we propose a policy, called CDA
(Class Dependent Assignment), where short jobs are assigned
Round-Robin as soon as they arrive, while long jobs are deferred and
assigned only when a back-end server becomes idle. Furthermore, when
processing a long job, a back-end server is not assigned any other
jobs.
Our approach is motivated by empirical evidence suggesting that the
sizes of files traveling on the Internet follow power-law
distributions, where long jobs constituting a small fraction of all
incoming jobs actually account for a large fraction of the overall
load. To gauge the performance of the proposed policy, we exercised
it on empirical data traces measured at Internet sites serving the
1998 World Cup. Since the assignment of long jobs incurs
computational overhead as well as extra communication overhead, we
studied the performance of CDA as a function of the fraction of jobs
classified as long. Our study shows that classification of even a
small fraction of jobs as long can have a profound impact on overall
response time performance. More specifically, our experimental
results show that if less than 3% of the jobs are classified as long,
then CDA outperforms traditional policies, such as Round-Robin, by two
orders of magnitude. From an implementation viewpoint, these results
support our contention that CDA -based assignment is a practical
policy combining low overhead and greatly improved performance.
DIMACS Home Page