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

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

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

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

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

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

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