基于樹型層次結構的計算資源共享與聚集

杜經緯，張 岳

（1.運城學院 計算機科學與技術系，山西 運城044000；2.中國科學院 數學與系統科學研究院，北京100120）

0 引 言

目前的異構環境下的計算資源共享與聚集系統往往采用集中式的結構，存在著規模小、可擴展性和穩健性差的缺點［1－3］，同時它們能夠計算的問題局限在沒有數據依賴的主－從 （Master－worker）模型 的 并 行 計 算［4－7］。 最 近 后 續 的非集中式的網絡拓撲，例如對等網絡結構［8－9］、層次結構［10］、基于組的對等網絡、基于代理網絡的結構［11］、帶超級節點的對等網絡等［12］相繼被采用，在一定程度上解決了傳統的計算平臺的不足。

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

1 樹型拓撲的體系結構

TLSA系統根據網絡拓撲結構和資源管理的功能需求，可以劃分為3個方面的層次結構，從下層到上層分別是節點連接協議層、資源可用性協議層、計算資源的發現協議層。

節點連接協議層：它定義了對等網絡中維護應用層覆蓋網絡的節點連接協議。它保持了一個類似于B樹的拓撲結構［13］，所以它是一種平衡的結構，每個節點具有m到2m個孩子，樹的高度不會超過Log（N），N為對等網絡的節點總數。該協議還描述了節點加入和退出網絡的算法，描述了該樹是如何保持平衡及節點異常退出和如何保持這種平衡結構。

資源可用性協議層：描述了空閑計算資源相關的信息，TLSA中的每個節點都會存儲其在B樹中的全局狀態和分支狀態，而且可以完成它自己和其雙親節點的更新，重新計算資源的狀態。該協議使用驗證技術使樹的上層節點避免網絡消息的洪泛，同時維持精確的可用性信息，使網絡的利用率最高。該驗證過程技術是穩定的與可靠的。

計算資源發現協議層：它使用了可用性協議中的每個分支的信息，從根節點自上往下來路由空閑的資源。它試圖發現最鄰近、最合適的空閑計算資源來給子任務。所以該資源搜索過程是通過一系列的網絡跳數來完成，網絡跳數是依賴于樹型結構的高度，它不會超過Log（N）。

在這3個協議層之上，應用開發員可以實現不同的資源分配策略，利用這種三層的平衡樹型結構，處理空閑的處理器資源，TLSA系統也可以把網絡中的其他資源考慮進去，例如內存資源，網絡帶寬資源與空閑磁盤空間等，這些都可以在資源可用性協議里面完成驗證。

2 樹型拓撲的工作機制

2.1 節點的連接協議

應用層覆蓋網絡是一種樹型的層次結構，與分布式哈希表不同的是，分布式哈希表中依賴于統一的資源描述，而且存儲的是樹的索引的一部分，通常用于范圍查詢。TLSA的這種平衡樹結構使每個節點只需要維護樹中的一個節點，更加適合于非統一的資源分配，因為B樹在節點加入和退出的時候可以自動的維持平衡，允許節點有多余兩個的孩子節點，使樹的高度維持在對數函數級別。

樹型結構的最要的功能是聚集位置鄰近的計算資源。TLSA中一個節點可以與最鄰近的通信，因為它們都是節點的兄弟或者子孫節點，而且它可以通過雙親節點達到其他的區域。關于最鄰近的節點通信，TLSA使用了一個高效的方式來組織節點，即是通過物理位置鄰近，它是通過節點的IP地址來判斷的。根據文獻 ［14］中的方法，節點可以很快的判斷并從樹型結構中進行插入，同時保證了低延遲與高帶寬。

TLSA中的樹與原始的B樹有一些區別，在B樹中的節點可能維持超過一個值，該值為IP地址。那些B樹將轉化成一組兄弟，網絡中每個節點擁有一個值，通過這種一對一的映射，每個節點完成了樹型結構的拓撲管理。而且每個內部節點具有一對值，它表達了節點與子孫節點的IP地址的間隔。這些間隔在樹型結構中當節點加入和刪除的時候被用來完成路由消息。它們之間的區別見圖1。與B樹一樣，TLSA中也存在一個常量m，節點具有m～2m個兄弟節點。如果這個限制超越了，樹型結果必須重新建立平衡。當一組兄弟節點具有超過2m個節點，它必須劃分成2組。另外一個方面如果它少于m個節點，它必須尋找一個相鄰組并且加入進去。

圖1 B樹與TLSA的層次網絡拓撲結構

考慮到容錯的問題，每個節點知道其同一層級的k個前驅和k個后繼，當節點異常退出，樹型結構將通過這些前驅和后繼來完成維護，因為節點的離開會影響到它的兄弟和雙親節點。很明顯的是k的設置是一個協議，它考慮到了樹型結構管理的負載和容錯特性。節點加入與退出的描述如下：

具有兩種類型的操作會影響到網絡的結構，另外作為一個邊界效應，必須有一個重新平衡觸發機制。節點加入系統往往是容易的，當一個節點請求加入的時候，請求消息通過樹型結構進行路由。

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

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

2.2 資源可用性協議

為了使用資源發現協議來尋找空閑的計算資源，每個節點內部必須存儲它子孫相關的信息，而且更加多的是與分支相關的信息。它描述了分支上大約的空閑處理器的數目，最大計算能力和到達目的節點的最小網絡跳數。通過這種方式可用性信息的管理具有可擴展性、因為它不只是依賴于節點的數目。

每個節點的分支上存儲的信息必須和它的雙親通信，這樣才可以高效的把路由請求傳遞到空間計算節點。所以每個節點不僅具有分支的信息，而且具有它的子分支的信息。用這種方式信息的發布就是很關鍵的，因為它保持更新，同時要避免網絡洪泛，特別是在根節點附近并且每層上具有很少節點的情況。這種發布的過程是通過資源可用性協議來完成，基本上當一個節點接收到一個改變它的孩子節點的消息通知的時候，它將決定是否通知它的雙親。通過具有最大計算能力 （computing capacity，CC）和到達目的節點的最小網絡跳數 （network hop，NH）的限制，這個過程就十分簡單。內部節點在它的孩子節點和自身必須分別重新計算新的CC和NH的最大值和最小值。如果這些值改變了，立刻重新路由新的通知消息給它的雙親節點。

這個問題隨著TLSA計算資源節點數目的增加而出現，因為當一個節點已經準備好的時候，它的祖先節點也在增加。如果通知驗證隨著狀態改變而發送，根節點將通知所有節點，可能會導致樹型結構頂部的高消息通信量。為了解決這個問題，TLSA中在樹的頂部設計了一個延緩消息通信機制，減少因為路由到頂部的消息量。

2.3 計算資源的發現協議

正如前面所描述的，當節點有許多子任務需要計算時，它將請求網絡發現空閑的計算資源，該過程的完成就是資源的發現協議，它使用資源可用性協議層描述的信息來判斷。通過啟發式規則，它將試圖分配最快，最鄰近的空閑節點，使子任務的完成最快和最合適。

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

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＿have＿father

send＿father （msg）；

else

send＿client＿node（msg）；

｝ ｝

最壞的情況是網絡中把子任務分配給葉子節點，這樣請求過程必須從樹型結構的根部到達終端節點，這個也是消息所經過的最長的路徑。在樹型結構中每個分支上的空閑計算資源的發現都是并行的進行的，而且從終端節點到樹的根部也是執行相同的過程，最壞所有的資源搜索的過程不會超過O（2logm N）步的網絡跳數，N為TLSA中的所有節點數，所以這樣使網絡的資源發現協議具有可擴展性與高效性。

這種網絡拓撲是一種比較好的結構，節點之間的相互協同能夠使網絡上的消息路由到最合適的目的節點，但是當網絡中的節點頻繁異常失效時，接收方并不是有質量保證的。鑒于這種原因，當使用超時機制來搜索資源的時候，所有的原始節點和目的節點在資源發現階段必須避免這個問題。

3 系統測試與性能分析

3.1 資源發現時間

TLSA的測試是通過模擬器來完成的，模擬器通過OMNeT＋＋模擬框架［15］。由于TLSA關注的網絡拓撲的維護，所以資源分配方式上使用了簡單的調度算法，即只要發現了資源，就分配子任務，類似于先來先服務FCFS調度。測試性能指標關注的是空閑計算節點的發現時間、消息的通信量與處理器的負載。每個測試過程都是通過改變TLSA中的節點數目、B樹的參數m等來體現網絡拓撲的尺寸與協議對系統性能的影響。

模擬器中一共設置了50 000個節點，m的值為從6到10。調整子任務的數目與數據文件的大小來重新設置實驗環境。TLSA中有3個約束條件：網絡延遲大約為200ms，網絡之間的連接速度為1Mb／s，節點的平均計算能力被設置為2000MIPS。

測試的時間體現的是節點數目和孩子節點數目對資源發現速度的影響程度。正如所期望的，在n個請求中到達最后一個空閑計算節點的網絡跳數時間復雜度為O（2 logm n）。因為這個原因，當系統中的n增加的時候，TLSA的網絡拓撲有比較好的性能。空閑計算資源的發現時間可以通過圖2中顯示，它是呈對數函數增加趨勢。m＝4，TLSA可以在2.5s內完成到大約9600個子任務；m＝10，1.3s內完成到大約9600個子任務。

圖2 TLSA中資源發現時間隨子任務數的變化

3.2 消息通信量

對于TLSA系統的網絡消息通信量和處理器的負載在兩個設置環境下進行了測試：節點普通的參入情況和高度活躍的情況。正常的活動意味著系統中有一定的消息請求，并且隨機的選擇節點，但是網絡拓撲并不是非常忙碌。在高活躍情況下，每個節點都是處于繁忙狀態，持續的接收到新的消息請求。消息通信量通過每秒鐘處理的字節數來體現。處理器的負載在模擬過程中更加難以測試，但是在處理器上的每個消息幾乎是常數，所以也是通過每秒鐘處理器中處理的數目來體現。表1和表2顯示了正常情況和活躍情況下的測試結果。它們顯示了m的值與還有樹的高度變化情況 （m＝10，網絡帶寬為1Mb／s），也體現了平均的處理器負載和最大處理器負載情況。在網絡中50000的節點數目下從根到葉子的消息通信量。

表1 正常情況下的處理器負載與消息通信量的測試結果

表2 活躍情況下的處理器負載與消息通信量的測試結果

從表1、表2中可以看出，資源發現協議受到m的影響，TLSA系統的整體負載隨著網絡拓撲樹的高度而變化，所以需要在樹的高度和m之間進行平衡。除了這些外，通過使用資源的可用性協議，在正常的參入情況下，葉子節點處的網絡消息通信量和處理器的負載比根節點處的要大。網絡中控制的消息通信量幾乎只有1KB／s，它是小于整體網絡帶寬1Mb／s的1%，這些測試結果是具有重要意義的。在TLSA的高度活躍情況下，節點處的性能因為比較高的處理器負載和網絡消息通信量而受到影響。

從表1和表2中看出，TLSA的消息控制負載比較低。在正常的情況下網絡消息通信量是1485B／s，處理器的負載只有5.77條／s。在系統活躍的情況下網絡的消息通信量為21947B／s，處理器的負載為65.3條／s，這些都是系統活躍比較特殊的實驗情形。

4 結束語

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

［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，Francesco 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，FANG 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，Feamster N，et al.Geographic locality of IP prefixes［C］.Berkeley，CA：Internet Measurement Conference，2005.

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