杜經(jīng)緯，張 岳

（1.運(yùn)城學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，山西 運(yùn)城044000；2.中國科學(xué)院 數(shù)學(xué)與系統(tǒng)科學(xué)研究院，北京100120）

0 引 言

目前的異構(gòu)環(huán)境下的計(jì)算資源共享與聚集系統(tǒng)往往采用集中式的結(jié)構(gòu)，存在著規(guī)模小、可擴(kuò)展性和穩(wěn)健性差的缺點(diǎn)［1－3］，同時(shí)它們能夠計(jì)算的問題局限在沒有數(shù)據(jù)依賴的主－從 （Master－worker）模型 的 并 行 計(jì) 算［4－7］。 最 近 后 續(xù) 的非集中式的網(wǎng)絡(luò)拓?fù)?，例如對等網(wǎng)絡(luò)結(jié)構(gòu)［8－9］、層次結(jié)構(gòu)［10］、基于組的對等網(wǎng)絡(luò)、基于代理網(wǎng)絡(luò)的結(jié)構(gòu)［11］、帶超級節(jié)點(diǎn)的對等網(wǎng)絡(luò)等［12］相繼被采用，在一定程度上解決了傳統(tǒng)的計(jì)算平臺(tái)的不足。

本文提出的基于樹型層次結(jié)構(gòu)的計(jì)算資源共享與聚集系統(tǒng) （tree－based layered sharing and aggregation，TLSA）也是一種非集中式的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。TLSA系統(tǒng)由對等網(wǎng)絡(luò)環(huán)境下的空閑節(jié)點(diǎn)組成，形成一個(gè)平衡的樹型層次結(jié)構(gòu)，節(jié)點(diǎn)可以尋找到系統(tǒng)中最近最合適的空閑計(jì)算資源來完成大量的子任務(wù)。TLSA中子任務(wù)是一個(gè)很重要的概念，它是由一個(gè)大的分布式計(jì)算問題所劃分后的編程單元，是粗粒度的并行計(jì)算的基本單元。TLSA系統(tǒng)中的每個(gè)節(jié)點(diǎn)都可以請求子任務(wù)的執(zhí)行，該請求過程通過鄰居節(jié)點(diǎn)和高效的資源發(fā)現(xiàn)協(xié)議就可以路由到最合適的空閑計(jì)算節(jié)點(diǎn)。樹型結(jié)構(gòu)的網(wǎng)絡(luò)拓?fù)渫ㄟ^自組織的可靠性協(xié)議來維護(hù)，同時(shí)保證了系統(tǒng)的比較低的消息通信量和平衡的處理器負(fù)載。本文的研究點(diǎn)關(guān)注在網(wǎng)絡(luò)拓?fù)涞臉?gòu)造與維護(hù)，最后通過一個(gè)簡單的資源分配算法對TLSA系統(tǒng)進(jìn)行了測試與性能分析，測試結(jié)果表明對于分布式計(jì)算中大量的子任務(wù)TLSA可以很快的完成，而且具有比較低的消息通信量。

1 樹型拓?fù)涞捏w系結(jié)構(gòu)

TLSA系統(tǒng)根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和資源管理的功能需求，可以劃分為3個(gè)方面的層次結(jié)構(gòu)，從下層到上層分別是節(jié)點(diǎn)連接協(xié)議層、資源可用性協(xié)議層、計(jì)算資源的發(fā)現(xiàn)協(xié)議層。

節(jié)點(diǎn)連接協(xié)議層：它定義了對等網(wǎng)絡(luò)中維護(hù)應(yīng)用層覆蓋網(wǎng)絡(luò)的節(jié)點(diǎn)連接協(xié)議。它保持了一個(gè)類似于B樹的拓?fù)浣Y(jié)構(gòu)［13］，所以它是一種平衡的結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)具有m到2m個(gè)孩子，樹的高度不會(huì)超過Log（N），N為對等網(wǎng)絡(luò)的節(jié)點(diǎn)總數(shù)。該協(xié)議還描述了節(jié)點(diǎn)加入和退出網(wǎng)絡(luò)的算法，描述了該樹是如何保持平衡及節(jié)點(diǎn)異常退出和如何保持這種平衡結(jié)構(gòu)。

資源可用性協(xié)議層：描述了空閑計(jì)算資源相關(guān)的信息，TLSA中的每個(gè)節(jié)點(diǎn)都會(huì)存儲(chǔ)其在B樹中的全局狀態(tài)和分支狀態(tài)，而且可以完成它自己和其雙親節(jié)點(diǎn)的更新，重新計(jì)算資源的狀態(tài)。該協(xié)議使用驗(yàn)證技術(shù)使樹的上層節(jié)點(diǎn)避免網(wǎng)絡(luò)消息的洪泛，同時(shí)維持精確的可用性信息，使網(wǎng)絡(luò)的利用率最高。該驗(yàn)證過程技術(shù)是穩(wěn)定的與可靠的。

計(jì)算資源發(fā)現(xiàn)協(xié)議層：它使用了可用性協(xié)議中的每個(gè)分支的信息，從根節(jié)點(diǎn)自上往下來路由空閑的資源。它試圖發(fā)現(xiàn)最鄰近、最合適的空閑計(jì)算資源來給子任務(wù)。所以該資源搜索過程是通過一系列的網(wǎng)絡(luò)跳數(shù)來完成，網(wǎng)絡(luò)跳數(shù)是依賴于樹型結(jié)構(gòu)的高度，它不會(huì)超過Log（N）。

在這3個(gè)協(xié)議層之上，應(yīng)用開發(fā)員可以實(shí)現(xiàn)不同的資源分配策略，利用這種三層的平衡樹型結(jié)構(gòu)，處理空閑的處理器資源，TLSA系統(tǒng)也可以把網(wǎng)絡(luò)中的其他資源考慮進(jìn)去，例如內(nèi)存資源，網(wǎng)絡(luò)帶寬資源與空閑磁盤空間等，這些都可以在資源可用性協(xié)議里面完成驗(yàn)證。

2 樹型拓?fù)涞墓ぷ鳈C(jī)制

2.1 節(jié)點(diǎn)的連接協(xié)議

應(yīng)用層覆蓋網(wǎng)絡(luò)是一種樹型的層次結(jié)構(gòu)，與分布式哈希表不同的是，分布式哈希表中依賴于統(tǒng)一的資源描述，而且存儲(chǔ)的是樹的索引的一部分，通常用于范圍查詢。TLSA的這種平衡樹結(jié)構(gòu)使每個(gè)節(jié)點(diǎn)只需要維護(hù)樹中的一個(gè)節(jié)點(diǎn)，更加適合于非統(tǒng)一的資源分配，因?yàn)锽樹在節(jié)點(diǎn)加入和退出的時(shí)候可以自動(dòng)的維持平衡，允許節(jié)點(diǎn)有多余兩個(gè)的孩子節(jié)點(diǎn)，使樹的高度維持在對數(shù)函數(shù)級別。

樹型結(jié)構(gòu)的最要的功能是聚集位置鄰近的計(jì)算資源。TLSA中一個(gè)節(jié)點(diǎn)可以與最鄰近的通信，因?yàn)樗鼈兌际枪?jié)點(diǎn)的兄弟或者子孫節(jié)點(diǎn)，而且它可以通過雙親節(jié)點(diǎn)達(dá)到其他的區(qū)域。關(guān)于最鄰近的節(jié)點(diǎn)通信，TLSA使用了一個(gè)高效的方式來組織節(jié)點(diǎn)，即是通過物理位置鄰近，它是通過節(jié)點(diǎn)的IP地址來判斷的。根據(jù)文獻(xiàn) ［14］中的方法，節(jié)點(diǎn)可以很快的判斷并從樹型結(jié)構(gòu)中進(jìn)行插入，同時(shí)保證了低延遲與高帶寬。

TLSA中的樹與原始的B樹有一些區(qū)別，在B樹中的節(jié)點(diǎn)可能維持超過一個(gè)值，該值為IP地址。那些B樹將轉(zhuǎn)化成一組兄弟，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)擁有一個(gè)值，通過這種一對一的映射，每個(gè)節(jié)點(diǎn)完成了樹型結(jié)構(gòu)的拓?fù)涔芾?。而且每個(gè)內(nèi)部節(jié)點(diǎn)具有一對值，它表達(dá)了節(jié)點(diǎn)與子孫節(jié)點(diǎn)的IP地址的間隔。這些間隔在樹型結(jié)構(gòu)中當(dāng)節(jié)點(diǎn)加入和刪除的時(shí)候被用來完成路由消息。它們之間的區(qū)別見圖1。與B樹一樣，TLSA中也存在一個(gè)常量m，節(jié)點(diǎn)具有m～2m個(gè)兄弟節(jié)點(diǎn)。如果這個(gè)限制超越了，樹型結(jié)果必須重新建立平衡。當(dāng)一組兄弟節(jié)點(diǎn)具有超過2m個(gè)節(jié)點(diǎn)，它必須劃分成2組。另外一個(gè)方面如果它少于m個(gè)節(jié)點(diǎn)，它必須尋找一個(gè)相鄰組并且加入進(jìn)去。

圖1 B樹與TLSA的層次網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

考慮到容錯(cuò)的問題，每個(gè)節(jié)點(diǎn)知道其同一層級的k個(gè)前驅(qū)和k個(gè)后繼，當(dāng)節(jié)點(diǎn)異常退出，樹型結(jié)構(gòu)將通過這些前驅(qū)和后繼來完成維護(hù)，因?yàn)楣?jié)點(diǎn)的離開會(huì)影響到它的兄弟和雙親節(jié)點(diǎn)。很明顯的是k的設(shè)置是一個(gè)協(xié)議，它考慮到了樹型結(jié)構(gòu)管理的負(fù)載和容錯(cuò)特性。節(jié)點(diǎn)加入與退出的描述如下：

具有兩種類型的操作會(huì)影響到網(wǎng)絡(luò)的結(jié)構(gòu)，另外作為一個(gè)邊界效應(yīng)，必須有一個(gè)重新平衡觸發(fā)機(jī)制。節(jié)點(diǎn)加入系統(tǒng)往往是容易的，當(dāng)一個(gè)節(jié)點(diǎn)請求加入的時(shí)候，請求消息通過樹型結(jié)構(gòu)進(jìn)行路由。

請求過程尋找新節(jié)點(diǎn)的IP地址所包含的間隔情況，然后它將達(dá)到具有最鄰近的IP地址的節(jié)點(diǎn)，新節(jié)點(diǎn)將成為最鄰近的兄弟，新節(jié)點(diǎn)更新它的鄰居的地址。當(dāng)雙親節(jié)點(diǎn)驗(yàn)證了新節(jié)點(diǎn)后，如果雙親節(jié)點(diǎn)的孩子超過了2m，就完成組的劃分，該規(guī)律和B樹類似。當(dāng)一個(gè)節(jié)點(diǎn)加入一個(gè)組之后，每個(gè)組內(nèi)成員檢查該組內(nèi)的數(shù)目，計(jì)算數(shù)目是通過參考節(jié)點(diǎn)的前驅(qū)和后繼節(jié)點(diǎn)列表完成的。當(dāng)一個(gè)根節(jié)點(diǎn)具有k個(gè)前驅(qū)和k個(gè)后繼后，它將尋找一個(gè)子孫的葉子節(jié)點(diǎn)，然后成為樹的新根。這種方式限制了使根不會(huì)超過2k個(gè)節(jié)點(diǎn)。

當(dāng)節(jié)點(diǎn)離開的時(shí)候，它必須檢查自身的孩子節(jié)點(diǎn)情況，如果有孩子節(jié)點(diǎn)，它將尋找一個(gè)葉子節(jié)點(diǎn)使其成為所有孩子的雙親。這個(gè)過程就像創(chuàng)建一個(gè)新根節(jié)點(diǎn)類似。如果節(jié)點(diǎn)沒有孩子，那么它將驗(yàn)證它的兄弟節(jié)點(diǎn)和雙親節(jié)點(diǎn)，然后更新它的地址列表。和節(jié)點(diǎn)的加入過程一樣，如果雙親節(jié)點(diǎn)接收到了節(jié)點(diǎn)離開消息，它將檢查孩子節(jié)點(diǎn)數(shù)目是否小于m，如果小于m，它將請求前驅(qū)節(jié)點(diǎn)或后繼節(jié)點(diǎn)，發(fā)送它的孩子直到其達(dá)到m。如果所有的孩子都不超過2m，它們將成為一個(gè)分支。

2.2 資源可用性協(xié)議

為了使用資源發(fā)現(xiàn)協(xié)議來尋找空閑的計(jì)算資源，每個(gè)節(jié)點(diǎn)內(nèi)部必須存儲(chǔ)它子孫相關(guān)的信息，而且更加多的是與分支相關(guān)的信息。它描述了分支上大約的空閑處理器的數(shù)目，最大計(jì)算能力和到達(dá)目的節(jié)點(diǎn)的最小網(wǎng)絡(luò)跳數(shù)。通過這種方式可用性信息的管理具有可擴(kuò)展性、因?yàn)樗恢皇且蕾囉诠?jié)點(diǎn)的數(shù)目。

每個(gè)節(jié)點(diǎn)的分支上存儲(chǔ)的信息必須和它的雙親通信，這樣才可以高效的把路由請求傳遞到空間計(jì)算節(jié)點(diǎn)。所以每個(gè)節(jié)點(diǎn)不僅具有分支的信息，而且具有它的子分支的信息。用這種方式信息的發(fā)布就是很關(guān)鍵的，因?yàn)樗３指?，同時(shí)要避免網(wǎng)絡(luò)洪泛，特別是在根節(jié)點(diǎn)附近并且每層上具有很少節(jié)點(diǎn)的情況。這種發(fā)布的過程是通過資源可用性協(xié)議來完成，基本上當(dāng)一個(gè)節(jié)點(diǎn)接收到一個(gè)改變它的孩子節(jié)點(diǎn)的消息通知的時(shí)候，它將決定是否通知它的雙親。通過具有最大計(jì)算能力 （computing capacity，CC）和到達(dá)目的節(jié)點(diǎn)的最小網(wǎng)絡(luò)跳數(shù) （network hop，NH）的限制，這個(gè)過程就十分簡單。內(nèi)部節(jié)點(diǎn)在它的孩子節(jié)點(diǎn)和自身必須分別重新計(jì)算新的CC和NH的最大值和最小值。如果這些值改變了，立刻重新路由新的通知消息給它的雙親節(jié)點(diǎn)。

這個(gè)問題隨著TLSA計(jì)算資源節(jié)點(diǎn)數(shù)目的增加而出現(xiàn)，因?yàn)楫?dāng)一個(gè)節(jié)點(diǎn)已經(jīng)準(zhǔn)備好的時(shí)候，它的祖先節(jié)點(diǎn)也在增加。如果通知驗(yàn)證隨著狀態(tài)改變而發(fā)送，根節(jié)點(diǎn)將通知所有節(jié)點(diǎn)，可能會(huì)導(dǎo)致樹型結(jié)構(gòu)頂部的高消息通信量。為了解決這個(gè)問題，TLSA中在樹的頂部設(shè)計(jì)了一個(gè)延緩消息通信機(jī)制，減少因?yàn)槁酚傻巾敳康南⒘俊?/p>

2.3 計(jì)算資源的發(fā)現(xiàn)協(xié)議

正如前面所描述的，當(dāng)節(jié)點(diǎn)有許多子任務(wù)需要計(jì)算時(shí)，它將請求網(wǎng)絡(luò)發(fā)現(xiàn)空閑的計(jì)算資源，該過程的完成就是資源的發(fā)現(xiàn)協(xié)議，它使用資源可用性協(xié)議層描述的信息來判斷。通過啟發(fā)式規(guī)則，它將試圖分配最快，最鄰近的空閑節(jié)點(diǎn)，使子任務(wù)的完成最快和最合適。

當(dāng)一個(gè)節(jié)點(diǎn)接收到消息需要計(jì)算n個(gè)子任務(wù)的時(shí)候，它首先檢測其自身是否已經(jīng)處于準(zhǔn)備狀態(tài)，如果準(zhǔn)備好了，它從消息中獲得一個(gè)子任務(wù)。然后它把剩余的子任務(wù)根據(jù)每個(gè)分支所擁有的空閑計(jì)算節(jié)點(diǎn)來分配給它的孩子節(jié)點(diǎn)，那些具有大的計(jì)算能力CC和比較小的網(wǎng)絡(luò)跳數(shù)NH的空閑節(jié)點(diǎn)具有優(yōu)先級。如果所有的孩子節(jié)點(diǎn)不能夠完成所有的子任務(wù)，那么一個(gè)帶有最后子任務(wù)的新的消息將發(fā)送到父節(jié)點(diǎn)，以便其可以達(dá)到其他距離比較遠(yuǎn)的分支。當(dāng)這個(gè)消息達(dá)到了樹型結(jié)構(gòu)的根節(jié)點(diǎn)時(shí)，它將不能發(fā)送到其他的分支了，它將返回最原始的初始化節(jié)點(diǎn)，這也意味著TLSA中沒有空閑的計(jì)算資源可以利用。這里每個(gè)孩子節(jié)點(diǎn)有空閑節(jié)點(diǎn)和它的分支節(jié)點(diǎn)的空閑域，計(jì)算能力域用來描述最大的計(jì)算能力max.power，網(wǎng)絡(luò)跳數(shù)域用來描述到達(dá)目的節(jié)點(diǎn)的最小網(wǎng)絡(luò)跳數(shù)min.hops。空閑資源的發(fā)現(xiàn)算法如下所描述。

discover（msg）｛

if i＿am＿ready｛start＿task；msg.num＿tasks－－；

｝

while msg.n＞0or branch＿full｛

for i in children｛

if （i.power ＞ ＝ max.power）and （i.hops ＜min.hops）

max＝i；

｝

add＿task＿to （max）；

msg.num＿tasks－－；

｝

if msg.num＿tasks＞0｛

if i＿h(yuǎn)ave＿father

send＿father （msg）；

else

send＿client＿node（msg）；

｝ ｝

最壞的情況是網(wǎng)絡(luò)中把子任務(wù)分配給葉子節(jié)點(diǎn)，這樣請求過程必須從樹型結(jié)構(gòu)的根部到達(dá)終端節(jié)點(diǎn)，這個(gè)也是消息所經(jīng)過的最長的路徑。在樹型結(jié)構(gòu)中每個(gè)分支上的空閑計(jì)算資源的發(fā)現(xiàn)都是并行的進(jìn)行的，而且從終端節(jié)點(diǎn)到樹的根部也是執(zhí)行相同的過程，最壞所有的資源搜索的過程不會(huì)超過O（2logm N）步的網(wǎng)絡(luò)跳數(shù)，N為TLSA中的所有節(jié)點(diǎn)數(shù)，所以這樣使網(wǎng)絡(luò)的資源發(fā)現(xiàn)協(xié)議具有可擴(kuò)展性與高效性。

這種網(wǎng)絡(luò)拓?fù)涫且环N比較好的結(jié)構(gòu)，節(jié)點(diǎn)之間的相互協(xié)同能夠使網(wǎng)絡(luò)上的消息路由到最合適的目的節(jié)點(diǎn)，但是當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)頻繁異常失效時(shí)，接收方并不是有質(zhì)量保證的。鑒于這種原因，當(dāng)使用超時(shí)機(jī)制來搜索資源的時(shí)候，所有的原始節(jié)點(diǎn)和目的節(jié)點(diǎn)在資源發(fā)現(xiàn)階段必須避免這個(gè)問題。

3 系統(tǒng)測試與性能分析

3.1 資源發(fā)現(xiàn)時(shí)間

TLSA的測試是通過模擬器來完成的，模擬器通過OMNeT＋＋模擬框架［15］。由于TLSA關(guān)注的網(wǎng)絡(luò)拓?fù)涞木S護(hù)，所以資源分配方式上使用了簡單的調(diào)度算法，即只要發(fā)現(xiàn)了資源，就分配子任務(wù)，類似于先來先服務(wù)FCFS調(diào)度。測試性能指標(biāo)關(guān)注的是空閑計(jì)算節(jié)點(diǎn)的發(fā)現(xiàn)時(shí)間、消息的通信量與處理器的負(fù)載。每個(gè)測試過程都是通過改變TLSA中的節(jié)點(diǎn)數(shù)目、B樹的參數(shù)m等來體現(xiàn)網(wǎng)絡(luò)拓?fù)涞某叽缗c協(xié)議對系統(tǒng)性能的影響。

模擬器中一共設(shè)置了50 000個(gè)節(jié)點(diǎn)，m的值為從6到10。調(diào)整子任務(wù)的數(shù)目與數(shù)據(jù)文件的大小來重新設(shè)置實(shí)驗(yàn)環(huán)境。TLSA中有3個(gè)約束條件：網(wǎng)絡(luò)延遲大約為200ms，網(wǎng)絡(luò)之間的連接速度為1Mb／s，節(jié)點(diǎn)的平均計(jì)算能力被設(shè)置為2000MIPS。

測試的時(shí)間體現(xiàn)的是節(jié)點(diǎn)數(shù)目和孩子節(jié)點(diǎn)數(shù)目對資源發(fā)現(xiàn)速度的影響程度。正如所期望的，在n個(gè)請求中到達(dá)最后一個(gè)空閑計(jì)算節(jié)點(diǎn)的網(wǎng)絡(luò)跳數(shù)時(shí)間復(fù)雜度為O（2 logm n）。因?yàn)檫@個(gè)原因，當(dāng)系統(tǒng)中的n增加的時(shí)候，TLSA的網(wǎng)絡(luò)拓?fù)溆斜容^好的性能。空閑計(jì)算資源的發(fā)現(xiàn)時(shí)間可以通過圖2中顯示，它是呈對數(shù)函數(shù)增加趨勢。m＝4，TLSA可以在2.5s內(nèi)完成到大約9600個(gè)子任務(wù)；m＝10，1.3s內(nèi)完成到大約9600個(gè)子任務(wù)。

圖2 TLSA中資源發(fā)現(xiàn)時(shí)間隨子任務(wù)數(shù)的變化

3.2 消息通信量

對于TLSA系統(tǒng)的網(wǎng)絡(luò)消息通信量和處理器的負(fù)載在兩個(gè)設(shè)置環(huán)境下進(jìn)行了測試：節(jié)點(diǎn)普通的參入情況和高度活躍的情況。正常的活動(dòng)意味著系統(tǒng)中有一定的消息請求，并且隨機(jī)的選擇節(jié)點(diǎn)，但是網(wǎng)絡(luò)拓?fù)洳⒉皇欠浅Ｃβ怠Ｔ诟呋钴S情況下，每個(gè)節(jié)點(diǎn)都是處于繁忙狀態(tài)，持續(xù)的接收到新的消息請求。消息通信量通過每秒鐘處理的字節(jié)數(shù)來體現(xiàn)。處理器的負(fù)載在模擬過程中更加難以測試，但是在處理器上的每個(gè)消息幾乎是常數(shù)，所以也是通過每秒鐘處理器中處理的數(shù)目來體現(xiàn)。表1和表2顯示了正常情況和活躍情況下的測試結(jié)果。它們顯示了m的值與還有樹的高度變化情況 （m＝10，網(wǎng)絡(luò)帶寬為1Mb／s），也體現(xiàn)了平均的處理器負(fù)載和最大處理器負(fù)載情況。在網(wǎng)絡(luò)中50000的節(jié)點(diǎn)數(shù)目下從根到葉子的消息通信量。

表1 正常情況下的處理器負(fù)載與消息通信量的測試結(jié)果

表2 活躍情況下的處理器負(fù)載與消息通信量的測試結(jié)果

從表1、表2中可以看出，資源發(fā)現(xiàn)協(xié)議受到m的影響，TLSA系統(tǒng)的整體負(fù)載隨著網(wǎng)絡(luò)拓?fù)錁涞母叨榷兓?，所以需要在樹的高度和m之間進(jìn)行平衡。除了這些外，通過使用資源的可用性協(xié)議，在正常的參入情況下，葉子節(jié)點(diǎn)處的網(wǎng)絡(luò)消息通信量和處理器的負(fù)載比根節(jié)點(diǎn)處的要大。網(wǎng)絡(luò)中控制的消息通信量幾乎只有1KB／s，它是小于整體網(wǎng)絡(luò)帶寬1Mb／s的1%，這些測試結(jié)果是具有重要意義的。在TLSA的高度活躍情況下，節(jié)點(diǎn)處的性能因?yàn)楸容^高的處理器負(fù)載和網(wǎng)絡(luò)消息通信量而受到影響。

從表1和表2中看出，TLSA的消息控制負(fù)載比較低。在正常的情況下網(wǎng)絡(luò)消息通信量是1485B／s，處理器的負(fù)載只有5.77條／s。在系統(tǒng)活躍的情況下網(wǎng)絡(luò)的消息通信量為21947B／s，處理器的負(fù)載為65.3條／s，這些都是系統(tǒng)活躍比較特殊的實(shí)驗(yàn)情形。

4 結(jié)束語

本文提出了一個(gè)基于樹型層次結(jié)構(gòu)的計(jì)算資源共享與聚集系統(tǒng)TLSA。通過模擬測試結(jié)果表明對于大規(guī)模的子任務(wù)，TLSA可以在很短的時(shí)間內(nèi)尋找到空閑資源，而且網(wǎng)絡(luò)消息通信量不超過O （logmN），具有低消息通信量、非集中性、可擴(kuò)展性、自組織特性。下一步的工作是在真實(shí)的環(huán)境下測試TLSA的性能，同時(shí)把更加多并行計(jì)算問題運(yùn)用到TLSA系統(tǒng)之上。

［1］Anderson D P.BOINC：A system for public－resource computingand storage ［C］.Proceedings of the Fifth International Workshop of Grid Computing.Washington，DC：IEEE Computer Society Press，2004：4－10.

［2］Franck Cappello，Samir Djilali，Gilles Fedak，et al.Computing on largescale distributed systems：Xtrem web architecture programming models security tests and convergence with grid ［J］.Future Generation Computer System，2005，21 （3）：417－437.

［3］Andrade N，Costa L，Germoglio G，et al.Peer－to－peer grid computing with the ourgrid community ［C］.Proceedings of the SBRC－IV Salao De Ferramentas，2005.

［4］Michele Amoretti，F(xiàn)rancesco Zanichelli，Gianni Conte.SP2A：A service－oriented framework for P2P－based grids ［C］.New York：Proceedings of 3rd International Workshop on Middleware for Grid Computing，2005：1－6.

［5］Shudo K，Tanaka Y，Sekiguchi S.P3：P2P－based middleware enabling transfer and aggregation of computational resources［C］.Proceedings of the IEEE International Symposium on Cluster Computing and the Grid.Washington，DC：IEEE Computer Society Press，2005：259－266.

［6］Anglano C，Canonico M，Guazzone G，et al.Peer－to－peer desktop grids in the real world：The share grid project ［C］.Proceedings of 8th IEEE International Symposium on Cluster Computing and the Grid，2008：621－626.

［7］BUTT A R，F(xiàn)ANG X，HU Y C，et al.Java peer－to－peer and accountability：Building blocks for distributed cycle sharing［C］.Virtual Machine Research and Technology Symposium，2004：163－176.

［8］Merz P，Gorunova K.Efficient broadcast in P2Pgrids ［C］.Proceedings of the IEEE／ACM International Symposium on Cluster Computing and the Grid，2005.

［9］Mason R，Kelly W.G2－p2p：A fully decentralized fault－tolerant cycle－stealing framework［J］.ACSW Frontiers，2005：33－39.

［10］Jerome Verbeke，Neelakanth Nadgir，Greg Ruetsch，et al.Sun microsystems inc framework for peer－to－peer distributed computing in a heterogenuous and decentralized environment［C］.Proc of the Third International Workshop on Grid Computing，2002：1－12.

［11］Neary M O，Phipps A，Richman S，et al.Javelin 2.0：Javabased parallel computing on the internet［G］.LNCS 1900：6th Int’l Euro－Par Conference. Springer Verlag，2000：1231－1238.

［12］YANG B，Garcia－Molina H.Designing a super－peer network［C］.Proceedings of the 19th International Conference on Data Engineering，2003.

［13］Jagadish H V，Ooi B，VU Q，et al.Vbi－tree：A peer topeer framework for supporting multi－dimensional indexing schemes［C］.22nd IEEE International Conference on Data Engineering，2006.

［14］Freedman M，Vutukuru M，F(xiàn)eamster N，et al.Geographic locality of IP prefixes［C］.Berkeley，CA：Internet Measurement Conference，2005.

［15］OMNeT＋＋模擬框架 ［S］.http：／／www.omnetpp.org／，2010.