葛君偉，王燕峰，方義秋

（重慶郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，重慶400065）

0 引 言

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

云計(jì)算和P2P技術(shù)應(yīng)用的有效結(jié)合是未來(lái)發(fā)展的趨勢(shì)，而相應(yīng)網(wǎng)絡(luò)的資源搜索是其研究的核心問(wèn)題［1］。

目前研究的P2P網(wǎng)絡(luò)主要可以分為三類：①集中式的P2P網(wǎng)絡(luò)，例如Napster；②非結(jié)構(gòu)化P2P網(wǎng)絡(luò)，例如Gnutella［2］。這兩種方案在設(shè)計(jì)初期并沒(méi)有考慮運(yùn)行在大規(guī)模網(wǎng)絡(luò)環(huán)境下，可擴(kuò)展性差；③結(jié)構(gòu)化P2P網(wǎng)絡(luò)，典型的算法有Chord，CAN，Pastry和Tapestry，它的優(yōu)點(diǎn)是具有良好的可擴(kuò)展性、魯棒性以及查找的準(zhǔn)確性，相比①、②兩種網(wǎng)絡(luò)結(jié)構(gòu)，結(jié)構(gòu)化的P2P網(wǎng)絡(luò)更適用于云計(jì)算。

在結(jié)構(gòu)化P2P網(wǎng)絡(luò)資源搜索算法中，Chord算法是一種以去中心化的方式實(shí)現(xiàn)分布式計(jì)算應(yīng)用中數(shù)據(jù)項(xiàng)查詢定位，該算法正符合本文在云計(jì)算中引進(jìn)P2P網(wǎng)絡(luò)技術(shù)的初衷，因此也就成為基于云計(jì)算的P2P資源搜索算法的首選。然而Chord算法沒(méi)有考慮到節(jié)點(diǎn)異構(gòu)性和路由表冗余的問(wèn)題，而這些問(wèn)題大都和網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)以及路由表的結(jié)構(gòu)密切相關(guān)［3］，因此，為了有效的提高資源搜索效率，本文提出一個(gè)有效的網(wǎng)絡(luò)拓?fù)淠Ｐ?，并改進(jìn)路由表結(jié)構(gòu)。

1 Chord

1.1 Chord的構(gòu)造與工作原理

Chord是由MIT實(shí)驗(yàn)室等人在2001年提出的一種結(jié)構(gòu)化的P2P模型，它主要解決了根據(jù)查詢消息的內(nèi)容定位目標(biāo)資源所在的具體位置這個(gè)問(wèn)題。

在Chord環(huán)中的每個(gè)節(jié)點(diǎn)有一個(gè)指向前驅(qū)結(jié)點(diǎn)指針，指向后繼結(jié)點(diǎn)的指針以及一張路由表，在節(jié)點(diǎn)n的路由表中，它的第j（1≤j≤m）項(xiàng)保存Chord環(huán)上順時(shí)針距當(dāng)前節(jié)點(diǎn)距離為2j－1的第一個(gè)節(jié)點(diǎn)，用finger［j］.start＝n＋2j－1（mod2m，1≤j≤m）來(lái)表示［4］。

圖1給出了N8的finger表和查找k為53的過(guò)程，以N8為例，它的finger表的第一項(xiàng)后繼結(jié)點(diǎn)是successor（n＋20）＝N14，第二項(xiàng)則是successor（n＋21）＝N14，依此類推得出直到第六項(xiàng)。對(duì)于Chord環(huán)上的任意節(jié)點(diǎn)n，查找數(shù)據(jù)對(duì)象k時(shí)，首先檢查k是否存在于自身，如果是，則直接回應(yīng)查找節(jié)點(diǎn)；否則，要檢查k是否落在n和successor（n）之間，如果是，則把它的后繼節(jié)點(diǎn)返回給查找節(jié)點(diǎn)；否則，節(jié)點(diǎn)要按照f(shuō)inger表來(lái)進(jìn)行路由，從finger表最后一項(xiàng)向前比較，如果finger表中第j項(xiàng)的后繼節(jié)點(diǎn)落在n和k之間，則把查找請(qǐng)求轉(zhuǎn)發(fā)給指針表第j項(xiàng)的后繼結(jié)點(diǎn)，通過(guò)遞歸這個(gè)過(guò)程，最終定位到k的后繼節(jié)點(diǎn)［5］。

圖1 Chord算法路由

1.2 Chord算法的不足

關(guān)于Chord算法，它也存在一些不足之處，例如：它忽略了節(jié)點(diǎn)的異構(gòu)性和路由表冗余過(guò)大等問(wèn)題，當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí)，這些問(wèn)題將嚴(yán)重制約著網(wǎng)絡(luò)中資源搜索的性能。

（1）節(jié)點(diǎn)異構(gòu)方面

對(duì)于Chord系統(tǒng)，目前大多數(shù)研究都認(rèn)為每個(gè)節(jié)點(diǎn)都是完全平等的，沒(méi)有考慮到網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)之間的異構(gòu)性，而實(shí)際P2P網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)都存在著差異，如果忽略這些差異，Chord系統(tǒng)在具體的使用中將存在許多困難［6］。

（2）路由表冗余方面

從圖1的Chord環(huán)可以看出，標(biāo)識(shí)符空間為26＝64，上線節(jié)點(diǎn)的個(gè)數(shù)為10，以節(jié)點(diǎn)N8為開(kāi)始，2i為跨度來(lái)尋找路由表中的后繼結(jié)點(diǎn)，分別以20、21、22為跨度，找到的后繼節(jié)點(diǎn)都是N14，也就是有接近一半的路由信息是冗余信息。

以上例子是以m＝6的情況來(lái)做的分析，一般情況下m取值為128，形成2128的環(huán)形空間，假定網(wǎng)絡(luò)中有節(jié)點(diǎn)264個(gè)節(jié)點(diǎn) （實(shí)際中節(jié)點(diǎn)數(shù)遠(yuǎn)比這要少），采用SHA－1來(lái)為節(jié)點(diǎn)分配關(guān)鍵字，可以近似的認(rèn)為節(jié)點(diǎn)在環(huán)上是均勻分布的，則每?jī)蓚€(gè)節(jié)點(diǎn)之間的間隔是2128／264＝264，每一個(gè)節(jié)點(diǎn)的路由表項(xiàng)有m＝128項(xiàng)路由信息。由于一個(gè)節(jié)點(diǎn)的路由表相鄰的兩個(gè)指針表項(xiàng)標(biāo)識(shí)符 （n＋2i－1mod2m）是以2的倍數(shù)遞增的，所以大概也有64／128＝50%的信息是冗余的，這些一則造成存儲(chǔ)空間的浪費(fèi)，另則造成路由信息不能大范圍的對(duì)Chord環(huán)進(jìn)行覆蓋，從而影響了路由的查詢效率［7］。

2 設(shè)計(jì)與分析

2.1 模型構(gòu)造

我們從宏觀的角度來(lái)看待云計(jì)算網(wǎng)絡(luò)，由于云計(jì)算網(wǎng)絡(luò)是由很多個(gè)云服務(wù)器連在一起構(gòu)成的，我們把一個(gè)云服務(wù)器當(dāng)做網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)，稱為云節(jié)點(diǎn)，作為構(gòu)成網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的基本元素。云節(jié)點(diǎn)在處理數(shù)據(jù)的能力、存儲(chǔ)空間、上線時(shí)間以及帶寬等方面存在著差異性［8］。

由于原始的Chord算法沒(méi)有考慮到節(jié)點(diǎn)異構(gòu)性的問(wèn)題，單一的引用Chord并不適用，所以必須在此基礎(chǔ)上進(jìn)行改進(jìn)。

具體的思想是：首先對(duì)網(wǎng)絡(luò)中各個(gè)云節(jié)點(diǎn)的IP地址進(jìn)行研究，把具有相同網(wǎng)絡(luò)號(hào)的云節(jié)點(diǎn)歸為一組，構(gòu)成Chord從環(huán)。然后在每一個(gè)組中，對(duì)各個(gè)云節(jié)點(diǎn)的性能進(jìn)行評(píng)估比較，根據(jù)其評(píng)估比較的結(jié)果，選擇性能最好的云節(jié)點(diǎn)作為超級(jí)云節(jié)點(diǎn)，和其他組中的超級(jí)云節(jié)點(diǎn)按照Chord算法組成Chord主環(huán)［9］；選擇性能僅次于超級(jí)云節(jié)點(diǎn)的節(jié)點(diǎn)作為后備云節(jié)點(diǎn)［10］，在本組超級(jí)云節(jié)點(diǎn)失效或者離開(kāi)網(wǎng)絡(luò)時(shí)，接替其工作，充當(dāng)新的超級(jí)云節(jié)點(diǎn)。

為了后面便于描述，我們?cè)诖硕x該建立的模型為MC－Chord，具體的模型結(jié)構(gòu)如圖2所示。

2.2 路由表的設(shè)計(jì)

圖2 MC－Chord模型

在本模型中，首先超級(jí)云節(jié)點(diǎn)是該所屬的Chord從環(huán)的一份子，所以需要一個(gè)從環(huán)finger表來(lái)表示在該從環(huán)中各個(gè)云節(jié)點(diǎn)之間的關(guān)系，同時(shí)，超級(jí)云節(jié)點(diǎn)也是Chord主環(huán)的一部分，所以還需要一個(gè)主環(huán)finger表來(lái)表示主環(huán)上各個(gè)超級(jí)云節(jié)點(diǎn)之間的關(guān)系。對(duì)于普通云節(jié)點(diǎn)來(lái)說(shuō)，只需要一個(gè)從環(huán)finger來(lái)表示所在從環(huán)上各個(gè)云節(jié)點(diǎn)之間的關(guān)系?？紤]到后備云節(jié)點(diǎn)的特殊性，除了要有一個(gè)表示從環(huán)云節(jié)點(diǎn)之間關(guān)系的從環(huán)finger表之外，還必須有一個(gè)和本組超級(jí)云節(jié)點(diǎn)完全一樣的主環(huán)finger表。

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

改進(jìn)的計(jì)算公式如下

據(jù)統(tǒng)計(jì)分析，在云節(jié)點(diǎn)的原始finger表構(gòu)造公式中，云節(jié)點(diǎn)finger表在 ［1，］范圍內(nèi)的指針項(xiàng)的后繼指針指向都是重復(fù)的，因此通過(guò)式 （1）中的第一項(xiàng)表達(dá)式，消除了finger表的重復(fù)部分，只保留了一項(xiàng)；當(dāng)i在 （，m］的范圍內(nèi)時(shí)，finger表項(xiàng)是跟原始的Chord的finger表算法一致。

以圖1所示的Chord環(huán)為例，表1是以云節(jié)點(diǎn)的原始finger表計(jì)算公式得出的N1的finger表結(jié)構(gòu)。表2則是以式 （1）計(jì)算出的N1的finger表結(jié)構(gòu)，其中路由finger表公式中的參數(shù)d＝6。對(duì)比表1和表2可知，改進(jìn)后N1的finger表沒(méi)有冗余信息。

考慮到式 （1）得出的finger表只覆蓋了半個(gè)Chord環(huán)上的云節(jié)點(diǎn)，為了使finger表能夠大范圍的覆蓋Chord環(huán)，對(duì)這公式再進(jìn)行修改，得到的公式為

由式 （5）得出N1的finger表結(jié)構(gòu)如表3所示。

表1 原Chord的N1的finger表

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

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

對(duì)比表2和表3，式 （2）計(jì)算出的N1的finger表的覆蓋范圍更為廣泛，而且沒(méi)有出現(xiàn)新的冗余信息。

由于原始的finger表計(jì)算公式得出的云節(jié)點(diǎn)finger表存在著冗余信息，利用式 （1）消除了相應(yīng)的冗余信息，但finger表的長(zhǎng)度也隨之縮短了，從而使得finger表空間未能被充分利用，由表2可以看出；式 （2）是在式 （1）的基礎(chǔ)上進(jìn)行改進(jìn)，改進(jìn)的效果是使得finger表的覆蓋范圍得到了一定程度的擴(kuò)展，但finger表的空間利用率并沒(méi)有得到提高，由表3可以看出?；诖耍枰谑?（2）基礎(chǔ)上再作進(jìn)一步改進(jìn)。

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

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

由式 （3）得出N1的finger表結(jié)構(gòu)如表4所示。

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

對(duì)比表3和表4，式 （3）得出的結(jié)果一方面使得云節(jié)點(diǎn)的finger表覆蓋范圍又進(jìn)一步擴(kuò)展了，另一方面解決了finger表空間未能充分利用的問(wèn)題，并且沒(méi)有出現(xiàn)新的冗余信息，從而提高資源查找的效率。

2.3 資源定位過(guò)程的描述

首先在從環(huán)內(nèi)進(jìn)行查找，如能查找到所需資源，則查找結(jié)束；否則，再進(jìn)行環(huán)間查找，直到找到相應(yīng)資源為止，主要步驟如下：

（1）云節(jié)點(diǎn)發(fā)起查詢，首先在本云節(jié)點(diǎn)的資源列表查詢，如果找到，直接返回；否則，轉(zhuǎn)入 （2）。

（2）在本云節(jié)點(diǎn)所屬的Chord從環(huán)上按照路由策略進(jìn)行查找，如果能找到所需資源存放的目標(biāo)云節(jié)點(diǎn)，則返回查詢結(jié)果，否則轉(zhuǎn)入 （3）。

（3）判斷本云節(jié)點(diǎn)是否為所屬?gòu)沫h(huán)的超級(jí)云節(jié)點(diǎn)，若是，則轉(zhuǎn)為 （5）；否則轉(zhuǎn)為 （4）。

（4）本云節(jié)點(diǎn)將查詢請(qǐng)求發(fā)至所屬?gòu)沫h(huán)的超級(jí)云節(jié)點(diǎn)。

（5）超級(jí)云節(jié)點(diǎn)在Chord主環(huán)上按照路由查找策略進(jìn)行查找目標(biāo)云節(jié)點(diǎn)所屬?gòu)沫h(huán)的超級(jí)云節(jié)點(diǎn)，如果成功，則轉(zhuǎn)下一步；否則，查詢失敗。

（6）目標(biāo)云節(jié)點(diǎn)所屬?gòu)沫h(huán)的超級(jí)云節(jié)點(diǎn)按照路由查找策略在所屬的從環(huán)進(jìn)行查找目標(biāo)云節(jié)點(diǎn)，如果能找到，則查詢成功，返回查詢結(jié)果；否則，查詢失敗。

3 仿 真

本次實(shí)驗(yàn)主要對(duì)Chord、MC－Chord和 MFC－Chord 3種模型在相同的環(huán)境下進(jìn)行仿真，實(shí)驗(yàn)的環(huán)境如下：

（1）操作系統(tǒng)：windows xp

（2）機(jī)器配置：CPU 2.2GHZ，2.0G 內(nèi)存

（3）實(shí)驗(yàn)工具：Eclipse （JDK1.5）

（4）仿真模擬器：Peersim

Peersim仿真軟件是一個(gè)模擬P2POverlay網(wǎng)絡(luò)的通用網(wǎng)絡(luò)模擬器，并且支持結(jié)構(gòu)化和非結(jié)構(gòu)化兩種網(wǎng)絡(luò)模擬，采用的是JAVA語(yǔ)言進(jìn)行開(kāi)發(fā)，是BISON項(xiàng)目的一部分，目前主要有兩種模擬方式：Cycle－Base和Event－Driven。

對(duì)于平均查詢跳數(shù)實(shí)驗(yàn)，本文設(shè)置1000，2000，4000，6000，8000，10000個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)上有10個(gè)文件，分別對(duì)3種模型進(jìn)行30次實(shí)驗(yàn)，得到每種模型的平均查詢跳數(shù)，并進(jìn)行對(duì)比，結(jié)果如圖3所示。

圖3 平均查詢跳數(shù)比較

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

對(duì)于平均查詢延遲實(shí)驗(yàn)，本文設(shè)置500，1000，2000，4000，6000，8000，10000個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)上有10個(gè)文件，分別對(duì)三種模型進(jìn)行30次實(shí)驗(yàn)，得到的每種模型的平均延遲，并進(jìn)行對(duì)比，結(jié)果如圖4所示。

圖4 平均查詢延遲比較

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

4 結(jié)束語(yǔ)

本文在云計(jì)算中引進(jìn)P2P技術(shù)，把云服務(wù)器充當(dāng)P2P網(wǎng)絡(luò)的網(wǎng)絡(luò)節(jié)點(diǎn)，最終建立了MFC－Chord模型，此模型一方面通過(guò)構(gòu)建超級(jí)云節(jié)點(diǎn)，解決在Chord系統(tǒng)中沒(méi)有考慮的節(jié)點(diǎn)異構(gòu)性的問(wèn)題，另一方面通過(guò)對(duì)Chord路由表算法的改進(jìn)，減少路由表的冗余信息，擴(kuò)展了路由表的覆蓋范圍。實(shí)驗(yàn)證明本模型可以有效降低平均查詢跳數(shù)和平均延遲，從而提高資源搜索的效率。

［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）. ［賈兆慶，尤晉元.非結(jié)構(gòu)化P2P中搜索算法及信任機(jī)制研究 ［D］.上海：上海交通大學(xué)，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）. ［姜守旭，韓希先，李建中.基于超節(jié)點(diǎn)的Chord系統(tǒng) ［J］.小型微型計(jì)算機(jī)系統(tǒng)，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.