通信工程師互聯(lián)網(wǎng)技術(shù)Chord協(xié)議

　　　在線輔導(dǎo)　面授招生　考試大綱　指定教材　試題匯總

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

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

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

編輯推薦：

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

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

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

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