對等網絡中ＤＨＴ搜索算法綜述

摘要：在P2P網路中如何快速準確地對資源進行定位是衡量其性能的一個關鍵。現在的分布式P2P系統普遍采取的是DHT（distributed hash table，分布式哈希表）搜索方法。基于DHT的P2P網絡搜索算法的研究已經是P2P研究的一個熱點。從P2P定義出發，介紹了P2P網絡按照拓撲結構的分類發展；然后深入介紹了目前對等網絡幾種分布式哈希查找算法Chord、CAN、SkipNet和Cycloid等，并對這些算法從拓撲結構、路由復雜度、路由表大小、容錯性、擴展性、負載平衡性等方面進行了評估比較；最后分析了這些算法的優缺點及今后研究的重點。

關鍵詞：對等網絡； 搜索； 分布式哈希表； Chord ； CAN； 關鍵字

中圖分類號：TP393文獻標志碼：A

文章編號：1001－3695(2008)06－1611－05

P2P是一種分布式網絡，網絡的參與者共享他們所擁有的一部分硬件資源（處理能力、存儲能力、網絡連接能力、打印機等）。這些共享資源需要由網絡提供服務和內容，能被其他對等節點(peer)直接訪問而無須經過中間實體。在此網絡中的參與者既是資源（服務和內容）提供者（server），又是資源（服務和內容）獲取者（client）。

P2P按照拓撲結構的不同可以分為三種：a)集中式拓撲模式，如Napster[1]。這種模式必須有中央服務器。當系統中節點數增多時，中央服務器就成為系統的瓶頸。b)分布式非結構化拓撲模式，如Gnutella[2]和Freenet[3]。每個節點存儲自身的信息或信息的索引，當用戶需要在P2P系統中獲取信息時，他們預先并不知道這些信息會在哪個節點上存儲，搜索采用泛洪方式，搜索在超出一定范圍后就不能進一步擴展。因此，在非結構化P2P系統中，信息搜索的算法難免會帶有一定的盲目性。c)分布式結構化拓撲模式，它們都是基于DHT技術的，如Chord[4]、CAN[5]、Pastry[6]和Tapestry[7]。每個節點只存儲特定信息或特定信息的索引。當用戶需要在P2P系統中獲取信息時，他們必須知道這些信息(或索引)可能存在于哪些節點中。由于用戶預先知道應該搜索哪些節點，避免了非結構化P2P系統中使用的泛洪式查找，提高了信息搜索的效率。

本文介紹了基于DHT的P2P搜索算法的原理，以及典型的分布式結構化路由算法（如Chord、CAN、Pastry、Tapestry、Kademlia[8]、SkipNet[9]）和基于常數度數的路由算法（如Viceroy[10]、Koorde[11]、Cycloid[12]）。

1DHT算法原理介紹

DHT算法使用分布式哈希函數來解決結構化的分布式存儲問題。分布式哈希表實際上是一張很大的散列表；每個節點被分配給一個屬于自己的散列塊，并成為這個散列塊的管理者。DHT及其發現技術為P2P網絡中資源的組織與查找提供了一種全新的算法思想。

該方法的原理是：每一份資源都由一組關鍵字進行標志，系統對其中的每個關鍵字進行哈希，得到關鍵字標志符key；網絡中的每個節點也通過哈希節點IP得到節點標志符ID；關鍵字標志符和節點標志符都是惟一的；按照某種映射關系，將關鍵字標志符映射到節點標志符上，該節點標志符對應的節點就存儲此關鍵字標志符的對應信息。所有的〈key，value〉對構成一張很大的文件索引散列表。其中：key 是關鍵字哈希；va－lue是要存儲的信息地址。例如：key=hash(千里之外.mp3)，value=http://video.com.cn/qlzw.mp3。每個節點按照某種規則維護散列表的一部分。這里的規則依協議的不同而不同。用戶搜索時，用同樣的哈希算法計算出每個關鍵字的標志符key，再根據關鍵字標志符知道該關鍵字標志對應信息的存儲位置，從而能夠快速定位資源的位置。

基于分布式哈希表的分布式檢索和路由算法因為具有查找可確定性、簡單性和分布性等優點，正成為國際上結構化P2P網絡研究和應用的熱點。

2現有DHT搜索算法介紹

2．1典型DHT搜索算法

自從DHT思想提出來以后，分布式結構化P2P搜索算法得到了快速發展。目前很多DHT協議被提出并且得到應用，其中比較典型的有美國麻省理工學院的Chord、加州大學伯克利分校的Tapestry和CAN、微軟研究院的Pastry和SkipNet、美國紐約大學的 Kademlia。

1）Chord在2001年由美國麻省理工學院提出。它的設計基于一維環形空間，每個關鍵字和節點都分配一個m bit的標志符；所有節點按照其節點標志符從小到大按順時針方向排列成一個Chord環。 〈key， value〉對存儲在節點標志等于key或者在Chord環上緊跟在key之后的節點，這個節點被稱為key的后繼節點。每個節點需要維護一個路由表（指針表），表中每一項包含相關節點的標志符和IP地址（和端口號）。如果關鍵字和節點標志符用m位二進制位數表示，那么指針表中最多含有m個表項，節點n的指針表中第i項是Chord環上標志大于或等于n+2i-1的第一個節點。顯然，指針表的第一項為當前節點的后繼節點。節點收到查詢key的請求時，首先檢查該關鍵字標志是否落在該節點標志與它的后繼節點標志之間。如果是，那么這個后繼節點就是存儲目標〈key，value〉對的節點；否則，節點將查找它的指針表，找到表中節點標志符最大但不超過key標志符的第一個節點，并將這個查詢請求轉發給該節點。通過重復這個過程，最終可以定位到存儲有目標〈key，value〉對的節點。圖1給出了Chord環和節點標志符是8的節點指針表[4]。

Chord的突出特點是算法簡單，性能較好，但是在Chord系統中，隨著節點規模的不斷增大，節點性能的差異會嚴重影響系統的效率。文獻[13]提出了雙向路由 dual－Chord。其基本思想是從當前節點的順時針和逆時針同時構造路由表，雙向路由的平均查找長度可以減少到1/3 log(N)。但是這種方法的路由表是原來的兩倍。文獻[14]提出一種改進的Chord算法G－Chord，通過對Chord環進行分組，實現組內節點的自治，而組間的路由和查詢則通過組代表進行，使得路由表的長度得到大幅度的減少，而且在總跳數和平均路徑長度方面基本保持一致。

2)CAN在2001年由美國加州大學伯克利分校提出。它的設計基于虛擬的d維笛卡兒坐標空間。這個坐標空間完全是邏輯的，與任何物理坐標系統都沒有關系；整個坐標空間動態地分配給系統中的所有節點，每個節點負責維護互不相交的一塊區域。與Chord標志符是一維的不同，它的每個關鍵字和節點通過哈希后都分別擁有一個d維向量的標志符，對應于d維坐標空間中的一點，〈key，value〉對存儲在負責管理key所在空間的節點上；每個CAN節點都要保存一張坐標路由表，包括它的鄰居節點（相鄰空間區域中的節點）的IP地址和其維護的虛擬坐標區域，當需要查詢key時，路由的每一步只需將查詢信息發給離key值更近的鄰接節點。圖2給出了二維CAN空間中節點1到點（x，y）的路由過程[5]。因為整個CAN空間要分配給系統中現有的全部節點，當一個新的節點加入網絡時，必須得到自己的一塊坐標空間。CAN通過分割現有的節點區域實現這一過程，它把某個現有節點的區域分裂成同樣大小的兩塊，自己保留其中的一塊而另一塊分給新加入的。

CAN算法的路由路徑趨于很長，定位內容花費的世紀鏈路延遲大，因此文獻[15]提出了一種CAN的擴展算法——eCAN(expressways CAN)。它考慮一個二維空間（實際上該算法適合任何維數空間），把空間劃分為四部分，每個節點保留其兩個鄰接區域的LRCs；然后每部分再同樣劃分為更小的四部分。這樣每個節點保留了所有LRC。實際上eCAN算法是在CAN算法的基礎上進一步引入了加速指針，因而提高了查找效率。文獻[16]提出了一種改進的CAN算法HIMCAN。該系統按照物理網絡距離把節點分成多組，組內獨立建立CAN，使用HD模型和FN模型參數以及結合算法將各組節點連接起來，組成全局意義的HiMCAN，實現查詢的路由本地化，優化路由參數，適合在廣域范圍實現結構性的P2P網絡應用。

3)Pastry由位于英國劍橋的微軟研究院和萊斯大學提出，它是自組織的重疊網絡。為了進行路由，Pastry把節點和關鍵字標志符表示為一串以2b為基的數(b的取值是路由表大小與任意兩節點間需要的最大路由跳數之間的折中)，查詢消息被路由到節點標志和關鍵字標志在數值上最接近的節點。方法是：每個節點將查詢消息轉發給下一個節點時，要保證這個節點標志和關鍵字標志的相同前綴至少要比當前節點的標志和關鍵字標志的相同前綴長一個數位（即b bit）。如果找不到這樣的鄰居節點，消息將轉發給前綴長度相同但是節點號數值更接近關鍵字標志的節點。為此每個Pastry節點都需要三張表：一張路由表、一個鄰居節點集和一個葉子節點集。節點收到一條查詢消息時，首先檢查該消息的關鍵字標志K是否落在葉子節點集范圍內。如果是，則直接將消息轉發給葉子節點集中節點標志和關鍵字標志最接近的節點。如果K沒有落在葉子節點集范圍內，節點就會將消息轉發給路由表中的一個節點。該節點的標志符和K的相同前綴至少要比當前節點的標志符和K的相同前綴長一個數位。如果路由表中相應的表項為空，或者表項中對應的節點不可達，這時查詢消息將被轉發給前綴長度相同但節點標志符更接近K的節點。很明顯，路由的每一步都比上一步向目標節點前進了一步，因此路由過程總是收斂的。

4)Tapestry是美國加州大學伯克利分校提出的一種新型的P2P網絡定位和路由算法。該算法可以對消息進行與位置無關的路由，將查詢消息傳遞到最近的存儲有目標對象拷貝的節點。Tapestry標志符用一個全局統一的進制表示（如使用十六進制）。所有的節點依據標志符自組織成一個重疊網絡。每個節點需要維護一個鄰居映射表，每個表項包括一個鄰居節點的標志符和IP地址。節點N的鄰居映射表分為多個級別，每個級別包含的鄰居節點數量等于標志符表示法的基數；每個級別中鄰居節點標志符和本節點標志符的相同前綴都比前一級別多一個數位。

Tapestry采用基于地址前綴的路由機制。其思想是按照從左到右的順序，每次只改變一個數位。圖3給出了節點5230查找節點42AD的過程[7]。這種方法可以保證路由至多經過logb N個節點就可以到達目的節點；同樣，由于每個節點的鄰居映射表的每個級別只需要保存b個表項，鄰居映射表的空間為logb N。

5)Kademlia協議是美國紐約大學在2002年提出的。與Chord、CAN、Pastry、Tapestry不同，在Kademlia網絡中，兩個節點之間距離并不是依靠物理距離、路由跳數來衡量的，而是根據兩個節點標志的異或（XOR），建立了一種全新的DHT拓撲結構，相比于其他算法，大大提高了路由查詢速度。 

每一個節點均維護了160個list。其中的每個list均被稱之為一個k－桶。在第i個list中，記錄了與當前節點距離為[2i，2i+1)的一些其他對端節點的網絡信息(Node ID、IP地址、UDP端口)。當需要查詢關鍵字key時，首先發起者從自己的k－桶中篩選出若干距離目標節點最近的節點，并向這些節點同時發送異步查詢請求；被查詢節點收到請求之后，將從自己的k－桶中找出自己所知道的距離目標節點最近的若干個節點，并返回給發起者；發起者在收到這些返回信息之后，再次從自己目前所有已知的距離目標較近的節點中挑選出若干沒有請求過的。上述步驟不斷重復，直至無法獲得比查詢者當前已知的k個節點更接近目標的活動節點為止。

6)SkipNet是2003年由微軟Redmond研究院提出的。與前面幾種結構化路由協議相比， 每個節點有兩個標志：字典域標志和數字域標志。字典域標志符由于一般使用網絡域名等標志串，它越近就表示網絡距離越近。SkipNet把節點組織成多個層次的環，每個環上的節點按照字典域標志符順時針排列。第0層的環比較特殊，它包含所有節點，稱該環為根環。以后第i層的環一分為二構成第i+1層環。SkipNet也是采用基于地址前綴的路由查找算法。由于它具有兩個地址空間，相應的路由算法也比其他算法多，分別有字典域路由、數字域路由和混合路由。字典域路由算法相當于折半查找過程；數字域路由算法相當于前綴匹配過程。

2．2基于超節點的DHT算法

很多結構化覆蓋網都保證消息可以通過不到log (N)次轉發到達目標節點，包括Chord、CAN、Tapestry、Pastry、SkipNet、Kademlia等。然而，另外一些結構化覆蓋網的研究者認為，O(logN)跳仍然效率不高，而現在的終端節點有能力維護更多的指針，從而取得更高的路由效率。他們提出一些在一跳或兩跳之內即可完成消息路由的結構化覆蓋網協議，包括Kelips[17]、One－hop[18]、Twins[19]等。

Kelips將節點分成k組，組內節點全連接，通過Gossip的方式進行更新。這樣維護開銷增大很多，但是路由可以在2跳完成。One－hop中每個超級節點維護全局路由狀態，記錄其他所有節點的信息。這樣路由可以在1跳內完成，查找速度快、延時小。這些協議與前述協議的根本不同在于，它們使用組播或者廣播的方式進行指針維護，即節點加入或退出時將消息廣播（或組播）給所有需要知道該消息的節點。這種方法較顯式探測的方法帶寬開銷小很多，因此節點可以維護非常大量的指針，保證路由在很少的跳數內完成。但是該方法路由表的開銷較大，路由表的開銷為O（N）或O（N1/2）。在大規模的重疊網環境中，由于可能存在大量的(數百萬)節點，加之節點都是動態加入和退出網絡，這一條件幾乎不可能滿足。

2．3常數度數DHT搜索算法

網絡節點度數決定了每個節點需要維護的鄰居節點數目。為減少維護開銷，近年來提出了具有常數度數的DHT算法，主要包括Koorde、Viceroy和Cycloid。

1）Viceroy基于一個具有常數度數和對數直徑的類似蝴蝶網的連接圖，它的每個節點都有兩個值：標號ID∈[0，1)和層號l。標號ID均勻獨立地分布在[0，1)上；層號是從區間[1，log N]之間隨機選取的一個值（N是網絡規模估計值）。標號ID可以惟一地標志一個節點，是不會變的；但是層號在節點的生存期內可作適當調整，層號只起路由作用，不起標志作用。所有的節點構成一個大環，同層節點又構成一個小環。一個位于1層的節點有7個指針指向它的鄰居節點，分別是在大環中的前驅和后繼節點、同一小環上的前后兩個相鄰節點以及下層l+1層的左右兩個節點和上面l-1層的上行節點。

Viceroy的路由包括三個步驟：通過上行指針上升到第一層的某個節點；通過下行指針到達一個離目標ID最近的節點；再通過大環或同層環到達目標節點。每次查詢的路徑長度需要O(log N)步。

2）Koorde結合了Chord環和de Bruijn圖的特征，節點和關鍵字標志符都是均勻分布在大小為2d的環形空間域中。其中，每一個節點都有兩個出度，節點標志為N的節點指向節點標志為2N和2N+1的節點。每個節點要維護后繼節點和首個de Bruijn節點。

Koorde的路由過程是：對于給定的鍵值K，路由算法必須根據相應的de Bruijn圖找到K的后繼節點；但由于de Bruijn圖是不完全的，Koorde是將查詢轉發給假象節點i的前驅節點來模擬完全de Bruijn圖進行查找。每個節點與其他節點的連接度為O(1)，每次查詢的路徑長度需要O(log N)步。

3）Cycloid將Pastry與CCC(cube－connected cycles)結合起來， 它模仿 CCC的拓撲結構。一個d維的CCC圖是在一個d為立方體上用d個節點的環替換各個頂點而構成的。Cycloid中每個節點都由一對標號（k，ad-1 ad-2 … a0)共同標志。立方體標號相同的所有節點構成一個小環，而這些小環又構成一個大環。每個節點有一個環上大鄰居(k-1，ad-1 ad-2 … akbk-1 … b0)和環上小鄰居(k-1，ad-1 ad-2 … akck-1 … c0)，還有一個立方體鄰居（k-1，ad-1 ad-2 … akxkxk-1 … x0)、兩個內部葉節點（分別指向本地環上前驅和后繼節點）、兩個外部葉節點（它們與本節點有著相同的立方體標號，分別指向前驅環和后繼環上具有最大環標志的節點）。

Cycloid的路由過程分為三個階段：上升階段找到環標號k≥MSDN的節點；再通過下降階段改變立方體標號，使之更接近目標節點的立方體標號；最后遍歷環循環找到目標節點。在節點數為n=d×2d的Cycloid系統中，每次查詢只要O(d)步，并且每個節點只需維護O(1)個鄰居，每一個節點與網絡中的其他節點連接只需七項，總的路徑長度為O(d)步。

3DHT搜索算法性能比較

上述介紹的算法都是基于分布式哈希表，其本質是一樣的，但都有自己的特點。表1歸納總結了各種算法的拓撲結構、路由表大小、路由復雜度和〈key，value〉的存放位置。下面將從算法擴展性、容錯性、負載平衡性三個方面綜合評估各種算法的優劣并作比較。

3．1算法容錯性

在對等網絡中，節點可能隨時退出或者失效，一旦如此，查找不能進行。Chord中節點失效時，每個包含該節點的指針表都要把該節點換成它的后繼節點，為此每個Chord節點都維護一張包括r個最近后繼節點的后繼列表。如果某個節點注意到它的后繼節點失效了，就可以用其后繼列表中第一個正常節點替換失效節點。正常情況下，CAN中每個節點向其所有鄰居節點發送周期性的更新消息。如果多次沒有接收到某個鄰居的更新消息，那么節點就認為這個鄰居失效。這時節點將啟動接管機制來更新路由表。采用這種機制可以有效地選擇面積最小的鄰居節點來接管失效節點。CAN中一個節點一個或幾個鄰居節點失效時，它依然可以沿著有效的路徑路由，因此CAN算法的穩健性很好。Pastry系統的節點一旦檢測出其葉子節點集L中的某個節點失效，它就會請求該集合中標志符最大或最小的節點將其葉子節點集L′發送過來（如果失效節點的標志符比當前節點的標志符大，則用葉子集中標志符最大的節點，反之則用標志符最小的節點），當前節點將從L′中選擇一個L中沒有的活動節點來替代失效節點。如果系統檢測出其路由表中某項節點失效，它將從該項所在的路由表行中選擇另一個節點，要求該節點將路由表中對應位置的項發過來。如果當前節點的路由表中對應行已經沒有可用節點，那么當前節點將從路由表的下一行中選擇一個節點。這個過程將繼續到當前節點能夠得到一個替代失效節點的節點號，或者當前節點遍歷了路由表為止。節點也會周期性地與鄰居節點集中的節點交換信息以檢測這些節點是否仍在。 Pastry 只有在|L|/2個葉子節點完全失效時才會路由失敗，因此Pastry的容錯性很好。Tapestry在Plaxton的思想上加入了容錯機制，當節點失效時，它的鄰居節點可以檢測到它失效并對路由表作相應調整，從而可適應P2P的動態變化特點。Kademlia要求每個節點必須周期性地發布全部自己存放的〈key，value〉對數據，并把這些數據緩存在自己的k個最近鄰居處。這樣存放在失效節點的數據會很快被更新到其他新節點上，因此Kademlia算法具有很好的容錯性。Koorde把首個de Bruijn點的三個前驅當成備份點，當首個de Bruijn點和三個備用點失效時才失敗。Viceroy采用Bucket來保存更多的信息，以解決節點失效問題。

3．2算法擴展性

One－hop、Kelips、Twins等路由復雜度為O(1)，是一個常數，查詢key時路由跳數不會隨著節點增多而變大，但是每個節點要維護所有其他節點或者組內所有節點的信息，因此新節點的加入或離開要更新的路由表信息很多，擴展性差。Chord、Pastry協議的開銷隨著系統規模(節點總數N)的增加而按照O(log N)的比例增加，而且新節點加入時需要更新的路由表信息也較少，因此它們可以用于大規模的系統。與Chord和CAN等相比，Tapestry在建立鄰居表時很好地考慮了節點鄰接性問題，它的節點動態加入算法很好地實現了系統的擴展性。Viceroy每個節點有進出兩種連接，一個節點的加入或離開要導致所有相關節點的狀態更新。Koorde節點加入或離開要通知它的前驅和后繼節點，更新它們的狀態并使其連接，但是de Brujin圖首個節點離開必須要等待系統穩定時才可以更新。Cycloid 中節點離開時要通知它內葉集合中的節點，如果此節點是所在環上標號最大的節點，那么還要通知它的外葉集合中的節點。One－hop是強聯通圖，每個節點的離開要通知其他所有的節點并更新所有的節點路由表信息。

3．3負載平衡性

DHT算法設計的一個重要性能就是平衡查詢負載。Chord、Tapestry、Pastry、Kademlia所有的節點以同等的概率分擔系統負荷，從而可以避免某些節點負載過大的情況，因此負載平衡性好。每個CAN節點都要保存一張坐標路由表，其中包括它的鄰居節點（相鄰空間區域中的節點）的IP地址和其維護的虛擬坐標區域。當需要查詢key時，路由的每一步只需將查詢信息發送給離key值更近的鄰接節點。維護面積大的節點的鄰居節點較多，查詢時負載也大。One－hop查詢key時只需要一跳，負載平衡且負載較輕。Kelips路由查詢時都要通過超節點，因此超節點的負載比普通節點的負載大。Koorde結合了Chord環和de Bruijn圖的特征，標志符為m的節點其de Brujin圖首個de Bruijn點的節點標志符為2m，所以造成標志符為偶數的節點查詢負載大，而標志符為奇數的節點查詢負載較輕。Viceroy維護了一個具有常數度數和對數直徑的類似蝴蝶網的連接圖，其所有節點都要經過上行指針到最上層，再由下行指針達到沒有下行指針的層，所以造成高層節點查詢負載大而低層節點查詢負載小。Cycloid中的key 存放在數值最接近的節點上。由于在路由的上升階段要保證k≥MSDN，對于環標志符較大的節點查詢負載較大，環標志符小的節點查詢負載較小。表2為這些算法從容錯性、擴展性、負載平衡性的比較。

在理論上，文獻[20]證明了Chord、Pastry、Tapestry就路由表的大小而言，它們所獲得的路由效率已經在數量級上達到最優。文獻[21]討論了各種算法所使用的拓撲結構和系統對節點失敗的適應性和對鄰選擇的兼容性的關系。文獻[22]用圖論的觀點比較了Chord、Pastry、Tapestry、CAN的路由性能和容錯性。

4結束語

本文綜述了在結構化P2P網絡中占有重要地位的分布P2P搜索算法，對每種算法核心思想進行了描述。基于分布式哈希表的搜索方法一直是研究的熱點，一些新的搜索方法不斷涌現，但是，目前大多數DHT算法都存在很多問題，歸納起來主要有下面幾點[23]：

a)不支持多關鍵字查詢。DHT算法通過對文件名進行哈希得到的關鍵字標志，文件的查詢是按關鍵值標志進行的，因此基于 DHT的算法只支持精確查詢，無法進行模糊匹配。由于DHT的精確關鍵詞映射的特性決定了無法與信息檢索等領域的研究成果結合，阻礙了基于DHT的P2P系統的大規模應用。現在研究這方面主要考慮的是數據存儲方式，如建立多關鍵字索引等。

b)不支持語義。DHT算法采用相容散列函數對關鍵字哈希，散列函數總是試圖保證生成的哈希值均勻隨機分布，結果兩個內容相似度很高但不完全相同的對象被生成了完全不同的散列值，存放到完全隨機的兩個節點上，因此目前DHT算法不支持語義。

c)沒有考慮熱點資源對網絡性能的影響。對于那些比較熱門的資源，查詢和下載最后均路由到存儲該資源的節點上，這就會造成這些節點的超載甚至崩潰，進而可能造成整個網絡的癱瘓。目前對此問題提出的解決方法是緩存和多點復制。

d)物理位置和邏輯位置關聯問題。由于節點加入系統時節點標志符是隨機分配的，使得兩個標志符很近的節點實際的物理位置可能很遠。節點之間進行對等通信時，不會優先選取距離自己最近的節點，這就存在請求延遲和下載延遲。目前人們開始研究在原有算法基礎上考慮節點的實際物理位置，如按物理位置對節點聚集或分類等，進一步研究還有待深入。

e)安全問題。P2P網絡中節點可以隨意加入和離開，但是有些節點攻擊可能影響系統數據搜索功能或給系統返回錯誤數據，嚴重時后者可能導致系統癱瘓。目前的DHT算法基本上均未考慮惡意攻擊問題。

參考文獻：

［1］Napster工程[EB/OL]. http://www.napster.com/.

[2]Gnutella工程[EB/OL]. http://gnutella.wego.com.

[3]CLARKE I，SANDERG O，WILEY B，et al. Freenet: a distributed anonymous information storage and retrieval system[C]//Proc ofICSI Workshop on Design Issues in Anonymity and Unobservability. Berkeley：[s.n.]，2000.

[4]STOICA I， MORRIS R， LIBEN－NOWELL D，et al. Chord: a scalable peer－to－peer lookup protocol for Internet applications[J]. IEEE/ACM Trans on Networking， 2003，11(1):17－32.

[5]RATNASAMY S，FRANCIS P，HANDLEY M，et al. A scalable content－addressable network[C]//Proc ofACM SIGCOMM Symposium on Communication，Architecture，and Protocols.2001.

[6] ROWSTORN A，DRUSCHEL P. Pastry:scalable，decentralized object location and routing for large－scale peer－to－peer systems[C]//Proc of the 18th IFIP/ACM International Conference on Distributed Systems Platforms(Middleware 2001). Heidelberg:[s.n.]，2001.

[7]ZHAO B Y，LING Huang，STRIBLING J， et al. Tapestry:a resilient global－scale overlay for service deployment[J].IEEE Journal on Selected Areas in Communications，2004，22(1): 41－53.

[8]MAYMOUNKOV P，MAZIERES D. Kademlia: a peer－to－peer information system based on the xor metric[C]//Proc of the 1st International Workshop on Peer－to－Peer Systems (IPTPS’02).Cambridge:[s.n.]，2002.

[9]HARVEY N J A，JONES M B，SAROIU S，et al. SkipNet: a scalable overlay network with practical locality properties[C]//Proc of the 4th USENIX Symposium on Internet Technologies and Systems.2003.

[10]MALKHI D，NAOR M，RATAJCZAK D. Viceroy:a scalable and dynamic emulation of the butterfly[C]//Proc of Principles of Distributed Computing.Monterey:[s.n.]，2002.

[11]KAASHOEK M F，KARGER D R. Koorde: a simple degree optimal distributed hash table[C]//Proc of the 2nd International Workshop on P2P Systems.Berkeley:[s.n.]，2003.

[12]SHEN Hai－ying， XU Cheng－zhong， CHEN Gui－hai，et al.Cycloid: a new constant－degree and lookup efficient P2P overlay network[C]//Proc of International Parallel and Distributed Symposium. Santa Fe:[s.n.]，2004.

[13]ZHANG Hao，JIN Hai，NIE Jin－wu，et al.Dual－Chord: a more effective distribute hash table[J].Mini－Micro System，2006，27(8):1450－1454.

[14]CHEN Gan， WU Guo－xing，YANG Wang. G－Chord: an improved routing algorithm for Chord[J].Journal of Southeast University: Natural Science Edition，2007，37(1):9－12.

[15]XU Zhi－chen，ZHANG Zheng. Building low－maintenance expressways for P2P systems，HPL－2002－41[R]. Palo Alto:Hewlett－Packard Lab， 2002.

[16]謝瑤，洪佩琳，李津生.HiMCAN:一種新型的基于DHT的P2P內容尋址網絡[EB/OL].(2005).http://www.stanford.edu/~yao－xie/HiMCAN.pdf.

[17]GUPTA I，BIRMAN K，LINGA P，et al. Kelips:building an efficient and stable P2P DHT through increased memory and background overhead[C]//Proc of the 2nd International Workshop on Peer－to－Peer Systems.2003.

[18]GUPTA A，LISKOV B，RODRIGUES R. One－hop lookups for peer－to－peer overlays[C]//Proc of the 9th Workshop on Hot Topics in Operation System(HOTOS IX).2003.

[19]VIAHA A C，De AMORIM M D，VINIOTIS Y，et al.Twins: a dual addressing space representation for self－organizing networks[J].IEEE Trans on Parallel Distrib Syst，2006，17(12):1468－1481.

[20]XU Jun，KUMAR A，YU Xing－xing. On the fundamental tradeoffs between routing table size and network diameter in peer－to－peer networks[C]//Procof the 22nd Annual Joint Conf of the IEEE Computer and Communications Societies. 2003.

[21]GUMMADI K，GUMMADI R，GRIBBLE S，et al .The impact of DHT routing geometry on resilience and proximity[C]//Proc of SIGCOMM.2003.

[22]LOGUINOV D，KUMAR A，RAI V，et al .Graph－theoretic analysis of structured peer－to－peer systems:routing distances and fault resilience[J]. IEEE/ACM Trans on Networking，2005，13(5):1107－1120.

[23]LI Yun－di，FENG Yong. Study of data search in DHT P2P networks[J]. Application Research of Computers ，2006，23(10):226－228.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文