文档介绍：第四章第三代P2P网络 ——结构化P2P体系
Chord、CAN、Tapestry、Pastry
Pastry与PAST:容错的混合式结构P2P网络
Pastry结合了环形结构与超立方体结构(实际是Plaxton mesh)的优点,提供高效的查询路由、确定性的对象定位和独立于具体应用的负载均衡
与Tapestry的不同在于后者是尽可能找到最近的副本,前者则希望副本能均匀、分散的放置
00年Microsoft Research与Rice ,01年发表[Rowstron & Druschel,2001]
Pastry的应用
SCRIBE
通用、可扩展的组通信和事件发布系统,提供应用层多播和任播
PAST
广域、安全的P2P归档存储系统
SQUIRREL
分布式的协同Web缓存,使得用户Web浏览器之间能共享缓存
SplitStream
基于Pastry的高带宽内容流化/发布系统
POST
提供通信、协同的消息框架,可用来支持安全E-mail、安全实时消息、分布式协同应用等
Scrivener
强调P2P系统资源公平共享的架构
其他Pastry项目
PASTA:剑桥大学开发的类似PAST的文件系统
Herald:Microsoft开发的出版/订阅事件发布服务
Pastiche:密西根大学开发的P2P备份系统
DPSR:普度大学开发的有拓扑意识的结构化P2P架构与移动Ad Hoc网多跳路由协议之间的协同项目
一、Pastry路由
Pastry结点与数据对象使用128位的ID,对象索引由与对象ID最接近的结点负责
Pastry采用前缀匹配(本质同Tapestry)
每个结点维护一个路由表、一个叶集和一个邻居集;路由表分层,每列从上到下分别代表与当前节点ID前缀匹配对应位数的结点,其行数就是Pastry采用的进制数;与当前结点nodeID在该位恰好相等的项标为阴影,通常是空指针
图中每项结点ID以X-Y-Z形式表示,其中X标识匹配的前缀,Y表示第一个不匹配位,Z则是结点ID的后几位
Pastry 结点状态
叶集L中包含|L|个与当前结点ID最邻近的“叶结点”,其中|L|/2个比当前ID小,|L|/2个大;叶集的作用在于保证Pastry路由的正确性,类似Chord中的后继列表
邻居集M中包含|M|个在网络物理层与当前结点临近的结点,其作用在于增强Pastry工作的局部性,路由过程中通常不使用M
Pastry结点状态=L+R+M,表中结点项数=|L|+ B*logBN+|M|,B为进制,N为网络结点总数
基于上述路由表,Pastry采用前缀逐位匹配路由,通常每一步至少比前一步多匹配一位前缀,直到无法匹配更多位数,此时的下一跳结点为ID与目的地最邻近的结点,更具体的说,是当前结点的叶集L中与目的ID最接近的结点
显然,Pastry定位跳数为O(logBN),由于叶集L的存在,其路由比Tapestry更快,更容错
为提高安全性,防止恶意结点的破坏,Pastry采用“随机路由”来减少路由的确定性,如,当多个结点都符合下一跳的条件时,不一定选择最优的,而是随机选择一个,以牺牲性能来换取安全
Pastry核心路由算法
路由表R中第l行第Dl项
T,D匹配的前缀长度
Li指叶集L中离当前结点ID第i近的结点
判断D是否在叶集L内
路由表项空缺或不可达
二、Pastry自组织和自适应
Pastry结点加入网络的三项工作
初始化路由表、叶集和邻居集,通知其他结点自己的到来,从现存结点获取需要负责的数据
JOIN STEP1:初始化路由表、叶集和邻居集
新结点X通过众所周知结点或者“扩展环”IP多播联系到一个现存结点A,通常在物理上离X很近
X通过A发送一条以X为目的地的消息,按前缀匹配路由算法,最终到达nodeID离X最近的结点Z
加入消息所走过路径上的每个结点将它们的路由表信息发给X,X接收并优化(类似Tapestry)
X直接从Z获得叶集并作修正,直接从A获得邻居集
JOIN STEP2:通知其它结点自己的到来
比Tapestry简单,只需要把X的结点状态信息发给自己的路由表、叶集、邻居集中的结点
收到更新消息的结点自己去选择用X替换表项
JOIN STEP3:新结点获取需要负责的数据
经典论文中未专门讲述,但类似于Tapestry,且更简单,只需要从叶集结点获取数据
结点的正常离开处理很简单,只需要通知自己所知的结点