CS 269: Lecture 11 MulticastThis WeekHistoryIronyLecturesAgendaMotivationMulticast Service ModelOpen Membership ModelOther Design Choices?Division of ResponsibilitiesTarget EnvironmentMulticast Routing AlgorithmsRouting Performance GoalsTwo Basic Routing ApproachesDVMRPBasic Forwarding RuleExampleBroadcasting ExtensionMulticast = Pruned BroadcastProblems with ApproachCore Based Trees (CBT)Slide 23DisadvantagesWhy Isn’t Multicast Pervasive?Possible Explanation [Holbrook & Cheriton ’99]Solution: Single-Source MulticastDiscussionUsing MulticastA Few ExamplesDistributing VideoLayered VideoExample of Rate/Quality TradeoffReceiver-driven Layered MulticastBasic AlgorithmJoin TimerScaling ProblemScaling Solution: Shared LearningRLM PaperPriority-drop and Uniform-dropLater Work ContradictsAssumptionsThe Cache Consistency ProblemTraditional Cache InvalidationMulticast Cache InvalidationReliable MulticastHow to Make Multicast Reliable?SRM Design ApproachRepair Request Timer RandomizationSuppressionLocal RecoveryApplication Layer Framing (ALF)Multicast’s True LegacyBenefits of Multicast1CS 269: Lecture 11MulticastScott Shenker and Ion StoicaComputer Science DivisionDepartment of Electrical Engineering and Computer SciencesUniversity of California, BerkeleyBerkeley, CA 94720-17762This WeekA Tale of Two FailuresMulticast and QoS: the lost decade3HistoryMulticast and QoS dominated research literature in the 90’sBoth failed in their attempt to become pervasively available-Both now available in enterprises, but not in public InternetBoth now scorned as research topics4IronyThe biggest critics of QoS were the multicast partisans-And the QoS advocates envied the hipness of mcast…They complained about QoS being unscalable-Among other complaints….Irony #1: multicast is no more scalable than QoSIrony #2: scaling did not cause either of their downfallsMany now think economics was the problem-Revenue model did not fit delivery model5LecturesToday: multicast-Focus on multicast as a state of mind, not on detailsWednesday: QoS-More “why” than “what”6AgendaPreliminariesMulticast routingUsing multicastReliable multicastMulticast’s philosophical legacy7MotivationOften want to send data to many machines at once-Video distribution (TV broadcast)-Teleconferences, etc.-News updatesUsing unicast to reach each individual is hard and wasteful-Sender state: ~O(n) and highly dynamic-Total load: ~O(nd) where d is net diameter-Hotspot load: load ~O(n) on host and first linkMulticast:-Sender state: O(1), total load O(d log n), hotspot load O(1)8Multicast Service ModelSend to logical group address-Location-independentDelivery limited by specified scope-Can reach “nearby” membersBest effort delivery9Open Membership ModelAnyone, anywhere, can joinDynamic membership-join and leave at willAnyone can send at any time-Even nonmembers10Other Design Choices?11Division of ResponsibilitiesHost’s responsibility to register interest with networks-IGMPNetwork’s responsibility to deliver packets to host-Multicast routing protocolLeft unspecified:-Address assignment (random, MASC, etc.)-Application-to-group mapping (session directory, etc.)12Target EnvironmentLANs connected in arbitrary topologyLANs support local multicastHost network cards filter multicast traffic13Multicast Routing Algorithms14Routing Performance GoalsRoughly equivalent to unicast best-effort service in terms of drops/delays-Efficient tree-No complicated forwarding machinery, etc.Low join/leave latency15Two Basic Routing ApproachesSource-based trees: (e.g., DVMRP, PIM-DM)-A tree from each source to group-State: O(G*S)-Good for dense groups (all routers involved)Shared trees: (e.g., CBT, PIM-SM)-A single tree for group, shared by sources-State: O(G)-Better for sparse groups (only routers on path involved)16DVMRPDeveloped as a sequence of protocols:-Reverse Path Flooding (RPF)-Reverse Path Broadcast (RFB)-Truncated Reverse Path Broadcasting (TRPB)-Reverse Path Multicast (RPM)General Philosophy: multicast = pruned broadcast-Don’t construct new tree, merely prune old oneObservation: -unicast routing state tells router shortest path to S-Reversing direction sends packets from S without forming loops17Basic Forwarding RuleRouting state:-To reach S, send along link LFlooding Rule:-If a packet from S is received along link L, forward on all other linksThis works fine for symmetric links-Ignore asymmetry todayThis works fine for point-to-point links-Can result in multiple packets sent on LANs18ExampleFlooding can cause a given packet to be sent multiple times over the same linkxxyyzzSSabduplicate packet19Broadcasting ExtensionFor each link, and each source S, define parent and child-Parent: shortest path to S (ties broken arbitrarily)-All other routers on link are childrenBroadcasting rule: only parent forwards packet to LProblem fixedBut this is still broadcast, not multicast!20Multicast = Pruned BroadcastStart with full broadcast (RPB)If leaf has no members, prune state-Send non-membership report (NMR)If all children of a router R prune, then router R sends NMR to parentNew joins send graft to undo pruning21Problems with ApproachStarting with broadcast means that all first packets go everywhereIf group has members on most networks, this is okBut if group is sparse, this is lots of wasted trafficWhat about a different approach:-Source-specific tree vs shared tree-Pruned broadcast vs explicitly constructed tree22Core Based Trees (CBT)Ballardie, Francis, and Crowcroft,-“Core Based Trees (CBT): An Architecture for Scalable Inter-Domain Multicast Routing”, SIGCOMM 93Similar to Deering’s Single-Spanning TreeUnicast packet to core, but forwarded to multicast groupTree construction by receiver-based “grafts”-One tree per group, only nodes on tree involvedReduce routing table state from O(S x G) to O(G)23ExampleGroup members: M1, M2, M3M1 sends datarootM1M2M3control (join) messagesdata24DisadvantagesSub-optimal delaySingle point of failure (core)Small, local groups with non-local core-Need good core selection-Optimal choice (computing topological center) is NP complete25Why Isn’t Multicast Pervasive?Sound technologyImplemented in most routersUsed by many enterprisesBut not available on public Internet26Possible Explanation[Holbrook &
View Full Document
Unlocking...