Task Assignment in a Distributed System: Improving Performance by Unbalancing Load
Crovella, Mark E.
Murta, Cristina D.
MetadataShow full item record
CitationCrovella, Mark; Harchol-Balter, Mor; Murta, Cristina. "Task Assignment in a Distributed System: Improving Performance by Unbalancing Load", Technical Report BUCS-1997-018, Computer Science Department, Boston University, October 31, 1997. [Available from: http://hdl.handle.net/2144/1618]
We consider the problem of task assignment in a distributed system (such as a distributed Web server) in which task sizes are drawn from a heavy-tailed distribution. Many task assignment algorithms are based on the heuristic that balancing the load at the server hosts will result in optimal performance. We show this conventional wisdom is less true when the task size distribution is heavy-tailed (as is the case for Web file sizes). We introduce a new task assignment policy, called Size Interval Task Assignment with Variable Load (SITA-V). SITA-V purposely operates the server hosts at different loads, and directs smaller tasks to the lighter-loaded hosts. The result is that SITA-V provably decreases the mean task slowdown by significant factors (up to 1000 or more) where the more heavy-tailed the workload, the greater the improvement factor. We evaluate the tradeoff between improvement in slowdown and increase in waiting time in a system using SITA-V, and show conditions under which SITA-V represents a particularly appealing policy. We conclude with a discussion of the use of SITA-V in a distributed Web server, and show that it is attractive because it has a simple implementation which requires no communication from the server hosts back to the task router.