Internet拓扑结构和IP多播 - 计算机网络和分布式系统实验室ppt课件

1、Internet拓扑结构与IP多播程远 2019.9提纲 Internet 拓扑结构 Internet 的构成 网络结构实例 隐藏的规律：power law IP多播 多播定义、概念及应用 多播协议 多播可扩展性的讨论Internet 拓扑结构？ Internet是研究对象。 ”You cant resolve the traffic jam problem of a city without looking at the street layout. ” 对网络的感性认识，解答一些基本的问题： Internet的规模？ 中国网络的基本情况？ Cernet的基本情况？ Internet拓扑图节

2、点度数概率分布：power lawInternet : 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号区域为骨干区域。 骨干区域的主要工作是在其余区域间传递路由信息。当一个非骨干区域的路由信息对外广播时,其路由信息是先传递至骨干区域,再由骨干区域将其信息向其他区域作广播。ASASASASIX

4、INTERNET自治系统AS(ISP网络)自治系统主干网地区级网络地区级网络主干校园网Internet交换中心IX(Internet Exchange Point)2019年April 1-16 10,999 个 AS系统 (大概是当前Internet所有AS系统总数的84%)34,209 个 peering sessions中国互联网概况至2019年6月， 全国IP网端口达到2618万个。从APNIC获得AS号103个，使用中的AS号？个。中国九大互联网中国科技网CSTNET）中国公用计算机互联网CHINANET）中国教育和科研计算机网CERNET）中国联通互联网UNINET）中国网通公用互

5、联网(CNCNET)中国国际经济贸易互联网CIETNET）中国移动互联网CMNET）中国长城互联网CGWNET）中国卫星集团互联网CSNET）中国三大交换中心IX）北京、上海、广州Cernet CERNET有相当于57个B类这么多的IP地址。 CERNET由一个主干网和八个地区网组成 主干网为一个自治系统，AS号4538。域内路由协议为OSPF。 OSPF area 0 （主干）： /24 DDN & SAT /24 POS 其他每一个地区网形成一个自治系统。域间运行BGP4协议CERNET 拓扑图CERNET华北地区网地理分布图天津大学天津主节点

6、（27所院校）河北师范大学石家庄主节点(41所院校)燕山大学中国语言大学中国农业大学教育部留学服务中心北京信息工程学院河北大学 10Mbps100Mbps Cisco7507 北京大学 Cisco120191Gbps清华大学北京邮电大学北京大学155Mbps64K/DDN100Mbps1Gbps Bay -BCNCisco12019网络管理站SUN 3500WWW MailFTP100Mbps100Mbps100Mbps北京有线台北京理工大学中国人民大学北京化工大学首都师范大学北方工业大学北京工业大学北大附中北京化工大学北京中医药大学对外经济贸易大学中国人民公安大学中国青年政治学院首都医科大学

7、Bay-BLNCisco 3640IP Phone东北大学秦皇岛分校2MbpsCisco 7010Bay-BLN 100Mbps100M北京大学医学部海淀广播局网络中心128KKKCisco 2500镜象服务器Bay-BCN256KCERNET华北地区网北大主节点网络逻辑图“Internet topology at the router and autonomous system level” Hierarchical Scale-free / cut-off power law 分布)1 .2(1kPkk:节点的度数Pk:节点度数大于k的概率Scale-freeASASASASIXIP Mu

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

9、(Source Specific Multicast) ASM模型的扩展，允许接受者选择发送者，即接受者只接收特定发送者的数据包，并且在构造转发树的时候进行裁剪。多播的应用 一对多 定时的媒体播放电视） “推送”(PUSH)效力股票价格，天气预报） 服务器镜像、缓存 多对多 视频会议、网络游戏 有反馈的一对多 资源发现、数据收集IP Multicast体系结构一）应用程序应用程序/多播地址多播地址主机主机-路由器协议路由器协议 (IGMP)域内多播协议域内多播协议域间多播协议域间多播协议hostsrouters注：以下域注：以下域” 均指自治系统均指自治系统(AS)IP Multicast体系

10、结构二） 发送者向多播地址发送数据包 多播地址：-55 接收者告知本网段的路由器他们需要接收哪些数据包 通过组管理协议进行。 发送者和接收者之间的路由器构造多播树，确保多播数据包到达正确的接收者网络 通过多播路由协议进行 进行RPF (Reverse Path Forwarding)检查Multicast简史 1988年， Stephen Deering 确定了IP multicast 模型 1992年，MBone建立，运行DVMRP (Distance-Vector Multicast Routing Protocol)协议。 随着MBone规模的

11、增加，域内(intra-domain) multicast协议相继提出，包括MOSPF (Multicast Extensions to OSPF), PIM-DM (Protocol Independent Multicast-Dense Mode), CBT (Core Based Trees), PIM-SM (Protocol Independent Multicast-Sparse Mode)等 2019年，规模持续增加时，一层拓扑结构显出不可扩展、不稳定等缺点，需要分层的拓扑结构，由域间(inter-domain) multicast协议支持，当前的协议有： MBGP (Multi

12、protocol Extensions to BGP4) / MSDP (Multicast Source Discovery Protocol)，和BGMP (Border Gateway Multicast Protocol) / MASC ( Multicast Address-Set Claim) 。多播地址 - 55,其中： -55保留为特殊地址 例如:本网段所有的主机；:本网段所有的路由器。 -55域内私有多播地址，类似于

13、IP中的内网地址。以此为目的的多播流只能在自治系统内转发。hostsroutersIGMP IGMPv1 同一网段中一个路由器被选为“询问者”。 询问者周期性的向本网段所有主机发送询问消息 属于组G的主机回应消息前，先等待随机时间(0-10s)以避免冲突。然后向组G发送报告，TTL=1。 路由器接收本网段所有的报告，没有回应的组被置为超时。 留意：正常情况下，每一组G只有一份报告送交给询问者，因为路由器只关心本网段有没有该组G的成员而不关心这些成员是谁。 IGMPv2,为主机增加了显式的加入、退出组的消息 IGMPv3,为主机增加了选择发送者的能力(SSM)hostsrouters域内多播协议

14、 域内协议 Dense mode ：开始时路由器向所有下行 端口发送数据报，然后根据反馈信息修剪这棵树。 DVMRP，类似于RIP协议构造路由表，每个路由器需要保存所有的发送者，组状态信息。 MOSPF，一个area中的路由器互相广播如下信息：哪些组属于哪个路由器，然后为每对(发送者，组)构造转发树。 PIM-DM，利用已有的路由表，广播然后修剪。 Sparse mode:接收者显式发送join消息到rp，此路径记下;发送者向rp注册。只有在树上的路由器需要存储状态；更高效 CBT ，Core/RP，双向树，支持厂家少 PIM-SM，RP相会点），单向树，每个group一个。hostsrout

15、ers多播转发树 源树，也称最短路径树SPT） 以发送者为树根，到每一个接收者的最短路径构成一棵转发树。 可以用二元组s, g)标示一棵源树。 从发送者到接收者的路径最优，但需要维护较多状态信息。 共享树ST 以某个路由器为根RP或Core到所有接收者的树。 可以用（*，g标示一棵共享树。 一棵树被多个发送者共享，维护较少的状态信息，但转发路径未必最优。树根的位置很重要。RPF 在构造多播树的过程中，路由器接收到一个数据包，要对它执行RPF (Reverse Path Forwarding)检查。具体过程为：路由器r获得该多播数据包的源地址s和进入路由器时的接口i，然后r执行“逆向转发检查”：

16、假想要把数据包用单播方式从r发送到s，查找路由表，看是不是会从接口i发送出去，若是，则RPF检查通过，接收并转发该数据包；否则RPF检查失败，丢弃该数据包。 这样，路由器可以确保自己在多播树中“入射的路径只有一条，并且是到发送者最优的那一条。 从全局来看则保证了构造的结果没有环路，是一棵树。DVMRP Distance-Vector Multicast Routing Protocol 较早提出的多播协议，首先部署在MBone上，“密集模式”。 发送者的第一跳路由器开始向所有下行端口发送多播数据包。网络中间的路由器对接收到的数据进行RPF检查。 最后一跳路由器根据IGMP信息返回修剪或嫁接一个

17、分支。DVMRP- Example TopologyggsgDVMRP- Phase 1: Truncated BroadcastggsgDVMRP- Phase 2: Pruningggsprune (s,g)prune (s,g)gDVMRP- Steady Stateggsgggraft (s,g)graft (s,g)DVMRP- Grafting on New Receiversggsggreport (g)DVMRP- Steady State after GraftingggsggPIM-SM Protocol Independent Multicast-Sparse Mode“

18、协议无关的多播协议。 不用交换多播路由信息 利用单播路由表 接收者向RP发送“join音讯，发送者发送之前首先向RP注册 “当前最好的域内协议 权衡效率和复杂性 得到最广泛的支持和部署RPR1R2R3R4Join 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 tr

19、eeS2Phase 3: Stop EncapsulationRPR1R2R3R4S1Join G for S1Join G for S2S2(S1,G)(S1,G)(S2,G)(*.G)Phase 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 and

20、RP entries differS2可扩展性讨论二） 每对发送者，组需要一棵树。 DVMRP：需要把信息Flood到全网，每一个路由器需要为每一对发送者，组保存状态信息，自己构造路由。 PIM-DM：类似于DVMRP，利用单播路由表。 MOSPF：划分为area，只需要把组员信息Flood到整个area。利用单播路由表。 每个组需要一棵共享树。 PIM-SM：需要RP,显式加入、退出消息，只有在多播树上的路由器需要为每一组保存状态信息，利用单播路由表。 CBT：类似于PIM-SM，需要Core。构造双向共享树。可扩展性讨论三） 经验显示单层的网络结构不具有可扩展性 每一个路由器都需要知道其他

21、所有的路由器/子网需要保存大量的状态信息）。 单层网络规模增加时趋向于不稳定，一个错误操作可能波及全网。 层次结构网络中的多播需要解决的问题： 域内多播路由协议 域间多播路由交换协议 连接不同域的多播树的机制 多播地址分配问题域间多播协议 域间协议 MBGP/PIM-SM/MSDP (near-term) MBGP用来交换域间的multicast路由，PIM-SM 用于连接不同域的同一多播组成员，MSDP用于不同域间的RP交换活动的 multicast发送者信息。 MASC/BGMP (long-term) MASC为各个AS域分配层次结构的多播地址。 BGMP构造一个以根域(root dom

22、ain)为根的双向域间多播树，这棵树可以由多个多播组共享。hostsroutersMSDP的提出 域内协议时：每一个多播组只有一个RP。当扩展到多个域时，每一个域内对于每一个活动的多播组都至少有一个RP，从而从全局的观点看，一个多播组有多个RP同时存在于不同的域中并且互不了解！ 对于域内的情况：接收者可以向RP发送“join消息加入多播树，发送者可以向同一RP注册，从而向位于同一域的接收者发送多播数据；而对于其他域的同组接收者就无能为力了。MSDP Multicast Source Discovery Protocol。每一个域向其他域宣告本域中活动着的发送者信息。 MSDP运行在路由器RP之

23、中。 相邻域的MSDP peer配置 MSDP sessions (TCP连接) 通讯 。 本域出现一个新的发送者时，该发送者向RP注册。 本域的MSDP peer获知该信息后，向所有邻域的 MSDP peers 发送Source Active (SA)音讯：包括发送者，组信息。 MSDP peers收到 SA消息后作RPF检查，以避免环路，检查成功则所有其他邻居发送该消息。 收到SA的MSDP peer (同样是RP)会察看自己域内是否有该多播组成员即是否已经构建了该多播组的转发树）。若是，则向该发送者发送一条PIM join消息以完成该组转发树的构建，或者通过转发树向域内的接收者转发数据。

24、MBGP Multiprotocol Extensions to BGP4 / Multicast BGP / BGP4+，运行于自治系统边界路由器。 MBGP用来提供域间的“下一跳信息，类似于BGP为单播提供域间“下一跳信息。 向相邻的自治系统通告“从我这里可以到达发送者s”。当RP或者多播组接收者试图向位于其他AS的多播发送者s发送一个join” 消息时，该消息需要沿着“逆向路径到达多播发送者s，有了MBGP提供的路由就可以做到这一点了。 MBGP并不负责域间多播树的构造，用现有协议PIM-SM就可以胜任。MBGP/PIM-SM/MSDPRPRPRPRPMSDP peerPhysical

25、linkABCDReceiverSourcePIM messageMSDP messageSASASAJoinJoinJoinJoinJoin可扩展性讨论四） Asia-Pacific Advanced Network (APAN) 和 Internet2 的主干网Abilene以及CERNET都部署了MBGP/PIM-SM/MSDP MSDP的SA需要定期散发每60秒），模式类似于DVMRP。虽然在域这个层次，但是当多播广泛部署后，若某个域同时存在成千上万个活动的发送者，则该域向其他邻域就要发送多条SA，并进一步散发出去。可扩展性讨论五） PIM-SM需要为每一个多播组构造一棵共享树并保存状

26、态。在Internet 中，可能有数量巨大的多播树通过主干网络，这些树的状态维护需要大量的资源。 公认只适于作为近期的解决方案，需要进一步研究具有更好可扩展性的多播体系结构。MASC/BGMP MASC/BGMP (long-term) MASC ( Multicast Address-Set Claim)为各个AS域分配层次结构的多播地址。 从而多播的组地址也可以像单播地址那样进行汇聚。 BGMP (Border Gateway Multicast Protocol) 构造一个以根域(root domain)为根的双向域间多播树，这棵树可以由多个多播组共享，对比与PIM-SM协议每一个多播组需要一棵共享树，从而进一步提高了可扩展性。总结 “单播-域内多播密集模式-域内多播稀疏模式-域间多播-多播地址汇聚/多播树