結(jié)構(gòu)化p2p中節(jié)點的負載不均衡

結(jié)構(gòu)化p2p中節(jié)點的負載不均衡

0基于網(wǎng)絡定位的負載均衡算法p2p是一個分布系統(tǒng)，參與者共享他們擁有的資源。這些共享資源可以直接訪問其他節(jié)點，而不需要經(jīng)過中間節(jié)點。網(wǎng)絡中的參與者既是資源(服務和內(nèi)容)提供者,又是資源(服務和內(nèi)容)獲取者。P2P技術(shù)使得網(wǎng)絡上的溝通變得更容易、更直接。P2P改變了目前Internet以太網(wǎng)站為中心的狀態(tài),重返非中心化,并把權(quán)利交還給用戶。P2P系統(tǒng)一般分為非結(jié)構(gòu)化和結(jié)構(gòu)化兩種。近年來,基于DHT的結(jié)構(gòu)化P2P系統(tǒng)以其嚴格的節(jié)點組織規(guī)則,良好的容錯能力、可擴展性和查找速度等,得到了廣泛的應用(如Chord、Pastry、Tapestry和CAN)。結(jié)構(gòu)化P2P系統(tǒng)利用相容hash函數(shù)把資源關(guān)鍵字隨機分配在各對等節(jié)點中,從而各節(jié)點以很高的概率分配到相同數(shù)目的關(guān)鍵字。文獻表明這種情況下,一個節(jié)點所負責的關(guān)鍵字數(shù)可能是其他節(jié)點的O(logN)倍(N是系統(tǒng)的總節(jié)點數(shù))。另外,它們假設系統(tǒng)各節(jié)點的能力是一樣的。但文獻表明P2P系統(tǒng)中各節(jié)點的能力(CPU處理能力、存儲能力、網(wǎng)絡連接能力等)有很大的差異。所以必須進行負載均衡,使能力強的節(jié)點處理更多的任務。本文針對以上問題,以Chord算法為基礎,提出了基于網(wǎng)絡定位的負載均衡算法。算法利用網(wǎng)絡定位技術(shù)產(chǎn)生系統(tǒng)中各節(jié)點的距離信息,使負載在物理位置相近的節(jié)點間進行轉(zhuǎn)移,從而最小化帶寬和延遲的消耗,達到快速有效轉(zhuǎn)移負載的目的。該算法由負載較輕的節(jié)點負責主要的負載轉(zhuǎn)移操作,節(jié)省了過載節(jié)點的資源,提高了負載轉(zhuǎn)移質(zhì)量。1節(jié)點負載均衡現(xiàn)有的負載均衡算法,有的忽略了系統(tǒng)中節(jié)點負載能力的差異;有的在負載轉(zhuǎn)移時,沒有考慮節(jié)點間的位置關(guān)系;有的增加了系統(tǒng)的復雜性,減小了容錯能力。文獻沒有考慮節(jié)點能力的差異,給每個DHT節(jié)點都分配O(logN)個虛擬服務器試圖解決負載均衡問題。但根據(jù)經(jīng)典球盒問題(ballsandbinsproblem),這種方案下一些節(jié)點的負載可能是其他節(jié)點的O(logN/loglogN)倍,所以單純依靠虛擬服務器并不能完全解決這個問題。CFS根據(jù)節(jié)點本身的能力來分配虛擬服務器,考慮到了節(jié)點能力的差異。當一個節(jié)點過載時簡單地刪除它的部分虛擬服務器。此算法在刪除過載節(jié)點的服務器時可能引起其他節(jié)點過載,過載節(jié)點需再次刪除虛擬服務器,從而使系統(tǒng)不穩(wěn)定,收斂時間過長。文獻提出了三種簡單的負載均衡算法:一對一、一對多、多對多。算法的基本思想是過載節(jié)點轉(zhuǎn)移虛擬服務器給非過載節(jié)點。在一對一方法中,非過載節(jié)點隨機選擇一個節(jié)點進行探測,當發(fā)現(xiàn)被探測節(jié)點是過載節(jié)點時轉(zhuǎn)移虛擬服務器到本節(jié)點。在一對多和多對多方法中,系統(tǒng)有d個目錄服務節(jié)點用來保存節(jié)點的負載信息,由目錄服務節(jié)點生成負載轉(zhuǎn)移策略。文獻擴展了一對多和多對多模式,使算法適應了動態(tài)P2P系統(tǒng)。然而,此算法在過載與非過載節(jié)點間轉(zhuǎn)移虛擬服務器時,并沒有考慮它們之間的位置相近關(guān)系,負載轉(zhuǎn)移需要消耗過多的帶寬和延遲。文獻在結(jié)構(gòu)化P2P系統(tǒng)之上再建立一個結(jié)構(gòu)(k-nary樹),由k-nary樹收集系統(tǒng)負載信息并生成虛擬服務器轉(zhuǎn)移策略。此算法考慮了節(jié)點之間的距離相近性,但是復雜化了P2P系統(tǒng)的覆蓋網(wǎng)絡,使系統(tǒng)容錯能力有所下降;同時,系統(tǒng)某些節(jié)點(如k-nary樹的根節(jié)點)的失效將產(chǎn)生單點失敗問題。文獻中每個資源關(guān)鍵字hash到d(d≥2)個不同的IDs上,然后在其中選擇負載最輕的節(jié)點存放資源的索引,而其他d-1個節(jié)點只存放指向這個索引的索引。仿真實驗表明,算法在d=O(logN)時,能達到最優(yōu)的負載均衡效果,但沒有考慮系統(tǒng)在動態(tài)環(huán)境下對算法的影響。2系統(tǒng)負載的確定本算法主要針對基于DHT的大規(guī)模P2P計算網(wǎng)絡,網(wǎng)絡中的每一項資源都給系統(tǒng)造成相應的負載(存儲空間、CPU計算時間和帶寬等)。作如下合理的假設:a)系統(tǒng)中只有一種瓶頸資源;b)在負載均衡算法運行期間各虛擬服務器的負載不變。2.1相關(guān)概念1物理dct節(jié)點本算法利用了虛擬服務器。虛擬服務器的概念在Chord/CFS中作為一種負載均衡的方法被提出。一個虛擬服務器相當于一個DHT節(jié)點,并負責一塊連續(xù)的ID空間。而一個物理DHT節(jié)點可以擁有m個虛擬服務器,所以一個物理節(jié)點對應的ID空間可能是非連續(xù)的。DHT節(jié)點之間以虛擬服務器為單位進行負載轉(zhuǎn)移。當某個物理節(jié)點過載時,該物理節(jié)點對應的一個或多個虛擬服務器將被轉(zhuǎn)移到非過載節(jié)點上。同時,虛擬服務器的轉(zhuǎn)移可以由DHT的離開和加入操作來實現(xiàn),無須引入新的操作。利用虛擬服務器可以很方便地在任意兩個節(jié)點之間進行負載轉(zhuǎn)移。2基于網(wǎng)絡定位的dct如今,網(wǎng)絡定位算法已經(jīng)廣泛應用于產(chǎn)生因特網(wǎng)節(jié)點間的物理位置信息。網(wǎng)絡定位算法分為兩種,即基于基礎設施的(infrastructured-based)和不基于基礎設施的(infrastructured-less)。前者(如GNP)使用路標節(jié)點作為參考節(jié)點;后者(如Vivaldi)中的任何節(jié)點都是其他節(jié)點的參考節(jié)點。本文使用第一種網(wǎng)絡定位算法的思想:物理位置相近的節(jié)點到指定的一組參考節(jié)點(路標)有相近的距離信息,并作了適當?shù)母膭?以使它更好地應用于本算法。在一個基于DHT的結(jié)構(gòu)化網(wǎng)絡中,路標節(jié)點可以從本結(jié)構(gòu)化網(wǎng)絡中選擇,也可以在因特網(wǎng)中任意選擇。假設有m個路標節(jié)點,一個DHT節(jié)點A到它們的距離可表示成A的網(wǎng)絡坐標〈d1,d2,…,dm〉。如果把節(jié)點A的網(wǎng)絡坐標映射到m維笛卡兒空間上,這個笛卡兒空間就叫路標空間。根據(jù)網(wǎng)絡定位技術(shù),兩個物理位置相近的DHT節(jié)點A和B有相近的網(wǎng)絡坐標,并且在路標空間上的位置也是相近的。路標節(jié)點越多,相近性誤差就越小。實驗表明利用15個路標節(jié)點足夠產(chǎn)生相近性誤差極小的坐標信息。本算法實驗將使用15個路標節(jié)點,然后利用網(wǎng)絡定位技術(shù),把十五維坐標空間映射到一維坐標空間并保存坐標的相近性,從而使每一個DHT節(jié)點A的網(wǎng)絡坐標都對應一個坐標數(shù)。網(wǎng)絡坐標相近的節(jié)點,它們對應的坐標數(shù)大小也是相近的。3cc與密度分布系數(shù)節(jié)點的聚集系數(shù)可以反映網(wǎng)絡的局部密度。聚集系數(shù)越大,局部密度越高。聚集系數(shù)定義為CC=(|E(Γv)|)/(C2kk2v)。其中:Γv={i:d(i,v)=1};v為取得的中心點。本算法根據(jù)聚集系數(shù)的大小來調(diào)整星型結(jié)構(gòu)區(qū)域。4局部利用率節(jié)點A的利用率指A的負載與A的能力比值,即utlA=loadA/capacityA。節(jié)點A計算的系統(tǒng)局部利用率指與A物理位置相近的節(jié)點(包括A)的負載和與能力和之比,即utl_LA=(∑pi=1loadi)/(∑pi?1capacityi)_LA=(∑pi=1loadi)/(∑pi-1capacityi)。其中:p為滿足條件|Hi-HA|<δ(Hi、HA分別為其他節(jié)點和A節(jié)點的坐標數(shù),δ為常量)的節(jié)點個數(shù)。5節(jié)點個數(shù)的表示與系統(tǒng)利用率的偏差dev指系統(tǒng)中的節(jié)點利用率與系統(tǒng)利用率utl之差的平方和,即dev=∑Ni=1(utli?utldev=∑Νi=1(utli-utl)2。其中:N表示系統(tǒng)中節(jié)點的個數(shù)。負載均衡算法的目標就是使偏差dev盡量小。6耗的帶寬分析負載轉(zhuǎn)移開銷包括轉(zhuǎn)移一定負載所消耗的帶寬和鏈路延遲時間。負載轉(zhuǎn)移消耗的帶寬可以通過負載轉(zhuǎn)移經(jīng)過的跳數(shù)來計算。負載轉(zhuǎn)移的延遲是轉(zhuǎn)移負載的大小與轉(zhuǎn)移時節(jié)點之間延遲的乘積和,即C=∑Si=1loadi×latC=∑Si=1loadi×lati。其中:S表示轉(zhuǎn)移負載的個數(shù)。2.2算法流程2.2.1負載均衡算法仿真本算法利用改進的分布式網(wǎng)絡定位技術(shù)產(chǎn)生的坐標數(shù)作為節(jié)點的IDs。文獻研究表明,網(wǎng)絡坐標相近的節(jié)點,物理位置也相近,并且路標節(jié)點越多,相近性誤差就越小。由于從網(wǎng)絡坐標映射到坐標數(shù)時,保存了節(jié)點間物理位置的相近性關(guān)系,坐標數(shù)(IDs)相近的節(jié)點,物理位置也相近?；诰W(wǎng)絡定位的負載均衡算法中,結(jié)構(gòu)化P2P系統(tǒng)的每一個節(jié)點周期性地計算系統(tǒng)局部利用率utl_LA和負載轉(zhuǎn)移閾值TA(TA=(utl_LA+ε)×CA。其中:utl_LA為系統(tǒng)局部利用率;CA為節(jié)點A的能力;ε為可調(diào)參數(shù)),ε用來在負載均衡質(zhì)量和負載轉(zhuǎn)移開銷之間取得折中,ε為0時,負載均衡質(zhì)量最好,但此時負載轉(zhuǎn)移開銷也最大。當節(jié)點A的負載LA小于TA時,節(jié)點A通知坐標數(shù)滿足條件|Hi-HA|<δ(Hi、HA分別為其他節(jié)點和本節(jié)點的坐標數(shù),δ為常量)的節(jié)點,并以A為中心構(gòu)造一個星型結(jié)構(gòu),如圖1所示。同時,節(jié)點A獲得周圍每一個過載節(jié)點需要轉(zhuǎn)移的虛擬服務器的索引及其負載大小,并按負載從小到大的順序排列成一個鏈表a;同樣,節(jié)點A也會獲得周圍每一個負載較輕節(jié)點能夠接受的負載數(shù)量(Ti-Li),包括節(jié)點A本身,并按負載數(shù)從小到大的順序排成一個鏈表b。仿真實驗表明,δ值為CC×log(N)時具有良好的負載均衡效果。這個過程的偽代碼如下:2.2.2刪除a、b鏈表,檢查dct系統(tǒng)中負載較輕節(jié)點完成星型結(jié)構(gòu)和鏈表a、b的組織之后,進行負載轉(zhuǎn)移。步驟如下:a)鏈表a中的每一個虛擬服務器V與鏈表b里符合條件(Ti-Li)≥load(V)中(Ti-Li)值最小的節(jié)點匹配。b)利用DHT中的離開和加入操作把虛擬服務器從過載節(jié)點轉(zhuǎn)移到負載較輕節(jié)點,并刪除a、b鏈表中相應的節(jié)點。c)循環(huán)執(zhí)行前面兩個步驟,直到鏈表a為空或者星型結(jié)構(gòu)中沒有節(jié)點能夠接收剩下的虛擬服務器(鏈表a不為空)。這時,節(jié)點A通知其他各節(jié)點解散星型結(jié)構(gòu)。對于大規(guī)模網(wǎng)絡,如果需要加快負載的擴散能力,當匹配完成后,鏈表a不為空,即還有虛擬服務器沒有被轉(zhuǎn)移。這時可以拓展星型結(jié)構(gòu),即通知δ≤|Hi-HA|<η的節(jié)點與原來不能進行負載轉(zhuǎn)移的過載節(jié)點構(gòu)成星型結(jié)構(gòu),并按上面的方法進行負載轉(zhuǎn)移。轉(zhuǎn)移完成后,解散星型結(jié)構(gòu)。算法的偽代碼如下:基于網(wǎng)絡定位的負載均衡算法中,負載的轉(zhuǎn)移可以利用DHT中的離開和加入操作來完成,無須引入新的操作。同時需要轉(zhuǎn)移的虛擬服務器索引和負載過輕節(jié)點的剩余能力按從小到大的順序分布在鏈表中排列,從而生成負載轉(zhuǎn)移策略的速度非常快。另外,負載在物理位置相近的節(jié)點之間進行,大大地節(jié)約了系統(tǒng)帶寬和延時等資源。系統(tǒng)中的節(jié)點周期性地執(zhí)行負載均衡算法,所以本算法能夠適應動態(tài)P2P系統(tǒng)。3負載均衡優(yōu)化3.1仿真實驗仿真實驗在結(jié)構(gòu)化P2P系統(tǒng)的Chord協(xié)議上實現(xiàn)。實驗中,Chord具有32bit的ID空間,并且虛擬服務器對應的ID空間大小是呈指數(shù)分布的。實驗用Pareto分布來產(chǎn)生各虛擬服務器的負載,由于Pareto分布的重尾(heavy-tailed)性,算法有效性的驗證是在最不利于負載均衡的情況下進行的。其他具體參數(shù)的設置如表1所示。實驗中,對MIT的kingdata數(shù)據(jù)庫中的mking-t拓撲文件作了適當?shù)臄U展,并使用它作為網(wǎng)絡拓撲結(jié)構(gòu)。Mking-t拓撲結(jié)構(gòu)是現(xiàn)有網(wǎng)絡的一部分,在它上面運行基于網(wǎng)絡定位的負載均衡算法能充分說明算法的有效性和實用性。3.2算法性能分析1)負載均衡效果圖2是負載均衡效果圖。負載均衡過程中的系統(tǒng)利用率為0.8。負載均衡之前,節(jié)點利用率與系統(tǒng)利用率的偏差(dev)為957.12;負載均衡之后,dev下降為12.58,比負載均衡之前下降了98.68%。從圖2可以看出,基于網(wǎng)絡定位的負載均衡算法可以得到理想的負載均衡效果。2)負載轉(zhuǎn)移的開銷圖3是負載轉(zhuǎn)移帶寬消耗累積分布圖。實驗通過轉(zhuǎn)移虛擬服務器經(jīng)過的跳數(shù)來衡量負載轉(zhuǎn)移需消耗的帶寬。從圖中可以看出,考慮節(jié)點間的物理位置相近關(guān)系時,在兩跳之內(nèi)可以轉(zhuǎn)移68%的負載,十跳之內(nèi)可以轉(zhuǎn)移89%的負載。而不考慮節(jié)點間的物理位置相近關(guān)系時,十跳之內(nèi)只轉(zhuǎn)移了15%的負載。從以上的比較可以看出,基于網(wǎng)絡定位的負載均衡算法能夠有效地在物理位置相近的節(jié)點之間進行負載轉(zhuǎn)移,從而減少轉(zhuǎn)移負載所需要的跳數(shù),達到節(jié)省帶寬的目的。圖4是負載轉(zhuǎn)移延遲消耗累積分布圖。從圖中可以看到,當考慮節(jié)點間的物理位置相近關(guān)系時,62%的負載轉(zhuǎn)移在鏈路延遲小于50的節(jié)點之間進行,98%的負載轉(zhuǎn)移在鏈路延遲小于200的節(jié)點之間進行;當不考慮節(jié)點間的物理位置相近關(guān)系時,只有19%的負載轉(zhuǎn)移在鏈路延遲小于200的節(jié)點之間進行。從以上可以看出,基于網(wǎng)絡定位的負載均衡算法可以節(jié)省負載轉(zhuǎn)移所耗費的時間,加快負載轉(zhuǎn)移速度。3)系統(tǒng)利用率對負載均衡效果的影響負載轉(zhuǎn)移因子(loadmovementfactor)定義為負載轉(zhuǎn)移總的開銷與系統(tǒng)中所有負載移動一次時的總開銷之比(只考慮延遲開銷)。例如,負載移動因子為0.1時,表示負載轉(zhuǎn)移消耗的帶寬是初始插入這些負載時的10%。99.9百分位節(jié)點利用率(99.9thpercentilenodeutilization)定義為一個利用率,它大于99.9%的節(jié)點利用率。節(jié)點i的利用率為其負載與能力之比:ui=Li/Ci。從圖5可以看出,每一條線代表一個特定的系統(tǒng)利用率。每一個點表示負載均衡周期在60～1200s時取得的一個值。經(jīng)過負載均衡后,即使系統(tǒng)高達0.912,仍然可保持99.9%的節(jié)點非過載,并且其中有一個負載轉(zhuǎn)移因子小于0.08。4仿真實驗2:轉(zhuǎn)移在物理位置相近的節(jié)點之間進行本文針對結(jié)構(gòu)化P2P系統(tǒng)中的負載均衡問題提出了一種基于網(wǎng)絡定位的負載均衡算法。算法由負載較輕的節(jié)點負責主要的負載轉(zhuǎn)移操作,節(jié)