針對異質多資源系統以代幣為基礎之負載平衡演算法

Abstract

網際網路由於讓使用者可以使用不同的線上資源像是執行個人化的應用程式，瀏覽與發佈網頁內容，與朋友及同事溝通，逐漸與人們的生活變得密不可分。從伺服器的角度來看，提供這些網際服務，為了同時維持另人滿意的服務品質，需要充份的計算資源與數種其他像記憶體、磁碟儲存空間及網路頻寬等資源。當所提供的服務數目增加，並且使用者偏好程度彼此之間有差異時，如何兼顧其服務品質與避免使用過多的計算機資源於是變得具有挑戰性。現在以網站為主的系統藉由在多台伺服器之間分散使用者的工作來運作負載平衡，然而，大部份這些技術考慮的是擁有相同資源數的同質系統伺服器環境。由於不同的服務對不同的資源的要求不同，且不同工作的比例也隨著時間而有差異，這些平衡負載的技術可能不能最佳地運作，而造成不必要的資源競爭。我們先前研究過在傳統資源排程的環境下，機器有不同的資源分布時負載平衡的問題，並且提出一以市場為主的方法來有效地減少因資源分配不平衡而產生的系統瓶頸。這篇論文中，我們延伸先前的研究，但是集中在工作執行時間短、數量極大的網站為主的系統。為了使用以市場為主的方法，我們提出一個以代幣為主的方法。伺服器不再以工作為基礎作交換，而是將代表工作量及特定多資源要求的代幣為基礎作交換，我們的目標是平衡伺服器的負載，以及有效地使用所有可用的系統資源。我們設定許多不同的系統設定，並作了廣泛的模擬實驗，並比較我們的方法與現存負載平衡的方法。結果顯示我們的方法提供了維持在一定水平的效能改進，在相同的工作產出下能使用更少數目的伺服器。

The Internet has become an indispensible media where people access various on-line services, such as executing personalized applications, browsing and publishing web contents, communicating with friends and co-workers, and so on. From the server-side perspective, providing an Internet service requires sufficient CPU power as well as other kinds of resources such as memory, disk space, and network bandwidth, in order to maintain satisfactory service quality. When the kinds of services increase and their popularity vary, how to ensure quality of service without acquiring excessive computing resources becomes a challenge. Modern web-based systems employ various load balancing techniques in order to spread user requests among multiple machines. However, most of these techniques assume that servers are homogenous with similar resource capacities. Because different services impose different requirements on different kinds of resources, and the request rates for different services are also different, these load balancing techniques may not operate optimally and result in unnecessary resource contention. We have studied the problem of load balancing among machines with heterogeneous resource capacities in a traditional resource scheduling context, and proposed a market-based approach to effectively reducing unnecessary system bottleneck. In this thesis, we extend the previous study but focus on web-based systems, where requests tend to be small in processing time but large in volume. To apply the same market-based principle, we propose a token-based approach in which the servers do not exchange load on a per-request basis, but rather on a token basis where each token represents a workload with specific multi-resource requirements. Our goal is to balance the server load and to make efficient use of all the available system resources. We have conduct extensive simulation under different system configurations and compare our method with existing load balancing schemes. The results showed that our approach provides substantial performance improvement, capable of delivering equivalent system throughput with fewer machines.