第十一章 应用层网络.ppt

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

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

2、net Applications.In Proceedings ACM Sigcomm 2001,San Diego,CA,Aug.2001.PastryA.Rowstron and P.Druschel,“Pastry:Scalable,distributed objectlocation and routing for large-scale peer-to-peer systems,”in IFIP/ACMInternational Conference on Distributed Systems Platforms(Middleware),2001 CANSylvia Rathasa

3、my,Paul Francis,Mark Handley,Richard Karp and Scott Shenker.A Scalable Content-Addressable Network.In ACM SIGCOMM01,2001 TapestryB.Y.Zhao,J.D.Kubiatowicz,and A.D.Joseph,Tapestry:An infrastructure for fault-tolerant wide-area location and routing,UC Berkeley,Tech.Rep.UCB/CSD-01-1141,April 2001.,对等网络(

4、P2P:Peer-to-Peer),1.概述P2P的引入背景，P2P的定义，P2P的特征，2.P2P网络的分类非结构化P2P结构化P2P3.几种非结构化P2P网络完全分布式的P2P网络、基于目录服务器的P2P网络、层次P2P网络4.几种结构化P2P网络Hash函数、基于分布式hash表的P2P网络原理Chord、Pastry、CAN、Tapestry,1.1 P2P引入背景(1),传统客户/服务器模式的不足,瓶颈问题：服务器的带宽、存储、计算等资源受限，容易成为网络瓶颈单点失效问题：服务器是整个网络的中心，失效将会导致服务无法访问,资源定义为网络节点的计算、存储等能力,1.1 P2P引入背景(

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

6、P2P的定义,P2P通信模式中各方都具有相同的能力，其中任何一方都可以发起一个通信会话。在P2P通信过程中，每个通信节点同时具有服务器和客户端的功能。P2P网络中的节点间采用P2P通信模式，它是构筑在现有网络基础设施上的一个分布式的重叠网络（Overlay Network）,1.4 P2P重叠网,P2P重叠网络构筑在已有的Internet基础设施网络之上，也称为应用层网络,P2P网络(overlay Network),1.5 P2P网络的特征,P2P网络是一个应用层网络，一般由网络边缘节点构成网络的扩展性好，但节点可随意加入退出，因而动态性强资源分布在各个节点中，而不是集中在一个服务器上进行管

7、理节点之间可直接建立连接，交互共享资源,1.6 P2P网络需要解决的问题,定位(Locating)：找到资源的存放位置路由(Routing)：将消息发送到目的节点网络拓扑：节点的组织方式，例如物理网络有星型拓扑、网状拓扑等，而对于P2P网络来说是拓扑是一个逻辑上概念，和具体的物理连接无关,P2P网络的最终目标是要实现资源共享，这些资源包括计算、存储等，其中内容存储类应用是P2P目前最主要的应用,物理网络拓扑,P2P逻辑拓扑,2.P2P网络分类(1),非结构化P2P网络拓扑是任意的内容的存储位置与网络拓扑无关结构化P2P网络拓扑结构是有规律的每个节点都随机生成一个标识(ID)内容的存储位置与网络

8、拓扑相关内容的存储位置与节点标识之间存在着映射关系,2.P2P网络分类(2),内容索引在P2P网络中，内容一般使用内容索引来表示,内容索引包括key和value两部分,其中key是内容的关键字,value是存放内容的实际位置,因此内容索引也表示为对内容索引表示电影夜宴可以从http:/,2.1 几种非结构化P2P,完全分布式的P2P网络不存在任何中心节点，peer通过网络泛洪查找key所对应的valuePeer之间直接建立连接下载内容基于目录服务器的P2P网络所有peer将索引发布到目录服务器上Peer通过目录服务器来查找key所对应的valuePeer之间直接建立连接下载内容层次P2P网络P

9、eer根据能力的不同，例如是否拥有足够强的计算存储能力，是否拥有公网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的节点,发布

10、(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下载，不再需要经过目录服务器！,拥有x

11、yz.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的节

12、点,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的内容下载采用完全在节点之间进行,不需要任何中心节点但是内容定位(也称为索引查询)或者采用泛洪,或者采用目录服务器的方式,缺乏有效

13、的、可扩展的索引查询机制，不能满足大规模网络的需求,2.2 几种结构化P2P,ChordPastryCANTapestry,基于分布式Hash表(DHT：Distributed Hash Table),结构化P2P:直接根据查询内容的关键字定位其索引的存放节点,2.2.1 Hash函数概述,Hash函数可以根据给定的一段任意长的消息计算出一个固定长度的比特串，通常称为消息摘要（MD：Message Digest），一般用于消息的完整性检验。Hash函数有以下特性：给定 P，易于计算出 MD（P）只给出 MD（P），几乎无法找出 P无法找到两条具有同样消息摘要的不同消息Hash函数MD5：消息摘

14、要长度固定为128比特SHA-1：消息摘要长度固定为160比特,2.2.1 Hash函数应用于P2P的特性,唯一性：不同的输入明文，对应着不同的输出摘要将节点IP地址的摘要作为节点ID，保证了节点ID在P2P环境下的唯一性SHA-1(“202.38.64.1”)=24b92cb1d2b81a47472a93d06af3d85a42e463eaSHA-1(“202.38.64.2”)=e1d9b25dee874b0c51db4c4ba7c9ae2b766fbf27,2.2.2 DHT原理(1),将内容索引抽象为对K是内容关键字的Hash摘要K=Hash(key)V是存放内容的实际位置，例如节点I

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

16、HT原理(3),k v,a.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),A128.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进行路由，将

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

18、表分布规则,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.3 Chord：简单查询过程,每个节点仅维护其后继节点ID、IP地址等信息查询消息通过后继节点指针在圆环上传递直到查询消息中包含的K落在某节点ID和它的后继节点ID之间速度太慢 O(N)，N为网络中节点数,N

19、56,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,N14,N14,N21,N32,N42,Looku

20、p(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将被反映到相关节点的指针表和后继节点指针中 新结点N

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

22、大,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路由跳数、地理距离、往返延时等节点ID分布采用环形结构,2.2.4 Pastry：Hash

23、表分布规则,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.4 Pastry：节点维护状态表(1),路由表R路由表包括 log2b N(m/b)行，每行包括2b-1个表项 路由表第n行与节点ID的前n个数位相同，但是第n+1个数位不同，也称为n数位前缀相同路由表中的每项包含节点ID，IP地址等根据邻近性度量选择距离本节点近的节点邻居节点集M邻居节

24、点集包含|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,31203203,11301233,12230203,13021022,2,10031203,10132102

25、,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(16 bits),m

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

27、9的查询消息 5324 0748 0605 0620 0629将消息转发到具有相同前缀,但是节点ID在数值上更接近D的节点。除非查询消息已经到达目的节点，否则该节点一定位于叶子节点集中。例如路由D=0629的查询消息5324 0748 0605 0609 0620 0629,路由查询消息的逻辑跳数：O(log2b N),2.2.4 Pastry：节点状态表和查询,节点路由表R中的每项与本节点具有相同的n数位长度前缀，但是下一个数位不同例如，对于节点N0201：N-:N1?,N2?,N3?N0:N00?,N01?,N03?N02:N021?,N022?,N023?N020:N0200,N0202

28、,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.4 Pastry：节点加入(1),初始化状态表新节点开始时知道一个根据邻近性度量接近自己的节点A节点A可以通过使用扩展环IP组播等机制自动定位，或者由系统管理员通过其它手段获得新节点通过运行SHA-1算法计算自己的IP地址(或者public key)的摘要得到节点ID为X节点X向节

29、点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个数位相同向其它相关节点通告自己的到来新节点向邻居节点集、叶子节点集和路由表中的每个节点

30、发送自己的状态，以更新这些节点的状态表,2.2.4 Pastry：节点加入(2),X0629,节点加入,Join消息,0629s routing table,2.2.4 Pastry：节点退出/失效,叶子节点集L中的节点失效：联系L中失效节点一边具有最大索引的存活节点(即节点ID最小或者最大的存活节点)，并且请求该节点的叶子节点集除非|L|/2个节点同时失效，否恢复过程始终是有效的失效检测：和叶子节点集中的节点周期性交互存活消息路由表R中的节点失效：如果失效节点对应的表项为Rdl(第l行第d列)，则联系同一行中的Ril,id所指向的存活节点并且获取该节点的Rdl表项，如果l行中没有存活节点，则

31、从下一行选择一个节点失效检测：和路由表中的节点联系(例如发送查询消息)如果无反应则检测到节点失效邻居节点表M中的节点失效：向M中的其它节点请求邻居节点表，检查每个新发现节点的距离(根据邻近性度量)，然后更新自己的邻居节点表失效检测：和邻居节点表中的每个节点周期性的联系，以确认节点存活,2.2.4 Pastry：路由本地性,根据邻近性度量为消息选择一条好的路由邻近性度量包括IP路由跳数、地理距离、往返延时等应用层为每个节点提供了根据邻近性度量确定到其它节点距离的功能，例如traceroute等新节点加入过程保持了本地性首先：A必定与X相接近A路由表中第0行表项A0与A相接近，而A与X接近，因此X

32、0可作为X0由于节点路由表中的下一行节点的可选择集合指数递减,因此B1中的节点到B的距离要比A到比的距离大得多(B在A0中),因此B1可作为X1,依此类推,C2可作为X2X向路由表和邻居节点集中的每个节点请求状态,并且使用更近的节点来更新自己的状态由于邻居节点集根据邻近性度量而不是节点ID前缀来维护节点信息,因此在这个过程中发挥重要作用实践中Pastry保持了良好的本地性伸展度(Stretch)大约为23伸展度(Stretch)：逻辑网络的路由延时/IP网络的单播路由延时,2.2.4 Pastry：总结,逻辑网络路由跳数O(log2b N)路由表开销log2b N*(2b-1)路由本地性：状态

33、表(路由表、邻居节点集、叶子节点集)中的表项选择在邻近性度量上与本节点相近的节点稳健性：只有在|L|/2个叶子节点完全失效时才会路由失败,2.2.5 CAN：概述,Content Addressable Network，内容寻址网络UC Berkeley提出节点ID分布分布在d维笛卡尔坐标空间坐标空间完全是逻辑的，和任何物理坐标没有任何关系,2.2.5 CAN：Hash表分布规则,每个节点都维护d维笛卡尔坐标空间中的一块区域新加入节点时划分坐标空间对于每个，通过Hash函数将K映射到坐标空间中的某点P，存储在维护该点所在区域的节点上在每一维都对k进行hash运算,1,d=2,2.2.5 CAN

34、：查询过程,节点在坐标路由表中只需维护它直接邻居的信息，包括邻居的IP地址及其维护的区域两个节点互为邻居是指：在d维坐标空间中，两个节点维护的区域在d1维的坐标上有重叠而在剩下的一维坐标上相互邻接，例如图中节点A的邻居为(N,S,E,W)查询消息沿着坐标空间从发起请求的点到目的点之间的一条路径转发查询消息路由到能够减少坐标空间距离的邻居节点有多条路径可以选择，在路由时能够绕开失效节点,W,N,A,S,E,B,d=2,2.2.5 CAN：节点加入,新加入的节点在CAN中查找已经存在的节点，即bootstrap节点找到可以划分空间的一个节点进行空间划分bootstrap节点提供系统中有效的并且可以

35、划分区间的节点A，新节点向节点A发送一个加入消息，该消息经过CAN的路由机制发送到A 通知被划分的节点的邻居节点进行路由表更新节点F的邻居表是由节点A的邻居节点的子集合，再加上节点A构成节点A刷新它的邻居节点空间，以删除那些现在已不是邻居节点的节点 新节点F发送刷新信息更新邻居节点的坐标路由表,bootstrap,d=2,A,F,B,C,D,E,G,C,2.2.5 CAN：节点退出/失效(1),失效检测每个节点周期性向邻居节点发送更新消息，如果消息中包括自身的区域范围、它的邻居列表以及这些邻居节点负责的区域范围。如果多次没有接收到某个邻居的更新消息，那么节点就认为这个邻居失效了，这时将启动接管

36、机制,2.2.5 CAN：节点退出/失效(2),接管机制当节点离开CAN时，必须保证它的区域被系统中剩余的节点接管，也即分配给其他仍然在系统中的节点。一般是由某个邻居节点来接管这个区域和所有的索引数据（K，V）对接管邻居节点的选择如果某个邻居节点负责的区域可以和离开节点负责的区域合并形成一个大的区域，那么将由这个邻居节点执行合并操作 否则该区域将交给其邻居节点中区域最小的节点负责 失效节点的每个邻居独立地启动一个时钟，每个时钟大小都和相应节点负责的区域面积成比例。如果时钟超时，节点将向失效节点的所有邻居节点发送接管消息，该消息中包括它自己的区域面积信息。当某个节点接收到接管消息后，如果它的区域

37、面积比发出消息的节点大，那么它将取消接管操作。否则它将发出自己的取代消息,2.2.5 CAN：节点退出/失效(3),A,B,B,B,B,节点失效后的区间合并,节点失效后由面积最小的邻居节点接管,2.2.5 CAN：负载均衡问题(1),负载均衡节点负担的面积越大，负载就越重假设整个坐标空间的面积是S，整个空间中共有n个节点，那么理想情况的均衡划分的结果应该是每个节点的面积都是V=S/n采用原始CAN节点加入划分机制，只有43%的节点面积为V,2.2.5 CAN：负载均衡问题(2),解决方案组播法寻找重负荷节点新加入系统的节点首先通过引导节点在全网范围内泛洪查找面积最大的节点，对其空间进行划分逻辑

38、结构自适应调整法通过目的节点向所有四周邻居进行泛洪，获取面积最大的节点，划分此节点空间缺点：需要泛洪消息，网络开销太大,2.2.5 CAN：总结,可扩展性：如果d维坐标空间划分成N个相等的区域，则每个节点维护2d个邻居节点的信息平均路由跳数(dN1/d)/4 增加维数可以减少在逻辑上的路由跳数，但是增加了节点维护的状态信息节点增加时节点维护的状态信息不变，而路由长度只是以O(N1/d)的数量级增长，可扩展性好稳健性：一个节点的一个或几个邻居节点失效时，它依然可以沿着有效的邻居节点进行寻路负载均衡问题拓扑失配问题,2.2.6 基于DHT的结构化P2P比较,2.2.7 几种结构化P2P,总结完全分

39、布式，不存在任何中心节点直接根据查询内容的关键字定位其索引的存放节点，查找具有确定性节点失效时表现出很好的健壮性 可扩展性好，系统开销小自动配置，不需要手工干预就可自动把新加入节点合并到系统中几个需要研究的问题模糊查找问题网络波动(Churn)问题路由本地性问题负载均衡问题安全问题,2.2.8 基于DHT的P2P应用,DHT接口APIDHT层次体系结构OpenDHTIndirect Internet Infrastructure(i3),DHT接口API,必须的接口Inset(K,V)：将存储到合适的节点上Lookup(K)：获取K所对应的V，例如节点IP地址支持各种应用K不需要任何语义上的意

40、义V与应用相关具体的API在底层的DHT重叠网络中实现,Lookup(K),Return Value,DHT层次体系结构,DHT层,例如Chord，Pastry，CAN等(自组织的重叠网络),基于DHT的P2P应用,File sharing CFS,PAST,Event notification ScribeNaming systems ChordDNS,Query and indexing Kademlia,Communication primitives I3,.,OpenDHT：概述,OpenDHT一个公共的DHT服务平台htpp:/opendht.org基于Bamboo DHT，改写自

41、Pastry设计原则：易于部署，易于使用客户端不需要运行DHT软件，而是通过OpenDHT服务平台获取所需的服务，从而实现基于DHT的P2P应用客户端接口APIPut(K,V,t)：将发布到OpenDHT网络，t为有效期Get(K)：根据K从OpenDHT网络获取对,OpenDHT：体系结构,Indirect Internet Infrastructure(i3),传统的Internet提供端到端通信模型通信一般在固定主机之间进行发送主机知道接收主机的IP地址，将分组直接发送给接收主机间接通信模型(i3)接收主机位置不固定，可能移动Mobility发送主机不知道接收主机的标识Multicast

42、,Anycast,i3原理(1),http:/i3.cs.berkeley.edu利用DHT网络提供的索引发布和查询，具有稳健性高效性可扩展性DHT网络实现可以使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

43、的分组，该分组以id为k，根据DHT路由查询算法在网络中转发，如果接收到该分组的服务器注册了标识为id的trigger，则将分组发送给trigger中指定的接收主机IP,i3原理(2),DHT网络,DHT网络,a.接收主机R在DHT网络中插入trigger(id,R),b.发送主机向DHT网络发送分组(id,data)，该分组被DHT网络中的服务器转发给相应的接收主机,I3原理(3),应用程序接口APIsendPacket(p)：发送分组insertTrigger(t)：插入triggerremoveTrigger(t)：删除trigger基于OpenDHT的实现需要扩展put/get接口以实

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

45、层次,LAKSHMINARAYANAN,K.,RAO,et al.Flexible and robust 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 Comm

46、unications,2004ESMY Chu,S Rao,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 HMTPB Zhang,S Jamin,L Zhang,Host Multicast:A Framework for Delivering Multicast To E

47、nd Users,in Proceedings of IEEE INFOCOM,2002 NICES Banerjee,B Bhattacharjee,C Kommareddy,Scalable Application Layer Multicast,in Proceedings of ACM SIGCOMM 2002;,应用层组播,IP组播回顾应用层组播概述应用层组播技术应用层组播评价指标应用层组播方案举例总结,应用层组播,1.IP组播回顾IP组播概述IP组播体系结构IP组播的局限性2.应用层组播概述3.应用层组播技术4.应用层组播评价指标5.应用层组播方案举例6.总结,1.1 IP组播概述

48、,组播(Multicast)也称为多播，发送分组给一群感兴趣的接收者，包括1对多、多对多模式可用于会议电视，分布式计算，视频转播，网络游戏，讨论组等应用IP组播由网络层来复制和转发分组给接收者IP组播采用特定的地址格式,IPv6组播地址格式,IPv4组播地址格式,单播和组播,单播：发送端向每个接收端都发送单播分组，路由器只转发分组,组播：发送端只发送一份分组，路由器根据需要复制并且向接收端转发分组,组播与单播相比，有效地降低了网络负载,1.2 IP组播体系结构,组播路由协议，如DVMRP，PIM功能：构造连接拥有组成员的组播路由器的组播树，以路由转发组播分组,组播管理协议，IGMP功能：组成员

49、的加入和退出,路由器之间,主机和路由器之间,IP组播需要网络即路由器支持,组播树,基于源的组播树最短路径树，每个源都会通过最有效的路径向每个接收端发送分组路由器必须跟踪所有的源，需要更多的存储资源共享组播树组播分组先被发送到一个公共点(也称为集合点)，再从该点发送到各个接收端所需的存储资源较少，但是并不总能使用最短路径,1.4 IP组播的局限性,可扩展性问题路由器需要为每个组维护状态，有时甚至需要为组播组中的每个源维护状态组播地址不易实现聚合，路由器的路由表和转发表需要为每个组播组维护一个表项难以支持高层功能IP组播提供尽力(best-effort)多点传送业务，终端系统负责处理高层功能在IP

50、组播中实现可靠性和拥塞控制非常复杂试图用统一的组播模型来适应所有的应用缺乏有效的网络管理和计费模型,IP组播大规模部署困难而缓慢应用层（或者终端系统end-system）组播的出现,导致,应用层组播,1.IP组播回顾2.应用层组播概述应用层组播概念应用层组播优势应用层组播应用3.应用层组播技术4.应用层组播评价指标5.应用层组播方案举例6.总结,2.1 应用层组播概念,Application-Layer(or end-system)Multicast终端系统通过重叠网进行通信，由终端节点来进行分组的复制和转发即组播功能底层网络只提供单播功能,IP组播,应用层组播,IP组播的带宽利用率最高，但是