一種構建Ｋａｄｅｍｌｉａ 網絡拓撲的高效算法
2009-01-01 00:00:00張昊戴長華張翀
計算機應用研究 2009年2期
（國防科學技術大學 信息系統與管理學院， 長沙 410073)
摘 要：通過對結構化P2P網絡Kademlia 的特點和分布式網絡拓撲管理協議的研究，提出了基于非結構化P2P網絡快速構建Kademlia 網絡拓撲的算法，并進行了實驗分析和性能評估。該算法在對數的步數內構建出滿意的Kademlia網絡拓撲，最后提出了對算法優化的相關策略。
關鍵詞：對等網；Kademlia；拓撲管理
中圖分類號：TP393.01 文獻標志碼：A
文章編號：10013695(2009)02053403
Efficient algorithm for building Kademlia topology
ZHANG Hao，DAI Changhua，ZHANG Chong
(School of Information System Management， National University of Defense Technology， Changsha 410073， China)Abstract:This paper firstly analyzed the Kademlia and protocols for distributed overlay topology management， and then proposed an algorithm for building Kademlia topology over unstructured P2P network. At last，demonstrated it through extensive simulation experiments that the proposed algorithm could create a perfect Kademlia topology in a logarithmic number of steps. Furthermore，proposed some strategies for optimizing the algorithm.
Key words:P2P; Kademlia; topology management
0 引言
在P2P研究領域，目前已有的P2P系統劃分為結構化和非結構化兩大類[1]。結構化P2P系統通過相容hash函數[2]將每個資源精確放置在確定的節點上，提供了資源標志ID到資源所在位置的映射關系，從而確保在有限跳數內定位到資源。結構化P2P系統以Tapestry[3]、Pastry[4]、CAN[5]、Kademlia[6]和Chord[7]系統為代表，具有查詢效率高的優點，但較為復雜、魯棒性一般。非結構化P2P系統又可分為集中式（Napster[8]）、全分布式（Gnutella[9]、Freenet[10]）和混合式（KaZaA[11]）三種。集中式P2P系統存在單點失效的問題，全分布式和混合式存在伸縮性差、查詢效率低的缺點[1]。
本文的出發點是如何從分布式非結構化P2P網絡上快速構建結構化P2P網絡。研究這個問題的意義在于快速構建一個面向特定任務的結構化P2P網絡。產生這種需求的場景如利用已有的分布式非結構化P2P系統中的節點快速構建一個分布式海量文件存取系統，這個海量存儲系統的存儲空間由系統內所有節點的存儲資源組成，系統的文件存儲和獲取功能由網絡中分散的節點通過互相協作來實現。這要求每個文件精確放置在確定的節點上，確保從網絡的任何位置能在有限跳數內定位到文件。相似的任務如在非結構化P2P網絡中快速構建分布式計算、緩存、搜索等系統，利用網絡中所有節點的能力解決網絡中任何位置提出的如計算、緩存、搜索等任務。要完成這些任務，一個較好的方法是在原有網絡的基礎上快速構建結構化的P2P網絡。
文獻[12]提出了快速構建Chord網絡的算法TChord，解決了從非結構化P2P網絡快速構建Chord網絡的問題。在結構化P2P網絡中， Kademlia 應用最為普遍，原理和實現簡單、維護網絡拓撲的開銷小，目前主流的P2P軟件如eMule、Bit Torrent、BitComet和BitSpirit等均采用了它作為輔助檢索協議。Chord各節點間存在嚴格的前趨后繼關系，采用穩定協議維護網絡拓撲，產生網絡負載較大。Kademlia采用K_buckets（K桶）的方法使維護網絡拓撲的負載大為減少，本文的研究目標是從非結構化P2P網絡快速構建結構化的Kademlia網絡。
如圖1所示，Kademlia網絡的所有節點都被當做一顆二叉樹的葉子。兩個節點x，y的距離基于數學的二進制異或運算：d(x，y)=xy。每個節點包含一個路由表，保存有一些與自己距離范圍在[2i，2i+1)內的一些節點信息，這些信息由一些(IP address，UDP port，node ID)數據列表構成。每一個這樣的列表都稱之為一個K桶，并且每個K桶的內部信息存放位置是根據上次看到的時間順序排列的，最近看到的放在頭部，最后看到的放在尾部。每個桶都有不超過K個數據項。節點間路由是通過逐步查詢距離目標節點更近的節點，最終收斂到目標節點上[6]。圖2表示了從節點1000路由到節點0100的過程。
1 算法基本思想
對于P2P網絡中的節點，節點直接連接的其他節點稱為該節點的鄰居節點。節點存儲了其鄰居節點的描述信息，包括網絡地址、端口及其他信息，這類描述信息稱為節點描述符。一個節點擁有的鄰居節點的描述符集合稱為該節點的局部視圖，局部視圖僅是整個P2P網絡拓撲的部分信息。
要將非結構化P2P網絡構建成結構化P2P網絡，首先要為每個節點分配全局惟一的ID值，可利用相容hash函數[2]為各個節點產生ID，這在介紹結構化P2P網絡的文獻多有介紹。因此，需要解決的關鍵問題是如何從非結構化P2P網絡快速構建結構化的Kademlia網絡的路由表，也就是K桶。最簡單的解決辦法是先用少量節點建立一個Kademlia網絡，然后再將其他節點依次加入Kademlia網絡，但整個構建網絡拓撲的時間與節點的個數成線性關系，效率太低。借鑒TMan協議[13]的思想，本文針對Kademlia網絡的特點，提出了一個快速構建Kademlia的算法實現。該算法以TMan協議為框架，并針對Kademlia網絡的特點定義了節點選擇算法、視圖提取算法和緩存策略。
TMan協議是M. Jelasity和O. Babaoglu提出的基于流言協議的分布式網絡拓撲管理協議。TMan協議的基本思想是從鄰居節點中選擇距離最近的節點進行交談，交談雙方從對方得到信息，并與自身原有信息合并，通過多輪談話使網絡拓撲向目標網絡拓撲漸進演化。對于網絡中的每一個節點都執行如下協議：
1）主動線程
do at a random time once in each consecutive interval of T time units
p＝selectPeer()
myDescriptor=(myAddress，myProfile)
message=merge(view，myDescriptor)
message=merge(message，rnd.view)
send message to p
receive message from p
view=selectView(merge(message，view))
2）被動線程
協議由兩個線程組成，主動線程主動與其他節點進行消息通信；被動線程等待其他節點向自己發送消息，節點通過收到的消息來更新自己的局部視圖。方法merge(view1，view2)返回view1和view2合并后的局部視圖；方法selectPeer()返回從本節點的局部視圖選出的節點地址；rnd.view是一個由節點抽樣協議[14]（peer sampling service）提供的隨機節點的集合，它的作用主要體現在直徑很大的覆蓋網絡中加快算法的收斂速度。
2 構建Kademlia網絡拓撲算法
借鑒TMan協議的思想，針對本研究問題的特殊性，本文提出了快速構建結構化的Kademlia網絡的算法，如下所示：
1）主動線程
do at a random time once in each consecutive interval of T time units
p=selectPeer();
newView=extractView(p);
newView.reply=true;
send newView to p;
2）被動線程
do forever
receive viewq from q;
if (newView.reply==true){
newView=extractView(q);
newView.reply=1;
send newView to q;}
cache.add(viewq);
refreshKbuckets(viewq);
其中：selectPeer()方法用于從本節點的局部視圖中選取用來交談的節點；extractView(peer p)方法用于從本節點的局部視圖中抽取對出節點p有用的部分視圖；cache.add(newView)用于將新收到的部分視圖緩存起來；refreshKbuckets(view v)用于重新組織K桶。
2.1 節點選擇方法selectPeer()
針對Kademlia網絡，節點選擇方法是先從本節點的局部視圖中選擇那些節點ID與本節點ID異或后值最小的n個節點，再從中隨機選擇某個節點。如此選擇的原因是異或距離小的節點的K桶互補性強，隨機選擇提高了算法的適應性，防止每次都選擇相同的節點。互補性強的原理如圖3所示。對于節點node ID:1000和節點node ID:1001，它們的K桶由area1、area2和area3等節點組成，其K桶的信息大部分是相互通用的。如果節點node ID:1000的K桶內信息很少，它可以學習節點node ID:1001的K桶信息，所以，異或距離小的節點的K桶互補性強。
2.2 視圖抽取方法extractView(peer p)
視圖抽取方法extractView(peer p)的目標是從本節點的局部視圖中抽取出對要交談的節點p有用的信息。因為研究目標是構建出Kademlia網絡，所以節點p需要的是可以填充到自己K桶的信息。因為異或距離小的節點的K桶互補性強，所以與p之間異或距離小的節點信息對于節點p也是非常有用的，它促進下一輪的節點選擇方法selectPeer()選出更優的節點。綜上分析，從本節點的局部視圖中提取的視圖應是以上兩種信息的集合。
2.3 緩存策略的應用
緩存策略是用來存儲在算法執行過程中收到的視圖中的節點描述信息。如果算法收斂速度很快，則緩存的節點信息仍是有效的可能性很大，因為在很短暫的時間內，系統中節點的狀態變化很小。對于節點的少許變化，主要可分為節點加入和退出兩種情況。對于加入，并不會對網絡構建過程產生壞的影響，因為新節點的加入不會影響網絡中原有節點的局部視圖的正確性，也可以規定必須在構建出Kademlia網絡后才允許節點加入；對于少量節點的退出，最終構建的Kademlia網絡可以克服少量節點的退出問題。因此，如果算法收斂較快，則可以認為緩存是可行的。經過模擬實驗，本算法可以在極少的步數內完成，可以認為加入緩存策略是合理的。
2.4 K桶更新算法refreshKbuckets(view v)
K桶更新算法的作用是將視圖v中的節點描述信息補充到Kbuckets，使Kbuckets趨于完整。這個方法的關鍵在于收到的視圖v中包括大量有用的信息，也就是說節點選擇方法和視圖抽取方法是整個算法的關鍵。
3 算法改進策略
為了提高K桶的時效性，對于一個節點描述符可以標注該描述符產生的時間，這樣可以選擇較新的節點描述符來組織K桶，使K桶的時效性進一步加強。值得注意的是，這種改進方法需要一個全局的時鐘服務。
算法沒有考慮節點間通信的時間延遲。為了進一步提高Kademlia網絡的路由效率，可以在組織K桶時考慮節點間的通信時延，選取時延較小的節點來組織K桶，以減少Kademlia網絡的路由時間。
4 算法實驗評估
算法采用peerSim作為網絡模擬平臺。對算法的評估采用對比算法產生的Kbuckets與最優的Kbuckets的方法。最優的Kbuckets是由整個網絡的全局信息產生的，因為它是基于整個網絡的全局信息，所以它是最完整的。一般情況下，由于節點的個數N遠小于2的m次冪(m為節點的ID長度)，節點的Kbuckets的部分Kbucket可能是空的，因為網絡中很可能不存在與該節點距離屬于[2i，2i+1)的節點。對于Kademlia的路由協議來說，不為空的Kbucket才有意義，所以比較不為空的Kbucket的個數的均值是有意義的，從而可以評估構建出的Kademlia網絡的有效性和算法的效率。本文分別針對每個節點有k=20個隨機鄰居的簡單網絡和k=2的無標度網絡[15]做如下實驗。
第一組實驗的底層非結構化網絡為每個節點有k=20個隨機鄰居的簡單網絡，節點ID長度為20和30，節點個數為1 000、5 000、10 000和20 000，分別執行算法，結果如圖4、5所示。X軸為進行交談的輪數（每個節點在一輪內主動發起一次交談）；Y軸為每個節點的Kbuckets中不為空的Kbucket個數的均值；虛線代表用網絡全局信息構建的Kademlia網絡中每個節點的Kbuckets中不為空的項的個數的均值；曲線分別表示節點個數為1 000、5 000、10 000和20 000的執行結果。實驗結果表明：算法以對數方式收斂，且在10輪以內，得到了滿意的Kademlia網絡，算法得到的K桶的完整性達到了99.99%以上。另一個明顯的特征是：對于Kademlia網絡，Kbuckets中不為空的Kbucket的個數的均值與ID長度的相關性很小，與網絡中節點的總個數相關性很大，與節點個數成對數關系。
第二組實驗的底層非結構化網絡為無標度網絡，如圖6所示，實驗結果類似于第一組實驗。
5 結束語
本文提出了一種快速構建Kademlia網絡的算法，闡述了算法的思想及詳細的執行過程，最后進行了實驗，算法在有限的執行輪數內得到了滿意的收斂效果。算法在其他形式的網絡中收斂性和算法的改進策略是下一步研究的重點。
參考文獻：
［1］
LUA E K，CROWCROFT J，PIAS M，et al.A survey and comparison of peertopeer overlay network schemes[J].Journal of IEEE Communications Survey and Tutorial，2005，7(2):7293.
［2］KARGER D，LEHMAN E，LEIGHTON T，et al.Consistent hashing and random trees:distributed caching protocols for relieving hot spots on the World Wide Web[C]//Proc of the 29th Annual ACM Symposium on Theory of Computing.New York:ACM Press，1997:654663.
［3］ZHAO B，KUBIATOWICZ J，JOSEPH A.Tapestry:an infrastructure for faulttolerant widearea location and routing， UCB/CSD011141[R].Berkeley: University of California at Berkeley， 2001.
［4］ROWSTRON A，DRUSCHEL P.Pastry:scalable， decentralized object location， and routing for largescale peertopeer systems[C]//Proc of IFIP/ACM International Conference on Distributed Systems Platforms.Berlin:SpringerVerlag， 2001:329350.
［5］RATNASAMY S，FRANCIS P，HANDLEY M，et al.A scalable contentaddressable network[C]//Proc of International Conference on Applications Technologies，Architectures，and Protocols for Computer Communication.New York:ACM Press，2001:161172.
［6］MAYMOUNKOV P，MAZIERES D. Kademlia:a peertopeer information system based on the XOR metric[C]//Proc of IPTPS’02.2002:5365.
［7］STOICA I，MORRIS R，KARGER D，et al.Chord:a scalable peertopeer lookup service for Internet applications[C]//Proc of Internatio-nal Conference on Applications Technologies，Architectures，and Protocols for Computer Communication.New York:ACM Press，2001:149160.
［8］The Napster homepage[EB/OL].http://free.napster.com.
［9］The Gnutella protocol specification v0.4[EB/OL]. http://www.clip2.com.
［10］CLARKE I，SANDBERG O，WILEY B，et al.Freenet:a distributed anonymous information storage and retrieval system[C]//Proc of International Workshop on Design Issues in Anonymity and Unobservability.Berlin:Springer，2000:4358.
［11］KaZaA media desktop[EB/OL]. http://www. kazaa.com.
［12］MONTRESOR A，JELASITY M，BABAOGLU O.Chord on demand[C]//Proc ofthe 5th IEEE International Conference on PeertoPeer Computing.2005:8794.
［13］JELASITY M，BABAOGLU O.TMan:gossipbased overlay topology management[C]//Proc of the 3rd International Workshop on Engineering SelfOrganizing Applications.2005.
［14］JELASITY M，GUERRAOUI R，KERMARREC A，et al.The peer sampling service:experimental evaluation of unstructured Gossipbased implementations[C]//Proc of the 5th ACM/IFIP/USENIX International Conference on Middleware.Berlin:SpringerVerlag，2004:7998.
［15］BARABASI A L，ALBERT R.Emergence of scaling in random networks[J].Science，1999，286(5439):509512.
