P2P网络体系(3)

大纲 第一代P2P网络：混合式P2P体系 第二代P2P网络：无结构P2P体系 第三代P2P网络：结构化P2P体系（＊）

第三代P2P网络：结构化P2P体系 Chord&CFS CAN Tapestry&OceanStore Pastry&Past Kademlia SkipNet Viceroy Koorde Cycloid

其他著名结构化P2P网络 实践系统：，提出更加容错、实用的P2P系统，如Kademlia(2002)，路由方式类似Chord，但采用异或的距离量度，并将网络结构配置信息融合到每条消息中；SkipNet(2003)模型，类似Chord，但采用跳表SkipList数据结构，提供结点路由、对象语义两方面的局部性，以前的结构化P2P网络都没有做到 理论模型：具有特殊性质的新型结构化P2P模型——常数度P2P网络，其路由、定位、自组织方式与过去的模型区别不大，但每个结点的“度”（即连接数）是固定的，不随网络规模改变，保持路由效率的同时减小了自适应开销，常见模型有Viceroy(2002)、Koorde(2003)、Cycloid(2004)

实践系统 一、Kademlia 二、SkipNet

一、Kademlia：基于异或度量的P2P信息系统 由于“异或”是对称的，因此Kademlia结点能从路由消息中获得有用的网络配置信息，这种“捎带更新”方法使得Kademlia以很小的开销获得了很大的自适应性 Kademlia不像Chord需要严格的路由表，可以发送消息给其路由表任意一段(interval)中的每一个结点，让基于时延选择路由下一跳，甚至让它们发送并行的异步消息

Kademlia的应用 Overnet网络 Overnet 现已被整合到eDonkey2000中 eDonkeyHybrid mlDonkey 运行于多平台、多网络的eDonkey扩展版软件 Kad网络 eMule 0.40版之后 2.5-28版之后 aMule All-platform eMule，eMule的多平台扩展版 RevConnect 基于DirectConnect协议的P2P文件共享软件，以Kademlia作为分布式散列表 KadC 用以在Overnet网络中发布、获取信息的C语言库 Azureus 2.3.0.0版之后，使用Kad网络作为BitTorrent Trackers失效时的替代 方法 BitTorrnet 4.1.0版之后，使用Kad网络为无Tracker的torrents服务 BitSpirit 基于BitTorrent协议的一个客户端，3.0版之后 eXeem 基于BitTorrent网络的一个P2P文件共享软件，用以取代BT中原有的Trackers

Kademlia的异或度量、结点状态和自组织 Kademlia结点、对象ID分配、以及索引负责方式同经典的P2P网络 设Kad网络中有两个结点，ID分别为x,y，其距离d(x,y)=x⊕y，d(x,y)=d(y,x)，具有对称性和三角属性，类似CAN、Tapestry和Pastry，不同于Chord 与Chord的顺时针环形度量一样具有单向性，保证了所有对相同数据对象的定位最终将会聚于相同的路径，且越往后走会聚的可能性越高

Kademlia的结点状态和自组织 每个Kad结点维护一个称为k-buckets的路由表，以采用160位ID为例，对每位i，结点都保存一个链表，称为一个k-bucket，其中记录到自己的异或距离在2i与2i+1之间的一些结点，并按照最近访问时间从尾到头排列 每个链表项是形如(IP, UDP port, nodeID)的三元组 i越大，其链表项越多，并呈指数增长，因此Kad网络给出链表长度上限k

Kademlia概况 ■距离的概念：两个标识符之间位异或的值。 数学依据：1)d(x,x)=0 2)if x!=y, d(x,y)!=0 3)d(x,y)+d(x,z)>=d(x,z) 距离[1,2] ■Kad路由表--K桶 K桶[0] null 0=<i<160,每个节点保存K个离本节点距离为2^i~2^(i+1)的节点信息。 ■Kad表动态更新策略： 当受到来自其他节点的消息时，即更新Kad桶。 发送节点在K桶中，移至列表尾部。 若K桶没满，则移至尾部。 若K桶满，则对列表头节点发送Ping命令。若没回复，则删除节点。 距离[2,4] K桶[1] null K桶[2] null 距离[4,8] K桶[159] Last-recently most-recently

Kademlia的四个远程调用(RPC remote procedure call) ■PING 测试节点是否在线 ■STORE 指示一个节点储存一个<Key,Value>对用于以后的检索 ■FIND_NODE 将目标节点ID作为变量，RPC接受端返回k个它所知道的最接近目标ID的节点信息。 ■FIND_VALUE 同FIND_NODE类似，返回K个所知道的最接近目标键值的节点信息。若接收者拥有这个键的STORE RPC，则只需返回这个已储存的值。

不断地进行上述的过程，直到本次响应得到的结果中无法更新原先的结果列表。 至此，本次查询结束，得到离目标节点最近的k个节点。 Kademlia：定位节点 输入参数：目标节点ID 得到： 网络中离节点ID最近的K个节点 具体算法： 先从自己的K桶中找出和键值最近的k个节点。向这k个节点发送FIND_NODE请求。接受方在他们的K桶中进行查询，如果发现离目标节点更近的节点，就返回这些节点(最多k个)。消息的请求者根据受到的响应来更新结果列表，这个结果列表保存k个离目标节点最近的节点。 不断地进行上述的过程，直到本次响应得到的结果中无法更新原先的结果列表。 至此，本次查询结束，得到离目标节点最近的k个节点。

Kademlia：定位资源 与定位节点的算法相似，对于以前STORE的消息，储存节点将会有对应STORE所储存的相关资源的信息。定位资源时，如果有一个节点存有相应的资源的值 的时候，它就返回该资源，定位结束。除了该点以外，定位资源与定位离键最近的节点过程相似。 资源的值被储存在多个节点上。储存值的节点将定期地搜索网络中与储存值对应的键值最接近的K个节点并且将值复制在这些节点上。 对于流行的内容， 为了应对更多可能的请求，通过让那些访问值的节点把值储存在附近的一些节点上(不在K个最近节点范围内)，来减少储存值的节点的负载。资源的值被储存在离键越来越远的地方,使得流行的搜索搜索可以更快找到资源的储存者。 提供文件的节点会周期性的更新网络上的信息(通过NODE_LOOKUOP和STORE消息)。当存有某个文件的节点都下线了，该文件的相关信息也从网络上消失了。

Kademlia：节点的加入和离开 当节点A要加入网络时，首先要确定一个已经存在于网络中的B。首先，A将B加入自己的K桶中。然后对自己进行一次FIND_NODE操作，并且根据受到的内容更新自己的K桶。然后对K桶进行刷新，在这同时A既更新了自己的K桶，又将自己插入到其他节点的K桶中。(将自己的到来告诉其它结点，以更新它们的状态，即为刷新) 节点的离开不需要发布任何信息。Kademlia要求每个节点必须周期性地发布自己存放<Key,value>对数据，并把这些数据缓存在自己的k个最近邻据节点上，这样存放在实效节点上的数据会很快地被更新到其他新节点上。

Kademlia特点 1、当Kad结点收到消息，用消息发送者的nodeID来更新相应的k-bucket，称为“捎带确认”piggy-backing，或捎带更新。 它还能有效地防止DoS攻击，攻击者无法用特定的nodeID填满其它结点的路由表，因为Kad网络只有检测到旧结点失效才会用新结点 2、路由主动更新：为保持路由表k-buckets的更新，如果某个路由表的所有结点在一个小时中未被查询，则从中任选一个ID对该结点做结点查询以刷新路由表

3、K个ID邻近复制：保证k个结点存储value，并且此k个结点每过一个小时就重新发布<key, value>对，以保证数据可用；同时还要求最初的发布者S结点每过24小时重新发布<key, value>，否则过期 4、为保持存储、查询的一致性，当任何一个结点A发现存在另一个结点B离保留在A上的键值对更近时，A会复制键值对到B，但不删除自己数据库中的键值对

Kademlia Binary Tree Subtrees of interest for a node 0011……

Kademlia Binary Tree Every node keeps touch with at least one node from each of its subtrees. (if there is a node in that subtree.) Corresponding to each subtree, there is a k-bucket.

Kademlia Search An example of lookup: node 0011 is searching for 1110……in the network

二、SkipNet：基于跳表、提供显式局部性的P2P模型 SkipNet通过“跳表”(SkipList)数据结构提供显式局部性，体现在两个方面 内容局部性，即语义上可控的对象放置，能够显式地指定数据对象的放置位置或放置范围 路由局部性，同一个组织中结点间消息路由的路径一定位于该组织内部 显式局部性是SkipNet的最大亮点，但也弱化了一致性散列函数的影响，不能提供很好的负载均衡；SkipNet通过折中的办法平衡负载均衡与局部性的矛盾，称为“受限负载均衡”，即数据只在某个范围内而不是全局分布均衡

SkipNet语义局部性能缓解一些在其它系统中非常严重的问题，如“网络分割”问题：Chord, Pastry等网络一旦分割，性能会急剧下降甚至不能正常工作；SkipNet保证同一个组织中结点间消息路由的路径一定位于该组织内，因此可以在隔离的情况下正常工作 路由局部性对安全性的影响 正面：组织内通信自闭，外界难以监听；便于控制和管理组织 反面：一旦被非法控制，影响很大

SkipNet采用两套独立而又相关的ID：NameID（名标识）和NumericID（数值标识） 在折中的方法里，SkipNet将结点名或者内容标识用“！”分成两部分，前一部分直接作为NameID，后一部分的散列值作为NumericID,从而在局部性与随机性之间取得平衡

SkipNet的组织结构 SkipList是一个有序的链接表，其中一些指针指向跳表中距离很远的结点，每个指针有它的层level，层越高指的越远 在一个“完全跳表”中，第h层指针指向距离2h的结点，通常每隔2i个结点才会有一个i层指针（最底层为第0层）。完全跳表支持O(logN)跳的关键码搜索 完全跳表过于严格，不适应网络的动态性，SkipNet采用“概率跳表”，每个结点按照概率选取自己具有哪层指针。0层必选，选择第i层 指针的概率为1/2h。仍支持O(logN)跳的关键码搜索

SkipNet 完全跳表 概率跳表

SkipNet中将跳表头尾相接成一个环，并且每个指针变为双向，因此结点路由表(R-Table)项数为2logN，其中第h层指针指向距离当前结点2^h跳的两个结点，一个沿顺时针方向，一个沿逆时针方向 图中，根环上结点之间按照结点名或其数据对象关键码（NameID）来排列

SkipNet根环（0层主环）及结点A、V的路由表

SkipNet环的拆分及A的路由表图示 Node A’s Routing Table M D O Root Ring A T Z V X M 000 Ring 001 Ring 010 Ring 011 Ring 100 Ring 101 Ring 110 Ring 111 M D Z A T L = 3 X V O M D A Ring 00 T Ring 01 Ring 10 Ring 11 L = 2 V Z O X Node A’s Routing Table M D O Ring 0 Ring 1 A T L = 1 Z V X M FIRST: A’S ROUTING TABLE CONSISTS OF THE FOLLOWING ENTRIES: D M AND T. T’S ROUTING TABLE ENTRIES CONSIST OF: A X V. SOURCE = A DESTINATION = V Alternate view of routing table pointers. Routing efficiency is preserved as long as ring populations are statistically preserved. So, starting from the bottom, can flip a coin to decide which subring to join of an existing ring. D O Root Ring A T Level: L = 0 Z V X 27 27 Eddie Bortnikov, Principles of Reliable Distributed Systems, Technion EE, Spring 2004

图例解释 因每层指针隔一个结点指向下一个结点，因此，第i层指针将第(i-1)层环分成两个i层环，而i-1层环中的每个结点以1/2的概率选择加入哪个i层环，导致实际的环拆分可能不等，但这种松散的组织方式有利于插入、删除操作，也能保持O(logN)的定位跳数 图中每层环给出了环标识ringID，根环没有环标识，最后一层环的ringID就是NumericID，显然，NumericID的前h位决定了它在第h层的环关系；而NumericID的作用类似于散列函数，是随机的、均匀的；

就ID分布而言，根环上的结点以NameID顺序串成一个环，最高层的单结点环则以NumericID排列 除了R-Table路由表，每个SkipNet结点还维护一个“叶集”L，与Pastry的叶集组成与功能类似，其中L/2个叶集结点是环上顺时针方向离当前结点最近的，另一半在逆时针方向上最近

SkipNet路由 两种方式：NameID路由，NumericID路由 NameID路由与Chord类似，是数值临近路由(可基于skiplist），下一跳总选择路由表中不超过目的结点NameID的最高层结点，直到两个NameID最近，路由跳数通常为O(logN) NumericID路由与Pastry类似，首先查找根环，直到发现一个结点与目的结点的NumericID匹配第一位，此时通过该结点“爬升”到它的1层环，再在1层环上查找与目的结点NumericID匹配的前两位的结点。依此类推，每次上升一层多匹配一位，直到不能匹配到更多位，又不能找到NumericID更接近的结点为止，此时到达的就是目的结点，路由跳数通常也为O(logN)

Routing By Name ID Like search in a Skip List Simple Rule: Forward the message to node that is closest to destination, without going too far. Route either clockwise/counterclockwise Terminates when messages arrives at a node whose name ID is closest to destination. Number of hops is O(log N) w.h.p. Message routed from highest level pointer in either clockwise / counter clockwise direction with name ID that are not past the destination value. Because nodes are doubly linked, scheme routes either to left or right pointers depending on name ID’s. 31 Eddie Bortnikov, Principles of Reliable Distributed Systems, Technion EE, Spring 2004

Example: Routing from A to V Ring 000 Ring 001 Ring 010 Ring 011 Ring 100 Ring 101 Ring 110 Ring 111 M D O A T L = 3 X V Z M D A Ring 00 T Ring 01 Ring 10 Ring 11 L = 2 V Z O X M D O Ring 0 Ring 1 A T L = 1 Z V X M FIRST: A’S ROUTING TABLE CONSISTS OF THE FOLLOWING ENTRIES: D M AND T. T’S ROUTING TABLE ENTRIES CONSIST OF: A X V. SOURCE = A DESTINATION = V Alternate view of routing table pointers. Routing efficiency is preserved as long as ring populations are statistically preserved. So, starting from the bottom, can flip a coin to decide which subring to join of an existing ring. D O Root Ring A T Level: L = 0 Z V X 32 Eddie Bortnikov, Principles of Reliable Distributed Systems, Technion EE, Spring 2004

Example: Routing from A to V Ring 000 Ring 001 Ring 010 Ring 011 Ring 100 Ring 101 Ring 110 Ring 111 M D O A T L = 3 X V Z M D A Ring 00 T Ring 01 Ring 10 Ring 11 L = 2 V Z O X M Node T’s Routing Table D O Ring 0 Ring 1 A T L = 1 Z V X M FIRST: A’S ROUTING TABLE CONSISTS OF THE FOLLOWING ENTRIES: D M AND T. T’S ROUTING TABLE ENTRIES CONSIST OF: A X V. SOURCE = A DESTINATION = V Alternate view of routing table pointers. Routing efficiency is preserved as long as ring populations are statistically preserved. So, starting from the bottom, can flip a coin to decide which subring to join of an existing ring. D O Root Ring A T Level: L = 0 Z V X 33 Eddie Bortnikov, Principles of Reliable Distributed Systems, Technion EE, Spring 2004

Example: Routing from A to V Ring 001 Ring 010 Ring 011 Ring 100 Ring 101 Ring 110 Ring 111 Ring 000 M D O A T L = 3 X V Z M D A Ring 00 T Ring 01 Ring 10 Ring 11 L = 2 V Z O X M D O A Ring 0 T Ring 1 L = 1 Z V X M FIRST: A’S ROUTING TABLE CONSISTS OF THE FOLLOWING ENTRIES: D M AND T. T’S ROUTING TABLE ENTRIES CONSIST OF: A X V. SOURCE = A DESTINATION = V Alternate view of routing table pointers. Routing efficiency is preserved as long as ring populations are statistically preserved. So, starting from the bottom, can flip a coin to decide which subring to join of an existing ring. D O Root Ring A T Level: L = 0 Z V X 34 Eddie Bortnikov, Principles of Reliable Distributed Systems, Technion EE, Spring 2004

Name ID Routing Algorithm Load Balancing // Invoked at all nodes (including the source and // destination nodes) along the routing path. RouteByNameID(msg) { // Forward along the longest pointer // that is between us and msg.nameID. h = localNode.maxHeight; while (h >= 0) { nbr = localNode.RouteTable[msg.dir][h]; if (LiesBetween(localNode.nameID, nbr.nameID, msg.nameID, msg.dir)) { SendToNode(msg, nbr); return; } h = h - 1; // h<0 implies we are the closest node. DeliverMessage(msg.msg); SendMsg(nameID, msg) { if( LongestPrefix(nameID,localNode.nameID)==0 ) msg.dir = RandomDirection(); else if( nameID<localNode.nameID ) msg.dir = counterClockwise; else msg.dir = clockwise; msg.nameID = nameID; RouteByNameID(msg); } Path Locality 35 Eddie Bortnikov, Principles of Reliable Distributed Systems, Technion EE, Spring 2004

Routing By Numeric ID Numeric id’s are random, no ring is sorted by them We can’t route top-down! Bottom-up Routing Routing begins at level 0 ring until a node is found whose numeric ID matches the destination numeric ID in the first digit. Messages forwarded from ring in level h, Rh, to a ring in level h+1, Rh+1, such that nodes in Rh+1 share h+1 digits with destination numeric ID. Terminates when message delivered, or none the nodes in Rh share h+1 digits with destination numeric ID 36 Eddie Bortnikov, Principles of Reliable Distributed Systems, Technion EE, Spring 2004

Example: Routing by Numeric ID Ring 000 Ring 001 Ring 010 Ring 011 Ring 100 Ring 101 Ring 110 Ring 111 Foo.c M D O A T L = 3 X V Z M D A Ring 00 T Ring 01 Ring 10 Ring 11 L = 2 V Z O X M D O Ring 0 Ring 1 A T L = 1 Z V X M Note that no ring is sorted by numeric id, so we need to search bottom up D O Root Ring A T Level: L = 0 Z V X 37 Eddie Bortnikov, Principles of Reliable Distributed Systems, Technion EE, Spring 2004

Routing by Numeric ID The same routing tables are used for routing by nameID and numericID The number of message hops is O(log N) whp What sequential data structure does this search resemble? The data structure is TRIE for prefix search 38 Eddie Bortnikov, Principles of Reliable Distributed Systems, Technion EE, Spring 2004

Routing Algorithm // Invoked at all nodes (including the source and destination nodes) along the routing path. // Initially: msg.ringLvl = -1, msg.startNode = msg.bestNode = null & msg.finalDestination = false RouteByNumericID(msg) { if (msg.numID == localNode.numID || msg.finalDestination) { DeliverMessage(msg.msg); return; } if (localNode == msg.startNode) { // Done traversing current ring. msg.finalDestination = true; SendToNode(msg.bestNode); h = CommonPrefixLen(msg.numID, localNode.numID); if (h > msg.ringLvl) { // Found a higher ring. msg.ringLvl = h; msg.startNode = msg.bestNode = localNode; } else if ( abs(localNode.numID - msg.numID) < abs(msg.bestNode.numID - msg.numID)) { // Found a better candidate for current ring. msg.bestNode = localNode; // Forward along current ring. nbr = localNode.RouteTable[clockWise][msg.ringLvl]; SendToNode(nbr); 39 Eddie Bortnikov, Principles of Reliable Distributed Systems, Technion EE, Spring 2004

SkipNet结点加入和离开 新结点N首先使用NumericID算法，发送以N为目的地的消息，以找到与其NumericID相应的最高层环；再使用NameID算法找到这层环上自己的邻居；然后通过该邻居，在下一层环上寻找邻居，以此类推，直到根环；完成后，N通知它所在每层环上的邻居结点将N加入路由表；新结点加入时发出的消息数为O(logN) SkipNet结点的离开、失效算法类似Chord，根环最重要，保证定位的正确性，应及时修正；高层环用来加速定位，类似Chord的Finger Table，对其修正较松散，只要主环正确，可以保证高层环正确修复

SkipNet的背景修复 与Chord的Stabilization一样，SkipNet也有类“背景修复”操作，整个过程开始于根环，每个结点周期性地发送消息给根环上自己的叶集中的邻居，检测是否可达，不可达则找新的邻居替换；进而修复1层环邻居，以此类推，每次修复i+1层环都是基于前一步已经修复好的i层环。此外 辅助性局部修复方法：某层环内，每个结点周期性地发送送消息给该层的邻居，告诉它“我认为我是你的第n层左(右)邻居”，收到消息的邻居检查到正确则不回复，错误则回复“我的左(右)邻居是XXX，不是你”，产生一个“冲突”，启动一个协作的过程修复状态使其一致

SkipNet的局部性 内容局部性、路由局部性，基于NameID标识和NameID路由（具体实现中SkipNet的设计者采用了反向DNS的命名风格，如edu.ustc.wang，以使同一域中的结点拥有共同的前缀） 受限负载均衡CLB：将数据对象名分成两个部分，第一部分是域名，保留原有DNS名的前缀，也称CLB域，第二部分是原有DNS名后缀的散列值，称CLB后缀，中间隔有“！”这样既保留了局部性，又在域内保持了负载均衡

受限负载均衡机制下数据对象的查询 使用NameID路由算法相应CLB域内的任意一个节点 然后使用NumericId路由算法在域内寻找带有CLB后缀散列值的结点，这一步要注意，当遇到ID界限（as determined by the name ID prefix boundary)时，查询必须反向走以确保没有结点被漏掉 两步加起来路由跳数量级仍为O(logN)，但跳数比单纯的两种路由方式更多

SkipNet的拓扑一致性 SkipNet依靠P-Table(Proximity Table, 临近表)提供物理网局部性（拓扑一致性） P-Table类似Pastry的邻居集M，但更复杂，它将表分成多个指数级的间隔(interval)，每个间隔保存一个邻近结点作为物理邻近的参照 当新结点N加入网络时，发送消息(P-Table join message)给物理上离自己很近的一个结点（称为种子结点，seed node），该消息为每个间隔维护一个常数项的链表，能容纳多个候选结点

种子结点收到消息后，使用自己的P-Table项填充消息中的间隔作为候选结点，然后将消息发给自己的P-Table中离N最远的结点作为下一跳，继续填充消息中的间隔，以此类推 当消息中每个间隔都有至少一个候选结点后，消息被回送给新结点N以初始化N的P-Table

SkipNet对网络分割问题的解决（请自学） 松散路由表：增加进制分出更多环 密集路由表：在R-Table每层两个方向增加额外的邻近结点指针(类似Chord的后继列表） 各有千秋 重复指针删除：相邻层的相邻结点指针重复，将其中一个替换成同样符合条件的邻近结点。替换后可改善25%的性能。 SkipNet对网络分割问题的解决（请自学） 08.10.16第10次课

常数度P2P模型：Viceroy、Koorde和Cycloid 无具体应用，理论意义 结点的度（连接数）固定，路由、定位、自组织方式与过去的模型区别不大，维持O(logN)的定位效率同时减小系统开销

一、Viceroy：基于蝴蝶结构的常数度P2P模型 蝴蝶拓扑（butterfly topology） Viceroy还将其覆盖网结点组织成一个与Chord非常相似的环形 Viceroy的结点、对象ID区间为[0,1) 每个结点有一个逆时针方向的前驱、一个顺时针方向的后继，每个数据对象（的索引）由其后继负责

Viceroy思维 We start at x searching for y Path from x to y : 1/2i + 1/2j + 1/2k + … The problem is to find a node with the right long-range link Chord/Tapestry: Each node has all log(n) links Viceroy: Each node has one long-range link out of: 1/2, 1/4, 1/8, 1/16 … A link to 1/2k distance points to a node with a link to 1/2(k+1) distance

Viceroy的拓扑结构 结点x的ID∈[0,1)，维护一个7项的路由表（即常数度为7）： 前两项是x在环上的前驱和后继 结点属于某层：l=x.level是在[1,logN]之间的随机正整数，N为结点总数 三、四项记录x到l+1层的两条连接 右下边：连接到距离x大约1/2l且最近的l+1层结点（clockwise-closest) 左下边：连接到离x最近的l+1层结点clockwise-closest) 第五项是上边：连接到离x最近的l-1层结点 后两项是与x同层且离x顺时针、逆时针方向最近的两个结点的连接，称为“同层环边”

A Butterfly Network

A Viceroy network

NLEVELi(x)：环上顺时针离x最近的i层结点 PLEVELi(x)：环上逆时针离x最近的i层结点 定义符号 NLEVELi(x)：环上顺时针离x最近的i层结点 PLEVELi(x)：环上逆时针离x最近的i层结点 NEXTONLEVER(x)：环上顺时针离x最近且与x同层的结点 PREVONLEVER(x)：环上逆时针离x最近且与x同层的结点 d(x,y)：环上顺时针从结点x到y的距离 qi(x,y)：环上顺时针方向位于(x,y)之间的i层结点数目 显然，x的左下边为NLEVELl+1(x)，右下边为NLEVELl+1(x+1/2^l)，上边为NLEVELl-1(x)

Viceroy实际上构建了三个“连接集” 主环(general ring)：通过前驱和后继连接形成 层环(level rings)：通过“同层环边”，每一层的结点被连成一个环 蝴蝶网(butterfly network)，任何一个l层的非叶结点通过两条“下边”连接到l+1层的两个结点，并通过“上边”连接到l-1层的一个结点 三个相互独立又相互联系的“连接集”，使得Viceroy既有经典的可变度P2P模型的对数定位效率，又有较好的容错性与自适应性

Viceroy查询 Initialization: set cur to x LOOKUP(x, y): Initialization: set cur to x Proceed to root: while cur.level > 1: cur = cur.parent Greedy search: if cur.id ≤ y < SUCC(cur).id, return cur. Otherwise, choose m from links of cur that minimize d(m, y), move to m and repeat. Demo: http://www.cs.huji.ac.il/labs/danss/anatt/viceroy.html

简化算法，查询函数为LOOKUP(x,y)，y为发起查询的结点，x为目的结点，查询函数要做的是找到沿顺时针方向离x最近(或相等)的结点 查询具体算法 简化算法，查询函数为LOOKUP(x,y)，y为发起查询的结点，x为目的结点，查询函数要做的是找到沿顺时针方向离x最近(或相等)的结点 查询算法分3步，cur表示当前结点，初始cur=y Lookup step1：Proceed to root(走到根) 若cur.level=1，跳到第二步 否则，若cur.up存在，令cur=cur.up，即往上层走，若cur.up不存在，令cur=cur.sucessor。该过程循环下去，直到走到最上层的根

Lookup step2：Traverse tree（遍历树，实质二分过程） 若d(cur,x)<1/2cur.level且cur.left存在，则令cur=cur.left，即往左下走 若d(cur.x)≥1/2cur.level且cur.right存在，则令cur= cur.right，即往右下走 如果上述两种情况的“下边”都不存在，或存在但超过了目的地x，则跳到第三步；如果“下边”存在且没有超过x，则重复第二步操作 Lookup step3：Traverse ring（遍历主环） 如果cur已是顺时针离x最近的结点，查询成功返回 否则，令cur=cur.successor或cur=cur.predecessor，哪个离x更近选哪个，重复该过程，直到查询成功

查询算法伪码

示例LOOKUP(x,y),x=0010，y=1110

Viceroy论文中证明：上述算法，前两步通常要走O(logN)跳，第三步可能要走O(log2N)跳 改进loopup step3：遍历层环和主环 如果同层环边cur.nextonlevel属于区间(cur,x)，则cur=cur.nextonlevel，如果cur.prevonlevel属于区间(cur,x)，则cur=cur.prevonlevel；如果都不满足，令cur= cur.successor或cur=cur.predecessor，哪个离x更近选哪个，重复该过程，直到查询成功

Viceroy层选择和加入结点算法 分布式网络只能估计结点总数N：结点x认为N=l/d(x,SUCC(x))，l是ID空间范围，分母是x到其后继的距离，即用空间尺度除以两个邻接结点间距离的平均值（不准确但合理） JOIN STEP1：生成nodeID，设为s JOIN STEP2：使用查询子程序找到s的后继，更新前驱后继，从而加入到主环 JOIN STEP3：从后继结点获得自己负责的数据 JOIN STEP4：根据估计结点数N随机选择自己的层，沿主环找到NEXTONLEVER(s)与PREVONLEVER(s)，更新层连接，加入层环 JOIN STEP5：沿主环找到左右下边，加入蝴蝶网

二、Koorde：整合Chord、de bruijn图的常数度P2P模型 结点度为常数2时，定位效率仍能达到O(logN) 结点度为O(logN)时，定位效率为O(logN/loglogN) Koorde使用一致性散列函数给结点和数据对象分配ID并组织在一个环上，数据对象由其后继结点负责，与Chord的原理相同

de Bruijn图 de Bruijn图将每个ID映射到一个de Bruijn结点 每个结点m有两条出边：一条指向结点2m(mod2b)，一条指向结点2m+1(mod2b)，b为ID位数，体现了Koorde的“常数度”属性 换个角度看，结点m指向的两个结点，一个是将m左移一位后最低位补0，另一个是将m左移一位后最低位补1

de bruijn路由 假设一个理想化的网络，ID空间中每个ID都对应一个结点，则图中共有2b个结点 设m为当前结点，k为目的结点，变量toShift初始为k，路由过程中不断被取首位bit，再左移，缩小m与k的差异 为到达k，每一步(递归调用lookup函数)m被拼接上toShift的首位bit值，成为t，然后再调用t的lookup函数来查找k(参数toShift被左移一位) 该过程递归下去，直到当前结点m=k

procedure m.lookup(k, toShift) if k=m then return(m) /* m owns k */ else{ t=m o topBit (toShift) /* o 表示拼接操作 */ return(t.lookup(k, toShift <<1)) } 上述过程中t离k越来越近，每一步两者之间差异的bit位数少1，因此，de Bruijn路由算法将在O(b)即O(logN)跳内到达目的地，而结点度为2

De Bruijn Graph Nodes are b-bit integers (b = log n) Node u has 2 neighbors (bit shifts): 2u mod 2b and 2u+1 mod 2b 100 110 1 1 000 010 101 111 1 1 1 1 1 001 011 1

De Bruijn Routing Shift in destination bits one by one b hops complete route Route from 000 to 110: 100 110 1 1 010 101 111 000 1 1 1 1 1 001 011 1

Koorde Idea Chord acts like a hypercube Koorde uses a deBruijn network Fingers flip one bit Degree log n (log n different flips) Diameter log n Koorde uses a deBruijn network Fingers shift in one bit Degree 2 (2 possible bits to shift in)

Koorde路由 de Bruijn算法是理想情形，实际网络中，ID空间中并非每个ID都对应一个实际结点，许多结点并不在网络中。ID空洞存在! 解决方案： 想象的路由：提供虚拟ID，仿真不存在的节点的路由 路由：虚拟ID引导de bruijn路由

Imaginary routing Node u holds two pointers Successor on ring One finger: predecessor of 2u (mod 2b) On sparse ring, is also predecessor of 2u+1 So handles both de Bruijn edges Node u “owns” all imaginary nodes between self and (real) successor Simulates de Bruijn routing from those imaginary nodes to others by forwarding to the others’ real owners

Code Procedure u.LOOKUP(k, toShift, i) if k Î (u,u.successor] then return u.successor /* as bucket for k */ else if i Î (u,u.successor] then /* i belongs to u; do de Bruijn hop */ return u.finger.LOOKUP(k, toshift áá 1, i ° topBit(toShift)) else /* i doesn’t belong to u; forward it */ return u.successor.LOOKUP(k, toShift, i) Initially call self.LOOKUP(k,k,self)

i为虚拟结点，引导着路由总体上按照de Bruijn路由来走，而d与successor则不断弥补m与i之间的差异 Koorde作者已经在论文中证明：该算法定位跳数最多为3b，即3logN，仍符合O(logN)的定位效率

True route tracks imaginary start finger (< double) imaginary(double) target successor

Koorde的容错性和自适应 de Bruijn指针可类比于Chord中的路由指针finger，只是用来加速定位，不影响定位正确性 一个de Bruijn指针的失效概率较高，还可以扩展为k度de Bruijn图，在增强容错性的同时提高定位效率到logkN跳

Variant: Koorde-K We used a binary de Bruijn Network Generalizes to other base K: 021 022 020 110 100 102 002 111 101 2 010 012 011 000 112 1 001 120 121 122

三、Cycloid：基于CCC的常数度P2P模型 Cycloid：圆环，其思想是用圆环去代替超立方体的每个结点，形成每个结点具有常数度的“带环立方体”CCC(cube-connected-cycles) 假设原立方体是d维的，则去取代原立方体每个结点的圆环也含有d个结点，且每个结点的度为3：其中两条边用来维护与环上前驱、后继结点的连接，第3条边用来维护与超立方体上其他环的连接(实际的Cycloid结点度为7，这3个CCC邻居是其中一部分) 采用与Pastry类似的定位、路由、自组织机制时，具有与Viceroy、Koorde一样好的性能

Pastry: hypercube connection How to maintain hypercube connection even after some nodes are absent?

CCC: Solution to Hypercube : 110 111 100 101 010 011 000 001 (000,0) (000,2) (000,1) F.P.Preparata, et al, The Cube-Connected Cycles: A Versatile Network for Parallel Computation, CACM, May 1981,

3维CCC结构

CCC: A new flexible connection Node number , represented as , Cubical neighbor Cyclic neighbor

CCC及Cycloid关键码分配 一个d维CCC是每个结点被用一个包含d个结点的圆环所取代的d维超立方体 每个结点用一个标识对(k, ad-1, ad-2…a0)来表示，其中k为“环标识”，a为“立方体标识”，每一位取值从0到d-1 Cycloid与Pastry都是基于超立方体结构的模型

Cycloid结点(4,101-1-1010)的路由表和叶集 NodeID(4,101-1-1010) Routing table cubical neighbor: (3,101-0-xxxx) cyclic neighbor: (3,101-1-1100) cyclic neighbor: (3,101-1-0011) Leaf Sets(half smaller, half larger) Inside Leaf Set(本地环) (3,101-1-1010) (6,101-1-1010) Outside Leaf Set(远程环) (7,101-1-1001) (6,101-1-1011)

每个Cycloid结点维护一个路由表和两个叶集：内叶集和外叶集，共7项，常数度为7 nodeID有8位说明基于8维CCC，x为通配符 路由表中维护一个“立方体邻居”和两个“环邻居” 内叶集维护结点在自己环上的前驱和后继结点 外叶集维护结点到“前驱环”和“后继环”上结点的指针（类似前驱、后驱的定义）

假设一个nodeID为(k, ad-1ad-2…a0)，其立方体邻居应该为k-1, ad-1ad-2…ak xx…x，x为通配符，ak表示ak比特取反；其环邻居应为k-1, bd-1bd-2…b0和k-1, cd-1cd-2…c0 ，前者是以k-1作为环标识，并且立方体标识比当前结点大但最接近的结点，后者是以k-1作为环标识，并且立方体标识比当前结点小但最接近的结点；如果nodeID中k=0，则该结点没有立方体邻居和环邻居，路由表为空 环标识k不仅代表了结点在环中的位置，更重要的是代表了路由表中立方体邻居与它的前缀匹配位数

对于Cycloid中每一个环上的结点而言，它们按环标识顺序串接起来，具有最大环标识的那个结点称为该环的“主结点” Cycloid路由表中，立方体邻居使得路由过程中可以从左到右逐步匹配目的ID的立方体标识，与Pastry前缀匹配路由很像；环邻居的作用在于匹配环标识；叶集的作用是辅助路由，帮助提高路由效率、检查路由终止条件并避免超过目的地

Cycloid结点(4,101-1-1010)的路由表和叶集结点

Cubical link vs. Cyclic link The nodes with the same cubical index are ordered by their cyclic index mod d on a local cycle. The left inside leaf set node points to the node’s predecessor and the right inside leaf set node points to the node’s successor in the local cycle. The largest cyclic index node in a local cycle is called the primary node of the local cycle. All local cycles are ordered by their cubical index mod 2^d on a large cycle. The left outside leaf set node points to the primary node in the node’s preceding remote cycle and the right outside leaf set node points to the primary node in the node’s succeeding remote cycle in the large cycle. The cubical links allow us to change cubical index from left to right, in the same left-to-right order as in Pastry. The cyclic links allow us to change the cyclic index. 由于存在大环，并以立方体的标识有序组织（实质是通过外叶集实现，即连接前趋环的主节点和后继环的主节点，外叶集的立方体标识是邻近的)；对于此大环，还通过环节点连接，环节点的立方体标识也是类似外叶集，只是环标识一个是k-1，一个是maximum。说明环节点有时可替代外叶集作类似的辅助路由。在这样的大环组织上是类似Chord的。不同的是，引入外长链－－立方体邻居，它使得有可能log(2^d)的降维，而要实现它，可采用环标识的定义来增强作用。

与Pastry类似，Cycloid也使用一致性安全散列函数将结点、数据对象映射到覆盖网中，给它们分配随机、唯一的ID，不同点在于Cycloid是一对: (环标识、立方体标识)，通常前者是将散列值模d，后者是将散列值模2^d 假设数据对象的objectID为k，它被分配到结点时，首先考虑立方体标识接近，再考虑环标识接近

Cycloid路由 定义MSDB(most significant different bit)为当前结点ID和目的ID不匹配的位数 第一步“上升”的目的是使当前结点的环标识k≥MSDB，由于k代表前缀匹配位数，因此这一步辅助地增加了当前结点ID和目的ID的匹配程度 第二步“下降”的目的是逐步匹配目的ID的立方体标识 第三步“遍历环”的目的是在叶集的局部范围内找到最终的目的结点

Routing Step 1：Ascending 当结点收到路由请求时，如果它的环标识k< MSDB，则将路由请求发给外叶集中某个结点。重复上述过程直到k≥MSDB Routing Step 2：Descending 如果k= MSDB，路由请求被发给当前结点的立方体邻居 如果k>MSDB，路由请求被发给当前结点的环邻居或內叶集结点，哪个最近选哪个 做完第二步以后，收到路由请求的结点还会从第一步做起 Routing Step 3：Traverse Cycle 如果目的ID在当前结点叶集范围内，则请求被发给叶集内最近的结点，重复该过程直至路由成功 立方体邻居和环邻居都是相对当前k环下的k-1环的立方体空间的邻近。在路由首先是解决立方体空间的邻近，因此，1,2步都是在立方体空间趋近（主要使用了立方体邻居和环邻居），并借助叶集进行跳跃.第三步是微调，实质属于前面2步。

注意红框及红线部分

Cycloid路由示例 （结点(0,0100)要发消息给(2,1111)）

Cycloid自组织 结点加入 新结点X首先联系“自举”结点A，通过A将以X为目的地的加入消息路由到离X最近的结点Z，Z的叶集复制给X 如果X和Z同属一个环，则Z的外叶集成为X的外叶集；如果Z是X的后继，则Z的前驱和Z本身成为X內叶集的左右结点，否则Z本身和Z的后继成为X內叶集的左右结点 如果X是其所在环中仅存的结点，则不与Z同环，此时X的內叶集左右结点只能是自己。如果Z所在环是X所在环的后继环，则Z的外叶集左结点和Z所在环的“主结点”分别成为X外叶集的左右结点；否则，Z所在环的主结点和Z的外叶集右结点分别成为X外叶集的左右结点

路由表的初始化采用“先本地后远程”的方法：X首先在自己所在环中按环标识降序搜索邻居；如果没找到，X就搜索自己的邻居环（使用外叶集），搜索方向取决于当前结点立方体标识的第k位：如果ak=1搜索方向是逆时针，否则顺时针，其目的在于增加找到邻居的可能性和速度 结点X初始化好自己的叶集与路由表后，首先通知內叶集结点更新状态，然后，如果X的外叶集结点是所在环的主结点，也通知更新。外叶集更新后，还要通知自己的內叶集结点更新状态…

结点离开 结点X离开之前，首先通知內叶集中的结点；如果X是所在环的主结点，则还要通知外叶集中的结点。外叶集中的结点收到消息后，需要通知它所在环的所有结点X将离开 上述工作，只能更新那些以X作为其叶集项的结点的状态，不能更新那些以X作为其路由表项的结点的状态，后者只能通过类似Chord的Stabilization自适应方法才能更新状态 08.10.21第11次课

结构化P2P网络的特点与分析 一、覆盖网拓扑结构 带弦环： 所有结点被组织在一个环上，环上只提供两种功能——取得当前结点的前驱和后继(单向环如Chord只提供后继)，只要后继关系正确，就能保证正确定位。为加速定位，加入“弦”，即维护一个路由表，指向环上离自己很远的结点。采用环形结构的P2P网络有Chord、Pastry、Kademlia、Cycloid

多维空间 超立方体（或Plaxton Mesh） 所有结点被组织在一个多维笛卡尔空间里（严格说是“多维环面(Torus)”结构），每个结点有自己在空间中的邻居，典型P2P网络是CAN， 超立方体（或Plaxton Mesh） 所有结点被组织在一个超立方体中，典型的有Tapestry、Pastry，覆盖网每层维护匹配nodeID不同长度前缀（或后缀）的结点；Cycloid的基础CCC则是基于超立方体改造

蝴蝶形 蝴蝶网中，每个结点有“层”，每层的结点通常维护两个下边、一个上边以及两个同层边，典型的有Viceroy，基于蝴蝶网，不过每个结点还保存一个前驱和一个后继从而组织成一个全局的环结构 de Bruijn图 每个节点有两条出边：一条指向结点2m(mod2b)，一条指向结点2m+1(mod2b)，b为ID位数。Koorde将de Bruijn图嵌入到Chord环中，提高了路由效率

CCC（cube-connected-cycles） 一个d维带环立方体CCC是每个结点被一个包含d个结点的圆环所取代的d维超立方体，因此，每个结点度为d。Cycloid是基于CCC结构的常数度P2P模型 其它形状（如跳表） 基于跳表SkipList的典型网络是SkipNet

二、分布式散列表 所有的结构化P2P网络都使用分布式散列表（DHT）来将结点、数据对象映射到覆盖网中 为使这种映射唯一、均匀、随机，分布式散列表都使用安全的一致性散列函数，其中最著名、也被大多数P2P系统采用的安全散列函数是SHA-1（安全散列算法），它能产生均匀、随机、与输入无关的160位散列值，并且散列值冲突的概率极小 理论上SHA-1等可以破解，但实际很困难，且在P2P网络中替换散列函数并不复杂

三、路由和定位 路由和定位的方式通常取决于两个因素 覆盖网拓扑结构、路由表结构 结构化P2P网络通常都维护一个比较小的路由表，采用分布式、局部性的贪心路由算法，逐步缩小当前结点与目的结点之间的ID差异 通常定位效率为O(logN)跳，并且能保证定位成功，单就覆盖网而言，此定位效率接近最优

典型路由方式 数值邻近路由 “数值”通常指结点ID值 路由过程中每一步，当前结点都在自己的路由表中选择与目的ID最邻近的结点作为下一跳 路由路径中每一跳的结点ID与目的ID的差距会越来越小，直至最接近目的ID的结点为止 广义上讲，几乎所有的结构化P2P路由算法都可以算“数值邻近”的，区别在于路由构造不同（如Chord使用指数间隔的Finger Table，Plaxton则是层次化路由表）或对于“邻近”的度量不同（如CAN的空间距离与Kademlia的异或距离）

逐位匹配路由 位置邻近路由 出自Plaxton，Tapestry、Pastry继承并扩展 采用层次化的路由表，每一步通常都与目的ID多匹配至少一位，其效率等价于ID位数，即O(logN) Koorde采用de Bruijn路由，每次将当前结点ID左移再拼接上未匹配的一位，实际也是逐位匹配路由 位置邻近路由 典型如CAN，每个结点的路由表记录自己在多维空间中的邻居，每次选择离目的结点最近的邻居作为下一跳，其定位效率等价于多维空间的直径 取d=logN时，即为O(logN)

层次路由 将结点组织到多个层次上，路由过程常常是先从低层爬到高层，再从高层走向底层 Viceroy采用蝴蝶网层次路由，通过路由表，首先沿“上边”走到“根”即1层结点，然后从1层结点出发沿“下左边”或“下右边”往下一层走，即从树根到叶子 SkipNet的NumericID路由也是层次化，首先查找“根环”，直到发现一个结点与目的结点NumericID匹配第一位，再通过该结点爬升到1层环，在其上查找匹配前两位的结点，依次进行直至结束 两者的结点都被组织到logN个层次，效率O(logN)

混合式路由 Chord、Pastry、Viceroy、Koorde、Cycloid都使用了环形路由作为基础，但结合了各自独特的路由方式 以Cycloid为例，使用类似Pastry的超立方体路由（逐位匹配路由），并结合了两种环形路由：主环上的环形路由以及每个小环上的环形路由 无论怎样结合，结构化P2P网络的路由效率保持在O(logN)

结点加入 四、动态结点算法（自适应、自组织） 几乎所有结构化P2P网络的结点加入算法为三步 Join Step1：新结点N以某种方式找到一个网络现存结点G，称为“自举结点” Join Step2：N通过G发送以N为目的地的消息，该消息最终到达ID与N最接近的结点Z，N从Z或者从消息路径的每个结点中获取路由表信息以及应由自己负责的数据，之后再做修正和优化 Join Step3：通知邻居结点更新路由表 结点加入开销较大，为O(logN)或O(log2N)

结点离开和失效 主动离开：通知邻居结点更新路由表并接管数据，可看作加入Join Step3的逆过程 结点失效：周期性检测路由表中的邻居；发现失效结点后进行路由表修复 对结点失效的处理是结构化P2P网络最大的开销所在

五、容错性与安全性 拓扑结构越严格、定位越准确，维护就越复杂，暴露给攻击者的弱点越多 从路由表设计上提高容错性 Chord使用“后继列表”取代单后继 Pastry既保存多个后继又保存多个前驱 Kademlia松散地保存邻居，仅根据收到的消息就能“捎带更新”路由表，不需要维护后继关系的正确性 CAN、Tapestry和Pastry，定位路径有多个选择，即使很多结点失效也能定位成功

结构化P2P网络的安全性难以完备，更复杂 应用系统中，CFS、OceanStore和PAST都通过散列方法保证数据完整性，尤其是OceanStore采用了层次化的AGUID、VGUID、BGUID来逐层认证 路由表的真实性：CFS中使用“现时”(Nonce)回馈的方法防止恶意结点伪造ID或虚报IP PAST使用“智能卡”提供安全性，由其产生和验证各种证书以及维护结点的“存储限额”。但“智能卡”发行机构的存在引入了集中式方法，破坏了P2P系统分布式的工作模式

覆盖网分割问题 结构化P2P网络比无结构P2P网络更容易被分割，且攻击者只要让某些关键性的结点失效，即可有效地阻碍整个网络的工作 目前没有公认的高效、实用解决方法 常数度P2P模型 在保持O(logN)路由效率的同时，每个结点只需维护常数个邻居，自适应开销小，但同时损失了容错性（修复困难，结点失效时效率下降明显）与安全性（易分割）

六、局部性 局部性的目的通常在于提高覆盖网与物理网的一致性，从而减小通信时延 CFS在其Chord层加入了服务器选择方法 Pastry通过每个结点维护“邻居集”来选择物理网上真正邻近的结点 Tapestry将数据对象分布式复制，在查询时帮助用户自动定位到很近的副本，从而在概率上减小时延 SkipNet基于“跳表”数据结构，提供路由、数据内容两个方面的语义局部性

七、增强机制：复制、缓存和分片 结构化P2P网络普遍采用“ID邻近复制”，即将数据对象复制到ID邻近的k个结点上，原因： 缓存也可以提高数据可用性，但主要目的是提高定位速度或获取速度。结构化P2P网络基本上使用“路径缓存”，其原因在于结构化P2P网络对象位置确定、拓扑结构严格，不同结点查询同一对象的路由路径往往会有重叠，而且越接近对象保存的结点，路由重叠的可能性越大

CFS中将每个文件分块，使用DHash中间层来分布和获取分块 OceanStore为提供持久性，采用“冗余编码”方法（erasure code）将数据对象分片存储在多个结点，只要获得部分分片即可重构原文件 PAST不进行文件分片，而是使用“副本转移”和“文件转移”的方法应付文件过大或者结点能力过低的情况

P2P网络各项属性总结 TTL为跳数限制 分类 P2P网络 拓扑结构 路由算法 路由效率 路由表项（结点度） 结点加入/离开的开销 容错性 安全性 混合式P2P网络 Napster 星型 服务器 O(1) 服务器单点 无 BitTorrent 一般 无结构P2P网络 Gnutella 随机图 洪泛法 TTL 很好 低 KaZaA 双层结构(随机图、星形) 超结点 O(1)+TTL 良好 eDonkey/ eMule Freenet 基于对象的洪泛法 HTL(Hops To Live) 匿名

N表示网络结点总数，d表示维度，B表示ID的进制， |L|表示叶集大小，|M|表示邻居集大小 分类 P2P网络 拓扑结构 路由算法 路由效率 路由表项（结点度） 结点加入/离开的开销 容错性 安全性 结构化P2P 网络 Chord 带弦环 数值邻近路由 O(logN) logN (logN)^2 一般 低 CAN 多维空间 位置邻近路由 2d 良好 Tapestry 超立方体 (Plaxton Mesh) 后缀匹配路由 O(logBN) B*logBN logBN Pastry (Mesh)、 环形 前缀匹配路由 B*logBN+|M|+|L| 很好 Kademlia 基于异或的带弦环

分类 P2P网络 拓扑结构 路由算法 路由效率 路由表项（结点度） 结点加入/离开的开销 容错性 安全性 结构化P2P 网络 SkipNet 跳表 数值邻近路由 前缀匹配路由 O(logN) 很好 局部可控 Viceroy 蝴蝶网 环形 蝴蝶路由 环形路由 7 logN 一般 低 Koorde de Bruijn图 de Bruijn路由 4 Cycloid CCC CCC路由

思考题 1、结构化路由表设计的本质是什么？你是否还能够想出新的实现结构？（常数度设计可借鉴新的空间结构） 2、SkipNet的数据内容的局部性是有启发性的一种尝试。类似的设计是否还可以提出来？ 3、为何结构化的极限在O(d)路由表项下的O(logN)查找效率？

课后阅读 Lua, E. K., J. Crowcroft, et al. (2005). A survey and comparison of peer-to-peer overlay network schemes, IEEE COMMUNICATIONS SURVEY AND TUTORIAL, MARCH 2004

Review III: [Gummadi et al.03] K. P. Gummadi, R. Gummadi, S. D. Gribble, S. Ratnasamy, S. Shenker and I. Stoica. The Impact of DHT Routing Geometry on Resilience and Proximity. In SIGCOMM 2003, pp. 381-394 [Ramabhadran et al.04] Sriram Ramabhadran, Sylvia Ratnasamy, Joseph M. Hellerstein, Scott Shenker. Brief Announcement: Prefix Hash Tree. In the 23rd ACM SIGACT-SIGOPS Symposium 2004, pp. 368-368. [Crespo et al.02] Arturo Crespo and Hector Garcia-Molina. Routing Indices For Peer-to-Peer Systems. In ICDCS 2002, pp. 23-32. 任选一，在下次上课前发到我邮箱zoufutai@sjtu.edu.cn

学期论文IDEA之二： 新的结构来实现结构化路由 新的数据结构或路由模型 新的路由表组织方法

附录：Skip List 1990才发明出来的新型数据结构，具有O(logN)查询效率。 Skip lists were invented in 1990 by William Pugh. He details how they work in Skip lists: a probabilistic alternative to balanced trees in Communications of the ACM, June 1990, 33(6) 668-676.

Consists of several levels. All keys appear in level 1 SkipList Structure Consists of several levels. All keys appear in level 1 Each level is a sorted list. If key x appears in level i, then it also appears in all levels below i Top Level 3 -1 37 1 21 1 Level 2 -1 7 37 71 21 -1 7 14 21 32 37 71 85 117 1 Level 1

More rules An element in level i points (via down pointer) to the element with the same key in the level below. In each level the keys -1 and 1 appear. (In our implementation, INT_MIN and INT_MAX Top points to the smallest element in the highest level. Top next-pointer Level 3 -1 37 1 21 Down-pointer Level 2 -1 7 37 71 1 21 -1 7 14 21 32 37 71 85 117 1 Level 1

An empty SkipList Top -1 1 Level 1

Finding an element with key x p=top While(1){ while (p->next->key < x ) p=p->next; If (p->down == NULL ) return p->next p=p->down ; } Observe that we return x, if exists, or succ(x) if x is not in the SkipList find(117), find(118) Top next-pointer Level 3 -1 37 1 21 down-pointer 7 37 71 1 Level 2 -1 21 -1 7 14 21 32 37 71 85 117 1 Level 1

Inserting new element X Determine k the number of levels in which x participates (explained later) Do find(x), and insert x to the appropriate places in the lowest k levels. (after the elements at which the search path turns down or terminates) Example - inserting 119. k=2 Top next-pointer Level 3 -1 37 1 21 Down-pointer 7 37 71 1 Level 2 -1 21 119 -1 7 14 21 32 37 71 85 1 Level 1

Inserting an element - cont. If k is larger than the current number of levels, add new levels (and update top) Example - inser(119) when k=4 119 1 -1 Top Level 3 -1 37 21 1 Level 2 -1 7 37 71 1 21 -1 7 14 21 32 37 71 85 1 Level 1

Determining k k - the number of levels at which an element x participate. Use a random function OurRnd() --- returns 1 or 0 (True/False) with equal probability. k=1 ; While( OurRnd() ) k++ ;

Deleteing a key x Find x in all the levels it participates, and delete it using the standard 'delete from a linked list' method. If one or more of the upper levels are empty, remove them (and update top) delete(71) Top next-pointer Level 3 -1 37 1 21 down-pointer 7 37 71 1 Level 2 -1 21 -1 7 14 21 32 37 71 85 117 1 Level 1