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

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

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

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

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

編輯推薦：

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

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

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

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