chord算法..ppt

chord算法..ppt

《chord算法..ppt》由会员分享，可在线阅读，更多相关《chord算法..ppt（56页珍藏版）》请在冰点文库上搜索。

2.P2P网络分类

（1）,非结构化P2P网络拓扑是任意的内容的存储位置与网络拓扑无关结构化P2P网络拓扑结构是有规律的每个节点都随机生成一个标识（ID）内容的存储位置与网络拓扑相关内容的存储位置与节点标识之间存在着映射关系,2.P2P网络分类

（2）,内容索引在P2P网络中，内容一般使用内容索引来表示,内容索引包括key和value两部分,其中key是内容的关键字,value是存放内容的实际位置,因此内容索引也表示为对内容索引表示电影夜宴可以从http:

/,2.1几种非结构化P2P,完全分布式的P2P网络不存在任何中心节点，peer通过网络泛洪查找key所对应的valuePeer之间直接建立连接下载内容基于目录服务器的P2P网络所有peer将索引发布到目录服务器上Peer通过目录服务器来查找key所对应的valuePeer之间直接建立连接下载内容层次P2P网络Peer根据能力的不同，例如是否拥有足够强的计算存储能力，是否拥有公网IP，分为超级节点和一般节点超级节点之间构成完全分布式的P2P网络超级节点和其所连接的一般节点构成基于目录服务器的P2P网络，其中超级节点具有目录服务器的功能,2.1.1完全分布式的P2P网络：

Gnutella

（1）,谁拥有xyz.mp3?

2.1.1完全分布式的P2P网络：

Gnutella

（2）,特点实现简单、不存在单点失效问题，但泛洪即全网广播查询消息的增加了网络负担，而且随着网络规模的增大，查询延时增加，因而不能保证查询结果,2.1.2基于目录服务器的P2P网络：

Napster

（1）,拥有xyz.mp3的节点,发布（key=xyz.mp3,value=1.2.3.4）,Insert（xyz.mp3,1.2.3.4）,AIP=1.2.3.4,目录服务器,索引发布,目录服务器上存储的是内容索引，而不是真正的内容！

2.1.2基于目录服务器的P2P网络：

Napster

（2）,内容定位,拥有xyz.mp3的节点,AIP=1.2.3.4,目录服务器,谁拥有xyz.mp3?

Search（xyz.mp3）1.2.3.4,B4.3.2.1,2.1.2基于目录服务器的P2P网络：

Napster（3）,内容下载,AIP=1.2.3.4,目录服务器,B4.3.2.1,直接从peer下载，不再需要经过目录服务器！

拥有xyz.mp3的节点,2.1.2基于目录服务器的P2P网络：

Napster（4）,特点索引发布和内容定位通过目录服务器进行,因此查询简单、高效，但是和客户/服务器模式一样，目录服务器存在瓶颈和单点失效问题，而且可扩展性差,2.1.3层次P2P网络：

KazaA

（1）,索引发布,拥有xyz.mp3的节点,Insert（xyz.mp3,1.2.3.4）,超级节点,1.2.3.4,超级节点上存放有其连接的一般节点的内容索引,2.1.3层次P2P网络：

KazaA

（2）,内容定位,谁拥有xyz.mp3?

超级节点,1.2.3.4,Search（xyz.mp3）1.2.3.4,拥有xyz.mp3的节点,2.1.3层次P2P网络：

KazaA（3）,内容下载,超级节点,1.2.3.4,拥有xyz.mp3的节点,直接从peer下载，不再需要经过超级节点！

2.1.3层次P2P网络：

KazaA（4）,特点考虑到了节点能力的不同，将其分为一般节点和超级节点，泛洪只在超级节点之间进行，与完全分布式的P2P网络相比，减少了泛洪开销当网络规模比较大时，随着超级节点数量的增加，泛洪的范围也将增大，因此查询时间具有不确定性,2.1.4几种非结构化P2P,总结非结构化P2P的内容下载采用完全在节点之间进行,不需要任何中心节点但是内容定位（也称为索引查询）或者采用泛洪,或者采用目录服务器的方式,缺乏有效的、可扩展的索引查询机制，不能满足大规模网络的需求,2.2几种结构化P2P,ChordPastryCANTapestry,基于分布式Hash表（DHT：

DistributedHashTable）,结构化P2P:

直接根据查询内容的关键字定位其索引的存放节点,2.2.1Hash函数概述,Hash函数可以根据给定的一段任意长的消息计算出一个固定长度的比特串，通常称为消息摘要（MD：

MessageDigest），一般用于消息的完整性检验。

Hash函数有以下特性：

给定P，易于计算出MD（P）只给出MD（P），几乎无法找出P无法找到两条具有同样消息摘要的不同消息Hash函数MD5：

消息摘要长度固定为128比特SHA-1：

消息摘要长度固定为160比特,2.2.1Hash函数应用于P2P的特性,唯一性：

不同的输入明文，对应着不同的输出摘要将节点IP地址的摘要作为节点ID，保证了节点ID在P2P环境下的唯一性SHA-1（“202.38.64.1”）=24b92cb1d2b81a47472a93d06af3d85a42e463eaSHA-1（“202.38.64.2”）=e1d9b25dee874b0c51db4c4ba7c9ae2b766fbf27,2.2.2DHT原理

（1）,将内容索引抽象为对K是内容关键字的Hash摘要K=Hash（key）V是存放内容的实际位置，例如节点IP地址等所有的对组成一张大的Hash表，因此该表存储了所有内容的信息每个节点都随机生成一个标识（ID），把Hash表分割成许多小块，按特定规则（即K和节点ID之间的映射关系）分布到网络中去，节点按这个规则在应用层上形成一个结构化的重叠网络给定查询内容的K值，可以根据K和节点ID之间的映射关系在重叠网络上找到相应的V值，从而获得存储文件的节点IP地址,2.2.2DHT原理

（2）,内容,内容关键字key,内容存储位置等信息value,内容索引,K=Hash（key）,提取,kv,Hash表,电影夜宴,电影、夜宴,http:

/,内容索引,K=hash（电影,夜宴）V=http:

/,2.2.2DHT原理（3）,kv,a.Hash表,b.分布式Hash表,规则?

N1,N48,N16,N32,N8,Chord、CAN、Tapestry、Pastry,在许多情况下,节点ID为节点IP地址的Hash摘要,2.2.2DHT原理（4）,插入（K1,V1）,（K1,V1）,查询（K1）,A128.1.2.3,B,K1=Hash（xyz.mp3）V1=128.1.2.3,xyz.mp3,C,索引发布和内容定位,2.2.2DHT原理（5）,定位（Locating）节点ID和其存放的对中的K存在着映射关系，因此可以由K获得存放该对的节点ID路由（Routing）在重叠网上根据节点ID进行路由，将查询消息最终发送到目的节点。

每个节点需要到其邻近节点的路由信息，包括节点ID、IP等网络拓扑拓扑结构由节点ID和其存放的对中的K之间的映射关系决定拓扑动态变化，需要处理节点加入/退出/失效的情况,在重叠网上节点始终由节点ID标识，并且根据ID进行路由,2.2.3Chord：

概述,UCBerkeley和MIT共同提出采用环形拓扑（Chord环）应用程序接口Insert（K,V）将对存在放到节点ID为Successor（K）上Lookup（K）根据K查询相应的VUpdate（K,new_V）根据K更新相应的VJoin（NID）节点加入Leave（）节点主动退出,2.2.3Chord：

Hash表分布规则,Hash算法SHA-1Hash节点IP地址m位节点ID（表示为NID）Hash内容关键字m位K（表示为KID）节点按ID从小到大顺序排列在一个逻辑环上存储在后继节点上Successor（K）：

从K开始顺时针方向距离K最近的节点,ID=hash（IP）=14,N56,K=hash（key）=54,N1,N8,N14,N21,N32,N38,N42,N48,N51,m=6,2.2.3Chord：

简单查询过程,每个节点仅维护其后继节点ID、IP地址等信息查询消息通过后继节点指针在圆环上传递直到查询消息中包含的K落在某节点ID和它的后继节点ID之间速度太慢O（N），N为网络中节点数,N56,K54,Lookup（K54）,N56,N1,N8,N14,N21,N32,N38,N42,N48,N51,m=6,2.2.3Chord：

指针表,N56,指针表,N8+1,N8+2,N8+4,N8+8,N8+16,N8+32,N14,N14,N14,N21,N32,N42,节点S的第i个指针successorn+2（i-1）,1im,2.2.3Chord：

基于指针表的扩展查找过程,指针表中有O（logN）个节点查询经过O（logN）跳,N56,K54,指针表,N8+1,N8+2,N8+4,N8+8,N8+16,N8+32,N14,N14,N14,N21,N32,N42,Lookup（K54）,指针表,N42+1,N42+2,N42+4,N42+8,N42+16,N42+32,N48,N48,N48,N51,N1,N14,2.2.3Chord：

网络波动（Churn）,Churn由节点的加入、退出或者失效所引起每个节点都周期性地运行探测协议来检测新加入节点或退出/失效节点，从而更新自己的指针表和指向后继节点的指针,2.2.3Chord：

节点加入,新节点N事先知道某个或者某些结点，并且通过这些节点初始化自己的指针表，也就是说，新节点N将要求已知的系统中某节点为它查找指针表中的各个表项在其它节点运行探测协议后，新节点N将被反映到相关节点的指针表和后继节点指针中新结点N的第一个后继结点将其维护的小于N节点的ID的所有K交给该节点维护；,2.2.3Chord：

节点退出/失效,当Chord中某个结点M退出/失效时，所有在指针表中包含该结点的结点将相应指针指向大于M结点ID的第一个有效结点即节点M的后继节点为了保证节点M的退出/失效不影响系统中正在进行的查询过程，每个Chord节点都维护一张包括r个最近后继节点的后继列表。

如果某个节点注意到它的后继节点失效了，它就用其后继列表中第一个正常节点替换失效节点,2.2.3Chord：

拓扑失配问题

（1）,O（LogN）逻辑跳数，但是每一逻辑跳可能跨越多个自治域，甚至是多个国家的网络重叠网络与物理网络脱节实际的寻路时延较大,2.2.3Chord：

拓扑失配问题

（2）,提取物理网络的拓扑信息改造Chord存在w个界标站点每个节点测量它到w个界标的RTT将RTT递增排列具有相同RTT序列的节点在物理网络上临近,2.2.3Chord：

总结,算法简单可扩展：

查询过程的通信开销和节点维护的状态随着系统总节点数增加成对数关系（O（logN）数量级）拓扑失配问题,2.2.4Pastry：

概述,Microsoft研究院和Rice大学共同提出考虑网络的本地性,解决物理网络和逻辑网络的拓扑失配的问题基于应用层定义的邻近性度量,例如IP路由跳数、地理距离、往返延时等节点ID分布采用环形结构,2.2.4Pastry：

Hash表分布规则,Hash算法SHA-1Hash节点IP地址m位节点ID（表示为NID）Hash内容关键字m位K（表示为KID）NID和KID是以2b为基的数,共有m/b个数位b是一个配置参数,一般为4节点按ID从小到大顺序排列在一个逻辑环上存储在NID与KID数值最接近的节点上,m=8,2m-10,b=2,2.2.4Pastry：

节点维护状态表

（1）,路由表R路由表包括log2bN（m/b）行，每行包括2b-1个表项路由表第n行与节点ID的前n个数位相同，但是第n+1个数位不同，也称为n数位前缀相同路由表中的每项包含节点ID，IP地址等根据邻近性度量选择距离本节点近的节点邻居节点集M邻居节点集包含|M|个在邻近性度量上最接近于本节点的节点，|M|为2b或者2X2b邻居节点集通常不用于路由查询消息，而是用来维护本地性叶子节点集L叶子节点集包含|L|个节点ID最接近本节点的节点，其中|L|/2个节点的ID大于本节点，|L|/2个ID小于本节点，|L|为2b或者2X2b,2.2.4Pastry：

节点维护状态表

（2）,NodeID10233102,Leafset,RoutingTable,Neighborhoodset,0,02212102,1,22301203,31203203,11301233,12230203,13021022,2,10031203,10132102,10323302,3,3,10222302,10200230,10211302,10230322,10231000,10232121,10233001,10233120,10233232,1,0,2,13021022,10200230,11301233,31301233,02212102,22301203,31203203,33213321,10233033,10233021,10233120,10233122,10233001,10233000,10233230,10233232,SMALLER,LARGER,节点ID最接近本节点的节点,b=2，因此节点ID的基数为4（16bits）,m/b行,依据邻近性度量最接近本节点的节点,每行2b-1个表项,第n行的前n个数位与本节点相同相同前缀下一数位其它,当前节点的第n个数位,第m列表项的下一数位为m,没有合适节点的表项为空,b=2,m=16,2.2.4Pastry：

查询过程,当一个K为D的查询消息到达节点A节点A首先看D是否在当前节点的叶子节点集中，如果是，则查询消息直接被转发到目的节点，也就是叶子节点集中节点ID与D数值最接近的那个节点（有可能就是当前节点），否则进行下一步在路由表中查找与D具有更长相同前缀的表项（至少比本节点多一个数位），如果该表项不为空，则将查询消息直接转发到该节点，否则进行下一步例如路由D=0629的查询消息53240748060506200629将消息转发到具有相同前缀,但是节点ID在数值上更接近D的节点。

除非查询消息已经到达目的节点，否则该节点一定位于叶子节点集中。

例如路由D=0629的查询消息532407480605060906200629,路由查询消息的逻辑跳数：

O（log2bN）,2.2.4Pastry：

节点状态表和查询,节点路由表R中的每项与本节点具有相同的n数位长度前缀，但是下一个数位不同例如，对于节点N0201：

N-:

N1?

N2?

N3?

N0:

N00?

N01?

N03?

N02:

N021?

N022?

N023?

N020:

N0200,N0202,N0203当有多个节点时，根据邻近性度量选择最近的节点维持了较好的本地性,N0002,N0201,N2001,N1113,N2120,N2222,N3001,N3033,N3200,m=8,2m-10,b=2,N0122,N0212,N0221,N0233,Routingtable,K2120,N0322,2.2.4Pastry：

节点加入

（1）,初始化状态表新节点开始时知道一个根据邻近性度量接近自己的节点A节点A可以通过使用扩展环IP组播等机制自动定位，或者由系统管理员通过其它手段获得新节点通过运行SHA-1算法计算自己的IP地址（或者publickey）的摘要得到节点ID为X节点X向节点A发送K为X的join消息，Pastry将该消息路由到节点ID在数值上最接近X的节点Z接收到join消息的节点，包括A、Z，以及A到Z路径上所有的节点将发送它们的状态表给X，X检查这些信息，并且可能从其它的节点请求状态，然后节点根据下面的过程初始化状态表:

由于A与X在邻近性度量上接近,所以使用A的邻居节点集来初始化X的邻居节点集由于Z的节点ID与X最相近,因此使用Z的叶子节点集来初始化X的叶子节点集X将join消息经过的第i个节点的路由表的第i行作为自己路由表的第i行Join消息经过的第i个节点与X的前i个数位相同向其它相关节点通告自己的到来新节点向邻居节点集、叶子节点集和路由表中的每个节点发送自己的状态，以更新这些节点的状态表,2.2.4Pastry：

节点加入

（2）,X0629,节点加入,Join消息,0629sroutingtable,2.2.4Pastry：

节点退出/失效,叶子节点集L中的节点失效：

联系L中失效节点一边具有最大索引的存活节点（即节点ID最小或者最大的存活节点），并且请求该节点的叶子节点集除非|L|/2个节点同时失效，否恢复过程始终是有效的失效检测：

和叶子节点集中的节点周期性交互存活消息路由表R中的节点失效：

如果失效节点对应的表项为Rdl（第l行第d列），则联系同一行中的Ril,id所指向的存活节点并且获取该节点的Rdl表项，如果l行中没有存活节点，则从下一行选择一个节点失效检测：

和路由表中的节点联系（例如发送查询消息）如果无反应则检测到节点失效邻居节点表M中的节点失效：

向M中的其它节点请求邻居节点表，检查每个新发现节点的距离（根据邻近性度量），然后更新自己的邻居节点表失效检测：

和邻居节点表中的每个节点周期性的联系，以确认节点存活,2.2.4Pastry：

路由本地性,根据邻近性度量为消息选择一条好的路由邻近性度量包括IP路由跳数、地理距离、往返延时等应用层为每个节点提供了根据邻近性度量确定到其它节点距离的功能，例如traceroute等新节点加入过程保持了本地性首先：

A必定与X相接近A路由表中第0行表项A0与A相接近，而A与X接近，因此X0可作为X0由于节点路由表中的下一行节点的可选择集合指数递减,因此B1中的节点到B的距离要比A到比的距离大得多（B在A0中）,因此B1可作为X1,依此类推,C2可作为X2X向路由表和邻居节点集中的每个节点请求状态,并且使用更近的节点来更新自己的状态由于邻居节点集根据邻近性度量而不是节点ID前缀来维护节点信息,因此在这个过程中发挥重要作用实践中Pastry保持了良好的本地性伸展度（Stretch）大约为23伸展度（Stretch）：

逻辑网络的路由延时/IP网络的单播路由延时,2.2.4Pastry：

总结,逻辑网络路由跳数O（log2bN）路由表开销log2bN*（2b-1）路由本地性：

状态表（路由表、邻居节点集、叶子节点集）中的表项选择在邻近性度量上与本节点相近的节点稳健性：

只有在|L|/2个叶子节点完全失效时才会路由失败,2.2.5CAN：

概述,ContentAddressableNetwork，内容寻址网络UCBerkeley提出节点ID分布分布在d维笛卡尔坐标空间坐标空间完全是逻辑的，和任何物理坐标没有任何关系,2.2.5CAN：

Hash表分布规则,每个节点都维护d维笛卡尔坐标空间中的一块区域新加入节点时划分坐标空间对于每个，通过Hash函数将K映射到坐标空间中的某点P，存储在维护该点所在区域的节点上在每一维都对k进行hash运算,1,d=2,2.2.5CAN：

查询过程,节点在坐标路由表中只需维护它直接邻居的信息，包括邻居的IP地址及其维护的区域两个节点互为邻居是指：

在d维坐标空间中，两个节点维护的区域在d1维的坐标上有重叠而在剩下的一维坐标上相互邻接，例如图中节点A的邻居为（N,S,E,W）查询消息沿着坐标空间从发起请求的点到目的点之间的一条路径转发查询消息路由到能够减少坐标空间距离的邻居节点有多条路径可以选择，在路由时能够绕开失效节点,W,N,A,S,E,B,d=2,2.2.5CAN：

节点加入,新加入的节点在CAN中查找已经存在的节点，即bootstrap节点找到可以划分空间的一个节点进行空间划分bootstrap节点提供系统中有效的并且可以划分区间的节点A，新节点向节点A发送一个加入消息，该消息经过CAN的路由机制发送到A通知被划分的节点的邻居节点进行路由表更新节点F的邻居表是由节点A的邻居节点的子集合，再加上节点A构成节点A刷新它的邻居节点空间，以删除那些现在已不是邻居节点的节点新节点F发送刷新信息更新邻居节点的坐标路由表,bootstrap,d=2,A,F,B,C,D,E,G,C,2.2.5CAN：

节点退出/失效

（1）,失效检测每个节点周期性向邻居节点发送更新消息，如果消息中包括自身的区域范围、它的邻居列表以及这些邻居节点负责的区域范围。

如果多次没有接收到某个邻居的更新消息，那么节点就认为这个邻居失效了，这时将启动接管机制,2.2.5CAN：

节点退出/失效

（2）,接管机制当节点离开CAN时，必须保证它的区域被系统中剩余的节点接管，也即分配给其他仍然在系统中的节点。

一般是由某个邻居节点来接管这个区域和所有的索引数据（K，V）对接管邻居节点的选择如果某个邻居节点负责的区域可以和离开节点负责的区域合并形成一个大的区域，那么将由这个邻居节点执行合并操作否则该区域将交给其邻居节点中区域最小的节点负责失效节点的每个邻居独立地启动一个时钟，每个时钟大小都和相应节点负责的区域面积成比例。

如果时钟超时，节点将向失效节点的所有邻居节点发送接管消息，该消息中包括它自己的区域面积信息。

当某个节点接收到接管消息后，如果它的区域面积比发出消息的节点大，那么它将取消接管操作。

否则它将发出自己的取代消息,2.2.5CAN：

节点退出/失效（3）,A,B,B,B,B,节点失效后的区间合并,节点失效后由面积最小的邻居节点接管,2.2.5CAN：

负载均衡问题

（1）,负载均衡节点负担的面积越大，负载就越重假设整个坐标空间的面积是S，整个空间中共有n个节点，那么理想情况的均衡划分的结果应该是每个节点的面积都是V=S/n采用原始CAN节点加入划分机制，只有43%的节点面积为V,2.2.5CAN：

负载均衡问题

（2）,解决方案组播法寻找重负荷节点新加入系统的节点首先通过引导节点在全网范围内泛洪查找面积最大的节点，对其空间进行划分逻辑结构自适应调整法通过目的节点向所有四周邻居进行泛洪，获取面积最大的节点，划分此节点空间缺点：

需要泛洪消息，网络开销太大,2.2.5CAN：

总结,可扩展性：

如果d维坐标空间划分成N个相等的区域，则每个节点维护2d个邻居节点的信息平均路由跳数（dN1/d）/4增加维数可以减少在逻辑上的路由跳数，但是增加了节点维护的状态信息节点增加时节点维护的状态信息不变，而路由长度只是以O（N1/d）的数量级增长，可扩展性好稳健性：

一个节点的一个或几个邻居节点失效时，它依然可以沿着有效的邻居节点进行寻路负载均衡问题拓扑失配问题,2.2.6基于DHT的结构化P2P比较,2.2.7几种结构化P2P,总结完全分布式，不存在任何中心节点直接根据查询内容的关键字定位其索引的存放节点，查找具有确定性节点失效时表现出很好的健壮性可扩展性好，系统开销小自动配置，不需要手工干预就可自动把新加入节点合并到系统中几个需要研究的问题模糊查找问题网络波动（Churn）问题路由本地性问题负载均衡问题安全问题,