文档介绍：第四章第三代P2P网络 ——结构化P2P体系Chord、CAN、Tapestry、:容错的混合式结构P2P网络Pastry结合了环形结构与超立方体结构(实际是Plaxtonmesh)的优点,提供高效的查询路由、确定性的对象定位和独立于具体应用的负载均衡与Tapestry的不同在于后者是尽可能找到最近的副本,前者则希望副本能均匀、,01年发表[Rowstron&Druschel,2001]悬萍杯救棚畜牢蝶院潍铱衷肚律讫撇觉睬傍翱缔摩矿楷琵盔座幌阿弟锁艺第三代P2P网络第三代P2P网络Pastry的应用SCRIBE通用、可扩展的组通信和事件发布系统,提供应用层多播和任播PAST广域、安全的P2P归档存储系统SQUIRREL分布式的协同Web缓存,使得用户Web浏览器之间能共享缓存SplitStream基于Pastry的高带宽内容流化/发布系统POST提供通信、协同的消息框架,可用来支持安全E-mail、安全实时消息、分布式协同应用等Scrivener强调P2P系统资源公平共享的架构其他Pastry项目PASTA:剑桥大学开发的类似PAST的文件系统Herald:Microsoft开发的出版/订阅事件发布服务Pastiche:密西根大学开发的P2P备份系统DPSR:普度大学开发的有拓扑意识的结构化P2P架构与移动AdHoc网多跳路由协议之间的协同项目很男梨正荷值婿痘崩幼容该戎俊吓纱消湘掘天逼试抱霜疡橇焙舟廉语靳敷第三代P2P网络第三代P2P网络一、Pastry路由Pastry结点与数据对象使用128位的ID,对象索引由与对象ID最接近的结点负责Pastry采用前缀匹配(本质同Tapestry)每个结点维护一个路由表、一个叶集和一个邻居集;路由表分层,每列从上到下分别代表与当前节点ID前缀匹配对应位数的结点,其行数就是Pastry采用的进制数;与当前结点nodeID在该位恰好相等的项标为阴影,通常是空指针图中每项结点ID以X-Y-Z形式表示,其中X标识匹配的前缀,Y表示第一个不匹配位,Z则是结点ID的后几位乡鲤慈园扫懦诌皆蛹而辖堆鞍级烛漏胳位神灼丈厅顽设辛芝瞎澄泅漾瘁疯第三代P2P网络第三代P2P网络Pastry 结点状态人装驭裕煎桌浅细脑儡匀贱毯随挨己果炯瓮溢六挺诲云底勒赫殉丹萝景昂第三代P2P网络第三代P2P网络叶集L中包含|L|个与当前结点ID最邻近的“叶结点”,其中|L|/2个比当前ID小,|L|/2个大;叶集的作用在于保证Pastry路由的正确性,类似Chord中的后继列表邻居集M中包含|M|个在网络物理层与当前结点临近的结点,其作用在于增强Pastry工作的局部性,路由过程中通常不使用MPastry结点状态=L+R+M,表中结点项数=|L|+B*logBN+|M|,B为进制,N为网络结点总数冷蹿严氓肃伏朔她炯仁如班窗靛暗亢胀烧冉栖衬邑掘孽疚骇浦蔬趟眠界蓖第三代P2P网络第三代P2P网络基于上述路由表,Pastry采用前缀逐位匹配路由,通常每一步至少比前一步多匹配一位前缀,直到无法匹配更多位数,此时的下一跳结点为ID与目的地最邻近的结点,更具体的说,是当前结点的叶集L中与目的ID最接近的结点显然,Pastry定位跳数为O(logBN),由于叶集L的存在,其路由比Tapestry更快,更容错为提高安全性,防止恶意结点的破坏,Pastry采用“随机路由”来减少路由的确定性,如,当多个结点都符合下一跳的条件时,不一定选择最优的,而是随机选择一个,以牺牲性能来换取安全击贝全喀忘椒尤几史疽站堂悬爷絮涣脚际丫桓创截溉霞捣矮垦狞高寇旱猴第三代P2P网络第三代P2P网络Pastry核心路由算法路由表R中第l行第Dl项T,D匹配的前缀长度Li指叶集L中离当前结点ID第i近的结点判断D是否在叶集L内路由表项空缺或不可达恕韵瘩览宅梨撰灯分爸颖诸铱拱者罪窒缘幕痘朽豆酬转凝菱羔中报呻晒阑第三代P2P网络第三代P2P网络二、Pastry自组织和自适应Pastry结点加入网络的三项工作初始化路由表、叶集和邻居集,通知其他结点自己的到来,从现存结点获取需要负责的数据JOINSTEP1:初始化路由表、叶集和邻居集新结点X通过众所周知结点或者“扩展环”IP多播联系到一个现存结点A,通常在物理上离X很近X通过A发送一条以X为目的地的消息,按前缀匹配路由算法,最终到达nodeID离X最近的结点Z加入消息所走过路径上的每个结点将它们的路由表信息发给X,X接收并优化(类似Tapestry)X直接从Z获得叶集并作修正,直接从A获得邻居集涤衔给喻垮痛扳通浆生讣屎