網(wǎng)格環(huán)境下的分布式負載均衡算法研究

網(wǎng)格環(huán)境下的分布式負載均衡算法研究

1網(wǎng)格環(huán)境負載均衡網(wǎng)格計算是一種新的分布計算方法。目標是在網(wǎng)絡環(huán)境中建立一個虛擬組織，并通過內(nèi)部空間的資源共享和合作，以滿足復雜應用程序中大規(guī)模計算的需求。但是由于網(wǎng)格中各站點的處理能力和容量不均衡,作業(yè)的到達模式不一致,從而造成有的站點大量的資源被閑置,有的站點卻負載過重,這就要解決網(wǎng)格環(huán)境下負載均衡的問題。網(wǎng)格環(huán)境的主要特性有:可擴展性、異構(gòu)性以及大量的傳輸延遲,負載均衡算法要達到兩個目標:第一,提高資源利用率;第二,降低平均作業(yè)響應時間。這就要求負載均衡算法能夠動態(tài)預測各站點負載狀況,使新到達的作業(yè)可以被委派到空閑的站點或者負載較輕的站點;另一方面,對處理能力強的站點委派較多的作業(yè)。提出的負載均衡算法綜合考慮了網(wǎng)格站點的負載狀況和處理能力。對于網(wǎng)格中的每個站點,根據(jù)處理能力和傳輸延遲,創(chuàng)建網(wǎng)格站點集群,從而解決負載委派和作業(yè)再分配。在負載均衡算法中,通過創(chuàng)建站點負載指數(shù)表來緩存同伴站點的負載信息,從而減少了負載預測時的傳輸成本。通過仿真實驗分析了該分布式動態(tài)負載均衡算法的性能,從實驗結(jié)果來看,該算法有效地降低了作業(yè)平均響應時間。2系統(tǒng)模型2.1網(wǎng)格層作業(yè)調(diào)度器的結(jié)構(gòu)網(wǎng)格系統(tǒng)是由多個計算結(jié)點組成,這些計算結(jié)點可以是個人主機、工作站、超級計算機等,各計算結(jié)點是異構(gòu)的,它們的體系結(jié)構(gòu)、操作系統(tǒng)、處理能力可能各不相同,這就需要一種具有負載均衡功能的作業(yè)調(diào)度程序根據(jù)各計算結(jié)點處理能力的差異來分配作業(yè),所以采用三層網(wǎng)格體系結(jié)構(gòu):網(wǎng)格層、站點層、結(jié)點層,分別表示為G層、S層、N層。網(wǎng)格層作業(yè)調(diào)度器負責網(wǎng)格站點之間的負載控制,G層由網(wǎng)絡互聯(lián)的站點集和S組成,G=(s網(wǎng)格站點的處理能力是由其包含的計算結(jié)點決定的,可以表示為該站點內(nèi)各計算結(jié)點的平均CPU處理速度。網(wǎng)格系統(tǒng)的異構(gòu)性決定了各站點在處理能力上可能各不相同。例如,站點s2.2通信模型如果消息在兩個站點對(s2.3作業(yè)陣列的執(zhí)行對任意站點s假設在每一個站點有一個全局等候作業(yè)隊列,隊列中的作業(yè)等待被委派到該站點下的某個計算結(jié)點執(zhí)行。只有在全局等候作業(yè)隊列中作業(yè)才可以被負載遷移,用GJQ(s3實時負載分配算法動態(tài)負載均衡算法根據(jù)一定的位置策略可以分為發(fā)送方觸發(fā)、接收方觸發(fā)、對稱觸發(fā)算法3.1差異網(wǎng)點選擇在網(wǎng)格系統(tǒng)中,各站點s的處理能力存在較大差異,通過站點集群算法產(chǎn)生處理能力相當?shù)恼军c集群。算法隨機選擇m個處理能力存在較大差異的站點作為引用站點集S。這種選擇方法是出于一種直覺,即如果各站點的處理能力相當,則距離接近。相似的一些方法也已經(jīng)被廣泛采用在應用站點集群方法之前,被引用的站點首先按照APW降序排列。對每個網(wǎng)格站點s上述方法只是一個近似方法,在度量近距離網(wǎng)格站點時,效果不佳,但通過實驗發(fā)現(xiàn),該方法卻適合于該文所研究的負載均衡,這是因為負載均衡不需要精確度量,下面就是如何用C3.2本地網(wǎng)點負載指數(shù)設計定義1同伴站點調(diào)度程序利用站點集群方法為站點s當一新站點進入網(wǎng)格系統(tǒng)時,調(diào)度程序首先為該站點尋找同伴站點集PSet,根據(jù)站點處理能力采用一種啟發(fā)式的方法尋找同伴站點,一般選擇比本地站點處理能力更強的站點作為同伴,主要考慮異構(gòu)站點。本地站點加入同伴站點集后,向鄰接的同伴站點發(fā)送請求得到鄰接同伴站點的負載指數(shù)消息,并把本地站點的負載指數(shù)發(fā)送到各鄰接同伴站點。本地站點維護一個按負載指數(shù)從大到小排列的鄰接同伴隊列Q定義2負載指數(shù)設計動態(tài)負載均衡算法的一個很重要的問題是如何確定負載指數(shù)來度量當前某個站點的負載情況,Kunz?sTET定義3執(zhí)行成本傳統(tǒng)方法在計算結(jié)點上作業(yè)的執(zhí)行成本時只考慮負載指數(shù),但是在網(wǎng)格環(huán)境下作業(yè)在執(zhí)行前輸入數(shù)據(jù)、傳輸過程中的通信成本、作業(yè)執(zhí)行完輸出結(jié)果,不同作業(yè)在這些方面所花費的時間成本差異較大,這也對負載均衡算法造成顯著影響,所以在計算作業(yè)執(zhí)行成本時也要考慮這些因素。如果某計算結(jié)點的負載較重,但作業(yè)到該結(jié)點的通信成本較低,則作業(yè)發(fā)送到該結(jié)點執(zhí)行的效率可能更高。?sIT(j定義4執(zhí)行受益率當作業(yè)j3.3兩組項負載指數(shù)和負載指數(shù)每個網(wǎng)格站點中都保存一個負載指數(shù)表,該表包含兩個數(shù)組項,即負載指數(shù)和負載指數(shù)采樣時間點。初始化時,利用站點集群策略構(gòu)造多集群網(wǎng)格系統(tǒng)G的同伴站點集PSet,G=(PSet當站點s算法1是s算法14負載均衡優(yōu)化在具有較多異構(gòu)站點的網(wǎng)格環(huán)境下,通過變化不同的系統(tǒng)負載,采用該文給出的算法,仿真結(jié)果如圖3所示。主要的參數(shù)ρ是平均系統(tǒng)負載,ρ=平均作業(yè)到達率/平均作業(yè)處理率,通過調(diào)整作業(yè)到達的平均時間間隔1/λ來獲取該參數(shù)。圖3顯示了如下4種作業(yè)調(diào)度算法在不同系統(tǒng)負載情況下,平均作業(yè)響應時間之間的差距。(1)Local:所有作業(yè)在源站點處理(2)Random:隨機選擇一個站點處理新到達的作業(yè)(3)Best-Neighbor負載均衡算法(表示為BN):新到達的作業(yè)在源站點或鄰居站點處理,不斷地在鄰居站點之間調(diào)整負載,如果源站點負載過重,則新作業(yè)被重新委派到一個鄰居站點。實驗中比較了該算法和Local算法、隨機選擇算法(用Random表示)、BN負載均衡算法在處理負載均衡時的效率。由圖3可以觀察出,負載較高時,4種算法的平均響應時間ART都較高。當平均系統(tǒng)負載逐漸增高時,4種算法的ART的差距逐漸增大,這是因為,系統(tǒng)負載較高時,該文的算法(用DLB表示)把新到達的作業(yè)分派到處理速度更高、負載最低的同伴站點處理,這樣就減少了平均作業(yè)響應時間,所以DLB算法的執(zhí)行效率更高。5動態(tài)負載均衡算法網(wǎng)格作為一種新型的分布式計算環(huán)境,不同于傳統(tǒng)的分布式計算系統(tǒng),主要表現(xiàn)在網(wǎng)格具有可擴展性、異構(gòu)性以及大量的通信延遲,這些特征也對網(wǎng)格環(huán)境下的負載均衡造成顯著影響,為了解決這些問題,提出了一種分散的動態(tài)負載均衡算法。通過仿真,比