《Internet拓扑结构与IP多播.ppt》由会员分享，可在线阅读，更多相关《Internet拓扑结构与IP多播.ppt（56页珍藏版）》请在三一办公上搜索。
1、Internet拓扑结构与IP多播,程远 2002.9,提纲,Internet 拓扑结构Internet 的构成网络结构实例隐藏的规律：power lawIP多播多播定义、概念及应用多播协议多播可扩展性的讨论,Internet 拓扑结构？,Internet是研究对象。”You cant resolve the traffic jam problem of a city without looking at the street layout.”对网络的感性认识，解答一些基本的问题：Internet的规模？中国网络的基本情况？Cernet的基本情况？Internet拓扑图节点度数概率分布：pow
2、er law,Internet:ASes+BGP,Internet由大约13000个自治系统(Autonomous System)构成自治系统：处于一个机构管理之下的若干网络和路由器构成了自治系统。每一个自治系统有一个16比特的自治系统号，全球唯一。其中1-32767可供分配，32768 64511暂时保留，64512 65534用于私有AS（类似于IP地址中的内网地址）边界网关协议(Border Gateway Protocol，BGP)：自治系统之间的路由协议。该协议的基本功能是与其它自治系统交换网络可达性信息,这种可达性信息包含了通往目标所要穿越的自治系统记录,利用这些信息,系统就可以构
3、建一个无环的自治系统连接图,并把形成的外部路由信息重发布给内部网关协议(Internal Gateway Protocol,IGP)。,AS内部结构（以OSPF为例）,一个域内路由协议为OSPF的AS被划分成若干区域(area)每个区域就是按同一OSPF路由协议组合在一起的一组路由器，区域中的路由器仅需备份本区域的拓扑结构数据库即可。每个区域都用一个数字来标识,其中0号区域为骨干区域。骨干区域的主要工作是在其余区域间传递路由信息。当一个非骨干区域的路由信息对外广播时,其路由信息是先传递至骨干区域,再由骨干区域将其信息向其他区域作广播。,INTERNET,自治系统AS(ISP网络),自治系统主干
4、网,地区级网络,地区级网络主干,校园网,Internet交换中心IX(Internet Exchange Point),2002年April 1-16 10,999 个 AS系统(大概是当前Internet所有AS系统总数的84%)34,209 个 peering sessions,中国互联网概况,至2002年6月，全国IP网端口达到2618万个。从APNIC获得AS号103个，使用中的AS号？个。中国九大互联网中国科技网（CSTNET）中国公用计算机互联网（CHINANET）中国教育和科研计算机网（CERNET）中国联通互联网（UNINET）中国网通公用互联网(CNCNET)中国国际经济贸易
5、互联网（CIETNET）中国移动互联网（CMNET）中国长城互联网（CGWNET）中国卫星集团互联网（CSNET）中国三大交换中心（IX）北京、上海、广州,Cernet,CERNET有相当于57个B类这么多的IP地址。CERNET由一个主干网和八个地区网组成主干网为一个自治系统，AS号4538。域内路由协议为OSPF。OSPF area 0（主干）：其他每一个地区网形成一个自治系统。域间运行BGP4协议,CERNET 拓扑图,CERNET华北地区网地理分布图,天津大学天津主节点（27所院校）,河北师范大学石家庄主节点(41所院校),燕山大学,中国语言大学中国农业大学教育部留学服务中心北京信息工
6、程学院,河北大学,10Mbps,100Mbps,Cisco7507,Cisco12008,1Gbps,清华大学,北京邮电大学,北京大学,155Mbps,64K/DDN,100Mbps,1Gbps,Bay-BCN,Cisco12008,网络管理站SUN 3500,WWW,Mail,FTP,100Mbps,100Mbps,100Mbps,北京有线台,北京理工大学中国人民大学北京化工大学首都师范大学北方工业大学北京工业大学北大附中北京化工大学北京中医药大学对外经济贸易大学中国人民公安大学中国青年政治学院首都医科大学,Bay-BLN,Cisco 3640,IP Phone,东北大学秦皇岛分校,2Mbp
7、s,Cisco 7010,Bay-BLN,100Mbps,100M,北京大学医学部,海淀广播局网络中心,128KKK,Cisco 2500,镜象服务器,Bay-BCN,256K,CERNET华北地区网北大主节点网络逻辑图,“Internet topology at the router and autonomous system level”,Hierarchical Scale-free/cut-offpower law 分布,k:节点的度数Pk:节点度数大于k的概率,Scale-free,IP Multicast,注：以下”多播”、”Multicast”均指IP Multicast,接收者
8、,发送者,其它主机,多播路由器,多播内容提纲,多播定义、概念及应用多播协议体系结构重点介绍PIM-SM/MBGP/MSDP其它多播协议多播的可扩展性问题,可扩展性讨论（一）,多播的定义,ASM(Any Source Multicast),RFC1121的多播服务模型：每一个多播组用一个单一的IP地址来标识，任意发送者发往该地址的数据可以到达所有的组成员组成员的个数不加限制组成员可以在Internet上任一位置组成员可以自由的加入或离开发送者不必是多播组的成员此种模式称为ASMSSM(Source Specific Multicast)ASM模型的扩展，允许接受者选择发送者，即接受者只接收特定发
9、送者的数据包，并且在构造转发树的时候进行裁剪。,多播的应用,一对多定时的媒体播放（电视）“推送”(PUSH)服务（股票价格，天气预报）服务器镜像、缓存多对多视频会议、网络游戏有反馈的一对多资源发现、数据收集,IP Multicast体系结构（一）,应用程序/多播地址,主机-路由器协议(IGMP),域内多播协议,域间多播协议,注：以下”域”均指自治系统(AS),IP Multicast体系结构（二）,发送者向多播地址发送数据包多播地址：接收者告知本网段的路由器他们需要接收哪些数据包通过组管理协议进行。发送者和接收者之间的路由器构造多播树，确保多播数据包到达正确的接收者网络通过多播路由协议进行进行
10、RPF(Reverse Path Forwarding)检查,Multicast简史,1988年，Stephen Deering 确定了IP multicast 模型1992年，MBone建立，运行DVMRP(Distance-Vector Multicast Routing Protocol)协议。随着MBone规模的增加，域内(intra-domain)multicast协议相继提出，包括MOSPF(Multicast Extensions to OSPF),PIM-DM(Protocol Independent Multicast-Dense Mode),CBT(Core Based T
11、rees),PIM-SM(Protocol Independent Multicast-Sparse Mode)等1997年，规模持续增加时，一层拓扑结构显出不可扩展、不稳定等缺点，需要分层的拓扑结构，由域间(inter-domain)multicast协议支持，当前的协议有：MBGP(Multiprotocol Extensions to BGP4)/MSDP(Multicast Source Discovery Protocol)，和BGMP(Border Gateway Multicast Protocol)/MASC(Multicast Address-Set Claim)。,多播地址
12、,224.0.0.0-239.255.255.255,其中：保留为特殊地址例如224.0.0.1:本网段所有的主机；224.0.0.2:本网段所有的路由器。域内私有多播地址，类似于IP中的内网地址。以此为目的的多播流只能在自治系统内转发。,hosts,routers,IGMP,IGMPv1同一网段中一个路由器被选为“询问者”。询问者周期性的向本网段所有主机发送询问消息属于组G的主机回应消息前，先等待随机时间(0-10s)以避免冲突。然后向组G发送报告，TTL=1。路由器接收本网段所有的报告，没有回应的组被置为超时。注意：正常情况下，每一组G只有一份报告送交给询问者，因为路由器只关心本网段有没有
13、该组G的成员而不关心这些成员是谁。IGMPv2,为主机增加了显式的加入、退出组的消息IGMPv3,为主机增加了选择发送者的能力(SSM),hosts,routers,域内多播协议,域内协议Dense mode：开始时路由器向所有下行端口发送数据报，然后根据反馈信息修剪这棵树。DVMRP，类似于RIP协议构造路由表，每个路由器需要保存所有的（发送者，组）状态信息。MOSPF，一个area中的路由器互相广播如下信息：哪些组属于哪个路由器，然后为每对(发送者，组)构造转发树。PIM-DM，利用已有的路由表，广播然后修剪。Sparse mode:接收者显式发送join消息到rp，此路径记下;发送者向r
14、p注册。只有在树上的路由器需要存储状态；更高效CBT，Core/RP，双向树，支持厂家少PIM-SM，RP（相会点），单向树，每个group一个。,hosts,routers,多播转发树,源树，也称最短路径树（SPT）以发送者为树根，到每一个接收者的最短路径构成一棵转发树。可以用二元组（s,g)标示一棵源树。从发送者到接收者的路径最优，但需要维护较多状态信息。共享树ST以某个路由器为根（RP或Core）到所有接收者的树。可以用（*，g）标示一棵共享树。一棵树被多个发送者共享，维护较少的状态信息，但转发路径未必最优。树根的位置很重要。,RPF,在构造多播树的过程中，路由器接收到一个数据包，要对它
15、执行RPF(Reverse Path Forwarding)检查。具体过程为：路由器r获得该多播数据包的源地址s和进入路由器时的接口i，然后r执行“逆向转发检查”：假想要把数据包用单播方式从r发送到s，查找路由表，看是不是会从接口i发送出去，若是，则RPF检查通过，接收并转发该数据包；否则RPF检查失败，丢弃该数据包。这样，路由器可以确保自己在多播树中“入射”的路径只有一条，并且是到发送者最优的那一条。从全局来看则保证了构造的结果没有环路，是一棵树。,DVMRP,Distance-Vector Multicast Routing Protocol较早提出的多播协议，首先部署在MBone上，“密
16、集模式”。发送者的第一跳路由器开始向所有下行端口发送多播数据包。网络中间的路由器对接收到的数据进行RPF检查。最后一跳路由器根据IGMP信息返回修剪或嫁接一个分支。,DVMRP-Example Topology,g,g,s,g,DVMRP-Phase 1:Truncated Broadcast,g,g,s,g,DVMRP-Phase 2:Pruning,g,g,s,prune(s,g),prune(s,g),g,DVMRP-Steady State,g,g,s,g,g,graft(s,g),graft(s,g),DVMRP-Grafting on New Receivers,g,g,s,g,g
17、,report(g),DVMRP-Steady State after Grafting,g,g,s,g,g,PIM-SM,Protocol Independent Multicast-Sparse Mode“协议无关”的多播协议。不用交换多播路由信息利用单播路由表接收者向RP发送“join”消息，发送者发送之前首先向RP注册“当前最好”的域内协议权衡效率和复杂性得到最广泛的支持和部署,RP,R1,R2,R3,R4,Join messagetoward RP,Shared tree after R1,R2,R3 join,Phase 1:Build Shared Tree,Join G,Pha
18、se 2:Sources Send to RP,RP,R1,R2,R3,R4,S1,unicast encapsulateddata packet to RP,RP decapsulates,forwards downShared tree,S2,Phase 3:Stop Encapsulation,RP,R1,R2,R3,R4,S1,Join G for S1,Join G for S2,S2,(S1,G),(S1,G)(S2,G),(*.G),Phase 4:Switch to Shortest Path Tree,RP,R1,R2,R3,R4,Join messagestoward S2
19、,shared tree,S1,S2,Phase 5:Prune(S2 off)Shared Tree,RP,R1,R2,R3,R4,S1,S2 distribution tree,Shared tree,Prune S2 off Shared tree where iif of S2 andRP entries differ,S2,可扩展性讨论（二）,每对（发送者，组）需要一棵树。DVMRP：需要把信息Flood到全网，每一个路由器需要为每一对（发送者，组）保存状态信息，自己构造路由。PIM-DM：类似于DVMRP，利用单播路由表。MOSPF：划分为area，只需要把组员信息Flood到整个
20、area。利用单播路由表。每个（组）需要一棵共享树。PIM-SM：需要RP,显式加入、退出消息，只有在多播树上的路由器需要为每一（组）保存状态信息，利用单播路由表。CBT：类似于PIM-SM，需要Core。构造双向共享树。,可扩展性讨论（三）,经验显示单层的网络结构不具有可扩展性每一个路由器都需要知道其他所有的路由器/子网（需要保存大量的状态信息）。单层网络规模增加时趋向于不稳定，一个错误操作可能波及全网。层次结构网络中的多播需要解决的问题：域内多播路由协议域间多播路由交换协议连接不同域的多播树的机制多播地址分配问题,域间多播协议,域间协议MBGP/PIM-SM/MSDP(near-term)
21、MBGP用来交换域间的multicast路由，PIM-SM 用于连接不同域的同一多播组成员，MSDP用于不同域间的RP交换活动的 multicast发送者信息。MASC/BGMP(long-term)MASC为各个AS域分配层次结构的多播地址。BGMP构造一个以根域(root domain)为根的双向域间多播树，这棵树可以由多个多播组共享。,hosts,routers,MSDP的提出,域内协议时：每一个多播组只有一个RP。当扩展到多个域时，每一个域内对于每一个活动的多播组都至少有一个RP，从而从全局的观点看，一个多播组有多个RP同时存在于不同的域中并且互不了解！对于域内的情况：接收者可以向RP
22、发送“join”消息加入多播树，发送者可以向同一RP注册，从而向位于同一域的接收者发送多播数据；而对于其他域的同组接收者就无能为力了。,MSDP,Multicast Source Discovery Protocol。每一个域向其他域宣告本域中活动着的发送者信息。MSDP运行在路由器RP之中。相邻域的MSDP peer配置 MSDP sessions(TCP连接)通讯。本域出现一个新的发送者时，该发送者向RP注册。本域的MSDP peer获知该信息后，向所有邻域的 MSDP peers 发送Source Active(SA)消息：包括（发送者，组）信息。MSDP peers收到 SA消息后作R
23、PF检查，以避免环路，检查成功则所有其他邻居发送该消息。收到SA的MSDP peer(同样是RP)会察看自己域内是否有该多播组成员（即是否已经构建了该多播组的转发树）。若是，则向该发送者发送一条PIM join消息以完成该组转发树的构建，或者通过转发树向域内的接收者转发数据。,MBGP,Multiprotocol Extensions to BGP4/Multicast BGP/BGP4+，运行于自治系统边界路由器。MBGP用来提供域间的“下一跳”信息，类似于BGP为单播提供域间“下一跳”信息。向相邻的自治系统通告“从我这里可以到达发送者s”。当RP或者多播组接收者试图向位于其他AS的多播发送
24、者s发送一个”join”消息时，该消息需要沿着“逆向路径”到达多播发送者s，有了MBGP提供的路由就可以做到这一点了。MBGP并不负责域间多播树的构造，用现有协议PIM-SM就可以胜任。,MBGP/PIM-SM/MSDP,RP,RP,RP,RP,MSDP peer,Physical link,A,B,C,D,Receiver,Source,PIM message,MSDP message,可扩展性讨论（四）,Asia-Pacific Advanced Network(APAN)和 Internet2 的主干网Abilene以及CERNET都部署了MBGP/PIM-SM/MSDPMSDP的SA需
25、要定期散发（每60秒），模式类似于DVMRP。虽然在域这个层次，但是当多播广泛部署后，若某个域同时存在成千上万个活动的发送者，则该域向其他邻域就要发送多条SA，并进一步散发出去。,可扩展性讨论（五）,PIM-SM需要为每一个多播组构造一棵共享树并保存状态。在Internet 中，可能有数量巨大的多播树通过主干网络，这些树的状态维护需要大量的资源。公认只适于作为近期的解决方案，需要进一步研究具有更好可扩展性的多播体系结构。,MASC/BGMP,MASC/BGMP(long-term)MASC(Multicast Address-Set Claim)为各个AS域分配层次结构的多播地址。从而多播的组
26、地址也可以像单播地址那样进行汇聚。BGMP(Border Gateway Multicast Protocol)构造一个以根域(root domain)为根的双向域间多播树，这棵树可以由多个多播组共享，对比与PIM-SM协议每一个多播组需要一棵共享树，从而进一步提高了可扩展性。,总结,“单播-域内多播密集模式-域内多播稀疏模式-域间多播-多播地址汇聚/多播树共享”多播的产生和发展的过程就是不断追求可扩展性的过程。AS级别的IP多播已经得到部署并取得较好的应用效果，整个Internet范围内IP多播的体系结构仍需要进一步的研究。,部分参考文献,1Kevin.Almeroth,The evolut
27、ion of multicast:From the MBone to inter-domain multicast to Internet2 deployment,IEEE Network,January/February 2000.2T.Wong and R.Katz.An analysis of multicast forwarding state scalability.International Conference on Network Protocols,2000.6 3Jun-Hong Cui,Jinkyu Kim,Dario Maggiorini,Khaled Boussett
28、a,and Mario Gerla.Aggregated Multicast-A Comparative Study.Technical report,UCLA CSD TR No.020011,February 2002.4Cisco System，Deploying Scalable multicast，Session RST2205A.V azquez,R.Pastor-Satorras,Internet topology at the router and autonomous system level,arXiv:cond-mat/0206084 v1 6 Jun 20026Kevin Almeroth，Introduction to Multicast Protocols and Applications，http:/www.cs.ucsb.edu/almeroth7CERNET主干网运行汇报-李星 2001.9,谢谢大家！,
