Internet组播简介.ppt

清华大学计算机系Internet组播简介1主要内容u为什么需要组播？u组播地址u主机和路由器的交互：IGMP u组播分发树u组播转发u域内组播路由协议u域间组播路由协议uIPv62主要内容u为什么需要组播？u组播地址u主机和路由器的交互：IGMP u组播分发树u组播转发u域内组播路由协议u域间组播路由协议uIPv63ServerRouterUnicastServerRouterMulticast单播和组播的比较4Example:Audio StreamingAll clients listening to the same 8 Kbps audio0TrafficMbps120406080100#ClientsMulticastUnicast组播的优势uuEnhanced EfficiencyEnhanced Efficiency:Controls network traffic and reduces server and CPU loadsuuOptimized PerformanceOptimized Performance:Eliminates traffic redundancyuuDistributed ApplicationsDistributed Applications:Makes multipoint applications possible5组播带来的问题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的！的！6组播带来的问题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 packets7组播的应用uMultimediaStreaming media,IPTVTraining,corporate communications Conferencingvideo/audiouNet GameuAny one-to-many data push applications8主要内容u为什么需要组播？u组播地址u主机和路由器的交互：IGMP u组播分发树u组播转发u域内组播路由协议u域间组播路由协议uIPv69uIPv4 Multicast Group Addresses Class“D”Address Space High order bits of 1st Octet=“1110”uReserved Link-local Addresses Transmitted with TTL=1 Examples:224.0.0.1 All systems on this subnet224.0.0.2 All routers on this subnet224.0.0.4 DVMRP routers224.0.0.5 OSPF routers224.0.0.13 PIMv2 routers组播地址 10uAdministratively Scoped AddressesPrivate address spaceSimilar to RFC1918 unicast addressesNot used for global Internet trafficUsed to limit“scope”of multicast trafficSame addresses may be in use at different locations for different multicast sessionsExamples组播地址 1132 Bits28 Bits25 Bits23 Bits48 Bits01-00-501-00-5e-7f-00-01e-7f-00-0111105 BitsLost组播地址IP Multicast MAC Address Mapping(FDDI and Ethernet)12 .01-Multicast MAC Address(FDDI and Ethernet)32-IP Multicast Addresses组播地址Be Aware of the 32:1 Address OverlapBe Aware of the 32:1 Address OverlapIP Multicast MAC Address Mapping(FDDI&Ethernet)13组播地址 uDynamic Group Address AssignmentHistorically accomplished using SDR applicationSessions/groups announced over well-known multicast groupsAddress collisions detected and resolved at session creation timeHas problems scaling14组播地址 uFuture dynamic techniques under considerationMulticast Address Set-Claim(MASC)Hierarchical,dynamic address allocation schemeExtremely complex garbage-collection problem Long ways offMADCAPSimilar to DHCPNeed application and host stack support15组播地址 uStatic Group Address AssignmentTemporary method to meet immediate needsYour AS number is inserted in middle two octetsRemaining low-order octet used for group assignmentDefined in IETF RFC3180GLOP Addressing in 233/816主要内容u为什么需要组播？u组播地址u主机和路由器的交互：IGMP u组播分发树u组播转发u域内组播路由协议u域间组播路由协议uIPv617Routers solicit group membership from directly connected hostsRFC 1112 specifies version 1 of IGMPRFC 2236 specifies version 2 of IGMPRFC 3376 specifies version 3 of IGMPSupported on latest service pack for Windows and most UNIX systemsHow hosts tell routers about group membership主机和路由器的交互：IGMP18H3uHost sends IGMP Report to join groupH3224.1.1.1ReportH1H2Joining a Group主机和路由器的交互：IGMP19uRouter sends periodic QueriesQueryOne member per group per subnet reports224.1.1.1ReportOther members suppress reports224.1.1.1SuppressedX224.1.1.1SuppressedXH1H2H3Maintaining a Group主机和路由器的交互：IGMP20Host quietly leaves groupH1H3H3#1Router sends 3 General Queries(60 secs apart)General Query#2No IGMP Report for the group is receivedGroup times out(Worst case delay=3 minutes)H2Leaving a Group(IGMPv1)主机和路由器的交互：IGMP21H1H3H3Leave to224.0.0.2224.1.1.1#1#1Group SpecificQuery to 224.1.1.1#2#2No IGMP Report is received within 3 secondsGroup 224.1.1.1 times outH2Leaving a Group(IGMPv2)主机和路由器的交互：IGMP22IGMPv3uRFC3376uEnables hosts to listen only to a specified subset of the hosts sending to the group23R1R3R2With IGMP,specific sources can be pruned back-S=2.2.2.2 in this caseIGMPv3:IGMPv324主要内容u为什么需要组播？u组播地址u主机和路由器的交互：IGMP u组播分发树u组播转发u域内组播路由协议u域间组播路由协议uIPv625Shortest Path or Source Distribution TreeReceiver 1BEADFSource 1Notation:(S,G)S=Source G=GroupCReceiver 2Source 2组播分发树26Receiver 1BEADFSource 1Notation:(S,G)S=Source G=GroupCReceiver 2Source 2组播分发树Shortest Path or Source Distribution Tree27组播分发树Shared Distribution TreeReceiver 1BEAD FNotation:(*,G)*=All Sources G=GroupCReceiver 2(RP)PIM Rendezvous PointShared Tree(RP)28组播分发树Shared Distribution TreeReceiver 1BEAFSource 1Notation:(*,G)*=All Sources G=GroupCReceiver 2Source 2(RP)PIM Rendezvous PointShared TreeSource TreeD(RP)29组播分发树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 Trees30主要内容u为什么需要组播？u组播地址u主机和路由器的交互：IGMP u组播分发树u组播转发u域内组播路由协议u域间组播路由协议uIPv631组播转发uMulticast Forwarding is backwards from Unicast ForwardingUnicast Forwarding is concerned about where the packet is goingMulticast Forwarding is concerned about where the packet came fromuMulticast Forwarding uses“Reverse Path Forwarding”32组播转发 What is RPF?What is RPF?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 RPF CheckThe RPF Check 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)33组播转发Example:RPF CheckingMcast PacketsRPF Check FailsRPF Check Fails Packet arrived on wrong interface!Packet arrived on wrong interface!34组播转发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!E0S1S0S2S1S1Multicast Packet fromSource 151.10.3.21XDiscard Packet!35组播转发A closer look:RPF Check SucceedsRPF Check Succeeds!Unicast Route TableUnicast Route TableNetworkNetwork Interface Interface151.10.0.0/16151.10.0.0/16S1S1198.14.32.0/24198.14.32.0/24S0S0204.1.16.0/24204.1.16.0/24E0E0E0S1S0S2Multicast Packet fromSource 151.10.3.21Packet Arrived on Correct Interface!S1S1Forward out all outgoing interfaces.(i.e.down the distribution tree)36主要内容u为什么需要组播？u组播地址u主机和路由器的交互：IGMP u组播分发树u组播转发u域内组播路由协议u域间组播路由协议uIPv637Multicast 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组播路由和单播路由38组播路由协议的类型uDense-modeUses“Push”ModelTraffic Flooded throughout networkPruned back where it is unwantedFlood&Prune behavior(typically every 3 minutes)uSparse-modeUses“Pull”ModelTraffic sent only to where it is requestedExplicit Join behavior39域内组播路由协议概况uCurrently,there are four multicast routing protocolsDVMRPv3(Internet-draft)DVMRPv1(RFC 1075)is obsolete and unused.A variant is currently implementedMOSPF(RFC 1584)PIM-DM(Internet-draft)PIM-SM(RFC 2362-v2)Others(CBT,OCBT,QOSMIC,SM,etc.)40uDense Mode ProtocolDistance vector-basedSimilar to RIPInfinity=32 hopsSubnet masks in route advertisementsDVMRP Routes usedFor RPF CheckTo build Truncated Broadcast Trees(TBTs)Uses special“Poison-Reverse”mechanismDVMRP概况41DVMRP概况uDense Mode ProtocolUses Flood and Prune operationTraffic initially flooded down TBTsTBT branches are pruned where traffic is unwantedPrunes periodically time-out causing reflooding42DVMRPSource 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 mroutedmrouted43DVMRPSource TreesForwarding onto Multi-access Networks Network XABC 22 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)44EXYABCD DVMRPSource TreesResulting Truncated Broadcast Tree for Source Network“S1”Source Network“S1”S1 Source Treemroutedmroutedmroutedmroutedmroutedmroutedmrouted45DVMRPSource TreesEach Source Network has its Own Truncated Broadcast Tree EXYABCD Note:IP Address of D C B A S2 Source TreeSource“S2”mroutedmroutedmroutedmroutedmroutedmroutedmrouted46DVMRPFlood&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 mroutedmroutedmroutedmroutedmroutedmroutedmrouted47DVMRPFlood&PruneRouters C is a Leaf Node so it sends an“(S,G)Prune”MessagePrunePruneSource“S”Receiver 1(Group“G”)EXYABCD mroutedRouter B Prunes interface.mroutedmroutedmroutedmroutedmroutedmroutedTruncated Broadcast Tree based on DVMRP route metrics(S,G)Multicast Packet Flow48DVMRPFlood&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 Flow49DVMRPFlood&PruneRouter E is now a Leaf Node;it sends an(S,G)Prune message.PrunePruneSource“S”Receiver 1(Group“G”)EXYABCD mroutedmroutedmroutedmroutedmroutedmroutedRouter D prunes interface.mroutedTruncated Broadcast Tree based on DVMRP route metrics(S,G)Multicast Packet Flow50DVMRPFlood&PruneFinal Pruned State Source“S”Receiver 1(Group“G”)EXYABCD mroutedmroutedmroutedmroutedmroutedmroutedmroutedTruncated Broadcast Tree based on DVMRP route metrics(S,G)Multicast Packet Flow51Receiver 2 joins Group“G”Receiver 2(Group“G”)Router Y sends a“Graft(S,G)”MessageGraftGraftDVMRPGraftingSource“S”Receiver 1(Group“G”)EXYABCD mroutedmroutedmroutedmroutedmroutedmroutedmroutedTruncated Broadcast Tree based on DVMRP route metrics(S,G)Multicast Packet Flow52DVMRPGraftingRouter E Responds with a“Graft-Ack”Graft-AckGraft-AckSends its Own“Graft(S,G)Message GraftGraftReceiver 2(Group“G”)Source“S”Receiver 1(Group“G”)EXYABCD mroutedmroutedmroutedmroutedmroutedmroutedmroutedTruncated Broadcast Tree based on DVMRP route metrics(S,G)Multicast Packet Flow53Receiver 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 Flow54DVMRPEvaluationuWidely used on the MBONE(being phased out)uSignificant scaling problemsSlow ConvergenceRIP-like behaviorSignificant amount of multicast routing state information stored in routers(S,G)everywhere No support for shared treesMaximum number of hops 32uNot appropriate for large scale production networksDue to flood and prune behaviorDue to its poor scalability55MOSPF(RFC 1584)uExtension to OSPF unicast routing protocolOSPF: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)56MOSPF(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 treeSeparate calculation is required for each(SNet,G)pair57Membership LSAsMembership LSAsArea 1Area 2MABR1MABR2Area 0MOSPF Membership LSAsMBMBMAMAMA58Area 1Area 2(S1,B)(S2,A)MOSPF Intra-Area TrafficMAMAMBMBMANot receiving(S2,A)trafficMABR1MABR2Area 059MOSPF 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 060MOSPF Inter-Area TrafficArea 1Area 2MAMAMBMBMA(S1,B)(S2,A)MABR1MABR2Area 061(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 LSAs62Area 1Area 2MABR1(S1,B)(S2,A)MABR2MOSPF Inter-Area TrafficMAMAMBMBMAArea 063Area 1Area 2MABR1(S1,B)(S2,A)MABR2MOSPF Inter-Area TrafficWildcard Receiver Flag(*,*)Wildcard Receiver Flag(*,*)Unnecessary traffic Unnecessary traffic still flowing to the still flowing to the MABR Routers!MABR Routers!Area 064(GA,GB)(GA)Area 1Area 2MABR1MABR2MOSPF Inter-Domain TrafficMAMAMAMBMBSummarizedMembership LSASummarizedMembership LSAExternal ASMASBRArea 0Membership LSAsMembership LSAs65MOSPF Inter-Domain Traffic(S2,B)External ASArea 1Area 2MAMABR1MAMBMBMAMABR2MASBR(S1,A)Area 066External 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 067MOSPFEvaluationuAppropriate for use within single routing domainuFlood multicast traffic everywhere to create state,Uses LSAs and the link-state databaseuProtocol dependentworks only in OSPF-based networks68MOSPFEvaluationuSignificant scaling problemsDijkstra algorithm run for EVERY multicast(SNet,G)pair!Dijkstra algorithm rerun when:Group Membership changesLine-flapsDoes not support shared-trees uNot appropriate forGeneral purpose multicast networks where the number of senders may be quite largeIP/TV(Every IP/TV client is a multicast source)69PIM-DMuProtocol IndependentSupports all underlying unicast routing protocols including:static,RIP,IGRP,EIGRP,IS-IS,BGP,and OSPFuUses reverse path forwardingFloods network and prunes back based on multicast group membershipAssert mechanism used to prune off redundant flowsuAppropriate for.Densely distributed receivers located in close proximity to sourceFew senders-to-many receivers(due to frequent flooding)70PIM-DM Flood&PruneSourceInitial FloodingReceiverMulticast Packets(S,G)State created inevery every router in the network!71PIM-DM Flood&PruneSourcePruning Unwanted TrafficReceiverMulticast PacketsPrunePrune Messages72PIM-DM Flood&PruneResults After PruningSourceReceiverMulticast PacketsFlood&Prune processrepea