以Small World演算法改善異質分散式系統間之動態負載平衡

Abstract

當在異質分散式系統網路當中，每個節點所擁有的計算能力不見得相同，所以每個節點所可以處理的訊息量也因此不同，所以如何設計出一個好的演算法能夠動態調整每個節點之間的負載平衡就顯得相當重要，讓整個異質分散式系統網路當中，可以處理最大的資訊量。因此，本論文將提出一個以Small World演算法為基礎，用以改善異質分散式網路系統的效能，其中包括，改善每個節點之間的負載平衡、以及改善整個異質分散式網路的節點數量藉此改善網路的大小與改善節點彼此之間的通訊成本。在影響負載平衡的原因，像是migration的機制、重新調整每個節點的workload，為此，我們所提出得演算法可以根據這些影響負載平衡的因素與整體網路的結構來改善整個分散式系統網路節點間的負載平衡. 我們首先針對在異質分散式系統網路的負載平衡設計了一個Overlay Network叫Functional Small World (FSW)。而這個FSW主要用來改善每個Node之間需要進行負載平衡時需要交換的資訊量，用來減低彼此互相溝通的通訊成本與縮減網路結構的大小以及透過tasks remigration process來減低延遲。接著我們的負載平衡演算法將會改善所建立得FSW網路，透過考量每個節點的平均負載能力. 在實驗與分析部分，我們將所提出得演算法與兩個較具代表性的演算法進行比較，分別為Nearest Neighbor Algorithm與Neighborhood Algorithm. 而所模擬得結果可以得知，我們所提出得演算法在response time、throughput、communication overhead與movements cost得比較上均較其他方法有著更顯著的改善。根據實驗的結果，我們可以證明所設計得演算法可以讓每個異質分散式系統網路的節點，可以根據他們的能力取得適當的工作量. 進而達到異質分散式系統網路每個節點之間的負載平衡的成效.

Load-balancing algorithms play a key role in improving the performance of distributed computing systems that consist of heterogeneous nodes with different capacities. The performance of load balancing algorithms and its convergence rate deteriorate as the number of nodes in the system, the network-diameter, the communication-overhead increase. Moreover, the load-balancing technical factors, such as the load migration rule, significantly affect the performance of rebalancing the load among nodes. Therefore, we propose an approach that improves the performance of load-balancing algorithms by considering both the load-balancing technical-factors and the structure of the network that executes the algorithm. We present the design of an overlay network, namely, Functional Small World (FSW) that facilitates efficient load-balancing in heterogeneous systems. FSW is based on two innovative ideas: 1) small world network; and 2) functional similarity. Nodes in FSW are clustered according to the similarity of their Functional Sets (FS) and organized as a small world overlay network. The FSW achieves the efficiency by reducing the number of nodes that exchange their information, deteriorating the network diameter, minimizing the communication-overhead, and decreasing the time-delay results from tasks re-migration process. We then propose an improved load-balancing algorithm that will be effectively executed within the constructed FSW, where nodes consider the capacity and calculate the average effective-load. We compare our approach with two significant diffusion methods presented in the literature, the nearest neighbor algorithm and the original neighborhood algorithm. The simulation results indicate that our approach considerably outperformed the mentioned approaches in terms of response time, throughput, communication overhead, and movements cost. Finally, we prove that the proposed approach converges to the state of fairness where the effective-load in all nodes is the same since each node receives an amount of workload proportional to its processing capacity. Therefore, we conclude that this approach has the advantage of being fair, simple and no node is privileged.