文档介绍：第四章第三代 P2P 网络——结构化 P2P 体系 Chord 、 CAN 、 Tapestry 、 Pastry Pastry 与 PAST :容错的混合式结构 P2P 网络? Pastry 结合了环形结构与超立方体结构(实际是 Plaxton mesh )的优点,提供高效的查询路由、确定性的对象定位和独立于具体应用的负载均衡?与 Tapestry 的不同在于后者是尽可能找到最近的副本,前者则希望副本能均匀、分散的放置? 00 年 Microsoft Research 与 Rice Univ. 开始设计, 01 年发表[Rowstron & Druschel,2001] Pastry 的应用 SCRIBE PAST SQUIRRE L SplitStrea m POST Scrivener 其他 Pastry 项目通用、可扩展的组通信和事件发布系统,提供应用层多播和任播广域、安全的 P2P 归档存储系统分布式的协同 Web 缓存,使得用户 Web 浏览器之间能共享缓存基于 Pastry 的高带宽内容流化/发布系统提供通信、协同的消息框架,可用来支持安全 E-mail 、安全实时消息、分布式协同应用等强调 P2P 系统资源公平共享的架构 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* log B N+|M| ,B为进制, N为网络结点总数?基于上述路由表, Pastry 采用前缀逐位匹配路由,通常每一步至少比前一步多匹配一位前缀,直到无法匹配更多位数,此时的下一跳结点为 ID与目的地最邻近的结点,更具体的说,是当前结点的叶集 L中与目的 ID最接近的结点?显然, Pastry 定位跳数为 O(log B N) ,由于叶集 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 ,且更简单,只需要从叶集结点获取数据?结点的正常离开处理很简单,只需要通知自己所知的结