云計算環境中一種基于Hash環的P2P網絡模型研究

邵澤云

摘要： P2P技術的應用在現代網絡系統中越來越普及，而云計算的出現給IT界帶來了全新的挑戰，因此，針對目前網絡的發展現狀，對P2P技術和云計算技術進行研究，提出了一種云計算環境中的P2P網絡模型，這是云計算技術與P2P技術的一種結合。通過對使用P2P技術的網絡中節點的處理能力、擁有的資源量、占據的帶寬大小等進行評估，得出網絡中各節點的層次結構并形成Hash環，然后利用一致性Hash算法在系統中對資源進行快速搜索。利用這種方法，由于每個節點只需要更新少量的信息就可以完成查詢路由，從而實現了網絡中資源的快速定位，提高了網絡資源搜索的效率。

關鍵詞： 云計算； P2P技術； 網絡模型； Hash環； 網絡資源搜索

中圖分類號： TN919?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2014）08?0138?04

Research of P2P network model based on Hash ring in cloud computing environment

SHAO Ze?yun

（College of Information Engineering， Longdong University， Qingyang 745000， China）

Abstract： The application of P2P technology becomes more and more popular in the modern network system， but the emergence of cloud computing has brought a new challenge to the IT industry. Therefore， in view of the development situation of network， a P2P network model in cloud computing environment is proposed for the study of P2P technology and cloud computing technology， which is a result combining the cloud computing technology with P2P technology. Based on the assessment of resource quantity， network bandwidth and node processing capacity in the network using P2P technology， the hierarchy structure of the each node in network and Hash ring were obtained， and then the consistent Hash algorithm was used to search for network resources in the system quickly. With this method， the routing query can be completed because each node needs to be updated only a small amount of information， and the quick positioning of resources in a network can be realized. It improved the efficiency of resource searchbecause each node

Keywords： cloud computation； P2P technology； network model； Hash ring； network resource search

0引言

隨著網絡技術的發展，網絡系統中的用戶數和數據等資源不斷增長，為了讓網絡能夠提供更好的服務，出現了好多新技術，如P2P技術、云計算技術等。從目前的發展現狀來看，P2P技術和云計算技術各有千秋，在未來網絡的發展中勢必要形成P2P技術和云計算技術的緊密結合，這樣網絡才能發揮更大性能和提供更好的服務。在云計算環境里，會有許多用戶和服務提供商，云計算技術解決的是在面對諸如大量用戶、海量數據存儲時，如何讓用戶能夠高效獲取所需的資源以及用那種方式能夠使用戶的數據在網絡中安全高效共享等，而P2P技術是一種適合在云計算環境中的眾多用戶間實現信息交換的很好用的技術[1]。在本文提出的該模型中，既考慮了云計算平臺的結構又考慮到P2P對等網目前的現狀，用戶既可以接入云來享受服務，也可以加入到云中成為云的一部分，既能與云中其他成員交互信息，也能為其他用戶提供服務 [2]。

1相關概念

1.1網絡的分層與結構化

將云計算網絡中的節點進行層次劃分，按照節點處理能力的強弱劃分不同層次，形成一個層次結構，最高層節點是由處理能力強的云計算服務提供商組成，按照節點處理能力由高到底分層，最下層是處理能力最弱的用戶節點，在整個層次結構中，上層節點為下層節點提供服務，下層節點利用上層節點提供的服務完成自身的功能，同時再向其下一層提供服務，這樣對資源的查找就可以在上級節點進行查找搜索，在此結構中，最重要的兩類節點是搜索節點和索引節點，搜索節點負責接收用戶查找搜索的請求，然后從其下層節點中查找資源，而索引節點就是處理能力強的云計算服務提供商的節點，主要保存搜索節點數據和對系統進行維護，當然，網絡狀態是一個動態變化的過程，如果某時段內索引節點的負載較重，也可以讓處理能力強的其他節點承擔索引節點的部分功能，以達到均衡負載，提高效率的目的[3]。

1.2DHT技術簡介

分布式哈希表技術（Distributed Hash Table，DHT）。使用分布式Hash運算來解決結構化的分布式存儲問題，其基本思想是通過對存儲對象的關鍵字進行Hash運算，得到相應的鍵值，對象的存儲是根據Hash運算得出的鍵值進行存儲的，DHT技術采用Hash函數不但加快了查找速度而且還增強了系統的安全性，便于管理，而且不會占用太多的網絡帶寬資源[4]。

DHT技術為P2P對等網絡中資源的組織與搜索提供了一種新的思想，目前有好多較為成熟的基于DHT算法的協議，如Kademlia，Chord，CAN等[5]。

1.3使用DHT技術形成Hash環的過程

Step1：對網絡中每個節點可以選用節點IP地址進行一致性Hash運算，通過Hash運算后得到節點的唯一標識ID，該ID值就作為此節點的標識；

Step2：對網絡中每個節點可提供的資源的標識進行一致性Hash運算，得到一個值，記為key；

Step3：將數據存儲位置作為邏輯地址，記為addr，此addr和step2中的key值組成二元組（key，addr）；

Step4：在step1中的ID和step2中的key都是通過一致性Hash運算得到的，因此從ID列表中找到與key值最接近的節點ID值，此節點存儲step3中的（key，addr）；

Step5：當進行數據搜索時，找出與該資源的key值最接近的下一ID節點，該資源的位置信息就是該節點所保存的（key，addr）中的addr值；

Step6：利用key值查詢下一節點ID值時，可利用位于高層節點的DHT表進行查找，類似于網絡層的路由查找方法，查找時可以采用類似折半查找的算法等，在節點進入和退出網絡比較頻繁時，由于每個節點只需更新少量的信息完成查詢，因此，查詢效率較高[6?7]。

下面給出一個Hash環示例，假設網絡上有節點N1，N9，N15，N22，N33，N39，N43，N49，N52，N57共10個節點，這些節點通過一致性Hash運算后得出節點ID值，根據節點ID值范圍，這10個節點邏輯上形成一個環，即Hash環，如圖1所示，圖中顯示了節點N9的查詢路由過程。

圖1 Hash環上N9節點的查詢路由

N9節點的查詢路由表如表1所示。

表1 N9節點的查詢路由表

2模型的基本結構

對于融合P2P技術的云計算網絡而言，網絡拓撲結構是動態變化的，在對等連接網絡中，雖然整個網絡中的每個節點的地位是平等的，但是在網絡拓撲中的節點分布呈現出一定的規律性，也就是說，在網絡中存在一些穩定性強、處理能力強、網絡帶寬較高的對等節點，這些對等節點可以承擔提供服務的工作，在云計算環境中，這些節點可以是云計算服務提供商，也可以普通用戶[7]，其設計思想就是將云計算服務提供商的哪些性能強、效率高而且提供很多資源的節點組織成一個邏輯集群，然后再進行分層，資源越豐富、帶寬越大、計算能力越強等的節點就離中心越近，由中心向外，節點處理能力越來越低，最外層是普通用戶[8?10]，模型的邏輯結構如圖2所示。

3網絡中節點的加入與退出

3.1節點加入過程

由云計算服務提供商對首次加入節點的性能進行評估，然后確定該用戶在網絡中所處的層次，云計算服務提供商還要根據此節點的評估情況以及自身負載等情況決定此節點是否需要承擔索引節點的相應功能，然后根據此用戶的數據信息在網絡中為其指定上層節點，同時還要確保本節點和上層節點之間的傳輸時間要小，然后網絡系統通過DHT算法確定本節點相應的ID值[11]。在圖2中，由一條鏈路上的節點形成一個Hash環，最高層節點負責更新下層節點信息，它不是Hash環。這些Hash環的結構如圖3所示。

圖2 網絡模型邏輯結構

圖3 第0層中心節點環和Hash環

當有新的節點要請求加入網絡時，云計算服務提供商先對其進行評估，得出節點所處的層次，然后對原Hash環進行劃分，找出前序節點并從中劃分出一部分空間分配給此節點作為該節點的私有空間，當該節點退出本網絡時，要將退出節點的資源進行回收，層次越高的節點其處理能力越強，而層次越低的節點其處理能力相對較弱，最底層的用戶節點處理能力最弱，基本沒有私有空間，因此也就沒有索引服務的功能[12?14]。節點加入Hash環的過程如下：

Step1：當新的節點M（假設新加入的節點是M）要加入網絡時，首先要與云計算服務提供商進行連接，云計算服務提供商根據該節點的相關信息對此節點進行評估，以確定新節點M在網絡中所處的層次，云計算服務提供商還要負責將與此節點通信距離短的其他節點的信息傳遞給節點M，有利于節點M進行后續的工作；

Step2：新節點M根據云計算服務提供商提供的信息，估算與上層節點傳遞信息的代價，然后選擇代價最小的上層節點N作為索引節點，節點M通過索引節點N找到其在Hash環上的后繼節點T，此后繼節點T根據M的ID值及層次信息，將自己的私有空間分割出一部分作為節點M的私有空間，當然節點T還保留屬于自己的私有空間；

Step3：節點M通過后繼節點T的信息找出前序節點H，然后，節點M向前序節點H和后繼節點T發送一個加入網絡的請求，節點H和T收到節點加入網絡的請求信息后，如果允許加入，就就分別更新自己的前序節點和后繼節點的信息，節點H的后繼是M，節點M的后繼是T；

Step4：節點M通過其后繼節點T在Hash環中找到自己的分級路由表中各條目對應的下一節點，從而實現分級路由的初始化過程；

Step5：最后更新這個Hash環中的其他節點的路由信息，實現使其隨網絡結構狀態的改變而改變，反映出網絡的最新狀態。

3.2節點退出過程

Step1：當節點M（假設要退出的節點是M）要退出網絡時，首先節點M要向前序節點H和后繼節點T發送離開本網絡系統的請求信息。

Step2：節點M的前序節點H和后繼節點T收到請求離開的信息后，如果允許其離開，就分別更新自己的后繼節點和前序節點信息，節點H的后繼節點改為節點T，而節點T的前序節點改為H。

Step3：節點T需要更新私有空間，要將節點M的私有空間收回并和自己的私有空間合并。

Step4：節點M要向中心節點環上的云計算服務提供商提出離開請求，云計算服務提供器收到請求離開信息后，如果允許離開，就更新網絡系統中的相應節點的信息，將節點M后面層節點的層次提高一層。

Step5：最后更新這個Hash環中的其他節點的路由表，實現使其隨網絡結構狀態的改變而改變，反映出網絡的最新狀態。

4模型中節點的路由信息

在網絡系統中，有大量云計算服務提供商組成的中心環的存在，能夠給其他層的節點提供信息，同時由于采用了根據節點能力進行分層和不同級別層間消息擴散和節點最優路徑預測的技術策略，這就可以使消息能夠盡量在一條花費時間短的路徑上傳播，這樣一來就降低了搜索資源的時間[15?17]。

5本模型的性能分析

為了分析該模型的性能，需要定義一些相關參數，如下：

假設本模型的網絡系統中的節點數為S，在應用Hash環技術后第I級私有空間上的節點數為Si，整個網絡系統中節點之間的平均往返時間為RTT，在應用Hash環技術后的系統中第I級私有空間上的節點之間的平均往返時間為RTTi，在整個網絡系統中進行一次路由查找需要的時間為T，在應用Hash環技術后的系統中第I級私有空間上進行一次路由查找的時間為Ti。

假設在網絡系統中進行路由查找時的不確定因素用參數a表示，那么在網絡系統中進行一次路由查找的時間為：

[T=RTT·a·LogS] （1）

應用Hash環技術后，在具有N級私有空間的網絡系統中進行一次路由查找需要的時間為：

[Tn=RTTi·a·LogSi+RTTi+1·a·LogSi+1Si+…+RTT·a·Log(SSn-1)]（2）

有式（1）和式（2）可得出式（3）：

[TTn=RTT·LogSRTTi·LogSi+RTTi+1·LogSi+1Si+…+RTT·LogSSn-1] （3）

對于一個層次N為1的模型，也就是2級模型來說，就會由式（3）得出式（4）：

[TTn=RTT·LogSRTT0·LogS0+RTT·(LogS-LogS0)] （4）

在式（4）中，RTT0通常情況下，層次最高，值很小，如果RTT0→0，則式子（4）可以簡化成為式（5）：

[TTn=LogSLogS-LogS0] （5）

在式（5）中。S0和S是指數關系，也就是說它們存在S0=Sx關系（0

[TTn=11-x] （6）

由式（6），可得出：

[Tn=T(1-x),0

即有：[Tn

從以上分析可知，本模型的路由選擇的時間是根據不同的私有空間劃分等級，因此與目前對等網絡相比較，路由查找時間會有不同程度的縮短，提高了資源搜索的效率。

6結語

云計算環境是由無數的節點組成，面對的是海量數據存數、數據交換與處理，而P2P技術最適合在這種環境中的對等節點之間傳遞信息。在本文模型中，利用P2P技術與云計算技術的緊密結合，利用在云計算環境中的網絡結構的特點，對節點根據能力進行層次劃分等級，并采用一致性Hash算法，使網絡中信息查詢搜索的效率得到提高，使網絡在面對海量數據時仍能提供更好的性能和服務。

參考文獻

[1] HSIAO H C， LIAO H. Load balance with imperfect information instructured peer?to?peer systems [J]. IEEE Transactions on Parallel Disturb System， 2011， 22（4）： 634?649.

[2] 孫秋景，曾凡平.一種信譽機制與云計算相結合的P2P環境信任模型[J].小型微型計算機系統，2010，31（7）：1328?1332.

[3] 陳珊珊.P2P網絡中基于權重因素的信任模型[J].計算機應用，2013，33（6）：1612?1614.

[4] 聶曉文，盧顯良，周旭，等.DHT 算法基本統計特性及應用[J].四川大學學報：工程科學版，2009，41（5）：170?175.

[5] 肖波，聶曉文，侯孟書.DHT網絡規模估計算法的定量分析與設計[J].電子科技大學學報，2011，40（2）：261?266.

[6] 賀智明，曹謙.基于Hash機制的WSN密鑰預分配方案[J].計算機工程與設計，2013（11）：3770?3774.

[7] 葉培順.非結構化P2P網絡的一種改進搜索算法[J].計算機與現代化，2013（12）：44?47.

[8] 張祖昶，王誠.P2P網絡中基于交易代價的信任模型研究[J].南京郵電大學學報：自然科學版，2013，33（6）：35?41.

[9] 馮登國，張敏，張妍，等.云計算安全研究[J].軟件學報，2011，22（1）：71?83.

[10] CHEN S， ZHANG Y， YANG G. Parameter?estimation based trust model for unstructured peer?to?peer networks [J]. IET Communications， 2011， 5（7）： 922?928.

[11] ZHANG De?gan， HU Yu?xia， WANG Dong， et a1. A new algorithm of service discovery based on DHT for mobile application [J]. Jouranal of Network， 2011， 6（10）： 1466?1474.

[12] 楊志興，湯紅波，柏溢，等.移動P2P分布式信任模型設計[J].計算機工程與應用，2013，49（23）：75?80.

[13] 李勇軍，代亞非.對等網絡信任機制研究[J].計算機學報，2010，33（3）：390?405.

[14] 于鑫，金朋飛，石川，等.基于仿真的P2P網絡信譽模型[J].計算機與現代化，2013（11）：112?115.

（上接第141頁）

[15] FAN Chao， HAO Qing， ZHAO Jing?ling. GA?Chord： an improvement to Chord algorithm based on group autonomy instructed P2P network [C]// IEEE 3rd International Conference on Broadband Network and Multimedia Technology. [S.l.]： IEEE， 2010： 1001?1004.

[16] MESHKOVA Elena， RIIHIJVI Janne， PETROVA Marina. A survey on resource discovery mechanisms， peer?to?peer and service discovery frameworks [J]. Computer Networks， 2008， 52（11）： 2097?2128.

[17] ANDROUTSELLIS?THEOTOKIS S， SPINELLIS D， LOURIDAS P， et al. A market?based approach to managing the risk of peer?to?peer transactions [J]. Computer Networks，2010， 54 （5）： 675?688.

在式（5）中。S0和S是指數關系，也就是說它們存在S0=Sx關系（0

[TTn=11-x] （6）

由式（6），可得出：

[Tn=T(1-x),0

即有：[Tn

從以上分析可知，本模型的路由選擇的時間是根據不同的私有空間劃分等級，因此與目前對等網絡相比較，路由查找時間會有不同程度的縮短，提高了資源搜索的效率。

6結語

云計算環境是由無數的節點組成，面對的是海量數據存數、數據交換與處理，而P2P技術最適合在這種環境中的對等節點之間傳遞信息。在本文模型中，利用P2P技術與云計算技術的緊密結合，利用在云計算環境中的網絡結構的特點，對節點根據能力進行層次劃分等級，并采用一致性Hash算法，使網絡中信息查詢搜索的效率得到提高，使網絡在面對海量數據時仍能提供更好的性能和服務。

參考文獻

[1] HSIAO H C， LIAO H. Load balance with imperfect information instructured peer?to?peer systems [J]. IEEE Transactions on Parallel Disturb System， 2011， 22（4）： 634?649.

[2] 孫秋景，曾凡平.一種信譽機制與云計算相結合的P2P環境信任模型[J].小型微型計算機系統，2010，31（7）：1328?1332.

[3] 陳珊珊.P2P網絡中基于權重因素的信任模型[J].計算機應用，2013，33（6）：1612?1614.

[4] 聶曉文，盧顯良，周旭，等.DHT 算法基本統計特性及應用[J].四川大學學報：工程科學版，2009，41（5）：170?175.

[5] 肖波，聶曉文，侯孟書.DHT網絡規模估計算法的定量分析與設計[J].電子科技大學學報，2011，40（2）：261?266.

[6] 賀智明，曹謙.基于Hash機制的WSN密鑰預分配方案[J].計算機工程與設計，2013（11）：3770?3774.

[7] 葉培順.非結構化P2P網絡的一種改進搜索算法[J].計算機與現代化，2013（12）：44?47.

[8] 張祖昶，王誠.P2P網絡中基于交易代價的信任模型研究[J].南京郵電大學學報：自然科學版，2013，33（6）：35?41.

[9] 馮登國，張敏，張妍，等.云計算安全研究[J].軟件學報，2011，22（1）：71?83.

[10] CHEN S， ZHANG Y， YANG G. Parameter?estimation based trust model for unstructured peer?to?peer networks [J]. IET Communications， 2011， 5（7）： 922?928.

[11] ZHANG De?gan， HU Yu?xia， WANG Dong， et a1. A new algorithm of service discovery based on DHT for mobile application [J]. Jouranal of Network， 2011， 6（10）： 1466?1474.

[12] 楊志興，湯紅波，柏溢，等.移動P2P分布式信任模型設計[J].計算機工程與應用，2013，49（23）：75?80.

[13] 李勇軍，代亞非.對等網絡信任機制研究[J].計算機學報，2010，33（3）：390?405.

[14] 于鑫，金朋飛，石川，等.基于仿真的P2P網絡信譽模型[J].計算機與現代化，2013（11）：112?115.

（上接第141頁）

[15] FAN Chao， HAO Qing， ZHAO Jing?ling. GA?Chord： an improvement to Chord algorithm based on group autonomy instructed P2P network [C]// IEEE 3rd International Conference on Broadband Network and Multimedia Technology. [S.l.]： IEEE， 2010： 1001?1004.

[16] MESHKOVA Elena， RIIHIJVI Janne， PETROVA Marina. A survey on resource discovery mechanisms， peer?to?peer and service discovery frameworks [J]. Computer Networks， 2008， 52（11）： 2097?2128.

[17] ANDROUTSELLIS?THEOTOKIS S， SPINELLIS D， LOURIDAS P， et al. A market?based approach to managing the risk of peer?to?peer transactions [J]. Computer Networks，2010， 54 （5）： 675?688.

在式（5）中。S0和S是指數關系，也就是說它們存在S0=Sx關系（0

[TTn=11-x] （6）

由式（6），可得出：

[Tn=T(1-x),0

即有：[Tn

從以上分析可知，本模型的路由選擇的時間是根據不同的私有空間劃分等級，因此與目前對等網絡相比較，路由查找時間會有不同程度的縮短，提高了資源搜索的效率。

6結語

云計算環境是由無數的節點組成，面對的是海量數據存數、數據交換與處理，而P2P技術最適合在這種環境中的對等節點之間傳遞信息。在本文模型中，利用P2P技術與云計算技術的緊密結合，利用在云計算環境中的網絡結構的特點，對節點根據能力進行層次劃分等級，并采用一致性Hash算法，使網絡中信息查詢搜索的效率得到提高，使網絡在面對海量數據時仍能提供更好的性能和服務。

參考文獻

[1] HSIAO H C， LIAO H. Load balance with imperfect information instructured peer?to?peer systems [J]. IEEE Transactions on Parallel Disturb System， 2011， 22（4）： 634?649.

[2] 孫秋景，曾凡平.一種信譽機制與云計算相結合的P2P環境信任模型[J].小型微型計算機系統，2010，31（7）：1328?1332.

[3] 陳珊珊.P2P網絡中基于權重因素的信任模型[J].計算機應用，2013，33（6）：1612?1614.

[4] 聶曉文，盧顯良，周旭，等.DHT 算法基本統計特性及應用[J].四川大學學報：工程科學版，2009，41（5）：170?175.

[5] 肖波，聶曉文，侯孟書.DHT網絡規模估計算法的定量分析與設計[J].電子科技大學學報，2011，40（2）：261?266.

[6] 賀智明，曹謙.基于Hash機制的WSN密鑰預分配方案[J].計算機工程與設計，2013（11）：3770?3774.

[7] 葉培順.非結構化P2P網絡的一種改進搜索算法[J].計算機與現代化，2013（12）：44?47.

[8] 張祖昶，王誠.P2P網絡中基于交易代價的信任模型研究[J].南京郵電大學學報：自然科學版，2013，33（6）：35?41.

[9] 馮登國，張敏，張妍，等.云計算安全研究[J].軟件學報，2011，22（1）：71?83.

[10] CHEN S， ZHANG Y， YANG G. Parameter?estimation based trust model for unstructured peer?to?peer networks [J]. IET Communications， 2011， 5（7）： 922?928.

[11] ZHANG De?gan， HU Yu?xia， WANG Dong， et a1. A new algorithm of service discovery based on DHT for mobile application [J]. Jouranal of Network， 2011， 6（10）： 1466?1474.

[12] 楊志興，湯紅波，柏溢，等.移動P2P分布式信任模型設計[J].計算機工程與應用，2013，49（23）：75?80.

[13] 李勇軍，代亞非.對等網絡信任機制研究[J].計算機學報，2010，33（3）：390?405.

[14] 于鑫，金朋飛，石川，等.基于仿真的P2P網絡信譽模型[J].計算機與現代化，2013（11）：112?115.

（上接第141頁）

[15] FAN Chao， HAO Qing， ZHAO Jing?ling. GA?Chord： an improvement to Chord algorithm based on group autonomy instructed P2P network [C]// IEEE 3rd International Conference on Broadband Network and Multimedia Technology. [S.l.]： IEEE， 2010： 1001?1004.

[16] MESHKOVA Elena， RIIHIJVI Janne， PETROVA Marina. A survey on resource discovery mechanisms， peer?to?peer and service discovery frameworks [J]. Computer Networks， 2008， 52（11）： 2097?2128.

[17] ANDROUTSELLIS?THEOTOKIS S， SPINELLIS D， LOURIDAS P， et al. A market?based approach to managing the risk of peer?to?peer transactions [J]. Computer Networks，2010， 54 （5）： 675?688.