2/21/2013 Elise King, CSL Communications
Written by Elise King, CSL Communications
CSL graduate student Qiaomin Xie and Assistant Professor Yi Lu recently won the Best Paper Award at the PERFORMANCE 2011 Conference for their paper, titled, “A Novel Load Balancing Algorithm for Dynamically Scalable Web Services.”
Xie is a Ph.D. candidate in electrical and computer engineering, while Lu is an ECE assistant professor.
The goal behind this research is to maintain short response times for data-intensive web services such as search engines and social networks, as delays in response times result in a loss of users and revenue.
A load balancing algorithm is used to reduce the response times for web services. However, existing algorithms with a centralized design fall short for large-scale data centers with distributed software dispatchers, so Lu and Xie proposed a novel algorithm in their paper.
In traditional small web server farms, a centralized hardware load balancer dispatches jobs to the processor with the least number of jobs using the Join-the-Shortest-Queve (JSQ) algorithm. But today, the need for dynamic scalability and divisibility among multiple tenants has motivated the use of distributed dispatchers in cloud data centers. The centralized JSQ algorithm becomes too complex as it incurs overwhelming communication overhead among dispatchers and servers.
Lu and Xie proposed in their paper to use a new algorithm, called Join-Idle-Queve (JIQ), which uses a randomized algorithm in the reverse direction from servers to dispatchers, in order to evenly distribute partial state information among the dispatchers. Lu and Xie found that when the same amount of work is performed to balance information instead of workload, the response time was improved 30-fold.
Xie and Lu co-authored the paper along with Gabriel Kliot, Alan Geller, James Larus and Albert Greenberg, who work at Microsoft. Lu began working with these other four members when she was at the Extreme Computing Group at Microsoft, and found that the current load balancing algorithm poses a real problem in cloud computing. The production groups at Microsoft are currently exploring potential deployment of the JIQ algorithm.
Both Lu and Xie started their research at CSL a year and a half ago. Lu’s research group focuses on “developing efficient architectures and algorithms for today’s large and complex networks such as the Internet, Cloud service data centers and social networks.”