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

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

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

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

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

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

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