In this paper we examine the problem of balancing load in alarge-scale distributed system when information about server loads maybe stale. It is well known that sending each request to the machine withthe apparent lowest load can behave badly in such systems, yet thistechnique is common in practice. Other systems use round-robin or randomselection algorithms that entirely ignore load information or that onlyuse a small subset of the load information. Rather than risk extremelybad performance on one hand or ignore the chance to use load informationto improve performance on the other, we develop strategies thatinterpret load information based on its age. Through simulation, weexamine several simple algorithms that use such load interpretationstrategies under a range of workloads. Our experiments suggest that byproperly interpreting load information, systems can (1) match theperformance of the most aggressive algorithms when load information isfresh relative to the job arrival rate, (2) outperform the best of theother algorithms we examine by as much as 60% when information ismoderately old, (3) significantly outperform random load distributionwhen information is older still, and (4) avoid pathological behavioreven when information is extremely old
展开▼
