第十一章 应用层网络.ppt

《第十一章 应用层网络.ppt》由会员分享，可在线阅读，更多相关《第十一章 应用层网络.ppt（149页珍藏版）》请在三一文库上搜索。

1、第十一章 应用层网络,应用层网络,对等网络 应用层组播 弹性重叠网,应用层网络(ON): Overlay Networks，也称为重叠网络 对等网络(P2P): Peer-to-Peer Networks 弹性重叠网络(RON): resilient Overlay Networks,应用层网络,对等网络 应用层组播 弹性重叠网,Resources,综述 罗杰文，Peer-To-Peer 综述，http:/ Chord I. Stoica, R. Morris, D. Karger, F. Kaashoek, H.Balakrishnan. Chord: A Scalable Peer-to-

2、Peer Lookup Service for Internet Applications. In Proceedings ACM Sigcomm 2001, San Diego, CA, Aug. 2001. Pastry A. Rowstron and P. Druschel, “Pastry: Scalable, distributed objectlocation and routing for large-scale peer-to-peer systems,” in IFIP/ACMInternational Conference on Distributed Systems Pl

3、atforms (Middleware), 2001 CAN Sylvia Rathasamy, Paul Francis, Mark Handley, Richard Karp and Scott Shenker.A Scalable Content-Addressable Network.In ACM SIGCOMM01, 2001 Tapestry B. Y. Zhao, J. D. Kubiatowicz, and A. D. Joseph, “Tapestry: An infrastructure for fault-tolerant wide-area location and r

4、outing,“ UC Berkeley, Tech. Rep. UCB/CSD-01-1141, April 2001.,对等网络(P2P: Peer-to-Peer),1. 概述 P2P的引入背景，P2P的定义，P2P的特征， 2. P2P网络的分类 非结构化P2P 结构化P2P 3. 几种非结构化P2P网络 完全分布式的P2P网络、基于目录服务器的P2P网络、层次P2P网络 4. 几种结构化P2P网络 Hash函数、基于分布式hash表的P2P网络原理 Chord、 Pastry、CAN、Tapestry,1.1 P2P引入背景(1),传统客户/服务器模式的不足,瓶颈问题：服务器的带宽、

5、存储、计算等资源受限，容易成为网络瓶颈 单点失效问题：服务器是整个网络的中心，失效将会导致服务无法访问,资源定义为网络节点的计算、存储等能力,1.1 P2P引入背景(2),网络边缘闲置资源利用的需求,随着计算技术的发展,位于Internet边缘的接入设备(也就是网络的最终用户)拥有 越来越强的计算、存储等能力，传统的网络结构无法有效地利用这些资源,资源定义为网络节点的计算、存储等能力,1.1 P2P引入背景(3),P2P网络 服务器功能分布化 分布式网络结构,客户/服务器模式的不足 (瓶颈问题, 单点失效问题) 2.网络边缘闲置资源的利用需求,1.2 P2P网络结构,完全分布式的网络结构 将服

6、务器的功能分布到各个网络中的各个节点，充分利用这些节点的计算、存储、带宽等资源 无中心服务器，网络中的节点既是客户端又是服务器,P2P网络中的节点也叫做对等节点(Peer),1.3 P2P的定义,P2P通信模式中各方都具有相同的能力，其中任何一方都可以发起一个通信会话。在P2P通信过程中，每个通信节点同时具有服务器和客户端的功能。 P2P网络中的节点间采用P2P通信模式，它是构筑在现有网络基础设施上的一个分布式的重叠网络（Overlay Network）,1.4 P2P重叠网,P2P重叠网络构筑在已有的Internet基础设施网络之上，也称为应用层网络,P2P网络 (overlay Netwo

7、rk),1.5 P2P网络的特征,P2P网络是一个应用层网络，一般由网络边缘节点构成 网络的扩展性好，但节点可随意加入退出，因而动态性强 资源分布在各个节点中，而不是集中在一个服务器上进行管理 节点之间可直接建立连接，交互共享资源,1.6 P2P网络需要解决的问题,定位(Locating)：找到资源的存放位置 路由(Routing)：将消息发送到目的节点 网络拓扑：节点的组织方式，例如物理网络有星型拓扑、网状拓扑等，而对于P2P网络来说是拓扑是一个逻辑上概念，和具体的物理连接无关,P2P网络的最终目标是要实现资源共享，这些资源包括计算、存储等， 其中内容存储类应用是P2P目前最主要的应用,物理

8、网络拓扑,P2P逻辑拓扑,2. P2P网络分类(1),非结构化P2P 网络拓扑是任意的 内容的存储位置与网络拓扑无关 结构化P2P 网络拓扑结构是有规律的 每个节点都随机生成一个标识(ID) 内容的存储位置与网络拓扑相关 内容的存储位置与节点标识之间存在着映射关系,2. P2P网络分类(2),内容索引 在P2P网络中，内容一般使用内容索引来表示,内容索引包括key和value两部分,其中key是内容的关键字,value是存放内容的实际位置,因此内容索引也表示为对 内容索引表示电影夜宴可以从http:/ P2P网络中实现内容共享的步骤 索引发布：告诉别人拥有或者知道的内容信息 内容定位：查找到内

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

10、络，其中超级节点具有目录服务器的功能,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),A IP=1.2.3.4,目录服务器,索引发布,目录服务器上存储的是内

11、容索引，而不是真正的内容！,2.1.2 基于目录服务器的P2P网络： Napster(2),内容定位,拥有xyz.mp3的节点,A IP=1.2.3.4,目录服务器,谁拥有xyz.mp3?,Search(xyz.mp3) 1.2.3.4,B 4.3.2.1,2.1.2 基于目录服务器的P2P网络： Napster(3),内容下载,A IP=1.2.3.4,目录服务器,B 4.3.2.1,直接从peer下载，不再需要经过目录服务器！,拥有xyz.mp3的节点,2.1.2 基于目录服务器的P2P网络： Napster(4),特点 索引发布和内容定位通过目录服务器进行,因此查询简单、高效，但是和客户

12、/服务器模式一样，目录服务器存在瓶颈和单点失效问题，而且可扩展性差,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下载，不再需要经

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

14、分布式Hash表 (DHT： Distributed Hash Table ),结构化P2P: 直接根据查询内容的关键字定位其索引的存放节点,2.2.1 Hash函数概述,Hash函数可以根据给定的一段任意长的消息计算出一个固定长度的比特串，通常称为消息摘要（MD：Message Digest），一般用于消息的完整性检验。 Hash函数有以下特性： 给定 P，易于计算出 MD（P） 只给出 MD（P），几乎无法找出 P 无法找到两条具有同样消息摘要的不同消息 Hash函数 MD5：消息摘要长度固定为128比特 SHA-1：消息摘要长度固定为160比特,2.2.1 Hash函数应用于P2P的特性

15、,唯一性：不同的输入明文，对应着不同的输出摘要 将节点IP地址的摘要作为节点ID，保证了节点ID在P2P环境下的唯一性 SHA-1(“202.38.64.1”) =24b92cb1d2b81a47472a93d06af3d85a42e463ea SHA-1(“202.38.64.2”) =e1d9b25dee874b0c51db4c4ba7c9ae2b766fbf27,2.2.2 DHT原理(1),将内容索引抽象为对 K是内容关键字的Hash摘要 K = Hash(key) V是存放内容的实际位置，例如节点IP地址等 所有的对组成一张大的Hash表，因此该表存储了所有内容的信息 每个节点都随机

16、生成一个标识(ID)，把Hash表分割成许多小块，按特定规则(即K和节点ID之间的映射关系)分布到网络中去，节点按这个规则在应用层上形成一个结构化的重叠网络 给定查询内容的K值，可以根据K和节点ID之间的映射关系在重叠网络上找到相应的V值，从而获得存储文件的节点IP地址,2.2.2 DHT原理(2),内容,内容关键字key,内容存储位置等信息 value,内容索引,K=Hash(key),提取,k v,Hash表,电影 夜宴,电影、夜宴,http:/ yeyan.avi,内容索引,K=hash(电影, 夜宴) V = http:/ yeyan.avi,2.2.2 DHT原理(3),k v,a.

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

18、发送到目的节点。每个节点需要到其邻近节点的路由信息，包括节点ID、IP等 网络拓扑 拓扑结构由节点ID和其存放的对中的K之间的映射关系决定 拓扑动态变化，需要处理节点加入/退出/失效的情况,在重叠网上节点始终由节点ID标识，并且根据ID进行路由,2.2.3 Chord：概述,UC Berkeley和MIT共同提出 采用环形拓扑(Chord环) 应用程序接口 Insert(K, V) 将对存在放到节点ID为Successor(K)上 Lookup(K) 根据K查询相应的V Update(K, new_V) 根据K更新相应的V Join(NID) 节点加入 Leave() 节点主动退出,2.2.3

19、 Chord：Hash表分布规则,Hash算法SHA-1 Hash节点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.3 Chord：简单查询过程,每个节点仅维护其后继节点ID、IP地址等信息 查询消息通过后继节点指针在圆环上传递 直到查询消息中包含的K落在某节点ID和它的后继节点ID之间 速

20、度太慢 O(N)，N为网络中节点数,N56,K54,Lookup(K54),N56,N1,N8,N14,N21,N32,N38,N42,N48,N51,m=6,2.2.3 Chord：指针表,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.3 Chord：基于指针表的扩展查找过程,指针表中有O (log N)个节点 查询经过O (log N)跳,N56,K54,指针表,N8+1,N8+2,N8+4,N8+8,N8+16,N8+32,N14,N1

21、4,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.3 Chord：网络波动(Churn),Churn由节点的加入、退出或者失效所引起 每个节点都周期性地运行探测协议来检测新加入节点或退出/失效节点，从而更新自己的指针表和指向后继节点的指针,2.2.3 Chord：节点加入,新节点N事先知道某个或者某些结点，并且通过这些节点初始化自己的指针表，也就是说，新节点N将要求已知的系统中某节点为它查找指针表中的各个表项 在其它节点运行探测协议后，新节点N将被

22、反映到相关节点的指针表和后继节点指针中 新结点N的第一个后继结点将其维护的小于N节点的ID的所有K交给该节点维护；,2.2.3 Chord：节点退出/失效,当Chord中某个结点M退出/失效时，所有在指针表中包含该结点的结点将相应指针指向大于M结点ID的第一个有效结点即节点M的后继节点 为了保证节点M的退出/失效不影响系统中正在进行的查询过程，每个Chord节点都维护一张包括r个最近后继节点的后继列表。如果某个节点注意到它的后继节点失效了，它就用其后继列表中第一个正常节点替换失效节点,2.2.3 Chord：拓扑失配问题(1),O(LogN)逻辑跳数，但是每一逻辑跳可能跨越多个自治域，甚至是多

23、个国家的网络 重叠网络与物理网络脱节 实际的寻路时延较大,2.2.3 Chord：拓扑失配问题(2),提取物理网络的拓扑信息改造Chord 存在w个界标站点 每个节点测量它到w个界标的RTT 将RTT递增排列 具有相同RTT序列的节点在物理网络上临近,2.2.3 Chord：总结,算法简单 可扩展：查询过程的通信开销和节点维护的状态随着系统总节点数增加成对数关系(O (log N)数量级) 拓扑失配问题,2.2.4 Pastry：概述,Microsoft研究院和Rice大学共同提出 考虑网络的本地性,解决物理网络和逻辑网络的拓扑失配的问题 基于应用层定义的邻近性度量,例如IP路由跳数、地理距离

24、、往返延时等 节点ID分布采用环形结构,2.2.4 Pastry： Hash表分布规则,Hash算法SHA-1 Hash节点IP地址m位节点ID(表示为NID) Hash内容关键字m位K(表示为KID) NID和KID是以2b为基的数,共有m/b个数位 b是一个配置参数,一般为4 节点按ID从小到大顺序排列在一个逻辑环上 存储在NID与KID数值最接近的节点上,m=8,2m-1 0,b=2,2.2.4 Pastry：节点维护状态表(1),路由表R 路由表包括 log2b N (m/b)行，每行包括2b -1个表项 路由表第n行与节点ID的前n个数位相同，但是第n+1个数位不同，也称为n数位前缀

25、相同 路由表中的每项包含节点ID，IP地址等 根据邻近性度量选择距离本节点近的节点 邻居节点集M 邻居节点集包含|M|个在邻近性度量上最接近于本节点的节点，|M|为2b或者2X2b 邻居节点集通常不用于路由查询消息，而是用来维护本地性 叶子节点集L 叶子节点集包含|L|个节点ID最接近本节点的节点，其中|L|/2个节点的ID大于本节点，|L|/2个ID小于本节点，|L|为2b或者2X2b,2.2.4 Pastry：节点维护状态表(2),Node ID 10233102,Leaf set,Routing Table,Neighborhood set,0,02212102,1,22301203,3

26、1203203,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,

27、SMALLER,LARGER ,节点ID最接近 本节点的节点,b=2，因此节点ID的 基数为4 (16 bits),m/b 行,依据邻近性度量最 接近本节点的节点,每行2b-1个表项,第n行的前n个数 位与本节点相同 相同前缀 下一数位 其它 ,当前节点的第n个数位,第m列表项的 下一数位为m,没有合适节点 的表项为空,b=2,m=16,2.2.4 Pastry：查询过程,当一个K为D的查询消息到达节点A 节点A首先看D是否在当前节点的叶子节点集中，如果是，则查询消息直接被转发到目的节点，也就是叶子节点集中节点ID与D数值最接近的那个节点(有可能就是当前节点)，否则进行下一步 在路由表中查找与

28、D具有更长相同前缀的表项(至少比本节点多一个数位)，如果该表项不为空，则将查询消息直接转发到该节点，否则进行下一步 例如路由D= 0629的查询消息 5324 0748 0605 0620 0629 将消息转发到具有相同前缀,但是节点ID在数值上更接近D的节点。除非查询消息已经到达目的节点，否则该节点一定位于叶子节点集中。 例如路由D=0629的查询消息 5324 0748 0605 0609 0620 0629,路由查询消息的逻辑跳数： O(log2b N),2.2.4 Pastry：节点状态表和查询,节点路由表R中的每项与本节点具有相同的n数位长度前缀，但是下一个数位不同 例如，对于节点N

29、0201： 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-1 0,b=2,N0122,N0212,N0221,N0233,Routing table,K2120,N0322,2.2.4 Pastry：节点加入(1),初始化状态表 新节点开始时知道一个根据邻近性度量接近自己的节点

30、A 节点A可以通过使用扩展环IP组播等机制自动定位，或者由系统管理员通过其它手段获得 新节点通过运行SHA-1算法计算自己的IP地址(或者public key)的摘要得到节点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的叶子节

31、点集 X将join消息经过的第i个节点的路由表的第i行作为自己路由表的第i行 Join消息经过的第i个节点与X的前i个数位相同 向其它相关节点通告自己的到来 新节点向邻居节点集、叶子节点集和路由表中的每个节点发送自己的状态，以更新这些节点的状态表,2.2.4 Pastry：节点加入(2),X 0629,节点加入,Join消息,0629s routing table,2.2.4 Pastry：节点退出/失效,叶子节点集L中的节点失效：联系L中失效节点一边具有最大索引的存活节点(即节点ID最小或者最大的存活节点)，并且请求该节点的叶子节点集 除非|L|/2个节点同时失效，否恢复过程始终是有效的 失

32、效检测：和叶子节点集中的节点周期性交互存活消息 路由表R中的节点失效：如果失效节点对应的表项为Rdl (第l行第d列) ，则联系同一行中的Ril, id所指向的存活节点并且获取该节点的Rdl表项，如果l行中没有存活节点，则从下一行选择一个节点 失效检测：和路由表中的节点联系(例如发送查询消息)如果无反应则检测到节点失效 邻居节点表M中的节点失效：向M中的其它节点请求邻居节点表，检查每个新发现节点的距离(根据邻近性度量)，然后更新自己的邻居节点表 失效检测：和邻居节点表中的每个节点周期性的联系，以确认节点存活,2.2.4 Pastry：路由本地性,根据邻近性度量为消息选择一条好的路由 邻近性度量

33、包括IP路由跳数、地理距离、往返延时等 应用层为每个节点提供了根据邻近性度量确定到其它节点距离的功能，例如traceroute等 新节点加入过程保持了本地性 首先：A必定与X相接近 A路由表中第0行表项A0与A相接近，而A与X接近，因此X0可作为X0 由于节点路由表中的下一行节点的可选择集合指数递减,因此B1中的节点到B的距离要比A到比的距离大得多(B在A0中),因此B1可作为X1,依此类推,C2可作为X2 X向路由表和邻居节点集中的每个节点请求状态,并且使用更近的节点来更新自己的状态 由于邻居节点集根据邻近性度量而不是节点ID前缀来维护节点信息,因此在这个过程中发挥重要作用 实践中Pastr

34、y保持了良好的本地性 伸展度(Stretch)大约为23 伸展度(Stretch)：逻辑网络的路由延时/IP网络的单播路由延时,2.2.4 Pastry：总结,逻辑网络路由跳数O(log2b N) 路由表开销log2b N *(2b -1) 路由本地性：状态表(路由表、邻居节点集、叶子节点集)中的表项选择在邻近性度量上与本节点相近的节点 稳健性：只有在|L|/2个叶子节点完全失效时才会路由失败,2.2.5 CAN：概述,Content Addressable Network，内容寻址网络 UC Berkeley提出 节点ID分布分布在d维笛卡尔坐标空间 坐标空间完全是逻辑的，和任何物理坐标没有

35、任何关系,2.2.5 CAN：Hash表分布规则,每个节点都维护d维笛卡尔坐标空间中的一块区域 新加入节点时划分坐标空间 对于每个，通过Hash函数将K映射到坐标空间中的某点P，存储在维护该点所在区域的节点上 在每一维都对k进行hash运算,1,d=2,2.2.5 CAN：查询过程,节点在坐标路由表中只需维护它直接邻居的信息，包括邻居的IP地址及其维护的区域 两个节点互为邻居是指：在d维坐标空间中，两个节点维护的区域在d1维的坐标上有重叠而在剩下的一维坐标上相互邻接，例如图中节点A的邻居为(N, S, E, W) 查询消息沿着坐标空间从发起请求的点到目的点之间的一条路径转发 查询消息路由到能够

36、减少坐标空间距离的邻居节点 有多条路径可以选择，在路由时能够绕开失效节点,W,N,A,S,E,B,d=2,2.2.5 CAN：节点加入,新加入的节点在CAN中查找已经存在的节点，即bootstrap节点 找到可以划分空间的一个节点进行空间划分 bootstrap节点提供系统中有效的并且可以划分区间的节点A，新节点向节点A发送一个加入消息，该消息经过CAN的路由机制发送到A 通知被划分的节点的邻居节点进行路由表更新 节点F的邻居表是由节点A的邻居节点的子集合，再加上节点A构成 节点A刷新它的邻居节点空间，以删除那些现在已不是邻居节点的节点 新节点F发送刷新信息更新邻居节点的坐标路由表,boots

37、trap,d=2,A,F,B,C,D,E,G,C,2.2.5 CAN：节点退出/失效(1),失效检测 每个节点周期性向邻居节点发送更新消息，如果消息中包括自身的区域范围、它的邻居列表以及这些邻居节点负责的区域范围。 如果多次没有接收到某个邻居的更新消息，那么节点就认为这个邻居失效了，这时将启动接管机制,2.2.5 CAN：节点退出/失效(2),接管机制 当节点离开CAN时，必须保证它的区域被系统中剩余的节点接管，也即分配给其他仍然在系统中的节点。一般是由某个邻居节点来接管这个区域和所有的索引数据（K，V）对 接管邻居节点的选择 如果某个邻居节点负责的区域可以和离开节点负责的区域合并形成一个大的

38、区域，那么将由这个邻居节点执行合并操作 否则该区域将交给其邻居节点中区域最小的节点负责 失效节点的每个邻居独立地启动一个时钟，每个时钟大小都和相应节点负责的区域面积成比例。如果时钟超时，节点将向失效节点的所有邻居节点发送接管消息，该消息中包括它自己的区域面积信息。当某个节点接收到接管消息后，如果它的区域面积比发出消息的节点大，那么它将取消接管操作。否则它将发出自己的取代消息,2.2.5 CAN：节点退出/失效(3),A,B,B,B,B,节点失效后的区间合并,节点失效后由面积最小的邻居节点接管,2.2.5 CAN：负载均衡问题(1),负载均衡 节点负担的面积越大，负载就越重 假设整个坐标空间的面

39、积是S ，整个空间中共有n个节点，那么理想情况的均衡划分的结果应该是每个节点的面积都是V=S/n 采用原始CAN节点加入划分机制，只有43%的节点面积为V,2.2.5 CAN：负载均衡问题(2),解决方案 组播法寻找重负荷节点 新加入系统的节点首先通过引导节点在全网范围内泛洪查找面积最大的节点，对其空间进行划分 逻辑结构自适应调整法 通过目的节点向所有四周邻居进行泛洪，获取面积最大的节点，划分此节点空间 缺点：需要泛洪消息，网络开销太大,2.2.5 CAN：总结,可扩展性：如果d维坐标空间划分成N个相等的区域，则 每个节点维护2d个邻居节点的信息 平均路由跳数(dN1/d)/4 增加维数可以减

40、少在逻辑上的路由跳数，但是增加了节点维护的状态信息 节点增加时节点维护的状态信息不变，而路由长度只是以O(N1/d)的数量级增长，可扩展性好 稳健性：一个节点的一个或几个邻居节点失效时，它依然可以沿着有效的邻居节点进行寻路 负载均衡问题 拓扑失配问题,2.2.6 基于DHT的结构化P2P比较,2.2.7 几种结构化P2P,总结 完全分布式，不存在任何中心节点 直接根据查询内容的关键字定位其索引的存放节点，查找具有确定性 节点失效时表现出很好的健壮性 可扩展性好，系统开销小 自动配置，不需要手工干预就可自动把新加入节点合并到系统中 几个需要研究的问题 模糊查找问题 网络波动(Churn)问题 路

41、由本地性问题 负载均衡问题 安全问题 ,2.2.8 基于DHT的P2P应用,DHT接口API DHT层次体系结构 OpenDHT Indirect Internet Infrastructure (i3),DHT接口API,必须的接口 Inset(K, V)：将存储到合适的节点上 Lookup(K) ：获取K所对应的V，例如节点IP地址 支持各种应用 K不需要任何语义上的意义 V与应用相关 具体的API在底层的DHT重叠网络中实现,Lookup(K),Return Value,DHT层次体系结构,DHT层,例如Chord，Pastry，CAN等 (自组织的重叠网络),基于DHT的P2P应用,F

42、ile sharing CFS, PAST, Event notification Scribe Naming systems ChordDNS, Query and indexing Kademlia, Communication primitives I3, .,OpenDHT：概述,OpenDHT一个公共的DHT服务平台 htpp:/opendht.org 基于Bamboo DHT，改写自Pastry 设计原则：易于部署，易于使用 客户端不需要运行DHT软件，而是通过OpenDHT服务平台获取所需的服务，从而实现基于DHT的P2P应用 客户端接口API Put(K, V, t)：将发布到

43、OpenDHT网络，t为有效期 Get(K)：根据K从OpenDHT网络获取对,OpenDHT：体系结构,Indirect Internet Infrastructure (i3),传统的Internet提供端到端通信模型 通信一般在固定主机之间进行 发送主机知道接收主机的IP地址，将分组直接发送给接收主机 间接通信模型(i3) 接收主机位置不固定，可能移动 Mobility 发送主机不知道接收主机的标识 Multicast, Anycast,i3原理(1),http:/i3.cs.berkeley.edu 利用DHT网络提供的索引发布和查询，具有 稳健性 高效性 可扩展性 DHT网络实现可以

44、使Chord、Pastry、CAN、Tapestry等 DHT网络中的每一个节点都为i3服务器 i3中节点通信过程 每个分组都带有一个标识，接收主机根据标识来获取相应的分组 接收主机在DHT网络中插入trigger (id, R), 其中id为希望接收的分组的标识，R是接收主机的IP地址， (id, R)根据id存储到DHT网络中相应的服务器节点（例如对于chord，(id, R)存储在id的后继节点即节点ID大于id的第一个节点上） 发送主机发送标识为id的分组，该分组以id为k，根据DHT路由查询算法在网络中转发，如果接收到该分组的服务器注册了标识为id的trigger，则将分组发送给tr

45、igger中指定的接收主机IP,i3原理(2),DHT网络,DHT网络,a. 接收主机R在DHT网络中插入trigger(id, R),b. 发送主机向DHT网络发送分组(id, data)，该分组被DHT网络中的服务器转发给相应的接收主机,I3原理(3),应用程序接口API sendPacket(p)：发送分组 insertTrigger(t)：插入trigger removeTrigger(t)：删除trigger 基于OpenDHT的实现 需要扩展put/get接口以实现服务器转发功能,Sean Rhea, Brighten Godfrey, et al., OpenDHT: A Pub

46、lic DHT Service and Its Uses, Proceedings of ACM SIGCOMM 2005, August 2005,i3应用：移动,Mobility,移动对于发送节点完全透明，接收节点只需更新相应的trigger,i3应用：组播,组播接收节点向DHT网络插入具有相同标识的trigger,i3应用：大规模组播,使用层次触发器构造组播树,以减轻服务器的负担 具有相同标识的trigger的数量代表在服务器上分组的复制因子 需要分布式算法来构造和维护trigger的层次,LAKSHMINARAYANAN, K., RAO, et al Flexible and rob

47、ust large scale multicast using i3. Tech. Rep. CS-02-1187, University of California-Berkeley, 2002.,应用层网络,对等网络 应用层组播 弹性重叠网,Resources,章淼,吴建平, “应用层组播研究综述“, 清华大学计算机系网络研究所，2003 Yeo C K,Lee B S,Er M H.A, “A survey of application level multicast techniques“, Computer Communications,2004 ESM Y Chu, S Rao,

48、S Seshan, H Zhang, R Vedantham, Enabling conferencing applications on the internet using an overlay muilticast architecture, In Proceedings of ACM SIGCOMM Computer Communication Review, 2001 HMTP B Zhang, S Jamin, L Zhang, Host Multicast: A Framework for Delivering Multicast To End Users, in Proceedings of IEEE INFOCOM, 2002 NICE S Banerjee, B Bhattacharjee, C Kommareddy, Scalable Application Layer Multicast, in Proceedings of A