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

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

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

返回目錄： 通信工程師互聯網技術新型網絡體系結構匯總

編輯推薦：

中級通信專業實務 互聯網技術教程匯總

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

通信專業實務考試設備與環境教程匯總

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