Internet组播简介

1清华大学计算机系Internet组播简介2主要内容u为什么需要组播？u组播地址u主机和路由器的交互：IGMP u组播分发树u组播转发u域内组播路由协议u域间组播路由协议uIPv63主要内容u为什么需要组播？u组播地址u主机和路由器的交互：IGMP u组播分发树u组播转发u域内组播路由协议u域间组播路由协议uIPv64ServerRouterUnicastServerRouterMulticast单播和组播的比较5Example:Audio StreamingAll clients listening to the same 8 Kbps audio00.20.40.60.8TrafficMbps120406080100#ClientsMulticastUnicast组播的优势:Controls network traffic and reduces server and CPU loads:Eliminates traffic redundancy:Makes multipoint applications possible6组播带来的问题uBest Effort Delivery:Drops are to be expected.Multicast applications should not expect reliable delivery of data and should be designed accordingly.Reliable Multicast is still an area for much research uNo Congestion Avoidance:Lack of TCP windowing and“slow-start”mechanisms can result in network congestion.If possible,Multicast applications should attempt to detect and avoid congestion conditions组播是基于组播是基于UDP的！的！7组播带来的问题uDuplicates:Some multicast protocol mechanisms(e.g.Asserts,Registers and SPT Transitions)result in the occasional generation of duplicate packetsuOut of Order Delivery:Some protocol mechanisms may also result in out of order delivery of packets8组播的应用uMultimedia Streaming media,IPTV Training,corporate communications Conferencingvideo/audiouNet GameuAny one-to-many data push applications9主要内容u为什么需要组播？u组播地址u主机和路由器的交互：IGMP u组播分发树u组播转发u域内组播路由协议u域间组播路由协议uIPv610uIPv4 Multicast Group Addresses 224.0.0.0239.255.255.255 Class“D”Address Space High order bits of 1st Octet=“1110”uReserved Link-local Addresses 224.0.0.0224.0.0.255 Transmitted with TTL=1 Examples:224.0.0.1 All systems on this subnet 224.0.0.2 All routers on this subnet 224.0.0.4 DVMRP routers 224.0.0.5 OSPF routers 224.0.0.13 PIMv2 routers组播地址 11uAdministratively Scoped Addresses 239.0.0.0239.255.255.255 Private address space Similar to RFC1918 unicast addresses Not used for global Internet traffic Used to limit“scope”of multicast traffic Same addresses may be in use at different locations for different multicast sessions Examples Site-local scope:239.253.0.0/16 Organization-local scope:239.192.0.0/14组播地址 1232 Bits28 Bits25 Bits23 Bits48 Bits01-00-5e-7f-00-0111105 BitsLost组播地址IP Multicast MAC Address Mapping(FDDI and Ethernet)239.255.0.113224.1.1.1224.129.1.1225.1.1.1225.129.1.1 .238.1.1.1238.129.1.1239.1.1.1239.129.1.10 x0100.5E01.01011-Multicast MAC Address(FDDI and Ethernet)32-IP Multicast Addresses组播地址Be Aware of the 32:1 Address OverlapIP Multicast MAC Address Mapping(FDDI&Ethernet)14组播地址 uDynamic Group Address Assignment Historically accomplished using SDR application Sessions/groups announced over well-known multicast groups Address collisions detected and resolved at session creation time Has problems scaling15组播地址 uFuture dynamic techniques under consideration Multicast Address Set-Claim(MASC)Hierarchical,dynamic address allocation scheme Extremely complex garbage-collection problem Long ways off MADCAP Similar to DHCP Need application and host stack support16组播地址 uStatic Group Address Assignment Temporary method to meet immediate needs Group range:233.0.0.0-233.255.255.255 Your AS number is inserted in middle two octets Remaining low-order octet used for group assignment Defined in IETF RFC3180 GLOP Addressing in 233/817主要内容u为什么需要组播？u组播地址u主机和路由器的交互：IGMP u组播分发树u组播转发u域内组播路由协议u域间组播路由协议uIPv618 Routers solicit group membership from directly connected hosts RFC 1112 specifies version 1 of IGMP RFC 2236 specifies version 2 of IGMP RFC 3376 specifies version 3 of IGMPSupported on latest service pack for Windows and most UNIX systems How hosts tell routers about group membership主机和路由器的交互：IGMP19H3uHost sends IGMP Report to join groupH3224.1.1.1ReportH1H2Joining a Group主机和路由器的交互：IGMP20uRouter sends periodic Queries to 224.0.0.1Query One member per group per subnet reports224.1.1.1Report Other members suppress reports224.1.1.1SuppressedX224.1.1.1SuppressedXH1H2H3Maintaining a Group主机和路由器的交互：IGMP21 Host quietly leaves groupH1H3H3#1 Router sends 3 General Queries(60 secs apart)General Query#2 No IGMP Report for the group is received Group times out(Worst case delay=3 minutes)H2Leaving a Group(IGMPv1)主机和路由器的交互：IGMP22 Host sends Leave message to 224.0.0.2H1H3H3Leave to224.0.0.2224.1.1.1 Router sends Group specific query to 224.1.1.1Group SpecificQuery to 224.1.1.1 No IGMP Report is received within 3 seconds Group 224.1.1.1 times outH2Leaving a Group(IGMPv2)主机和路由器的交互：IGMP23IGMPv3uRFC3376uEnables hosts to listen only to a specified subset of the hosts sending to the group24Source=1.1.1.1Group=224.1.1.1H1-Member of 224.1.1.1R1R3R2Source =2.2.2.2Group=224.1.1.1 H1 wants to receive from S=1.1.1.1 but not from S=2.2.2.2 With IGMP,specific sources can be pruned back-S=2.2.2.2 in this caseIGMPv3:Join 1.1.1.1,224.1.1.1Leave 2.2.2.2,224.1.1.1IGMPv325主要内容u为什么需要组播？u组播地址u主机和路由器的交互：IGMP u组播分发树u组播转发u域内组播路由协议u域间组播路由协议uIPv626Shortest Path or Source Distribution TreeReceiver 1BEADFSource 1Notation:(S,G)S=Source G=GroupCReceiver 2Source 2组播分发树27Receiver 1BEADFSource 1Notation:(S,G)S=Source G=GroupCReceiver 2Source 2组播分发树Shortest Path or Source Distribution Tree28组播分发树Shared Distribution TreeReceiver 1BEAD FNotation:(*,G)*=All Sources G=GroupCReceiver 2(RP)PIM Rendezvous PointShared Tree(RP)29组播分发树Shared Distribution TreeReceiver 1BEAFSource 1Notation:(*,G)*=All Sources G=GroupCReceiver 2Source 2(RP)PIM Rendezvous PointShared TreeSource TreeD(RP)30组播分发树u Source or Shortest Path treesuses more memory O(S G)but you get optimal paths from source to all receiversminimizes delayu Shared treesuses less memory O(G)but you may get sub-optimal paths from source to all receiversmay introduce extra delayCharacteristics of Distribution Trees31主要内容u为什么需要组播？u组播地址u主机和路由器的交互：IGMP u组播分发树u组播转发u域内组播路由协议u域间组播路由协议uIPv632组播转发uMulticast Forwarding is backwards from Unicast Forwarding Unicast Forwarding is concerned about where the packet is going Multicast Forwarding is concerned about where the packet came fromuMulticast Forwarding uses“Reverse Path Forwarding”33组播转发A router forwards a multicast datagram only if received on the up stream interface to the source(i.e.it follows the distribution tree)The routing table used for multicasting is checked against the“source”IP address in the packet If the datagram arrived on the interface specified in the routing table for the source address;then the RPF check succeeds Otherwise,the RPF Check failsReverse Path Forwarding(RPF)34组播转发Source151.10.3.21Example:RPF CheckingMcast Packets35组播转发RPF Check Fails!Unicast Route TableNetwork Interface151.10.0.0/16S1198.14.32.0/24S0204.1.16.0/24E0A closer look:RPF Check FailsPacket Arrived on Wrong Interface!E0S1S0S2Multicast Packet fromSource 151.10.3.21XDiscard Packet!36组播转发A closer look:RPF Check Succeeds!E0S1S0S2Multicast Packet fromSource 151.10.3.21Packet Arrived on Correct Interface!Forward out all outgoing interfaces.(i.e.down the distribution tree)37主要内容u为什么需要组播？u组播地址u主机和路由器的交互：IGMP u组播分发树u组播转发u域内组播路由协议u域间组播路由协议uIPv638Multicast Routing is not unicast routingu You have to think of it differentlyu It is not like OSPFu It is not like RIPu It is not like anything you may be familiar with组播路由和单播路由39组播路由协议的类型uDense-mode Uses“Push”Model Traffic Flooded throughout network Pruned back where it is unwanted Flood&Prune behavior(typically every 3 minutes)uSparse-mode Uses“Pull”Model Traffic sent only to where it is requested Explicit Join behavior40域内组播路由协议概况uCurrently,there are four multicast routing protocols DVMRPv3(Internet-draft)DVMRPv1(RFC 1075)is obsolete and unused.A variant is currently implemented MOSPF(RFC 1584)PIM-DM(Internet-draft)PIM-SM(RFC 2362-v2)Others(CBT,OCBT,QOSMIC,SM,etc.)41uDense Mode Protocol Distance vector-based Similar to RIP Infinity=32 hops Subnet masks in route advertisements DVMRP Routes used For RPF Check To build Truncated Broadcast Trees(TBTs)Uses special“Poison-Reverse”mechanismDVMRP概况42DVMRP概况uDense Mode Protocol Uses Flood and Prune operation Traffic initially flooded down TBTs TBT branches are pruned where traffic is unwanted Prunes periodically time-out causing reflooding43DVMRPSource TreesRoute for source network of metric“n”nmSource NetworkEXYABCD 234Poison reverse(metric+infinity)sent to upstream“parent”routerRouter depends on“parent”to receive traffic for this source2233331113535Truncated Broadcast Trees Are Built using Best DVMRP Metrics Back to Source NetworkLowest IP Address Used in Case of a Tie(Note:IP Address of D C B A)33mroutedmroutedmroutedmroutedmroutedResulting Truncated Broadcast Tree for Source Network mroutedmrouted44DVMRPSource TreesForwarding onto Multi-access Networks Network XABC 211mroutedmroutedmroutedRoute advertisement for network X of metric“n”n Both B and C have routes to network X.To avoid duplicates,only one router can be“Designated Forwarder”for network X.Router with best metric is elected as the“Designated Forwarder”.Lowest IP address used as tie-breaker.Router C wins in this example.(Note:IP Address of C B)45EXYABCD DVMRPSource TreesResulting Truncated Broadcast Tree for Source Network“S1”Source Network“S1”S1 Source Treemroutedmroutedmroutedmroutedmroutedmroutedmrouted46DVMRPSource TreesEach Source Network has its Own Truncated Broadcast Tree EXYABCD Note:IP Address of D C B A S2 Source TreeSource“S2”mroutedmroutedmroutedmroutedmroutedmroutedmrouted47DVMRPFlood&PruneSource“S”Receiver 1(Group“G”)Truncated Broadcast Tree based on DVMRP route metrics(S,G)Multicast Packet FlowInitial Flooding of(S,G)Multicast Packets Down Truncated Broadcast TreeEXYABCD mroutedmroutedmroutedmroutedmroutedmroutedmrouted48DVMRPFlood&PruneRouters C is a Leaf Node so it sends an“(S,G)Prune”MessageSource“S”Receiver 1(Group“G”)EXYABCD mroutedRouter B Prunes interface.mroutedmroutedmroutedmroutedmroutedmroutedTruncated Broadcast Tree based on DVMRP route metrics(S,G)Multicast Packet Flow49DVMRPFlood&PruneRouters X,and Y are also Leaf Nodesso they send“Prune(S,G)”Messages PrunePruneSource“S”Receiver 1(Group“G”)EXYABCD mroutedmroutedmroutedmroutedmroutedmroutedRouter E prunes interface.mroutedTruncated Broadcast Tree based on DVMRP route metrics(S,G)Multicast Packet Flow50DVMRPFlood&PruneRouter E is now a Leaf Node;it sends an(S,G)Prune message.Source“S”Receiver 1(Group“G”)EXYABCD mroutedmroutedmroutedmroutedmroutedmroutedRouter D prunes interface.mroutedTruncated Broadcast Tree based on DVMRP route metrics(S,G)Multicast Packet Flow51DVMRPFlood&PruneFinal Pruned State Source“S”Receiver 1(Group“G”)EXYABCD mroutedmroutedmroutedmroutedmroutedmroutedmroutedTruncated Broadcast Tree based on DVMRP route metrics(S,G)Multicast Packet Flow52Receiver 2 joins Group“G”Receiver 2(Group“G”)Router Y sends a“Graft(S,G)”MessageDVMRPGraftingSource“S”Receiver 1(Group“G”)EXYABCD mroutedmroutedmroutedmroutedmroutedmroutedmroutedTruncated Broadcast Tree based on DVMRP route metrics(S,G)Multicast Packet Flow53DVMRPGraftingRouter E Responds with a“Graft-Ack”Sends its Own“Graft(S,G)Message Receiver 2(Group“G”)Source“S”Receiver 1(Group“G”)EXYABCD mroutedmroutedmroutedmroutedmroutedmroutedmroutedTruncated Broadcast Tree based on DVMRP route metrics(S,G)Multicast Packet Flow54Receiver 2(Group“G”)Source“S”Receiver 1(Group“G”)EXYABCD mroutedmroutedmroutedmroutedmroutedDVMRPGraftingRouter D Responds with a“Graft-Ack”Graft-AckBegins Forwarding(S,G)Packets mroutedmroutedTruncated Broadcast Tree based on DVMRP route metrics(S,G)Multicast Packet Flow55DVMRPEvaluationuWidely used on the MBONE(being phased out)uSignificant scaling problems Slow ConvergenceRIP-like behavior Significant amount of multicast routing state information stored in routers(S,G)everywhere No support for shared trees Maximum number of hops 32uNot appropriate for large scale production networks Due to flood and prune behavior Due to its poor scalability56MOSPF(RFC 1584)uExtension to OSPF unicast routing protocol OSPF:Routers use link state advertisements to understand all available links in the network(route messages along least-cost paths)MOSPF:Includes multicast information in OSPF link state advertisements to construct multicast distribution trees(each router maintains an up-to-date image of the topology of the entire network)57MOSPF(RFC 1584)uGroup membership LSAs are flooded throughout the OSPF routing domain so MOSPF routers can compute outgoing interface listsuUses Dijkstra algorithm to compute shortest-path tree Separate calculation is required for each(SNet,G)pair58Membership LSAsMembership LSAsArea 1Area 2MABR1MABR2Area 0MOSPF Membership LSAsMBMBMAMAMA59Area 1Area 2(S1,B)(S2,A)MOSPF Intra-Area TrafficMAMAMBMBMANot receiving(S2,A)trafficMABR1MABR2Area 060MOSPF Inter-Area TrafficArea 1Area 2MAMAMBMBMAWildcard Receiver Flag(*,*)Wildcard Receiver Flag(*,*)(S1,B)(S2,A)Wildcard Receivers“pull”traffic from all sources in the area.MABR1MABR2Area 061MOSPF Inter-Area TrafficArea 1Area 2MAMAMBMBMA(S1,B)(S2,A)MABR1MABR2Area 062(S1,B)(S2,A)(GA,GB)(GA)Area 1Area 2MABR1MABR2MOSPF Inter-Area TrafficMAMAMAMBMBSummarizedMembership LSASummarizedMembership LSAMABR routers inject Summary Membership LSAs into Area 0.Area 0Membership LSAsMembership LSAs63Area 1Area 2MABR1(S1,B)(S2,A)MABR2MOSPF Inter-Area TrafficMAMAMBMBMAArea 064Area 1Area 2MABR1(S1,B)(S2,A)MABR2MOSPF Inter-Area TrafficWildcard Receiver Flag(*,*)Wildcard Receiver Flag(*,*)Area 065(GA,GB)(GA)Area 1Area 2MABR1MABR2MOSPF Inter-Domain TrafficMAMAMAMBMBSummarizedMembership LSASummarizedMembership LSAExternal ASMASBRArea 0Membership LSAsMembership LSAs66MOSPF Inter-Domain Traffic(S2,B)External ASArea 1Area 2MAMABR1MAMBMBMAMABR2MASBR(S1,A)Area 067External ASArea 1Area 2MABR1(S1,B)(S2,A)MABR2MASBRMOSPF Inter-Domain TrafficWildcard Receiver Flag(*,*)Wildcard Receiver Flag(*,*)Unnecessary traffic may flow all the way to the MASBR Router!Area 068MOSPFEvaluationuAppropriate for use within single routing domainuFlood multicast traffic everywhere to create state,Uses LSAs and the link-state databaseuProtocol dependent works only in OSPF-based networks69MOSPFEvaluationuSignificant scaling problems Dijkstra algorithm run for EVERY multicast(SNet,G)pair!Dijkstra algorithm rerun when:Group Membership changes Line-flaps Does not support shared-trees uNot appropriate for General purpose multicast networks where the number of senders may be quite large IP/TV(Every IP/TV client is a multicast source)70PIM-DMuProtocol Independent Supports all underlying unicast routing protocols including:static,RIP,IGRP,EIGRP,IS-IS,BGP,and OSPFuUses reverse path forwarding Floods network and prunes back based on multicast group membership Assert mechanism used to prune off redundant flowsuAppropriate for.Densely distributed receivers located in close proximity to source Few senders-to-many receivers(due to frequent flooding)71PIM-DM Flood&PruneSourceInitial FloodingReceiverMulticast Packets(S,G)State created inrouter in the network!72PIM-DM Flood&PruneSourcePruning Unwanted TrafficReceiverMulticast Packets Messages73PIM-DM Flood&PruneResults After PruningSourceReceiverMulticast PacketsFlood&Prune processrepeats every 3 minutes!(S,G)State still exists inevery router in the network!74PIM-DM Assert MechanismE0Incoming Multicast Packet(Successful RPF Check)E0S0 Routers receive packet on an interface in their“oilist”!Only one router should continue sending to avoid duplicate packetsS0Routers send“PIM Assert”messagesAssert AssertCompare distance and metric valuesRouter with best route to source winsIf metric&distance equal,highest IP adr winsLosing router stops sending(prunes interface)75PIM-DM EvaluationuMost effective for large number of densely distributed receivers located in close proximity to sourceuAdvantages:Easy to configuretwo commands ip pim dense-mode Simple flood and prune mechanismuPotential issues.Inefficient flood and prune behavior Complex Assert mechanism Mixed control and data planes Results in(S,G)state in every router in the network No support for shared trees76PIM-SM(RFC 2362)uSupports both source and shared trees Assumes no hosts want multicast traffic unless they specifically ask for ituUses a Rendezvous Point(RP)Senders and Receivers“rendezvous”at this point to learn of each others existence Senders are“registered”with RP by their first-hop router Receivers are“joined”to the Shared Tree(rooted at the RP)by their local Designated Router(DR)uAppropriate for Wide scale deployment for both densely and sparsely populated groups in the enterprise Optimal choice for all production networks regardless of size and membership density77PIM-SM Shared Tree JoinReceiverRP(*,G)JoinShared Tree(*,G)State created onlyalong the Shared Tree.78PIM-SM Sender RegistrationReceiverRP(S,G)JoinSourceShared Tree(S,G)Register(unicast)Source Tree(S,G)State created onlyalong the Source Tree.Traffic Flow79PIM-SM Sender RegistrationReceiverRPSourceShared TreeSource TreeRP sends a Register-Stop back to the first-hop router to stop the Register process.(S,G)Register-Stop(unicast)Traffic Flow(S,G)Register(unicast)(S,G)traffic begins arriving at the RP via the Source tree.80PIM-SM Sender RegistrationReceiverRPSourceShared TreeSource TreeTraffic FlowSource traffic flows nativelyalong SPT to RP.From RP,traffic flows downthe Shared Tree to Receivers.81PIM-SM SPT SwitchoverReceiverRP(S,G)JoinSourceSource TreeShared TreeLast-hop router joins the Source Tree.Additional(S,G)State is created along new part of the Source Tree.Traffic Flow82PIM-SM SPT SwitchoverReceiverRPSourceSource TreeShared Tree(S,G)RP-bit PruneTraffic begins flowing down the new branch of the Source Tree.Additional(S,G)State is created along the Shared Tree to prune off(S,G)traffic.Traffic Flow83PIM-SM SPT SwitchoverReceiverRPSource(S,G)Traffic flow is now pruned off of the Shared Tree and is flowing to the Receiver via the Source Tree.Source TreeShared TreeTraffic Flow84PIM-SM SPT SwitchoverReceiverRPSourceSource TreeShared Tree(S,G)traffic flow is no longer needed by the RP so it Prunes the flow of(S,G)traffic.Traffic Flow(S,G)Prune85PIM-SM SPT SwitchoverReceiverRPSource(S,G)Traffic flow is now only flowing to the Receiver via a single branch of the Source Tree.Source TreeShared TreeTraffic Flow86PIM-SM FFFuThe default behavior of PIM-SM in Cisco IOS is that routers with directly connected members will join the Shortest Path Tree as soon as they detect a new multicast sourcePIM-SM Frequently Forgotten Fact87PIM-SMEvaluationuEffective for sparse or dense distribution of multicast receiversuAdvantages:Traffic only sent down“joined”branches Can switch to optimal source-trees for high traffic sources dynamically Unicast routing protocol-independent Basis for inter-domain multicast routing When used with MBGP and MSDP88主要内容u为什么需要组播？u组播地址u主机和路由器的交互：IGMP u组播分发树u组播转发u域内组播路由协议u域间组播路由协议uIPv689域间组播路由协议uBGMP(Border Gateway Multicast Protocol)(未来)(Internet-draft)uMSDP(Multicast Source Discover Protocol)(RFC 3618)uMBGP(Multi-protocol BGP)(RFC 2283)uSSM(Source Specific Multicast)(RFC 3569)90域间组播路由协议BGMPuBGMP(边界网关组播协议)u基本思想对在网络中活动的任何组播组,存在一个单单独的双向共享树独的双向共享树,该共享树可以跨越包含该组发送者或接收者的所有域u组播的根域应该是这样的一个域它拥有一个特定的特定的组播地址范围 91域间组播路由协议BGMPu任何组播组都存在跨越域的双向共享树u显式加入模型u发向根域的加入和剪枝u每个组单根域u需要BGP4+必须携带NLRI区域中的组前缀需要建立双向树u要求严格的层次化的地址分配MASC被推荐为分配方式92BGMPA host in C joins to Group GDomainADomainEDomainCDomainDDomainBDomainFRoot domainC1A2E1A1A4A3D1B1B2F1F2joinjoinjoin93BGMPTree constructed,data goes to CDomainADomainEDomainCDomainDDomainBDomainFRoot domainC1A2E1A1A4A3D1B1B2F1F294BGMPDomain E joins to GDomainADomainEDomainCDomainDDomainBDomainFjoinC1A2E1A1A4A3D1B1B2F1F2join95BGMPtree constructed.Data goes to EDomainADomainEDomainCDomainDDomainBDomainFC1A2E1A1A4A3D1B1B2F1F296理想与现实uBGMP和MASC非常遥远两者都非常难以实施仍处于IETF草案提案阶段uISP目前要部署组播,解决方案如何?97Interdomain MulticastCampus MulticastMulticast ComponentsEnd-to-End ArchitectureEnd-to-End ArchitectureuEnd Stations(hosts-to-routers):IGMPuSwitches(Layer 2 optimization):CGMP,IGMP Snooping or RGMPuRouters(Multicast Forwarding Protocol):PIM SM or Bidirectional PIMuMulticast routing across domains MBGP uMulticast Source Discovery MSDP with PIM-SMuSource Specific Multicast PIM-SSMISP B Multicast SourceY ISP A Multicast Sourc