Internet拓朴结构与IP多播课件

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拓扑图节点度数概率分布：power l

2、awInternet : ASes + BGPInternet由大约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号区域为骨干区域。骨干区域的主要工作是在其余区域间传递路由信息。当一个非骨干区域的路由信息对外广播时,其路由信息是先传递至骨干区域,再由骨干区域将其信息向其他区域作广播。2002年April 1-16 10,999 个 AS系统

4、 (大概是当前Internet所有AS系统总数的84%)34,209 个 peering sessions中国互联网概况至2002年6月， 全国IP网端口达到2618万个。从APNIC获得AS号103个，使用中的AS号？个。中国九大互联网中国科技网（CSTNET）中国公用计算机互联网（CHINANET）中国教育和科研计算机网（CERNET）中国联通互联网（UNINET）中国网通公用互联网(CNCNET)中国国际经济贸易互联网（CIETNET）中国移动互联网（CMNET）中国长城互联网（CGWNET）中国卫星集团互联网（CSNET）中国三大交换中心（IX）北京、上海、广州CERNET 拓扑图CE

5、RNET华北地区网地理分布图天津大学天津主节点（27所院校）河北师范大学石家庄主节点(41所院校)燕山大学中国语言大学中国农业大学教育部留学服务中心北京信息工程学院河北大学10Mbps100MbpsCisco7507北京大学Cisco120081Gbps清华大学北京邮电大学北京大学155Mbps64K/DDN100Mbps1Gbps Bay -BCNCisco12008网络管理站SUN 3500WWW MailFTP100Mbps100Mbps100Mbps北京有线台北京理工大学中国人民大学北京化工大学首都师范大学北方工业大学北京工业大学北大附中北京化工大学北京中医药大学对外经济贸易大学中国人

6、民公安大学中国青年政治学院首都医科大学Bay-BLNCisco 3640IP Phone东北大学秦皇岛分校2MbpsCisco 7010Bay-BLN100Mbps100M北京大学医学部海淀广播局网络中心128KKKCisco 2500镜象服务器Bay-BCN256KCERNET华北地区网北大主节点网络逻辑图“Internet topology at the router and autonomous system level”Hierarchical Scale-free / cut-offpower law 分布k:节点的度数Pk:节点度数大于k的概率ASASASASIXIP Multic

7、ast注：以下”多播”、”Multicast”均指IP Multicast接收者发送者其它主机多播路由器多播内容提纲多播定义、概念及应用多播协议体系结构重点介绍PIM-SM/MBGP/MSDP其它多播协议多播的可扩展性问题可扩展性讨论（一）多播的定义ASM (Any Source Multicast) ,RFC1121的多播服务模型：每一个多播组用一个单一的IP地址来标识，任意发送者发往该地址的数据可以到达所有的组成员组成员的个数不加限制组成员可以在Internet上任一位置组成员可以自由的加入或离开发送者不必是多播组的成员此种模式称为ASMSSM (Source Specific Multi

8、cast)ASM模型的扩展，允许接受者选择发送者，即接受者只接收特定发送者的数据包，并且在构造转发树的时候进行裁剪。多播的应用一对多定时的媒体播放（电视）“推送”(PUSH)服务（股票价格，天气预报）服务器镜像、缓存多对多视频会议、网络游戏有反馈的一对多资源发现、数据收集IP Multicast体系结构（二）发送者向多播地址发送数据包多播地址：-55接收者告知本网段的路由器他们需要接收哪些数据包通过组管理协议进行。发送者和接收者之间的路由器构造多播树，确保多播数据包到达正确的接收者网络通过多播路由协议进行进行RPF (Reverse Path Forwarding)检查Multicast简史1

9、988年， 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 Trees), PIM-SM (Protocol Independent

10、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) 。IGMPIGMPv1同一网段中一个路由器被选为“询问者

11、”。询问者周期性的向本网段所有主机发送询问消息属于组G的主机回应消息前，先等待随机时间(0-10s)以避免冲突。然后向组G发送报告，TTL=1。路由器接收本网段所有的报告，没有回应的组被置为超时。注意：正常情况下，每一组G只有一份报告送交给询问者，因为路由器只关心本网段有没有该组G的成员而不关心这些成员是谁。IGMPv2,为主机增加了显式的加入、退出组的消息IGMPv3,为主机增加了选择发送者的能力(SSM)hostsrouters域内多播协议域内协议Dense mode ：开始时路由器向所有下行端口发送数据报，然后根据反馈信息修剪这棵树。DVMRP，类似于RIP协议构造路由表，每个路由器需要

12、保存所有的（发送者，组）状态信息。MOSPF，一个area中的路由器互相广播如下信息：哪些组属于哪个路由器，然后为每对(发送者，组)构造转发树。PIM-DM，利用已有的路由表，广播然后修剪。Sparse mode:接收者显式发送join消息到rp，此路径记下;发送者向rp注册。只有在树上的路由器需要存储状态；更高效CBT ，Core/RP，双向树，支持厂家少PIM-SM，RP（相会点），单向树，每个group一个。hostsrouters多播转发树源树，也称最短路径树（SPT）以发送者为树根，到每一个接收者的最短路径构成一棵转发树。可以用二元组（s, g)标示一棵源树。从发送者到接收者的路径最

13、优，但需要维护较多状态信息。共享树ST以某个路由器为根（RP或Core）到所有接收者的树。可以用（*，g）标示一棵共享树。一棵树被多个发送者共享，维护较少的状态信息，但转发路径未必最优。树根的位置很重要。RPF在构造多播树的过程中，路由器接收到一个数据包，要对它执行RPF (Reverse Path Forwarding)检查。具体过程为：路由器r获得该多播数据包的源地址s和进入路由器时的接口i，然后r执行“逆向转发检查”：假想要把数据包用单播方式从r发送到s，查找路由表，看是不是会从接口i发送出去，若是，则RPF检查通过，接收并转发该数据包；否则RPF检查失败，丢弃该数据包。这样，路由器可以

14、确保自己在多播树中“入射”的路径只有一条，并且是到发送者最优的那一条。从全局来看则保证了构造的结果没有环路，是一棵树。DVMRPDistance-Vector Multicast Routing Protocol较早提出的多播协议，首先部署在MBone上，“密集模式”。发送者的第一跳路由器开始向所有下行端口发送多播数据包。网络中间的路由器对接收到的数据进行RPF检查。最后一跳路由器根据IGMP信息返回修剪或嫁接一个分支。DVMRP- Example TopologyggsgDVMRP- Phase 1: Truncated BroadcastggsgDVMRP- Phase 2: Prunin

15、gggsprune (s,g)prune (s,g)gDVMRP- Steady Stateggsgggraft (s,g)graft (s,g)DVMRP- Grafting on New Receiversggsggreport (g)DVMRP- Steady State after GraftingggsggPIM-SMProtocol Independent Multicast-Sparse Mode“协议无关”的多播协议。不用交换多播路由信息利用单播路由表接收者向RP发送“join”消息，发送者发送之前首先向RP注册“当前最好”的域内协议权衡效率和复杂性得到最广泛的支持和部署RPR

16、1R2R3R4Join messagetoward RPShared tree after R1,R2,R3 joinPhase 1: Build Shared TreeJoin GPhase 2: Sources Send to RPRPR1R2R3R4S1unicast encapsulateddata packet to RPRP decapsulates,forwards downShared treeS2Phase 3: Stop EncapsulationRPR1R2R3R4S1Join G for S1Join G for S2S2(S1,G)(S1,G)(S2,G)(*.G)P

17、hase 4: Switch to Shortest Path TreeRPR1R2R3R4Join messagestoward S2shared treeS1S2Phase 5: Prune (S2 off) Shared TreeRPR1R2R3R4S1S2 distribution treeShared treePrune S2 off Shared tree where iif of S2 andRP entries differS2可扩展性讨论（二）每对（发送者，组）需要一棵树。DVMRP：需要把信息Flood到全网，每一个路由器需要为每一对（发送者，组）保存状态信息，自己构造路由

18、。PIM-DM：类似于DVMRP，利用单播路由表。MOSPF：划分为area，只需要把组员信息Flood到整个area。利用单播路由表。每个（组）需要一棵共享树。PIM-SM：需要RP,显式加入、退出消息，只有在多播树上的路由器需要为每一（组）保存状态信息，利用单播路由表。CBT：类似于PIM-SM，需要Core。构造双向共享树。可扩展性讨论（三）经验显示单层的网络结构不具有可扩展性每一个路由器都需要知道其他所有的路由器/子网（需要保存大量的状态信息）。单层网络规模增加时趋向于不稳定，一个错误操作可能波及全网。层次结构网络中的多播需要解决的问题：域内多播路由协议域间多播路由交换协议连接不同域的

19、多播树的机制多播地址分配问题域间多播协议域间协议MBGP/PIM-SM/MSDP (near-term) MBGP用来交换域间的multicast路由，PIM-SM 用于连接不同域的同一多播组成员，MSDP用于不同域间的RP交换活动的 multicast发送者信息。MASC/BGMP (long-term)MASC为各个AS域分配层次结构的多播地址。 BGMP构造一个以根域(root domain)为根的双向域间多播树，这棵树可以由多个多播组共享。hostsroutersMSDP的提出域内协议时：每一个多播组只有一个RP。当扩展到多个域时，每一个域内对于每一个活动的多播组都至少有一个RP，从而

20、从全局的观点看，一个多播组有多个RP同时存在于不同的域中并且互不了解！对于域内的情况：接收者可以向RP发送“join”消息加入多播树，发送者可以向同一RP注册，从而向位于同一域的接收者发送多播数据；而对于其他域的同组接收者就无能为力了。MSDP Multicast Source Discovery Protocol。每一个域向其他域宣告本域中活动着的发送者信息。 MSDP运行在路由器RP之中。 相邻域的MSDP peer配置 MSDP sessions (TCP连接) 通讯 。 本域出现一个新的发送者时，该发送者向RP注册。 本域的MSDP peer获知该信息后，向所有邻域的 MSDP pee

21、rs 发送Source Active (SA)消息：包括（发送者，组）信息。 MSDP peers收到 SA消息后作RPF检查，以避免环路，检查成功则所有其他邻居发送该消息。 收到SA的MSDP peer (同样是RP)会察看自己域内是否有该多播组成员（即是否已经构建了该多播组的转发树）。若是，则向该发送者发送一条PIM join消息以完成该组转发树的构建，或者通过转发树向域内的接收者转发数据。MBGPMultiprotocol Extensions to BGP4 / Multicast BGP / BGP4+，运行于自治系统边界路由器。MBGP用来提供域间的“下一跳”信息，类似于BGP为单

22、播提供域间“下一跳”信息。向相邻的自治系统通告“从我这里可以到达发送者s”。当RP或者多播组接收者试图向位于其他AS的多播发送者s发送一个”join” 消息时，该消息需要沿着“逆向路径”到达多播发送者s，有了MBGP提供的路由就可以做到这一点了。MBGP并不负责域间多播树的构造，用现有协议PIM-SM就可以胜任。MBGP/PIM-SM/MSDPRPRPRPRPMSDP peerPhysical linkABCDReceiverSourcePIM messageMSDP messageSASASAJoinJoinJoinJoinJoin可扩展性讨论（四）Asia-Pacific Advanced

23、 Network (APAN) 和 Internet2 的主干网Abilene以及CERNET都部署了MBGP/PIM-SM/MSDPMSDP的SA需要定期散发（每60秒），模式类似于DVMRP。虽然在域这个层次，但是当多播广泛部署后，若某个域同时存在成千上万个活动的发送者，则该域向其他邻域就要发送多条SA，并进一步散发出去。可扩展性讨论（五）PIM-SM需要为每一个多播组构造一棵共享树并保存状态。在Internet 中，可能有数量巨大的多播树通过主干网络，这些树的状态维护需要大量的资源。公认只适于作为近期的解决方案，需要进一步研究具有更好可扩展性的多播体系结构。MASC/BGMPMASC/B

24、GMP (long-term)MASC ( Multicast Address-Set Claim)为各个AS域分配层次结构的多播地址。 从而多播的组地址也可以像单播地址那样进行汇聚。BGMP (Border Gateway Multicast Protocol) 构造一个以根域(root domain)为根的双向域间多播树，这棵树可以由多个多播组共享，对比与PIM-SM协议每一个多播组需要一棵共享树，从而进一步提高了可扩展性。总结“单播-域内多播密集模式-域内多播稀疏模式-域间多播-多播地址汇聚/多播树共享”多播的产生和发展的过程就是不断追求可扩展性的过程。AS级别的IP多播已经得到部署并取得较好的应用效果，整个Int