多集群網格系統的ＲＮ－Ｔｒｅｅ應用研究及模擬實現

摘 要：在對RN-Tree原理分析的基礎上，將RN-Tree應用于組成P2P網絡的多集群網格系統中，研究其查找過程以及查找性能。在單機上編程模擬了多集群網格系統的RN-Tree生成過程及查找過程。模擬方式能夠避免在真實的大規模多集群網格系統中實驗所產生的高成本代價，并可以在短時間內實現多次實驗，快速得到大量有效的實驗數據。實驗結果表明，在多集群網格系統中的RN-Tree應用具有非常良好的查找性能。

關鍵詞：集群； 網格； Chord； RN-Tree； 模擬

中圖分類號：TP338.8文獻標志碼：A

文章編號：1001-3695(2009)06-2257-03

doi:10.3969/j.issn.1001-3695.2009.06.078

Application research and simulation of RN-Tree in multi-cluster grid system

LI Xue-tao， GUAN Qun， TAN Shu-dan

(College of Computer， Sichuan University， Chengdu 610065， China)

Abstract:

Based on the analysis of the theory of RN-Tree， implemented RN-Tree in the multi-cluster grid system which constructs the P2P networks， and also studied the process and performance of looking-up. Simulated the generation and looking-up process of RN-Tree of multi-cluster grid system on the uniprocesser. The simulation can void the high cost that lost in the genuine large-scale multi-cluster grid system， and can do experiments within a short time while get abundant valid experiment data quickly. The experiment result shows that the implementation of RN-Tree in the multi-cluster grid system owns perfect capability of looking-up.

Key words：cluster; grid; Chord; RN-Tree; simulation

RN-Tree(rendezvous node tree)是一種建立在P2P網絡之上、包含了所有當前網絡有效節點的樹^[1]。Chord環是P2P網絡技術中性能較高的一種維護動態插入節點以及查找目標節點的方案^[2]，而RN-Tree正是通過Chord環生成的一種查找性能比Chord環更優良的算法。

目前，RN-Tree的應用集中在單處理機組成的P2P網絡中^[1]。如果將RN-Tree應用于多集群網格系統，需要研究其查找性能是否優良。根據RN-Tree的生成原理，可以用實驗模擬多集群網格系統中的RN-Tree的生成過程以及查找過程，對實驗結果進行分析。在真實的多集群系統中進行實驗存在極高的運行成本，故模擬實驗具有重要的價值。

1 RN-Tree原理分析

通過在每個節點上建立finger table以及前驅和后繼，Chord環可以有效地解決在P2P網絡中的動態節點插入問題^[3]。在查找作業方面，Chord環通過將關鍵字置入finger table中的方式來實現查找。

RN-Tree在Chord環的基礎之上發展而來。Chord環中所有節點都具有一個全局的并且惟一的非負整型屬性：GUID。每一個有效節點都有一個前驅和一個后繼^[4]。為方便說明，設有效節點N前驅的GUID為Pid(N)，后繼的GUID為Sid(N)。RN-Tree算法規定，如果一個有效節點與其前驅之間包含GUID為0的節點，那么將此節點作為生成樹的根節點。這樣做的目的是為了保證根節點不具有父節點而其他節點都具有父節點。將Chord環中根節點之后的所有有效節點依次執行以下操作：按式(1)計算X。

X=(Pid(N) + 1 )/2（1）

如果Chord環中GUID為X的節點是有效節點，那么將此節點作為當前操作節點的父節點，否則將此節點后面的節點中第一個有效節點作為當前操作節點的父節點。對每一個有效節點執行完該操作之后，RN-Tree便建立完畢。

RN-Tree的查找作業則是通過從任意節點開始遍歷樹的查找算法完成。相比Chord環，RN-Tree的查找優勢在于，每一個節點除了擁有finger table之外，還擁有其父節點以及孩子節點的信息，而任何一對父親—孩子節點在Chord環中都可能距離非常遙遠，這樣就可以平衡查找過程中的最好情況和最差情況，使平均查找時間縮短。

2 多集群網格系統的RN-Tree應用研究

2.1 多集群網格系統的構成

通常，在P2P網絡中的每一個節點是一個單獨的處理機，而在多集群網格系統中，每一個節點都是一個集群。集群擁有若干個計算節點，每一個計算節點又包含若干個處理機。集群比單獨的處理機性能更強大，運算速度更快，內存空間更廣。

但是，正因為集群的性能強大，使得維護集群網絡需要更多的資源，查找目標節點可能花費的代價更大。因此，尋找一種合適的查找算法非常重要。在多集群網格系統中，查找目標通常是某一個集群內的某一個符合要求的計算節點。其計算節點的性能指標可以概括為所含CPU數目、CPU運算速度、內存空間。當某一個查找作業開始時，會從當前集群插入，開始尋找符合要求的目標計算節點，并最終找到此計算節點所屬的集群，將需要完成的事務交給目標節點來完成。

2.2 通過Chord環建立RN-Tree

為方便說明，通過一個例子演示RN-Tree的建立過程，如圖1所示。

在圖1中，一個多集群網格系統組成的Chord環中包含19個節點。其中，GUID為3、6、7、11、14、16的是有效節點，即在這些節點上各有一個集群。

在生成RN-Tree的過程中，首先確定根節點為3，因為3與其前驅16之間包含0節點。之后對根節點的后繼6執行操作：找到6的前驅3計算公式如下：

X=(Pid(6)+1 )/2=2

GUID為2的節點不是有效節點，故尋找2之后的第一個有效節點為3，則將3作為6的父節點存入RN-Tree中。依此類推，7的父節點為3；11和14的父節點為6；16的父節點為7。通過對全部有效節點的操作，生成了一棵包含所有6個有效節點的RN-Tree。

2.3 通過RN-Tree完成查找作業

在多集群網格系統中，當某一個作業插入網格系統時，需要網格系統提供一個集群來完成該作業。此集群必須至少包含一個符合要求的計算節點，否則查找失敗。開始時，插入點的集群將目標節點的性能指標與自身所含的計算節點相比較，如果有合適的計算節點，則安排其執行作業。如果沒有，則開始在網格內尋找其他集群，以完成查找作業。

由于建立了RN-Tree，使得查找過程與Chord環不同。首先，要遍歷當前節點的子樹，如果有某一個節點上的集群包含符合要求的計算節點，則結束查找，將作業交給該集群執行。如果沒有，則將插入節點轉移到當前節點的父節點，并再次開始遍歷子樹的過程，如果找到符合要求的集群，則結束查找。當然，在遍歷過程中，如果遇到第一次插入的節點（即已經查找過的節點），則跳過。依此遍歷完整棵RN-Tree，如果仍然沒有找到符合要求的集群，則返回提示信息。

2.4 多集群網格系統的RN-Tree查找性能分析

由于RN-Tree中的節點可以存儲其父節點以及孩子節點的信息，使得查找時不用依賴finger table中的關鍵字，而是通過遍歷樹的形式完成查找。同時，由于集群網格系統的節點相對穩定，使生成RN-Tree要消耗的資源比較少。從理論上分析，在多集群網格系統中使用RN-Tree是合適的。

查找作業的過程是否適合使用RN-Tree，還需要大量實驗來證明。然而，在真實的大規模集群網格系統中進行實驗需要非常高的運行成本。事實上，很難在同一個區域內找到大量集群，必須依靠互聯網，而這樣所帶來的實驗成本會更高。因此，有必要通過編程實現在一臺主機上模擬整個網格系統，并進行大量查找作業的實驗，以低運行成本得出快速準確有效的

數據。

3 多集群網格系統的RN-Tree模擬實現

實現策略是：a)隨機創建一個模擬的多集群網格系統；b)創建一個空間足夠大的Chord環，將多集群網格系統隨機散列其中;c)通過Chord環生成RN-Tree;d)隨機生成一個查找作業，隨機選擇一個插入節點，開始查找目標節點；e)反復進行多次實驗（5 000次），記錄實驗數據，進行分析。

1)創建一個模擬的多集群網格系統

在模擬系統中，創建GrideSimData對象來模擬集群網格。

 public class GrideSimData{

 private int did;// 對應FingerTable中的位置

private List〈CpuNode〉 cpuNodes;//集群包含的計算節點列表

}

其中，類成員List〈CpuNode〉 cpuNodes包含了該集群所擁有的所有計算節點。

定義CpuNode對象

public class CpuNode{

private int cid;

private int size;// 節點內包含CPU個數

private int memory;// 節點內存(單位GB)

private int speed;// 節點運算速度（單位mips ）

}

將集群個數設為參數M。隨機生成M個GrideSimData對象，在每一個GrideSimData對象中創建一個List〈CpuNode〉。其中包含若干個計算節點，計算節點的個數同樣由隨機數在一定范圍內生成。每個計算節點的size、memory和speed通過隨機數得到。

2)創建Chord環并散列網格系統

利用jchord工程實現Chord環。重載工程中Identificador對象，在其成員變量中加入之前已創建好的GrideSimData對象。

Chord環空間總量由參數在一定范圍內設定（范圍上限取1 024），并根據輸入參數M確定創建集群的數量，在Chord環中隨機散列M個有效節點。將M個集群隨機對應到M個有效節點中，組成一個多集群Chord環。同時建立finger table，存儲在jchord工程的fingertable對象中。

3)通過Chord環生成RN-Tree

(1)構建基礎樹。定義樹結構對象，命名為RendezvousTree對象。定義setRoot方法（設定根節點）、appendChild（掛接孩子節點）方法以及其他樹結構所需方法。

(2)設定根節點。在多集群Chord環的基礎上，找到符合根節點條件的有效節點，作為生成樹的根節點，調用RendezvousTree對象中的setRoot方法，設定到RndezvousTree中。

(3)掛接孩子節點。根據公式(X=(Pid(N)+1)/2)，依次查找有效節點的父節點，使用appendChild方法將當前節點掛接到父節點上。最終生成一棵完整的RN-Tree。

4)插入查找作業查找目標節點

(1) 生成預設目標節點。實驗需要反復執行很多次，需要大量實驗數據的匯總結果，所以隨機生成是主要的預設目標節點的方式。建立一組目標節點對象，命名為purpose對象。其中的size、memory和speed屬性隨機生成。

(2)創建查找作業對象，命名為task對象。Task對象包含了List〈purepose〉。將之前隨機建立的一組目標節點存放在List〈purpose〉中。

(3)開始查找作業。隨機生成一個插入節點，從此節點開始遍歷樹，遍歷過程為子樹、父節點、父節點的子樹……在每一個節點中，將其所包含的所有計算節點與目標節點比較，若符合要求，則返回該集群節點信息；否則繼續查找，直到找到目標節點。若查找失敗，目標節點不存在，則返回提示信息。此處給出核心算法代碼描述。

searchTask(Node insertNode){

 while( insertNode?!= 1){

 /* 當已經查找過當前節點時跳轉*/

if (hasFindThisNode(insertNode)){

if (insertNode.parentNode != 1){

insertNode = insertNode.parentNode;

continue;

}

else

Return 1;

 }

 /* 與當前集群節點下的計算節點匹配*/

for(CpuNode cn: List){

if (find(puupose， cn))

Return insertNode;

}

 /* 繼續查找其他節點，直到遍歷完整棵樹*/

if (insertNode.firstChildNode != 1){

insertNode = insertNode.firstChildNode;

continue;

}

if (insertNode.parentNode != 1){

insertNode = insertNode.parentNode;

continue;

}

 }

}

4 實驗過程及分析

4.1 實驗初始值設置

Chord空間總量為1 024，有效節點數依次為10、15、20、25、30、40、50。在每一種有效節點的情況下，在Chord環上進行5 000次和10 000次查找作業，計算查找次數的均值；在RN-Tree上進行5 000次和10 000次實驗，計算均值。每次查找作業的目標節點和插入節點生成方式均為隨機生成，并在相同的目標節點和插入節點的條件下，先后進行Chord環查找以及RN-Tree查找。集群的計算節點數隨機空間總量為100。

4.2 實驗運行結果

按照上述初始值進行實驗，運行結果如表1所示。

在表1中，節點欄表示Chord環的有效節點個數；次數列表示實驗進行的次數。兩者交叉的部分是在某一有效節點個數的條件下，進行5 000/10 000次的實驗，最終得到的平均查找次數。

這里對Chord環的有效節點個數進行了分段實驗，每一個數量段內都分為兩種實驗次數，即5 000和10 000次實驗。可以發現，5 000與10 000次實驗所得數據相差極其細微，數據在這樣規模的實驗次數下比較穩定，這說明了5 000和10 000次的實驗結果都是有效的。

4.3 對比分析

選取10 000次實驗的數據作對比，如圖 2所示。

RN-Tree在所選取的6個有效節點個數段中都具有一定的查找優勢，平均查找次數都有一定的減少，這就節省了查找時間，提高了查找效率，使查找的性能得到加強，同時降低了資源消耗。經計算，6種節點個數情況下的查找次數分別減少1.03%、1.29%、1.19%、1.21%、1.18%、0.93%。可見，RN-Tree適合在多集群網格系統中使用，并具有一定的改進效果，相比Chord環具有一定的優勢。另外，在多集群網格系統中，系統環境比較穩定，節點插入的頻率比單處理機組成的網絡要小，使生成RN-Tree的資源消耗比在單處理機網絡中要低。因此，生成RN-Tree所造成的額外開銷在多集群網格中不會對系統造成太大影響。這也是RN-Tree適合在多集群系統中使用的另一個優勢。

5 結束語

多集群網格系統的模擬實現，證明了RN-Tree在系統中的應用是適合的，相對單純依靠Chord的查找作業具有一定的優勢。同時，模擬實現成功避免了因運行大規模集群系統所造成的高成本代價，并且最終得到了快速有效的實驗數據。下一步工作是在模擬實現的基礎上，改進RN-Tree算法，以改變樹的平衡因子、高性能集群位置重置等方法，不斷提高查找性能，得到更優化的算法。

參考文獻：

[1]KIM J S， BHATTACHARJEE B， KELEHER P J， et al. Matching jobs to resources in distributed desktop grid environments， CS-TR-4791[R]. Maryland: University of Maryland， 2006:15-19.

[2] MARSH M， KIM J S， NAM B， et al. Matchmaking and implementation issues for a P2P desktop[C]//Proc of IEEE International Symposium on Parallel and Distributed.[S.l.]:IEEE Press， 2008:1-5.

[3]SHUDO K， TANAKA Y， SEKIGUCHI S. P3: P2P-based middleware enabling transfer and aggregation of computational resources[C]//Proc of IEEE International Symposium on Cluster Computing and the Grid.[S.l.]:IEEE Press， 2005: 259-266.

[4]CHAKRAVARTI A J， BAUMGARTNER G， LAURIA M. The orga-nic grid: self-organizing computation on a peer-to-peer network[J]. IEEE Trans on Systems， Man and Cybernetics， 2005， 35(3): 373-384.

[5]BUTT A R， FANG X， HU Y C， et al. Java， peer-to-peer， and accountability: building blocks for distributed cycle sharing[C]//Proc of the 3rd USENIX Virtual Machines Research and Technology Syposium (VM 2004). 2004: 13.

[6]ANDERSON D. BOINC: a system for public-resource computing and storage[C]//Proc of the 5th IEEE/ACM International Workshop on Grid Computing. 2004: 4-10.

[7]KIM J S， BHATTACHARJEE B， KELEHER P J， et al. Resource discovery techniques in distributed desktop grid environments[C]//Proc of the 7th IEEE/ACM International Conference on Grid Computing.[S.l.]:IEEE Press， 2006: 9-16.

[8]KIM J S， BHATTACHARJEE B， KELEHER P J， et al. Using content-addressable networks for load balancing in desktop grid[C]//Proc of the 16th International Symposium on High Performance Distributed Computing Table of Contents Monterey. 2007:189-198.

[9]KIM J S， BHATTACHARJEE B， KELEHER P J， et al. Creating a robust desktop grid using peer-to-peer services[C]//Proc of IEEE International Symposium on Parallel and Distributed. 2007: 1-7.