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

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

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