在線輔導　面授招生　考試大綱　指定教材　試題匯總

1.Chord協(xié)議
Chord在2001年由麻省理工學院提出，其核心思想就是要解決在P2P應用中遇到的基本問題：如何在P2P網(wǎng)絡中找到存有特定數(shù)據(jù)的節(jié)點。與前兩種協(xié)議不同，Chord專門為P2P應用設計，因此考慮了在P2P應用中可能遇到的特殊問題。
　　①哈希算法
Chord使用相容哈希作為哈希算法。在相容哈希協(xié)議中并沒有定義具體的箅法，在Chord協(xié)議中將其規(guī)定為SHA-1。
　　②路由算法
Chord在相容哈希的基礎上提供了優(yōu)化的路由算法，每個節(jié)點維護少量的路由信息，通過這些路由信息，可以提高査詢的效率。

這一方案有兩個重要的特征：首先,每個節(jié)點都需要知道一部分節(jié)點的信息，而且離它最近的節(jié)點，它就知道越多的信息。其次，每個節(jié)點的指針表通常并不包括足夠多的信息可以確定任意一個關鍵字的位置。當節(jié)點n不知道關鍵字1的后繼節(jié)點時，如果n能夠找到一個節(jié)點，這個節(jié)點的標識符更接近，那么這個節(jié)點就知道該關鍵字的更多信息。根據(jù)這一特征，n將查找它的指針表，找到節(jié)點標識符大于k的第一個節(jié)點，并詢問節(jié)點,看是否知道哪個節(jié)點更接近匕通過重復這個過程,最終將會知道A的后繼節(jié)點。
在查詢的過程中查詢節(jié)點將請求發(fā)送到與鍵值最接近的節(jié)點上。收到查詢請求的節(jié)點如果發(fā)現(xiàn)自身存儲了被查詢的信息，可以直接回應查詢節(jié)點(這與相容哈希完全相同）；如果被查詢的信息不在本地就根據(jù)查詢表將請求轉發(fā)到與鍵值最接近的節(jié)點上。這樣的過程一直持續(xù)到找到相應的節(jié)點為止。不難看出，查詢過程實際上就是折半査找的過程。經(jīng)過Chord的優(yōu)化后，查詢需要的跳數(shù)由O(N)減少到OdogCN))這樣即使在大規(guī)模的P2P網(wǎng)絡中（例如N=100000000),查詢的跳數(shù)也僅為0(8)，每個節(jié)點僅需存儲27個（log2100000000)其他節(jié)點的信息。
Chord還考慮到多個節(jié)點同時加人系統(tǒng)的情況并對節(jié)點加人/退出算法作了優(yōu)化。
新節(jié)點n的加人分為3個階段：
a.初始化新節(jié)點的指針表。假設節(jié)點《在加人網(wǎng)絡之前通過某種機制知道網(wǎng)絡中的某個節(jié)點n。這時，為了初始化n的指針表，n將要求節(jié)點：為它查找指針表中的其他表項。
b.更新現(xiàn)有其他節(jié)點的指針表。節(jié)點加人網(wǎng)絡后將調用其他節(jié)點的更新函數(shù)，讓其他節(jié)點更新其指針表。
c.從后繼節(jié)點把關鍵字傳遞到節(jié)點這一步是把所有后繼節(jié)點是的關鍵字轉移到上。整個加人操作的時間復雜度是0(log2JV),如果采用更復雜的算法，可以把復雜度降低到CKlogN。
在對等網(wǎng)絡中，某個對等節(jié)點隨時可能退出系統(tǒng)或者發(fā)生失效，因此，處理節(jié)點失效是一個重要的問題。在Chord中，當節(jié)點n失效時,所有在指針表中包括n的節(jié)點都必須把n替換成的后繼節(jié)點。另外，節(jié)點n的失效不能影響系統(tǒng)中正在進行的査詢過程。
在失效處理中最關鍵的步驟是維護正確的后繼指針。為丁保證這一點，每個Chord節(jié)點都維護一張包括一個最近后繼的后繼列表。如果節(jié)點注意到它的后繼節(jié)點失效了，它就用后繼列表中第一個正常節(jié)點替換失效節(jié)點。
③優(yōu)缺點分析
Chord算法本身具有如下優(yōu)點：
負載平衡。這一優(yōu)點來自于一致性哈希，也就是一致性哈希中提到的平衡性。所有的節(jié)點以同等的概率分擔系統(tǒng)負荷，從而可以避免某些節(jié)點負載過大的情況。
分布性。Chord是純分布式系統(tǒng)，節(jié)點之間完全平等并完成同樣的工作。這使得Chord具有很高的魯棒性,可以抵御DOS攻擊。
可擴展性。Chord協(xié)議的開銷隨著系統(tǒng)規(guī)模（結點總數(shù)/V)的增加而按照O(logN)的比例增加。因此Chord可以用于大規(guī)模的系統(tǒng)。
可用性。Chord協(xié)議要求節(jié)點根據(jù)網(wǎng)絡的變化動態(tài)的更新查詢表，因此，能夠及時恢復路由關系，使得查詢可以可靠地進行。
命名的靈活性。Chord并未限制查詢內容的結構，因此應用層可以靈活的將內容映射到鍵值空間而不受協(xié)議的限制。

返回目錄： 通信工程師互聯(lián)網(wǎng)技術新型網(wǎng)絡體系結構匯總

編輯推薦：

中級通信專業(yè)實務 互聯(lián)網(wǎng)技術教程匯總

中級通信專業(yè)實務傳輸與接入教程匯總

通信專業(yè)實務考試設備與環(huán)境教程匯總

通信專業(yè)實務考試交換技術教程匯總