Internet组播简介.

1、清华大学计算机系Internet组播简介1主要内容为什么需要组播？组播地址主机和路由器的交互：IGMP 组播分发树组播转发域内组播路由协议域间组播路由协议IPv62主要内容为什么需要组播？组播地址主机和路由器的交互：IGMP 组播分发树组播转发域内组播路由协议域间组播路由协议IPv63ServerRouterUnicastServerRouterMulticast单播和组播的比较4Example: Audio StreamingAll clients listening to the same 8 Kbps audio0TrafficMbps120406080100# ClientsMulti

2、castUnicast组播的优势Enhanced Efficiency: Controls network traffic and reduces server and CPU loadsOptimized Performance: Eliminates traffic redundancyDistributed Applications: Makes multipoint applications possible5组播带来的问题Best Effort Delivery: Drops are to be expected. Multicast applications should not

3、expect reliable delivery of data and should be designed accordingly. Reliable Multicast is still an area for much research No Congestion Avoidance: Lack of TCP windowing and “slow-start” mechanisms can result in network congestion. If possible, Multicast applications should attempt to detect and avo

4、id congestion conditions组播是基于UDP的！6组播带来的问题Duplicates: Some multicast protocol mechanisms (e.g. Asserts, Registers and SPT Transitions) result in the occasional generation of duplicate packetsOut of Order Delivery: Some protocol mechanisms may also result in out of order delivery of packets7组播的应用Mult

5、imediaStreaming media, IPTVTraining, corporate communications Conferencingvideo/audioNet GameAny one-to-many data push applications8主要内容为什么需要组播？组播地址主机和路由器的交互：IGMP 组播分发树组播转发域内组播路由协议域间组播路由协议IPv69IPv4 Multicast Group Addresses Class “D” Address Space High order bits of 1st Octet = “1110”Reserved Link-l

6、ocal 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组播地址 10Administratively Scoped AddressesPrivate address spaceSimilar to RFC1918 unicast addressesNot used for

7、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-5e-7f-00-0111105 BitsLost组播地址IP Multicast MAC Address Mapping(FDDI and Ethernet)12 . . .01 - Mu

8、lticast MAC Address(FDDI and Ethernet)32 - IP Multicast Addresses组播地址Be Aware of the 32:1 Address OverlapIP Multicast MAC Address Mapping(FDDI & Ethernet)13组播地址 Dynamic Group Address AssignmentHistorically accomplished using SDR applicationSessions/groups announced over well-known multicast groupsAd

9、dress collisions detected and resolved at session creation timeHas problems scaling14组播地址 Future dynamic techniques under considerationMulticast Address Set-Claim (MASC)Hierarchical, dynamic address allocation schemeExtremely complex garbage-collection problem Long ways offMADCAPSimilar to DHCPNeed

10、application and host stack support15组播地址 Static 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主要内容为什么需要组播？组播地址主机和路由器的交互：IGMP 组播分发树组播转发域

11、内组播路由协议域间组播路由协议IPv617Routers 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 membersh

12、ip主机和路由器的交互：IGMP18H3Host sends IGMP Report to join groupH3224.1.1.1ReportH1H2Joining a Group主机和路由器的交互：IGMP19Router sends periodic QueriesQueryOne member per group per subnet reports224.1.1.1ReportOther members suppress reports224.1.1.1SuppressedX224.1.1.1SuppressedXH1H2H3Maintaining a Group主机和路由器的交互

13、：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#1Group SpecificQuery to 224.1.1.1#2No

14、IGMP Report is received within 3 secondsGroup 224.1.1.1 times outH2Leaving a Group (IGMPv2)主机和路由器的交互：IGMP22IGMPv3RFC3376Enables 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

15、主要内容为什么需要组播？组播地址主机和路由器的交互：IGMP 组播分发树组播转发域内组播路由协议域间组播路由协议IPv625Shortest 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 Dis

16、tribution 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

17、TreeSource TreeD (RP)29组播分发树 Source or Shortest Path treesuses more memory O(S G)but you get optimal paths from source to all receiversminimizes delay Shared treesuses less memory O(G)but you may get sub-optimal paths from source to all receiversmay introduce extra delayCharacteristics of Distributi

18、on Trees30主要内容为什么需要组播？组播地址主机和路由器的交互：IGMP 组播分发树组播转发域内组播路由协议域间组播路由协议IPv631组播转发Multicast Forwarding is backwards from Unicast ForwardingUnicast Forwarding is concerned about where the packet is goingMulticast Forwarding is concerned about where the packet came fromMulticast Forwarding uses “Reverse Pat

19、h Forwarding”32组播转发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 Check The routing table used for multicasting is checked against the “source” IP address in the packet If the datagram arrive

20、d 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 Fails Packet arrived on wrong interface!34组播转发RPF Check Fails! Unicast Route TableNetwork

21、 Interface151.10.0.0/16S1198.14.32.0/24S0204.1.16.0/24E0A closer look: RPF Check FailsPacket Arrived on Wrong Interface!E0S1S0S2S1Multicast Packet fromSource 151.10.3.21XDiscard Packet!35组播转发A closer look: RPF Check SucceedsRPF Check Succeeds! Unicast Route TableNetwork Interface151.10.0.0/16S1198.1

22、4.32.0/24S0204.1.16.0/24E0E0S1S0S2Multicast Packet fromSource 151.10.3.21Packet Arrived on Correct Interface!S1Forward out all outgoing interfaces.(i. e. down the distribution tree)36主要内容为什么需要组播？组播地址主机和路由器的交互：IGMP 组播分发树组播转发域内组播路由协议域间组播路由协议IPv637Multicast Routing is not unicast routing You have to th

23、ink of it differently It is not like OSPF It is not like RIP It is not like anything you may be familiar with组播路由和单播路由38组播路由协议的类型Dense-modeUses “Push” ModelTraffic Flooded throughout networkPruned back where it is unwantedFlood & Prune behavior (typically every 3 minutes)Sparse-modeUses “Pull” Model

24、Traffic sent only to where it is requestedExplicit Join behavior39域内组播路由协议概况Currently, 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 (C

25、BT, OCBT, QOSMIC, SM, etc.)40Dense 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概况Dense Mode ProtocolUses Flood and Pru

26、ne 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

27、 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 Sour

28、ce Network mroutedmrouted43DVMRPSource TreesForwarding onto Multi-access Networks Network XABC 2211mroutedmroutedmroutedRoute 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 wit

29、h 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 Treemroutedmroutedmroutedmroutedm

30、routedmroutedmrouted45DVMRPSource 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 rou

31、te 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” MessagePruneSource “S”Receiver 1(Group “G”)EXYABCD mrou

32、tedRouter 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 mrou

33、tedmroutedmroutedmroutedmroutedmroutedRouter 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.PruneSource “S”Receiver 1(Group “G”)EXYABCD mroutedmroutedmrouted

34、mroutedmroutedmroutedRouter 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 DVM

35、RP route metrics (S, G) Multicast Packet Flow51Receiver 2 joins Group “G”Receiver 2(Group “G”)Router Y sends a “Graft (S, G)” MessageGraftDVMRPGraftingSource “S”Receiver 1(Group “G”)EXYABCD mroutedmroutedmroutedmroutedmroutedmroutedmroutedTruncated Broadcast Tree based on DVMRP route metrics (S, G)

36、Multicast Packet Flow52DVMRPGraftingRouter E Responds with a “Graft-Ack”Graft-AckSends its Own “Graft (S, G) Message GraftReceiver 2(Group “G”)Source “S”Receiver 1(Group “G”)EXYABCD mroutedmroutedmroutedmroutedmroutedmroutedmroutedTruncated Broadcast Tree based on DVMRP route metrics (S, G) Multicas

37、t 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 Flow54D

38、VMRPEvaluationWidely used on the MBONE (being phased out)Significant 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 32Not appropriate for large scale produc

39、tion networksDue to flood and prune behaviorDue to its poor scalability55MOSPF (RFC 1584)Extension 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

40、 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)Group membership LSAs are flooded throughout the OSPF routing domain so MOSPF routers can compute outgoing interface listsUs

41、es 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) trafficMABR1MAB

42、R2Area 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

43、 , 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 063Are

44、a 1Area 2MABR1(S1 , B)(S2 , A)MABR2MOSPF Inter-Area TrafficWildcard Receiver Flag(*, *)Wildcard Receiver Flag(*, *)Unnecessary traffic still flowing to the MABR Routers!Area 064(GA , GB)(GA )Area 1Area 2MABR1MABR2MOSPF Inter-Domain TrafficMAMAMAMBMBSummarizedMembership LSASummarizedMembership LSAExt

45、ernal 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 tra

46、ffic may flow all the way to the MASBR Router!Area 067MOSPFEvaluationAppropriate for use within single routing domainFlood multicast traffic everywhere to create state, Uses LSAs and the link-state databaseProtocol dependentworks only in OSPF-based networks68MOSPFEvaluationSignificant scaling proble

47、msDijkstra algorithm run for EVERY multicast (SNet, G) pair!Dijkstra algorithm rerun when:Group Membership changesLine-flapsDoes not support shared-trees Not appropriate forGeneral purpose multicast networks where the number of senders may be quite largeIP/TV(Every IP/TV client is a multicast source

48、)69PIM-DMProtocol IndependentSupports all underlying unicast routing protocols including: static, RIP, IGRP, EIGRP, IS-IS, BGP, and OSPFUses reverse path forwardingFloods network and prunes back based on multicast group membershipAssert mechanism used to prune off redundant flowsAppropriate for.Dens

49、ely 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 router in the network!71PIM-DM Flood & PruneSourcePruning Unwanted TrafficReceiver

50、Multicast PacketsPrune Messages72PIM-DM Flood & PruneResults After PruningSourceReceiverMulticast PacketsFlood & Prune processrepeats every 3 minutes!(S, G) State still exists inevery router in the network!73PIM-DM Assert MechanismE0Incoming Multicast Packet(Successful RPF Check) E0S0 Routers receiv

51、e packet on an interface in their “oilist”! Only one router should continue sending to avoid duplicate packets1S012Routers send “PIM Assert” messagesAssert Assert22Compare distance and metric valuesRouter with best route to source winsIf metric & distance equal, highest IP adr winsLosing router stop

52、s sending (prunes interface)74PIM-DM EvaluationMost effective for large number of densely distributed receivers located in close proximity to sourceAdvantages:Easy to configuretwo commandsip pim dense-modeSimple flood and prune mechanismPotential issues.Inefficient flood and prune behaviorComplex As

53、sert mechanismMixed control and data planesResults in (S, G) state in every router in the networkNo support for shared trees75PIM-SM (RFC 2362)Supports both source and shared treesAssumes no hosts want multicast traffic unless they specifically ask for itUses a Rendezvous Point (RP)Senders and Recei

54、vers “rendezvous” at this point to learn of each others existenceSenders are “registered” with RP by their first-hop routerReceivers are “joined” to the Shared Tree (rooted at the RP) by their local Designated Router (DR)Appropriate forWide scale deployment for both densely and sparsely populated gr

55、oups in the enterpriseOptimal choice for all production networks regardless of size and membership density76PIM-SM Shared Tree JoinReceiverRP(*, G) JoinShared Tree(*, G) State created onlyalong the Shared Tree.77PIM-SM Sender RegistrationReceiverRP(S, G) JoinSourceShared Tree(S, G) Register(unicast)

56、Source Tree(S, G) State created onlyalong the Source Tree.Traffic Flow78PIM-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 b

57、egins arriving at the RP via the Source tree.79PIM-SM Sender RegistrationReceiverRPSourceShared TreeSource TreeTraffic FlowSource traffic flows nativelyalong SPT to RP.From RP, traffic flows downthe Shared Tree to Receivers.80PIM-SM SPT SwitchoverReceiverRP(S, G) JoinSourceSource TreeShared TreeLast

58、-hop router joins the Source Tree.Additional (S, G) State is created along new part of the Source Tree.Traffic Flow81PIM-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

59、 Shared Tree to prune off (S, G) traffic.Traffic Flow82PIM-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 Flow83PIM-SM SPT SwitchoverReceiverRPSourceSource TreeShared Tree(S, G

60、) traffic flow is no longer needed by the RP so it Prunes the flow of (S, G) traffic.Traffic Flow(S, G) Prune84PIM-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 Flow85PIM-SM FFFThe default