通信工程师互联网技术考试Pastry

　　　在线辅导　面授招生　考试大纲　指定教材　试题汇总

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网络中如何理想地做到这一点的确有很大的难度。

返回目录： 通信工程师互联网技术新型网络体系结构汇总

编辑推荐：

中级通信专业实务 互联网技术教程汇总

中级通信专业实务传输与接入教程汇总

通信专业实务考试设备与环境教程汇总

通信专业实务考试交换技术教程汇总