基于層次策略的動態(tài)負載均衡算法研究.pdf

1、隨著計算機及網(wǎng)絡技術的發(fā)展，大規(guī)模并行分布式處理系統(tǒng)得到了廣泛的應用。對于一個分布式系統(tǒng)而言，多個節(jié)點之間如何進行動態(tài)的任務分配調度，即動態(tài)負載均衡，在很大程度上影響著系統(tǒng)的性能，因而具有較高的理論研究價值和應用前景，受到了人們長期的關注。近年來，各國研究人員對此進行了大量的研究，提出了一系列的動態(tài)負載均衡算法。但這些算法并沒有完全解決目前存在的問題，因此仍有必要對分布式系統(tǒng)的動態(tài)負載均衡進行進一步的研究。 本文對負載均衡所涉及

2、的各個方面，包括概念、分類、特點、算法機制、驅動策略、難點、算法步驟等進行了詳細的討論，總結了負載均衡的研究現(xiàn)狀，同時還重點分析比較了現(xiàn)有的多個靜態(tài)和動態(tài)負載均衡算法，指出了它們各自的特點和缺陷。 在上述討論的基礎之上，本文從網(wǎng)絡基礎體系結構——拓撲出發(fā)，通過對常見的網(wǎng)孔、超立方和網(wǎng)狀拓撲進行邏輯上的改造，根據(jù)本文中所給法則將物理拓撲劃分為多個物理區(qū)域并指定每個區(qū)域的信息中心節(jié)點，必要時對這些信息中心節(jié)點組成的二級邏輯分區(qū)再指定

3、二級信息中心節(jié)點，依此類推，最后使得物理拓撲形成邏輯上的層次結構。通過推導和計算可以證明，網(wǎng)絡上的通信經(jīng)這樣的層次處理后，能夠從局部區(qū)域擴展到整體，確實減少了很多基礎的通信開銷。 基于上述的層次方法，本文提出了一個新的動態(tài)負載均衡算法，能夠較好解決已有算法的諸如穩(wěn)定性不夠、應用比較單一、通用性不夠等缺陷和不足。在此基礎之上，本文還提出了一個基于預測的算法機制，該機制能夠應用于均衡算法使得節(jié)點負載信息能夠被準確及時的獲取，從而為任

4、務的遷移提供更好的依據(jù)；并由此建立了一個基于預測的層次負載均衡模型。算法的主要思想是通過各個局部區(qū)域的優(yōu)化達到系統(tǒng)整體的接近最優(yōu)化并特別考慮了任務之間的相互關系和系統(tǒng)內節(jié)點性能可能存在的差異；算法還通過改進傳統(tǒng)的驅動策略，使用新的任務調度規(guī)則，在改善底層通信的基礎上，使得系統(tǒng)減少了較多的額外開銷，提高了算法的效率。該算法的主要特點是： (1)自適應參數(shù)可調。算法不是單一的使用某種驅動策略，而是在系統(tǒng)運行過程中動態(tài)調整負載閾值和參

5、數(shù)，視用戶對系統(tǒng)的要求選擇參數(shù)值，從而獲得更好的性能表現(xiàn)。 (2)系統(tǒng)穩(wěn)定，不會出現(xiàn)顛簸。算法中局部區(qū)域的使用，使得節(jié)點處理機上任務的遷移首先在內部區(qū)域上進行，必要時再進行區(qū)域之間的遷移；同時算法改進了以往的驅動策略，遷移必須從重載節(jié)點到輕載節(jié)點，目的性強，避免了一些效率不高的遷移和對節(jié)點不必要的打擾。 (3)簡單實用。算法沒有采用基于人工智能理論等耗費較大的調度方法，而是使用局部優(yōu)化帶動全局優(yōu)化的思想方法和較有針對性的

6、“極端”任務調度方法，除了增加一定空間耗費和任務遷移本身帶來的通信路徑上的開銷外，額外開銷比較少。 (4)具有較好的通用性。算法可以適用于目前最常見的網(wǎng)孔和超立方拓撲構成的同構、異構分布式系統(tǒng)，也可以推廣到最一般的網(wǎng)狀拓撲。 論文還通過實驗比較和實例分析驗證了層次策略負載均衡算法的正確性和有效性。因此，本文提出的層次策略負載均衡算法確實能夠比較有效和靈活地解決分布式系統(tǒng)的負載均衡問題，從而彌補了現(xiàn)有算法存在的一些缺陷。