云計算中基于Chord算法的研究與改進

葛君偉，王燕峰，方義秋

（重慶郵電大學 計算機科學與技術學院，重慶400065）

0 引 言

“云計算”作為一種新興的分布式計算模式，目前正受到人們的普遍關注。但是由于其相關技術還不成熟，人們對于云安全的種種焦慮以及不想 “云”被少數巨頭控制等因素成為云計算發展的瓶頸。因此，古老的P2P技術在這樣的新技術階段就顯現了它獨特的優勢，可以為云計算的發展顯現出一份新的活力。

云計算和P2P技術應用的有效結合是未來發展的趨勢，而相應網絡的資源搜索是其研究的核心問題［1］。

目前研究的P2P網絡主要可以分為三類：①集中式的P2P網絡，例如Napster；②非結構化P2P網絡，例如Gnutella［2］。這兩種方案在設計初期并沒有考慮運行在大規模網絡環境下，可擴展性差；③結構化P2P網絡，典型的算法有Chord，CAN，Pastry和Tapestry，它的優點是具有良好的可擴展性、魯棒性以及查找的準確性，相比①、②兩種網絡結構，結構化的P2P網絡更適用于云計算。

在結構化P2P網絡資源搜索算法中，Chord算法是一種以去中心化的方式實現分布式計算應用中數據項查詢定位，該算法正符合本文在云計算中引進P2P網絡技術的初衷，因此也就成為基于云計算的P2P資源搜索算法的首選。然而Chord算法沒有考慮到節點異構性和路由表冗余的問題，而這些問題大都和網絡的拓撲結構以及路由表的結構密切相關［3］，因此，為了有效的提高資源搜索效率，本文提出一個有效的網絡拓撲模型，并改進路由表結構。

1 Chord

1.1 Chord的構造與工作原理

Chord是由MIT實驗室等人在2001年提出的一種結構化的P2P模型，它主要解決了根據查詢消息的內容定位目標資源所在的具體位置這個問題。

在Chord環中的每個節點有一個指向前驅結點指針，指向后繼結點的指針以及一張路由表，在節點n的路由表中，它的第j（1≤j≤m）項保存Chord環上順時針距當前節點距離為2j－1的第一個節點，用finger［j］.start＝n＋2j－1（mod2m，1≤j≤m）來表示［4］。

圖1給出了N8的finger表和查找k為53的過程，以N8為例，它的finger表的第一項后繼結點是successor（n＋20）＝N14，第二項則是successor（n＋21）＝N14，依此類推得出直到第六項。對于Chord環上的任意節點n，查找數據對象k時，首先檢查k是否存在于自身，如果是，則直接回應查找節點；否則，要檢查k是否落在n和successor（n）之間，如果是，則把它的后繼節點返回給查找節點；否則，節點要按照finger表來進行路由，從finger表最后一項向前比較，如果finger表中第j項的后繼節點落在n和k之間，則把查找請求轉發給指針表第j項的后繼結點，通過遞歸這個過程，最終定位到k的后繼節點［5］。

圖1 Chord算法路由

1.2 Chord算法的不足

關于Chord算法，它也存在一些不足之處，例如：它忽略了節點的異構性和路由表冗余過大等問題，當網絡規模較大時，這些問題將嚴重制約著網絡中資源搜索的性能。

（1）節點異構方面

對于Chord系統，目前大多數研究都認為每個節點都是完全平等的，沒有考慮到網絡中各個節點之間的異構性，而實際P2P網絡中的各個節點都存在著差異，如果忽略這些差異，Chord系統在具體的使用中將存在許多困難［6］。

（2）路由表冗余方面

從圖1的Chord環可以看出，標識符空間為26＝64，上線節點的個數為10，以節點N8為開始，2i為跨度來尋找路由表中的后繼結點，分別以20、21、22為跨度，找到的后繼節點都是N14，也就是有接近一半的路由信息是冗余信息。

以上例子是以m＝6的情況來做的分析，一般情況下m取值為128，形成2128的環形空間，假定網絡中有節點264個節點 （實際中節點數遠比這要少），采用SHA－1來為節點分配關鍵字，可以近似的認為節點在環上是均勻分布的，則每兩個節點之間的間隔是2128／264＝264，每一個節點的路由表項有m＝128項路由信息。由于一個節點的路由表相鄰的兩個指針表項標識符 （n＋2i－1mod2m）是以2的倍數遞增的，所以大概也有64／128＝50%的信息是冗余的，這些一則造成存儲空間的浪費，另則造成路由信息不能大范圍的對Chord環進行覆蓋，從而影響了路由的查詢效率［7］。

2 設計與分析

2.1 模型構造

我們從宏觀的角度來看待云計算網絡，由于云計算網絡是由很多個云服務器連在一起構成的，我們把一個云服務器當做網絡中的一個節點，稱為云節點，作為構成網絡拓撲結構的基本元素。云節點在處理數據的能力、存儲空間、上線時間以及帶寬等方面存在著差異性［8］。

由于原始的Chord算法沒有考慮到節點異構性的問題，單一的引用Chord并不適用，所以必須在此基礎上進行改進。

具體的思想是：首先對網絡中各個云節點的IP地址進行研究，把具有相同網絡號的云節點歸為一組，構成Chord從環。然后在每一個組中，對各個云節點的性能進行評估比較，根據其評估比較的結果，選擇性能最好的云節點作為超級云節點，和其他組中的超級云節點按照Chord算法組成Chord主環［9］；選擇性能僅次于超級云節點的節點作為后備云節點［10］，在本組超級云節點失效或者離開網絡時，接替其工作，充當新的超級云節點。

為了后面便于描述，我們在此定義該建立的模型為MC－Chord，具體的模型結構如圖2所示。

2.2 路由表的設計

圖2 MC－Chord模型

在本模型中，首先超級云節點是該所屬的Chord從環的一份子，所以需要一個從環finger表來表示在該從環中各個云節點之間的關系，同時，超級云節點也是Chord主環的一部分，所以還需要一個主環finger表來表示主環上各個超級云節點之間的關系。對于普通云節點來說，只需要一個從環finger來表示所在從環上各個云節點之間的關系。考慮到后備云節點的特殊性，除了要有一個表示從環云節點之間關系的從環finger表之外，還必須有一個和本組超級云節點完全一樣的主環finger表。

對于以上每一個finger表，為了提高其路由效率，本文在MC－Chord的基礎上，對節點的finger表計算公式進行修改，修改后的模型稱為 MFC－Chord。首先對i進行分步考慮，并向公式引進一個參數d，d表示當前云節點和后繼云節點之間的距離。由于一致性散列函數能夠使所有的物理節點大致均勻的分布在Chord環上，所以任意云節點和它的后繼云節點的距離大致都相等。

改進的計算公式如下

據統計分析，在云節點的原始finger表構造公式中，云節點finger表在 ［1，］范圍內的指針項的后繼指針指向都是重復的，因此通過式 （1）中的第一項表達式，消除了finger表的重復部分，只保留了一項；當i在 （，m］的范圍內時，finger表項是跟原始的Chord的finger表算法一致。

以圖1所示的Chord環為例，表1是以云節點的原始finger表計算公式得出的N1的finger表結構。表2則是以式 （1）計算出的N1的finger表結構，其中路由finger表公式中的參數d＝6。對比表1和表2可知，改進后N1的finger表沒有冗余信息。

考慮到式 （1）得出的finger表只覆蓋了半個Chord環上的云節點，為了使finger表能夠大范圍的覆蓋Chord環，對這公式再進行修改，得到的公式為

由式 （5）得出N1的finger表結構如表3所示。

表1 原Chord的N1的finger表

表2 式 （1）得出的N1的finger表

表3 式 （2）得出的N1的finger表

對比表2和表3，式 （2）計算出的N1的finger表的覆蓋范圍更為廣泛，而且沒有出現新的冗余信息。

由于原始的finger表計算公式得出的云節點finger表存在著冗余信息，利用式 （1）消除了相應的冗余信息，但finger表的長度也隨之縮短了，從而使得finger表空間未能被充分利用，由表2可以看出；式 （2）是在式 （1）的基礎上進行改進，改進的效果是使得finger表的覆蓋范圍得到了一定程度的擴展，但finger表的空間利用率并沒有得到提高，由表3可以看出。基于此，需要在式 （2）基礎上再作進一步改進。

據統計分析，由式 （2）得出的finger表覆蓋范圍約為3／4個Chord環，則還有1／4個Chord環還沒有覆蓋，因此消除冗余信息之后，采取從 （2m－2m－2，2m）的范圍中選取云節點添加到路由表尾部。為了保證路由表的空間能夠被充分利用，選取云節點的數目就等于刪除的冗余信息數；假設刪除的冗余信息數為N，為了能夠保證選取的云節點分布均勻，且保證選取的最后一個云節點不為起始云節點，則把 （2m－2m－2，2m－d）這個范圍平均分成N份，然后從每份中選取一個云節點添加到finger表中。得到的公式如下

假設Chord環上的云節點都是均勻分布的，一般情況下，1／4個Chord環所覆蓋的云節點數遠大于刪除的冗余信息數，所以在 （2m－2m－2，2m－d）范圍內被平均分成N份后，每一份范圍中所包含的云節點數必定不小于1，因此在每一份范圍中選取云節點添加到finger尾部后，finger表并不會出現新的冗余信息。

由式 （3）得出N1的finger表結構如表4所示。

表4 式 （3）得出的N1的finger表

對比表3和表4，式 （3）得出的結果一方面使得云節點的finger表覆蓋范圍又進一步擴展了，另一方面解決了finger表空間未能充分利用的問題，并且沒有出現新的冗余信息，從而提高資源查找的效率。

2.3 資源定位過程的描述

首先在從環內進行查找，如能查找到所需資源，則查找結束；否則，再進行環間查找，直到找到相應資源為止，主要步驟如下：

（1）云節點發起查詢，首先在本云節點的資源列表查詢，如果找到，直接返回；否則，轉入 （2）。

（2）在本云節點所屬的Chord從環上按照路由策略進行查找，如果能找到所需資源存放的目標云節點，則返回查詢結果，否則轉入 （3）。

（3）判斷本云節點是否為所屬從環的超級云節點，若是，則轉為 （5）；否則轉為 （4）。

（4）本云節點將查詢請求發至所屬從環的超級云節點。

（5）超級云節點在Chord主環上按照路由查找策略進行查找目標云節點所屬從環的超級云節點，如果成功，則轉下一步；否則，查詢失敗。

（6）目標云節點所屬從環的超級云節點按照路由查找策略在所屬的從環進行查找目標云節點，如果能找到，則查詢成功，返回查詢結果；否則，查詢失敗。

3 仿 真

本次實驗主要對Chord、MC－Chord和 MFC－Chord 3種模型在相同的環境下進行仿真，實驗的環境如下：

（1）操作系統：windows xp

（2）機器配置：CPU 2.2GHZ，2.0G 內存

（3）實驗工具：Eclipse （JDK1.5）

（4）仿真模擬器：Peersim

Peersim仿真軟件是一個模擬P2POverlay網絡的通用網絡模擬器，并且支持結構化和非結構化兩種網絡模擬，采用的是JAVA語言進行開發，是BISON項目的一部分，目前主要有兩種模擬方式：Cycle－Base和Event－Driven。

對于平均查詢跳數實驗，本文設置1000，2000，4000，6000，8000，10000個節點，每個節點上有10個文件，分別對3種模型進行30次實驗，得到每種模型的平均查詢跳數，并進行對比，結果如圖3所示。

圖3 平均查詢跳數比較

由圖3可以看出，MFC－Chord與Chord、MC－Chord相比，平均路由跳數有所減少，并且隨著節點數的增加，MFC－Chord曲線較Chord更為平緩，與MC－Chord曲線趨向于平行。因此MFC－Chord的查詢效率優于Chord和MC－Chord。

對于平均查詢延遲實驗，本文設置500，1000，2000，4000，6000，8000，10000個節點，每個節點上有10個文件，分別對三種模型進行30次實驗，得到的每種模型的平均延遲，并進行對比，結果如圖4所示。

圖4 平均查詢延遲比較

由圖4可以看出，MFC－Chord與Chord、MC－Chord相比，平均延遲有所減少，并且隨著節點數的增加，MFCChord的平均延遲較Chord減少的更加明顯，與MC－Chord相比，平均延遲的減少值趨向于一個常值，因此MFCChord的資源查找效率要優于Chord和MC－Chord。

4 結束語

本文在云計算中引進P2P技術，把云服務器充當P2P網絡的網絡節點，最終建立了MFC－Chord模型，此模型一方面通過構建超級云節點，解決在Chord系統中沒有考慮的節點異構性的問題，另一方面通過對Chord路由表算法的改進，減少路由表的冗余信息，擴展了路由表的覆蓋范圍。實驗證明本模型可以有效降低平均查詢跳數和平均延遲，從而提高資源搜索的效率。

［1］Ozalp Babaoglu，Moreno Marzolla，Michele Tamburini，et al.Design and implementation of a P2Pcloud system ［C］／／Technical Report UBLCS，2011.

［2］JIA Zhaoqing，YOU Jinyuan.Research of unstructured P2P search algorithms and trust mechanism ［D］.Shanghai：Shanghai Jiaotong University，2008 （in Chinese）. ［賈兆慶，尤晉元.非結構化P2P中搜索算法及信任機制研究 ［D］.上海：上海交通大學，2008.］

［3］JIANG Shouxu，HAN Xixian，LI Jianzhong.Chord system based on super nodes ［J］.Mini－Micro Computer Systems，2007，28 （2）：266－270 （in Chinese）. ［姜守旭，韓希先，李建中.基于超節點的Chord系統 ［J］.小型微型計算機系統，2007，28 （2）：266－270.］

［4］Bartosz Biskupski，Jim Dowling，Jan Sacha.Properties and mechanisms of self－organizing MANET and P2Psystems ［J］.ACM Transactions on Autonomous and Adaptive Systems，2007，2 （1）：1－34.

［5］Stratis Ioannidis，Peter Marbach.On the design of hybrid peerto－peer system ［J］.ACM SIGMETRICS Performance Review，2008，36 （1）：157－158.

［6］Gao W L，Zhang G H，Wang M W，et al.An agricultural information sharing system based on P2Pnetwork technology ［J］.Intelligent Automation and Soft Computing，2010，16 （6）：945－951.

［7］Liu L，Xu J，Russell D，et al.Efficient and scalable search on scale－free P2Pnetworks ［J］.Peer－to－Peer Networking and Applications，2009，2 （2）：98－108.

［8］Zhang Yu，Cao Yuanda，Cheng Baodong.A layered P2Pnetwork topology based on physical network topology ［C］／／Dalian：4th International Conference on Wireless Communications，Networking and Mobile Computing，2008：1－4.

［9］Yu S，Yu J，Kamil K，et a1.DR－Chord－F an efficient doublering chord protocol［C］／／Ummuqi，China：Proc 7th 1EEE Int Conf Grid and Coop Comput，2007.

［10］Kim C S，Lee S，Han J I，et al.DChord：An efficient and robust peer to peer lookup system ［J］.Malaysian Journal of Computer Science，2010，23 （1）：37－48.