結(jié)構(gòu)化p2p網(wǎng)絡(luò)的應(yīng)用

結(jié)構(gòu)化p2p網(wǎng)絡(luò)的應(yīng)用

1結(jié)構(gòu)化p2p網(wǎng)絡(luò)近年來(lái)，p2p網(wǎng)絡(luò)作為一種新的網(wǎng)絡(luò)安全形式，受到了人們的高度重視。根據(jù)節(jié)點(diǎn)間拓?fù)浣Y(jié)構(gòu)的不同,P2P網(wǎng)絡(luò)可以分為非結(jié)構(gòu)化P2P網(wǎng)絡(luò)和結(jié)構(gòu)化P2P網(wǎng)絡(luò)。非結(jié)構(gòu)化P2P網(wǎng)絡(luò)的節(jié)點(diǎn)間的聯(lián)系是隨機(jī)產(chǎn)生的,其節(jié)點(diǎn)查找消息主要通過(guò)泛洪(blooding)或隨機(jī)漫步(randomwalk)的方法在節(jié)點(diǎn)間傳播,具有查找效率低、網(wǎng)絡(luò)資源消耗大的特點(diǎn),但因其實(shí)現(xiàn)簡(jiǎn)單,運(yùn)行穩(wěn)定而得以廣泛的應(yīng)用。這類P2P網(wǎng)絡(luò)最經(jīng)典的應(yīng)用是文件共享,如Gnutella。為了改進(jìn)非結(jié)構(gòu)化P2P網(wǎng)絡(luò)的不足,研究者開始關(guān)注結(jié)構(gòu)化P2P網(wǎng)絡(luò)。結(jié)構(gòu)化P2P網(wǎng)絡(luò)節(jié)點(diǎn)間的聯(lián)系通過(guò)一定的拓?fù)湟?guī)則產(chǎn)生,因此節(jié)點(diǎn)與其鄰節(jié)點(diǎn)具有特定的邏輯關(guān)系,這種關(guān)系因路由算法的不同而不同。由于節(jié)點(diǎn)間的邏輯關(guān)系,節(jié)點(diǎn)查找消息可以按照特定的路由路徑到達(dá)目標(biāo)節(jié)點(diǎn),具有查找效率高、資源消耗少的特點(diǎn)。結(jié)構(gòu)化P2P網(wǎng)絡(luò)支持具有哈希表語(yǔ)義的lookup操作,因此也被稱為分布式哈希表(DistributedHashTable,DHT)。目前已經(jīng)出現(xiàn)的較為典型的結(jié)構(gòu)化P2P算法有Chord,Pastry,Taperstry,CAN,Viceroy等。結(jié)構(gòu)化P2P網(wǎng)絡(luò)因其優(yōu)良的性能和較少的資源消耗在學(xué)術(shù)界受到了很大的重視。但是,基于結(jié)構(gòu)化P2P網(wǎng)絡(luò)的應(yīng)用服務(wù)的研究較為薄弱,目前僅有Chord/DHash(/chord/)項(xiàng)目中所開發(fā)的網(wǎng)絡(luò)存儲(chǔ)系統(tǒng)原型。要進(jìn)一步推動(dòng)結(jié)構(gòu)化P2P網(wǎng)絡(luò)的發(fā)展,除了在可用性部署能力等方面繼續(xù)改進(jìn)結(jié)構(gòu)化P2P算法以外,還需要加強(qiáng)利用結(jié)構(gòu)化P2P網(wǎng)絡(luò)提供各類應(yīng)用服務(wù)的研究。大部分結(jié)構(gòu)化P2P網(wǎng)絡(luò)都具有一定的負(fù)載均衡能力,這使結(jié)構(gòu)化P2P網(wǎng)絡(luò)非常適合應(yīng)用于需要負(fù)載均衡的環(huán)境。計(jì)算力資源整合指在單臺(tái)計(jì)算機(jī)無(wú)法滿足計(jì)算任務(wù)對(duì)計(jì)算力要求的情況下,整合網(wǎng)絡(luò)中其它計(jì)算機(jī)的閑置計(jì)算力資源以共同完成計(jì)算任務(wù)。它是一種對(duì)負(fù)載均衡具有較高要求的服務(wù),如著名的BOINC(/)系統(tǒng)就是這樣一個(gè)計(jì)算力資源整合系統(tǒng)。本文認(rèn)為,除了在負(fù)載均衡上的優(yōu)勢(shì)外,與其它計(jì)算力資源整合方法相比,利用結(jié)構(gòu)化P2P網(wǎng)絡(luò)進(jìn)行計(jì)算力資源整合還具有以下的優(yōu)勢(shì):(1)結(jié)構(gòu)化P2P網(wǎng)絡(luò)是完全自組織的,沒(méi)有服務(wù)器的存在。網(wǎng)絡(luò)中的成員在提供計(jì)算力的同時(shí),也能利用網(wǎng)絡(luò)的總體計(jì)算力為自己服務(wù),節(jié)點(diǎn)間是完全平等的,這使Internet上的公共用戶更愿意參與進(jìn)來(lái),從而獲得更強(qiáng)的總體計(jì)算力。(2)接受服務(wù)的節(jié)點(diǎn)不需要了解網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量、具體節(jié)點(diǎn)的狀態(tài)等信息,邏輯上可以將整個(gè)網(wǎng)絡(luò)視為一臺(tái)具有強(qiáng)大計(jì)算能力的超級(jí)計(jì)算機(jī),這有助于減少節(jié)點(diǎn)管理和索引的開銷。目前結(jié)構(gòu)化P2P網(wǎng)絡(luò)上的計(jì)算力資源整合的研究尚未見(jiàn)文獻(xiàn)全面報(bào)道。本文將對(duì)結(jié)構(gòu)化P2P網(wǎng)絡(luò)上的計(jì)算力資源整合方法進(jìn)行研究,并結(jié)合研究成果設(shè)計(jì)一個(gè)分布式的大質(zhì)數(shù)測(cè)試程序。本文的其余部分是這樣組織的:第2節(jié)系統(tǒng)闡述基于結(jié)構(gòu)化P2P網(wǎng)絡(luò)的計(jì)算力資源整合方法,從理論和工程上對(duì)系統(tǒng)模型、計(jì)算任務(wù)的分解、分配、結(jié)果匯總,網(wǎng)絡(luò)通信開銷的控制,提高可靠性,適應(yīng)動(dòng)態(tài)變化的計(jì)算力和提高負(fù)載均衡能力方面進(jìn)行深入的研究;第3節(jié)結(jié)合第2節(jié)的成果開發(fā)一個(gè)分布式大質(zhì)數(shù)測(cè)試系統(tǒng);第4節(jié)以該系統(tǒng)為基礎(chǔ),測(cè)試并分析本文所提出的方法的各項(xiàng)性能;最后總結(jié)本文的研究成果。2在p2p網(wǎng)絡(luò)下，構(gòu)建基本力源的方法2.1任務(wù)系統(tǒng)計(jì)算方法計(jì)算力資源的整合方法有很多。對(duì)于結(jié)構(gòu)化P2P網(wǎng)絡(luò)這樣的松耦合系統(tǒng),分治法是一種較好的思路。分治法將一個(gè)大型計(jì)算任務(wù)分解成一定數(shù)量的工作片斷,分解后得到的工作片斷按一定的規(guī)則分配給網(wǎng)絡(luò)中的節(jié)點(diǎn),節(jié)點(diǎn)根據(jù)當(dāng)前的運(yùn)算負(fù)荷決定是否接受計(jì)算任務(wù),并向任務(wù)發(fā)出者發(fā)送計(jì)算結(jié)果或拒絕通知。最后,任務(wù)發(fā)出者綜合各工作片斷的計(jì)算結(jié)果,導(dǎo)出原計(jì)算任務(wù)的結(jié)果。在這個(gè)計(jì)算模型下,至少有下列問(wèn)題需要解決:(1)如何將一個(gè)計(jì)算任務(wù)分解、分配到網(wǎng)絡(luò)節(jié)點(diǎn),并將工作片斷的結(jié)果匯總成最終的計(jì)算結(jié)果;(2)就計(jì)算任務(wù)本身而言,網(wǎng)絡(luò)通信屬于一種“額外開銷”,如何使通信開銷不成為系統(tǒng)的瓶頸;(3)P2P網(wǎng)絡(luò)是一個(gè)動(dòng)態(tài)環(huán)境,節(jié)點(diǎn)的構(gòu)成相當(dāng)復(fù)雜,采取何種保證措施才能使每一個(gè)工作片斷都得到有效的處理(即得到計(jì)算并返回結(jié)果);(4)隨著節(jié)點(diǎn)的動(dòng)態(tài)加入與退出以及節(jié)點(diǎn)本身狀態(tài)的變化,網(wǎng)絡(luò)的總體計(jì)算力在不斷變化,如何適應(yīng)這種變化以使資源利用最大化;(5)在網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量無(wú)法獲取以及節(jié)點(diǎn)間具有很強(qiáng)異構(gòu)性的情況下,如何分配任務(wù)使得網(wǎng)絡(luò)中各節(jié)點(diǎn)的負(fù)載處于相對(duì)平衡的狀態(tài)。這些問(wèn)題是基于結(jié)構(gòu)化P2P網(wǎng)絡(luò)的計(jì)算力資源整合的關(guān)鍵問(wèn)題,本文將對(duì)這些問(wèn)題進(jìn)行深入的研究,并提出一系列解決方案。2.2工作片的分配計(jì)算任務(wù)的分解與結(jié)果匯總很大程度上與具體的計(jì)算任務(wù)有關(guān),大部分情況下屬于數(shù)學(xué)問(wèn)題,很難找到一個(gè)通用的方法,本文對(duì)此不做深入討論。在第3節(jié)的原型系統(tǒng)中,對(duì)于具體的問(wèn)題,本文設(shè)計(jì)了問(wèn)題分解與結(jié)果匯總方法。計(jì)算任務(wù)分解為工作片斷后,緊接著要解決的問(wèn)題是工作片斷的分配,即將工作片斷交由某一網(wǎng)絡(luò)節(jié)點(diǎn)來(lái)處理。分配的主要原則是負(fù)載均衡。一般而言,結(jié)構(gòu)化P2P網(wǎng)絡(luò)本身就具有一定的負(fù)載均衡能力,如Chord算法使用了SHA-1散列來(lái)生成它的key,使得key分布較為均勻。本文采用的方法是,對(duì)工作片斷的二進(jìn)制表示做散列操作,得到與特定結(jié)構(gòu)化P2P算法長(zhǎng)度要求一致的key,并將工作片斷分配給負(fù)責(zé)維護(hù)這一key的節(jié)點(diǎn)來(lái)完成計(jì)算。這種方法在結(jié)構(gòu)化P2P網(wǎng)絡(luò)中具有通用性,并且可以獲得初步的負(fù)載均衡能力。本文后續(xù)部分進(jìn)一步研究如何獲得更高的系統(tǒng)性能和資源利用率。2.3多網(wǎng)融合發(fā)展網(wǎng)絡(luò)實(shí)驗(yàn)的總開銷處理一個(gè)工作片斷的開銷包括如下幾個(gè)部分:網(wǎng)絡(luò)通信(節(jié)點(diǎn)查找與任務(wù)分配)時(shí)間、排隊(duì)時(shí)間、計(jì)算時(shí)間、結(jié)果返回與處理時(shí)間。結(jié)果返回與處理時(shí)間非常短,不屬于本文研究的重點(diǎn),因此工作片斷總的開銷實(shí)際上由前面三個(gè)部分組成。網(wǎng)絡(luò)通信時(shí)間指結(jié)構(gòu)化P2P網(wǎng)絡(luò)查找負(fù)責(zé)與工作片斷對(duì)應(yīng)的key的節(jié)點(diǎn)并將工作片斷發(fā)往該節(jié)點(diǎn)的時(shí)間。如果節(jié)點(diǎn)正在忙于處理其它工作片斷,會(huì)將當(dāng)前工作片斷置于等待隊(duì)列中,這就是排隊(duì)時(shí)間。排隊(duì)時(shí)間受節(jié)點(diǎn)當(dāng)前負(fù)荷的影響,但可以用第2.6.2節(jié)提出的語(yǔ)義隊(duì)列的思想加以控制。工作片斷排隊(duì)期間,節(jié)點(diǎn)實(shí)際上并未閑置,可以不認(rèn)為是額外開銷。因此,網(wǎng)絡(luò)通信時(shí)間成為了唯一的額外開銷。遺憾的是,網(wǎng)絡(luò)通信時(shí)間是由P2P網(wǎng)絡(luò)本身(包括網(wǎng)絡(luò)狀況、節(jié)點(diǎn)的數(shù)量、節(jié)點(diǎn)加入退出的頻率等)決定的,上層應(yīng)用很難從根本上減少,只能動(dòng)態(tài)地適應(yīng)網(wǎng)絡(luò)。因此,目標(biāo)可以轉(zhuǎn)化為:合理控制網(wǎng)絡(luò)通信時(shí)間占總開銷的比重。在總開銷一定的情況下,比重太低,則表明單個(gè)工作片斷的計(jì)算時(shí)間長(zhǎng),節(jié)點(diǎn)負(fù)荷過(guò)重;比重太高,則表明大量的時(shí)間花費(fèi)在了網(wǎng)絡(luò)通信上,計(jì)算力資源利用率低。因此要選擇一個(gè)合適的比重,既能降低節(jié)點(diǎn)負(fù)荷,又能保證較高的資源利用率。本文設(shè)計(jì)的控制網(wǎng)絡(luò)通信時(shí)間所占比重的算法如下。首先實(shí)時(shí)地獲取總開銷中各個(gè)部分的耗時(shí)。處理工作片斷的節(jié)點(diǎn)記錄工作片斷的計(jì)算時(shí)間t1和排隊(duì)時(shí)間t2,并在結(jié)果返回的報(bào)文中包括這兩個(gè)值。工作片斷發(fā)送端測(cè)量工作片斷的即時(shí)周轉(zhuǎn)時(shí)間iTT(InstantTurnaroundTime),并計(jì)算網(wǎng)絡(luò)通信時(shí)間iCT=iTT-t1-t2。根據(jù)每個(gè)工作片斷的即時(shí)周轉(zhuǎn)時(shí)間,可以實(shí)時(shí)地計(jì)算出系統(tǒng)當(dāng)前的平均周轉(zhuǎn)時(shí)間。設(shè)系統(tǒng)當(dāng)前的平均周轉(zhuǎn)時(shí)間為TT,收到第n個(gè)工作片斷的計(jì)算結(jié)果后,可測(cè)出相應(yīng)工作片斷的即時(shí)周轉(zhuǎn)時(shí)間iTTn,根據(jù)如下公式更新TT值:不妨標(biāo)記收到的各個(gè)工作片斷的周轉(zhuǎn)時(shí)間分別為iTT0,iTT1,…,iTTn,令TT0=iTT0,展開上式得:從以上分析可以看出,當(dāng)前的TT值受最近的iTT值影響較大,這樣的計(jì)算方法使得計(jì)算得到的TT值更能反映網(wǎng)絡(luò)的近況,有利于適應(yīng)網(wǎng)絡(luò)的動(dòng)態(tài)變化。用同樣的方法可計(jì)算平均網(wǎng)絡(luò)通信時(shí)間CT。獲得了以上數(shù)據(jù)后,在系統(tǒng)運(yùn)行過(guò)程中,可以實(shí)時(shí)監(jiān)測(cè)到當(dāng)前網(wǎng)絡(luò)通信時(shí)間所占的比重T=CT/TT,并設(shè)定該比重的上限u、下限v。當(dāng)T>u時(shí),增加后繼工作片斷的計(jì)算量;當(dāng)T<v時(shí),減小后繼工作片斷的計(jì)算量(計(jì)算量的增減方法與具體應(yīng)用相關(guān))。在實(shí)際實(shí)現(xiàn)中,為了進(jìn)一步減少瞬間值帶來(lái)的誤差,只有當(dāng)T>u(T<v)的狀態(tài)維持一個(gè)設(shè)定的時(shí)間t后,才調(diào)整后繼工作片斷的計(jì)算量。第4.1節(jié)通過(guò)實(shí)驗(yàn)驗(yàn)證了這一方法的可行性。2.4工作片的重傳由于P2P網(wǎng)絡(luò)的復(fù)雜性,有時(shí)會(huì)出現(xiàn)節(jié)點(diǎn)查找失敗、報(bào)文丟失、節(jié)點(diǎn)拒絕請(qǐng)求等情況,這些都將使發(fā)送者無(wú)法收到相應(yīng)工作片斷的計(jì)算結(jié)果,導(dǎo)致整個(gè)任務(wù)無(wú)法完成。為了適應(yīng)這樣的環(huán)境,本文提出了使用重傳機(jī)制提高系統(tǒng)可靠性的方法。需要重傳的工作片斷分為兩類:一是被節(jié)點(diǎn)拒絕的工作片斷,二是在指定時(shí)間內(nèi)未收到計(jì)算結(jié)果的工作片斷,即超時(shí)。兩種情況下,任務(wù)發(fā)出者都采用二進(jìn)制指數(shù)退避法執(zhí)行重傳。但在第二種情況下,需要確定初始的超時(shí)時(shí)間。在第2.3節(jié)中,已經(jīng)給出了實(shí)時(shí)獲取當(dāng)前系統(tǒng)平均周轉(zhuǎn)時(shí)間TT的方法。初始超時(shí)時(shí)間設(shè)定為當(dāng)前TT的c倍(c>1)。對(duì)于上述算法中k和c的具體數(shù)值,可以不做規(guī)定,由具體的計(jì)算任務(wù)根據(jù)實(shí)際情況確定。重傳機(jī)制的介入,確保了所有的工作片斷都能得到計(jì)算并被響應(yīng),提高了系統(tǒng)的可靠性。2.5發(fā)送速率控制結(jié)構(gòu)化P2P網(wǎng)絡(luò)的特性決定了任務(wù)發(fā)出者無(wú)法準(zhǔn)確獲知網(wǎng)絡(luò)中節(jié)點(diǎn)的具體數(shù)量和總體計(jì)算力。在運(yùn)行過(guò)程中,隨著節(jié)點(diǎn)的加入和離開,以及各節(jié)點(diǎn)本身的狀態(tài)變化,網(wǎng)絡(luò)的總體計(jì)算力呈現(xiàn)動(dòng)態(tài)變化的態(tài)勢(shì)。在這種情況下,任務(wù)發(fā)出者無(wú)法確定連續(xù)向網(wǎng)絡(luò)中發(fā)送多少工作片斷較為合適,因此需要一種機(jī)制使工作片斷的發(fā)送速率與網(wǎng)絡(luò)的總體計(jì)算力動(dòng)態(tài)匹配。否則,節(jié)點(diǎn)只能以固定的速率向網(wǎng)絡(luò)發(fā)送工作片斷。速率過(guò)慢,總體計(jì)算力得不到充分的發(fā)揮;速率過(guò)快,則造成網(wǎng)絡(luò)中的節(jié)點(diǎn)負(fù)載過(guò)高,大量工作片斷被拒絕或丟包率增高,不利于充分、合理地利用總體計(jì)算力。本文借鑒TCP協(xié)議中的慢啟動(dòng)和擁塞控制算法來(lái)解決上述問(wèn)題。在計(jì)算力資源整合中,發(fā)生擁塞的主要標(biāo)志是任務(wù)發(fā)出者收到節(jié)點(diǎn)的拒絕通知,這通常是由于已分配但未得到處理的工作片斷的總計(jì)算量超過(guò)了網(wǎng)絡(luò)當(dāng)前的總體計(jì)算力,任務(wù)發(fā)出者應(yīng)降低發(fā)出工作片斷的速率。本文針對(duì)這一特點(diǎn)設(shè)計(jì)了一個(gè)簡(jiǎn)化的發(fā)送速率控制方法。任務(wù)發(fā)送者設(shè)置一個(gè)發(fā)送窗口,保證其已發(fā)送但未得到處理的工作片斷數(shù)量不超過(guò)發(fā)送窗口的大小。初始發(fā)送窗口大小設(shè)置為1,每收到一個(gè)計(jì)算結(jié)果,就增加窗口大小。提供計(jì)算力的節(jié)點(diǎn)設(shè)置一個(gè)等待隊(duì)列,當(dāng)隊(duì)列中的工作片斷數(shù)量到達(dá)隊(duì)列長(zhǎng)度時(shí),拒絕新到的工作片斷,以免其負(fù)擔(dān)過(guò)重。當(dāng)任務(wù)發(fā)出者收到拒絕通知時(shí),表明網(wǎng)絡(luò)中節(jié)點(diǎn)已經(jīng)過(guò)載了,此時(shí)減小發(fā)送窗口的大小。待新的計(jì)算結(jié)果收到時(shí),再逐漸增大窗口大小,以適應(yīng)總體計(jì)算力的變化。窗口大小將維持在一個(gè)動(dòng)態(tài)平衡狀態(tài),以擬合網(wǎng)絡(luò)的總體計(jì)算力變化。發(fā)送窗口每次減小和增大的具體數(shù)值屬于系統(tǒng)策略問(wèn)題,不屬于本文的研究重點(diǎn)。引入了發(fā)送速率控制機(jī)制后,任務(wù)發(fā)送者將隨著網(wǎng)絡(luò)總體計(jì)算力的變化自動(dòng)地以適當(dāng)?shù)乃俾拾l(fā)送工作片斷,使其能夠充分合理地利用網(wǎng)絡(luò)節(jié)點(diǎn)的總體計(jì)算力。第4.2和4.3節(jié)通過(guò)實(shí)驗(yàn)驗(yàn)證了這一算法的有效性。2.6節(jié)點(diǎn)間異構(gòu)特性結(jié)構(gòu)化P2P算法中key的分布一般是均勻的。但相對(duì)于key的數(shù)量(如Chord算法為2160)而言,網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量較少,無(wú)法保證節(jié)點(diǎn)的分布是完全均勻的。在這種情況下,勢(shì)必會(huì)有一部分節(jié)點(diǎn)負(fù)責(zé)較多的key,另一部分節(jié)點(diǎn)負(fù)責(zé)較少的key。如果某一節(jié)點(diǎn)所負(fù)責(zé)的key數(shù)量很多,而其所負(fù)責(zé)的key又被頻繁請(qǐng)求,該節(jié)點(diǎn)就會(huì)過(guò)載,在網(wǎng)絡(luò)中形成熱點(diǎn)(HotSpot)。熱點(diǎn)的存在會(huì)嚴(yán)重影響網(wǎng)絡(luò)的整體性能。在P2P網(wǎng)絡(luò)中,網(wǎng)絡(luò)節(jié)點(diǎn)的構(gòu)成非常復(fù)雜,既有性能一般的普通PC,也有性能高上幾個(gè)數(shù)量級(jí)的高性能集群。根據(jù)節(jié)點(diǎn)當(dāng)前的工作狀態(tài),其閑置計(jì)算力也處于動(dòng)態(tài)的變化之中,這就是節(jié)點(diǎn)間的異構(gòu)特性。這些因素決定了工作片斷不應(yīng)以絕對(duì)平均的方法分配給每一個(gè)節(jié)點(diǎn),而要根據(jù)計(jì)算力的差異動(dòng)態(tài)地進(jìn)行分配。本節(jié)將提出解決上述兩個(gè)問(wèn)題的方案。第4.4節(jié)給出了改進(jìn)前后負(fù)載均衡能力的對(duì)比。2.6.1工作片段的長(zhǎng)轉(zhuǎn)觀節(jié)點(diǎn)過(guò)載的標(biāo)志是等待隊(duì)列已滿而新的工作片斷還在不斷地到達(dá)。為了緩解節(jié)點(diǎn)的負(fù)荷,并增強(qiáng)負(fù)載均衡能力,本文引入重定向機(jī)制。具體工作過(guò)程如下:當(dāng)節(jié)點(diǎn)的等待隊(duì)列滿而新的工作片斷到達(dá)時(shí),將該工作片斷重定向到節(jié)點(diǎn)的某一鄰居節(jié)點(diǎn)(如Chord中的后繼節(jié)點(diǎn))。若該鄰居節(jié)點(diǎn)仍然過(guò)載,則再次將工作片斷重定向到下一個(gè)鄰居節(jié)點(diǎn),直至未過(guò)載節(jié)點(diǎn)。引入重定向機(jī)制后,負(fù)責(zé)key較多的節(jié)點(diǎn)可以將工作片斷轉(zhuǎn)發(fā)到其它節(jié)點(diǎn)上去,減輕本節(jié)點(diǎn)的負(fù)荷;負(fù)責(zé)key較少的節(jié)點(diǎn)有機(jī)會(huì)接收從負(fù)責(zé)key較多的節(jié)點(diǎn)轉(zhuǎn)發(fā)來(lái)的工作片斷,增加本節(jié)點(diǎn)的負(fù)荷,從而在整個(gè)網(wǎng)絡(luò)范圍內(nèi)改善節(jié)點(diǎn)和計(jì)算任務(wù)分布不均勻帶來(lái)的負(fù)載不均衡問(wèn)題。如果整個(gè)網(wǎng)絡(luò)都處在過(guò)載的狀態(tài)中,工作片斷將會(huì)在網(wǎng)絡(luò)中循環(huán),造成不必要的開銷。在實(shí)際實(shí)現(xiàn)中,每一個(gè)工作片斷的請(qǐng)求報(bào)文中都設(shè)置跳數(shù)限制字段,其初始值由任務(wù)發(fā)出者填入,工作片斷每次被重定向時(shí),該字段都會(huì)減小1。當(dāng)該字段值減小到0時(shí),如果仍然需要重定向,則最后一個(gè)處理該工作片斷的節(jié)點(diǎn)將向任務(wù)發(fā)出者發(fā)出拒絕通知。如第2.5節(jié)中所描述的,任務(wù)發(fā)出者收到拒絕通知后,將調(diào)整工作片斷的發(fā)送速率,以降低整個(gè)網(wǎng)絡(luò)的負(fù)荷,且被拒絕的工作片斷將在一段時(shí)間后被重新分配。下面以Chord算法為例,從理論上分析利用重定向機(jī)制提高負(fù)載均衡能力的原理。假設(shè)網(wǎng)絡(luò)中的節(jié)點(diǎn)總數(shù)為M,總工作片斷數(shù)量為W。理想情況下,每個(gè)節(jié)點(diǎn)接收的工作片斷數(shù)量N如下式所示:實(shí)際上,由于節(jié)點(diǎn)分布不均,造成每個(gè)節(jié)點(diǎn)接收到的工作片斷的數(shù)量不同。設(shè)節(jié)點(diǎn)i接收到的工作片斷數(shù)量為Ni。在不啟用重定向機(jī)制的情況下,各節(jié)點(diǎn)收到的工作片斷數(shù)量的標(biāo)準(zhǔn)差S1如公式(2)所示:啟用了重定向機(jī)制后,節(jié)點(diǎn)將工作片斷重定向到其后繼節(jié)點(diǎn)。假定重定向的最大跳數(shù)限制為h,理想情況下,每個(gè)工作片斷被轉(zhuǎn)發(fā)0次,1次,…,h次的概率為1/(h+1)。在實(shí)際的動(dòng)態(tài)網(wǎng)絡(luò)中,這個(gè)概率會(huì)動(dòng)態(tài)地變化,并且不會(huì)在節(jié)點(diǎn)間平均分布?？梢约俣總€(gè)工作片斷被發(fā)0次,1次,…,h次的概率分別為k0/(h+1),k1/(h+1),…,kh/(h+1),且+1。在這個(gè)模型下,節(jié)點(diǎn)i收到的實(shí)際工作片斷總數(shù)可表達(dá)如下:各節(jié)點(diǎn)收到的工作片斷數(shù)量的標(biāo)準(zhǔn)差為標(biāo)準(zhǔn)差S越小,表明網(wǎng)絡(luò)中各節(jié)點(diǎn)完成的工作片斷的數(shù)量差別越小,即負(fù)載均衡能力越強(qiáng)。在式(2)中,沒(méi)有任何可以人為控制的變量。在式(4)中,當(dāng)h趨向于正無(wú)窮大時(shí),每個(gè)工作片斷被轉(zhuǎn)發(fā)0次,1次,2次,…,h次的概率趨向于平均,即1/(h+1),且,由此并結(jié)合(4)式可得,當(dāng)h→+∞時(shí),有因此,增大(4)式中h的值,可以降低各節(jié)點(diǎn)收到的工作片斷數(shù)量的標(biāo)準(zhǔn)差,提高負(fù)載均衡能力。在實(shí)際網(wǎng)絡(luò)中,h值取得過(guò)高,將導(dǎo)致工作片斷頻繁被轉(zhuǎn)發(fā),通信量增加,影響性能,并且,由于節(jié)點(diǎn)等待隊(duì)列的存在,無(wú)限制提高h(yuǎn)并不會(huì)使網(wǎng)絡(luò)達(dá)到理想化的負(fù)載均衡狀態(tài)。第4.4節(jié)的實(shí)驗(yàn)給出了h值與負(fù)載均衡能力的關(guān)系。2.6.2語(yǔ)義任務(wù)長(zhǎng)度的確定在上述實(shí)現(xiàn)中,衡量等待隊(duì)列長(zhǎng)度的單位是隊(duì)列中工作片斷的數(shù)量。判斷隊(duì)列是否已滿的標(biāo)準(zhǔn),是排隊(duì)中的工作片斷的數(shù)量是否達(dá)到隊(duì)列長(zhǎng)度的上限。由前所述,節(jié)點(diǎn)之間存在異構(gòu)性,而且任務(wù)發(fā)出者會(huì)根據(jù)網(wǎng)絡(luò)狀況動(dòng)態(tài)調(diào)整工作片斷的計(jì)算量,因此每個(gè)工作片斷的計(jì)算量并不相同。進(jìn)而每個(gè)工作片斷的計(jì)算耗時(shí)是不固定的,僅根據(jù)工作片斷數(shù)量來(lái)確定節(jié)點(diǎn)是否過(guò)載并不能達(dá)到完全公平的效果。為了解決這個(gè)問(wèn)題,本文提出了語(yǔ)義隊(duì)列的概念。語(yǔ)義隊(duì)列的長(zhǎng)度用時(shí)間來(lái)表示,而不是通常的工作片斷數(shù)量。這個(gè)時(shí)間是節(jié)點(diǎn)完成當(dāng)前隊(duì)列中所有工作片斷所要花費(fèi)的時(shí)間。在多任務(wù)操作系統(tǒng)中,節(jié)點(diǎn)在執(zhí)行計(jì)算的同時(shí),還要受系統(tǒng)中其它運(yùn)算任務(wù)的影響,因此節(jié)點(diǎn)的計(jì)算能力會(huì)發(fā)生波動(dòng)。為了計(jì)算當(dāng)前語(yǔ)義隊(duì)列的長(zhǎng)度,節(jié)點(diǎn)實(shí)時(shí)監(jiān)測(cè)當(dāng)前的運(yùn)算速度,并進(jìn)一步導(dǎo)出當(dāng)前隊(duì)列中所有工作片斷的總計(jì)算時(shí)間,即語(yǔ)義隊(duì)列的長(zhǎng)度。為了防止大計(jì)算量的工作片斷反復(fù)因語(yǔ)義隊(duì)列滿而被拒絕,允許任務(wù)發(fā)出者在被拒絕后重傳的工作片斷的請(qǐng)求報(bào)文中指定該工作片斷不受語(yǔ)義隊(duì)列影響。節(jié)點(diǎn)收到“不受語(yǔ)義隊(duì)列影響”的工作片斷后,不得因語(yǔ)義隊(duì)列滿而拒絕或重定向該工作片斷。引入語(yǔ)義隊(duì)列后,為了控制節(jié)點(diǎn)負(fù)載,只要控制語(yǔ)義隊(duì)列的長(zhǎng)度,但要保證隊(duì)列至少可容納一個(gè)工作片斷。這樣,即使節(jié)點(diǎn)之間存在很大的異構(gòu)性,由于隊(duì)列長(zhǎng)度是按計(jì)算耗時(shí)而不是工作片斷的絕對(duì)數(shù)量來(lái)衡量的,計(jì)算力較弱的節(jié)點(diǎn)也不會(huì)因計(jì)算負(fù)擔(dān)過(guò)重而過(guò)載,整個(gè)網(wǎng)絡(luò)的負(fù)載均衡能力得到了進(jìn)一步的提升。3-嵌入式大質(zhì)數(shù)測(cè)試系統(tǒng)的實(shí)現(xiàn)本節(jié)將基于以上研究成果設(shè)計(jì)并實(shí)現(xiàn)一個(gè)分布式大質(zhì)數(shù)測(cè)試系統(tǒng),以檢驗(yàn)上述方案的可行性與有效性。在第4節(jié)中,將進(jìn)一步測(cè)試系統(tǒng)的各項(xiàng)性能。3.1節(jié)點(diǎn)對(duì)于多元小區(qū)間的優(yōu)化算法設(shè)計(jì)這個(gè)分布式大質(zhì)數(shù)測(cè)試系統(tǒng)的目的是檢驗(yàn)上述結(jié)構(gòu)化P2P網(wǎng)絡(luò)上的計(jì)算力資源整合方法,因此此處不準(zhǔn)備對(duì)各種質(zhì)數(shù)測(cè)試算法的優(yōu)劣進(jìn)行對(duì)比,也不對(duì)質(zhì)數(shù)測(cè)試算法本身進(jìn)行數(shù)學(xué)上的優(yōu)化,而直接使用簡(jiǎn)單試除法,即用區(qū)間內(nèi)的所有奇數(shù)試除N(N為大于3的奇數(shù))。若區(qū)間內(nèi)的某一整數(shù)P除盡了N,則P就是N的因子,N為合數(shù);若區(qū)間內(nèi)的整數(shù)都無(wú)法除盡N,則N為質(zhì)數(shù)。為了使用第2節(jié)中的方法整合網(wǎng)絡(luò)中計(jì)算機(jī)的閑置計(jì)算力,需要調(diào)整上述算法以適應(yīng)分布式計(jì)算。首要問(wèn)題是計(jì)算任務(wù)的分解與結(jié)果的匯總。這里,我們簡(jiǎn)單地把整個(gè)除數(shù)區(qū)間分成若干個(gè)小區(qū)間,并將各個(gè)小區(qū)間的除法任務(wù)作為工作片斷發(fā)往網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行計(jì)算。節(jié)點(diǎn)返回的計(jì)算結(jié)果有兩種:一是小區(qū)間內(nèi)的除數(shù)均無(wú)法除盡被除數(shù),二是小區(qū)間的某個(gè)整數(shù)P除盡了被除數(shù)。若所有工作片斷的計(jì)算結(jié)果都是第一種情況,則被測(cè)整數(shù)是質(zhì)數(shù);若某一個(gè)小區(qū)間的計(jì)算結(jié)果為第二種情況,則被測(cè)整數(shù)是合數(shù)。通過(guò)動(dòng)態(tài)調(diào)整小區(qū)間的長(zhǎng)度,任務(wù)發(fā)出者可以調(diào)整每個(gè)工作片斷的計(jì)算量。3.2工作片的運(yùn)行本文設(shè)計(jì)的大質(zhì)數(shù)測(cè)試系統(tǒng)以經(jīng)典的結(jié)構(gòu)化P2P算法Chord為基礎(chǔ),采用第2節(jié)的研究成果開發(fā)。結(jié)構(gòu)化P2P網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)既是客戶端也是服務(wù)端,為了敘述上的方便,此處將發(fā)出計(jì)算任務(wù)的節(jié)點(diǎn)稱為客戶端,將接受工作片斷完成計(jì)算的節(jié)點(diǎn)稱為服務(wù)端?？蛻舳说墓δ苁莿?dòng)態(tài)地將計(jì)算任務(wù)分解成適應(yīng)當(dāng)前網(wǎng)絡(luò)狀況的計(jì)算量不等的工作片斷,并按第2.2-2.5節(jié)描述的方法發(fā)往P2P網(wǎng)絡(luò)中的節(jié)點(diǎn)。該工作片斷同時(shí)被放置于客戶端的未決結(jié)果隊(duì)列中,等待回復(fù)。客戶端的運(yùn)行過(guò)程可用圖1所示的狀態(tài)轉(zhuǎn)換圖來(lái)表示?？蛻舳藛?dòng)計(jì)算任務(wù)后,就進(jìn)入圖1所示的工作流程中。如果客戶端收到一個(gè)計(jì)算結(jié)果,表明被測(cè)數(shù)不是質(zhì)數(shù)時(shí),上述過(guò)程立即終止(即發(fā)送退出信號(hào)),并輸出結(jié)果。在WORK-ING狀態(tài),只要發(fā)送窗口未滿,程序就根據(jù)當(dāng)前的網(wǎng)絡(luò)狀態(tài)生成適當(dāng)計(jì)算量的工作片斷,發(fā)往網(wǎng)絡(luò)進(jìn)行計(jì)算。在WAIT＿1狀態(tài),發(fā)送窗口處于滿狀態(tài),程序等待直到窗口大小允許發(fā)送新的工作片斷。在WAIT＿2狀態(tài),所有的工作片斷都已經(jīng)發(fā)送,程序等待所有計(jì)算結(jié)果都返回后退出。為了處理工作片斷被拒絕或超時(shí)的情況,還有一個(gè)單獨(dú)的線程,定時(shí)檢查未決結(jié)果隊(duì)列中的工作片斷。若有被拒絕或超時(shí),則適時(shí)重傳。服務(wù)端的功能是接收工作片斷并完成計(jì)算,每個(gè)服務(wù)端可設(shè)置多個(gè)獨(dú)立的工作線程,同時(shí)處理收到的工作片斷。在多CPU的計(jì)算機(jī)上,操作系統(tǒng)可將每個(gè)線程調(diào)度到不同的CPU上運(yùn)行,提高單機(jī)計(jì)算力資源的利用率。每個(gè)線程的工作流程可用圖2所示的狀態(tài)轉(zhuǎn)換圖來(lái)表示。服務(wù)端啟動(dòng)后開始接收客戶端發(fā)出的工作片斷并置于等待隊(duì)列中,每個(gè)工作線程獨(dú)立地從等待隊(duì)列中獲取工作片斷,執(zhí)行計(jì)算任務(wù)。程序?qū)Φ却?duì)列進(jìn)行了同步,以保證多個(gè)線程同時(shí)訪問(wèn)時(shí)不會(huì)出現(xiàn)沖突。在WORKING狀態(tài),程序?qū)ぷ髌瑪啻淼挠?jì)算任務(wù)進(jìn)行計(jì)算,并將結(jié)果返回給客戶端。為了使程序工作時(shí)減小對(duì)系統(tǒng)其它進(jìn)程的影響,當(dāng)工作線程進(jìn)入WORKING狀態(tài)后,線程優(yōu)先級(jí)自動(dòng)降到最低。在WAIT狀態(tài),等待隊(duì)列為空,即沒(méi)有收到新的工作片斷,程序?qū)⒁恢钡却?直到有新的工作片斷到達(dá)或被中止。4可行性實(shí)驗(yàn)結(jié)果本節(jié)將結(jié)合大質(zhì)數(shù)測(cè)試系統(tǒng),對(duì)本文提出的基于結(jié)構(gòu)化P2P網(wǎng)絡(luò)的計(jì)算力資源整合方法的各項(xiàng)性能進(jìn)行實(shí)驗(yàn)分析,以驗(yàn)證這一方案的可行性和有效性。所有性能測(cè)試是在SPIS系統(tǒng)上完成的。SPIS系統(tǒng)是由P2P研究小組自主研發(fā)的面向服務(wù)的結(jié)構(gòu)化P2P網(wǎng)絡(luò)支撐平臺(tái),在這一平臺(tái)可以支撐各種基于結(jié)構(gòu)化P2P網(wǎng)絡(luò)的應(yīng)用服務(wù)。本文在這一平臺(tái)上實(shí)現(xiàn)了上述分布式大質(zhì)數(shù)測(cè)試系統(tǒng),并在該系統(tǒng)上對(duì)這一方法的性能進(jìn)行了測(cè)試與分析。4.1通信開裂占總開銷的比重此項(xiàng)實(shí)驗(yàn)系檢驗(yàn)系統(tǒng)控制網(wǎng)絡(luò)通信開銷的能力。實(shí)驗(yàn)中對(duì)1個(gè)長(zhǎng)度為70bit的質(zhì)數(shù)進(jìn)行測(cè)試,參與測(cè)試的節(jié)點(diǎn)共有5個(gè)。這些節(jié)點(diǎn)上同時(shí)還在運(yùn)行其它的任務(wù),因此計(jì)算能力是動(dòng)態(tài)變化的。計(jì)算TT值時(shí)使用的參數(shù)k為0.1,控制網(wǎng)絡(luò)通信時(shí)間所占比重T的上限u設(shè)定為0.25,下限v設(shè)定為0.05,即目標(biāo)是將通信開銷控制在5%到25%的區(qū)間內(nèi)?？蛻舳嗣渴盏揭粋€(gè)工作片斷,記錄當(dāng)時(shí)的TT值和CT值,單位為秒。TT值與CT值曲線如圖3所示。圖3中反映出,由于結(jié)構(gòu)化P2P網(wǎng)絡(luò)的復(fù)雜性以及節(jié)點(diǎn)的動(dòng)態(tài)性,不同的工作片斷從發(fā)出、分配、等待、計(jì)算到結(jié)果返回的代價(jià)(即TT值)處在不斷波動(dòng)的狀態(tài)中,但是通過(guò)動(dòng)態(tài)調(diào)整工作片斷的計(jì)算量,通信開銷所占的比重并不太大。為了更好地觀察通信開銷占總開銷的比重,實(shí)驗(yàn)中以5%為單位統(tǒng)計(jì)了通信開銷在不同范圍內(nèi)的工作片斷的數(shù)量,如圖4所示。圖4反映了大部分工作片斷的通信開銷集中于0～15%的區(qū)間內(nèi),與控制目標(biāo)5%到25%是相符的。對(duì)數(shù)據(jù)進(jìn)一步測(cè)算后得出,所有報(bào)文的總通信開銷是12.1%,同樣在預(yù)期的控制目標(biāo)內(nèi)。相對(duì)于結(jié)構(gòu)化P2P網(wǎng)絡(luò)的動(dòng)態(tài)性及其路由算法的復(fù)雜性,這一數(shù)據(jù)是可以接受的。這一系列實(shí)驗(yàn)結(jié)果表明,第2.3節(jié)提出的控制通信開銷的算法可以有效地控制網(wǎng)絡(luò)通信開銷的比重,提高對(duì)網(wǎng)絡(luò)總體計(jì)算力的利用率。4.2工作片面積分析此項(xiàng)實(shí)驗(yàn)系檢驗(yàn)第2.5節(jié)提出的動(dòng)態(tài)調(diào)整工作片斷發(fā)送速率的能力。實(shí)驗(yàn)過(guò)程與第4.1節(jié)相同。實(shí)驗(yàn)中記錄了每個(gè)工作片斷的發(fā)送時(shí)戳,并以100s為區(qū)間單位統(tǒng)計(jì)發(fā)出的工作片斷數(shù)量。圖5給出了各時(shí)間段內(nèi)發(fā)出工作片斷的數(shù)量。圖5顯示出不同時(shí)間段內(nèi)發(fā)出的工作片斷數(shù)量具有很大的波動(dòng)。分析其原因,主要有兩方面:一是節(jié)點(diǎn)的動(dòng)態(tài)性引起網(wǎng)絡(luò)總體計(jì)算力的不斷變化,二是各個(gè)工作片斷的計(jì)算量也在動(dòng)態(tài)地變化。這個(gè)圖反映出第2.5節(jié)中提出的算法能夠依據(jù)當(dāng)前的網(wǎng)絡(luò)狀況實(shí)時(shí)地調(diào)整工作片斷的發(fā)送速率,而不是以某一固定的速率發(fā)送,可以更好地?cái)M合網(wǎng)絡(luò)的動(dòng)態(tài)變化,充分利用網(wǎng)絡(luò)總體計(jì)算力,也避免了給工作節(jié)點(diǎn)帶來(lái)過(guò)重的負(fù)擔(dān)。第4.3節(jié)進(jìn)一步通過(guò)實(shí)驗(yàn)驗(yàn)證了系統(tǒng)適應(yīng)網(wǎng)絡(luò)總體計(jì)算力變化的能力。4.3節(jié)點(diǎn)數(shù)量對(duì)計(jì)算能耗的影響此項(xiàng)實(shí)驗(yàn)是檢驗(yàn)系統(tǒng)適應(yīng)網(wǎng)絡(luò)總體計(jì)算力變化的能力。實(shí)驗(yàn)中選取了4個(gè)長(zhǎng)度不同的質(zhì)數(shù)進(jìn)行測(cè)試,4個(gè)質(zhì)數(shù)分別是:28405810648960169,852469546242554531,3174309817-9322324351,1008331732565760816359。每個(gè)質(zhì)數(shù)測(cè)試4次,每次使用數(shù)量不同的節(jié)點(diǎn)參與計(jì)算,并記錄計(jì)算所耗費(fèi)的時(shí)間。4個(gè)節(jié)點(diǎn)的CPU均為PentiumIV3.0(HT)。得到節(jié)點(diǎn)數(shù)量與計(jì)算耗時(shí)的關(guān)系如圖6所示。本文的方法將一個(gè)大的計(jì)算任務(wù)分配到網(wǎng)絡(luò)中不同的節(jié)點(diǎn)上,目標(biāo)是盡可能利用節(jié)點(diǎn)的閑散計(jì)算力,因此參與的節(jié)點(diǎn)越多,完成同一個(gè)任務(wù)耗費(fèi)的時(shí)間應(yīng)越少。以圖6對(duì)質(zhì)數(shù)31743098179322324351的實(shí)驗(yàn)數(shù)據(jù)為例,當(dāng)節(jié)點(diǎn)數(shù)量為1,2,3和4時(shí),完成整個(gè)計(jì)算過(guò)程耗費(fèi)的時(shí)間分別是5043s,2878s,1947s和1317s,耗費(fèi)的時(shí)間呈遞減趨勢(shì),這與我們的預(yù)期目標(biāo)是相符合的。同樣,對(duì)其它3個(gè)長(zhǎng)度不同的質(zhì)數(shù)的測(cè)試結(jié)果也是符合預(yù)期目標(biāo)的。從以上實(shí)驗(yàn)數(shù)據(jù)看出,隨著節(jié)點(diǎn)數(shù)量的增長(zhǎng),程序能夠自動(dòng)適應(yīng)計(jì)算力的變化,對(duì)于同一項(xiàng)計(jì)算任務(wù),計(jì)算耗時(shí)隨著節(jié)點(diǎn)數(shù)量的增多而減少。這一結(jié)果表明,上述方案有效利用了網(wǎng)絡(luò)的總體計(jì)算力,能夠適應(yīng)網(wǎng)絡(luò)總體計(jì)算力的變化,適合在動(dòng)態(tài)變化的結(jié)構(gòu)化P2P網(wǎng)絡(luò)上部署。4.