通信工程師互聯(lián)網(wǎng)技術(shù)考試Pastry

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

1.Pastry
Pastry在2001年由位于英國劍橋的微軟研究院和萊斯（Rice）大學(xué)提出。Pastry也是DHT的一個(gè)變種。
①哈希算法
Pastry使用相容哈希作為哈希算法。哈希所得的鍵值為一維（實(shí)際上使用的是128bit的整數(shù)空間）。Pastry也沒有規(guī)定具體應(yīng)該采用何種哈希算法。
②路由算法
在Pastry協(xié)議中，每個(gè)節(jié)點(diǎn)都擁有一個(gè)128bit的標(biāo)識（NodeId)。為了保證NodeID的性，一般由節(jié)點(diǎn)的網(wǎng)絡(luò)標(biāo)（如IP地址）經(jīng)過哈希得到。
Pastry中的每個(gè)節(jié)點(diǎn)擁有一個(gè)路由表R(R0utingtable)，一個(gè)鄰居節(jié)點(diǎn)集M(Neigh-borhoodSet)和一個(gè)葉子節(jié)點(diǎn)集合L（Leafset），它們一起構(gòu)成了節(jié)點(diǎn)的狀態(tài)表。
路由表共有l(wèi)ogBN(B=26為系統(tǒng)參數(shù)，典型值為16，N表示系統(tǒng)的節(jié)點(diǎn)總數(shù))行，每行包括B-1個(gè)表項(xiàng)，每個(gè)表項(xiàng)記錄了一個(gè)鄰居節(jié)點(diǎn)的信息（節(jié)點(diǎn)標(biāo)識、IP地址、當(dāng)前狀態(tài)等）。這樣就形成了擁有（B-l）logBJV個(gè)條目的二維表格。路由表第；1行的表項(xiàng)所記錄的鄰居節(jié)點(diǎn)的NodeID前”個(gè)數(shù)位和當(dāng)前節(jié)點(diǎn)的前72個(gè)數(shù)位相同，而第n+1個(gè)數(shù)位則分別取從0到B_1的值（除了當(dāng)前節(jié)點(diǎn)第;i+l數(shù)位的值）。這樣形成的路由表很類似IP路由中最長掩碼匹配的算法。參數(shù)6(或B)的大小非常關(guān)鍵：B過大則節(jié)點(diǎn)需要維護(hù)很大的路由表，可能超出節(jié)點(diǎn)的負(fù)載能力；但路由表大些可以存儲更多的鄰居節(jié)點(diǎn)，在轉(zhuǎn)發(fā)時(shí)更為精確。平均毎次路由査找需要的跳數(shù)在Pastry中計(jì)算的結(jié)果是logBN，因此B的選擇反映了路由表大小和路由效率之間的折中。
葉子節(jié)點(diǎn)集合L中存放的是在鍵值空間中與當(dāng)前節(jié)點(diǎn)距離最近的|L|個(gè)節(jié)點(diǎn)的信息，其中一半節(jié)點(diǎn)標(biāo)識大于當(dāng)前節(jié)點(diǎn)，另一半節(jié)點(diǎn)標(biāo)識小于當(dāng)前節(jié)點(diǎn)。|L|的典型值為26或者2-26。
鄰居節(jié)點(diǎn)集合M中存放的是在真實(shí)網(wǎng)絡(luò)中與當(dāng)前節(jié)點(diǎn)“距離”最近的|Af丨個(gè)節(jié)點(diǎn)的信息?！熬嚯x’’的定義在Pastry中非常類似IP路由協(xié)議中對距離的定義，也就是考慮到轉(zhuǎn)發(fā)跳數(shù)、傳輸路徑帶寬、QoS等綜合因素后所得的轉(zhuǎn)發(fā)開銷（可以參見OSPF等路由協(xié)議）。Pastry并未提供距離信息的獲取方法，而是假設(shè)應(yīng)用層可以通過某種手段(人工配制或自動協(xié)商)得到信息并配置鄰居節(jié)點(diǎn)集合。|M|的典型值為26或者2-26。

當(dāng)前節(jié)點(diǎn)已知的其他節(jié)點(diǎn)的信息。路由表共有4X8項(xiàng)，可以看出由上至下節(jié)點(diǎn)ID重合的位數(shù)（前綴）不斷增加。鄰居集合中的節(jié)點(diǎn)ID由于來源于應(yīng)用層。一般沒有規(guī)律性可循。
Pastry的路由過程如下：
首先，路由査詢消息中將攜帶被查詢對象ID,又稱消息鍵值。當(dāng)收到路由消息時(shí)，節(jié)點(diǎn)首先檢查消息鍵值是否落在葉子節(jié)點(diǎn)集合的范圍內(nèi)。如果是，則直接把消息轉(zhuǎn)發(fā)給葉子節(jié)點(diǎn)集合中節(jié)點(diǎn)標(biāo)識和消息鍵值最接近的節(jié)點(diǎn)I否則就從路由表中根據(jù)最長前綴優(yōu)先的原則選擇一個(gè)節(jié)點(diǎn)作為路由目標(biāo),轉(zhuǎn)發(fā)路由消息。如果不存在這樣的節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)將會從其維護(hù)的所有鄰居節(jié)點(diǎn)集合（包括路由表葉子集合及鄰居集合中的節(jié)點(diǎn)）中選擇一個(gè)距離消息鍵值最近的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)目標(biāo)。
從上述過程中可以看出，每一步路由和上一步相比都更靠近目標(biāo)節(jié)點(diǎn)，因此，這個(gè)過程是收斂的。如果路由表不為空，每步路由至少能夠增加一個(gè)前綴匹配數(shù)位，因此，在路由表始終有效時(shí)，路由的步數(shù)至多為logBN。
③優(yōu)缺點(diǎn)分析
Pastry的路由利用了成熟的最大掩碼匹配算法，因此，實(shí)現(xiàn)時(shí)可以利用很多現(xiàn)成的軟件算法和硬件框架，可以獲得很好的效率。
與Chord和CAN相比，Pastry引入了葉子節(jié)點(diǎn)和鄰居節(jié)點(diǎn)集合的概念。在應(yīng)用層能夠及時(shí)準(zhǔn)確地獲得這兩個(gè)集合的節(jié)點(diǎn)信息時(shí)，可以大大加快路由査找的速度，同時(shí)降低因路由引起的網(wǎng)絡(luò)傳輸開銷；不過在動態(tài)變化的P2P網(wǎng)絡(luò)中如何理想地做到這一點(diǎn)的確有很大的難度。

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

編輯推薦：

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

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

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

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