15-744: Computer NetworkingMulticast RoutingExample ApplicationsOverviewIP Multicast ArchitectureMulticast – Efficient Data DistributionMulticast Router ResponsibilitiesIP Multicast Service Model (rfc1112)IP Multicast AddressesMulticast Scope Control – Small TTLsMulticast Scope Control – Large TTLsSlide 13Slide 14Slide 15Shared vs. Source-based TreesSource-based TreesShared TreeShared vs. Source-Based TreesRouting TechniquesSlide 21Distance-Vector Multicast RoutingExample TopologyBroadcast with TruncationPruneGraftSteady StateSlide 28Supporting Multicast on the InternetIP MulticastEnd System MulticastPotential Benefits Over IP MulticastConcerns with End System MulticastSlide 34ImplosionRetransmissionExposureIdeal Recovery ModelScalable Reliable Multicast (SRM)SRM Request SuppressionDeterministic SuppressionSRM Star TopologySRM: Stochastic SuppressionSRM (Summary)Slide 45Multicast Congestion ControlVideo Adaptation: RLMLayered Media StreamsDrop Policies for Layered MulticastRLM IntuitionSlide 51RLM Join ExperimentJoin ExperimentsRLM Scalability?Next Lecture15-744: Computer NetworkingL-20 Multicast2Multicast Routing•Unicast: one source to one destination•Multicast: one source to many destinations•Two main functions:•Efficient data distribution •Logical naming of a group3Example Applications•Broadcast audio/video•Push-based systems•Software distribution•Web-cache updates •Teleconferencing (audio, video, shared whiteboard, text editor)•Multi-player games•Server/service location•Other distributed applications4Overview•IP Multicast Service Basics•Multicast Routing Basics•Overlay Multicast•Reliability•Congestion Control5IP Multicast ArchitectureHostsRoutersService modelHost-to-router protocol(IGMP)Multicast routing protocols(various)6Multicast – Efficient Data DistributionSrc Src7Multicast Router Responsibilities•Learn of the existence of multicast groups (through advertisement)•Identify links with group members•Establish state to route packets•Replicate packets on appropriate interfaces•Routing entry:Src, incoming interface List of outgoing interfaces8IP Multicast Service Model (rfc1112)•Each group identified by a single IP address•Groups may be of any size•Members of groups may be located anywhere in the Internet•Members of groups can join and leave at will•Senders need not be members•Group membership not known explicitly •Analogy:•Each multicast address is like a radio frequency, on which anyone can transmit, and to which anyone can tune-in.9IP Multicast Addresses•Class D IP addresses•224.0.0.0 – 239.255.255.255•How to allocated these addresses?•Well-known multicast addresses, assigned by IANA•Transient multicast addresses, assigned and reclaimed dynamically, e.g., by “sdr” program1 1 1 0 Group ID11Multicast Scope Control – Small TTLs•TTL expanding-ring search to reach or find a nearby subset of a groups12312Multicast Scope Control – Large TTLs•Administrative TTL Boundaries to keep multicast traffic within an administrative domain, e.g., for privacy or resource reasonsAn administrative domainTTL threshold set oninterfaces to these links,greater than the diameterof the admin. domainThe rest of the Internet13Overview•IP Multicast Service Basics•Multicast Routing Basics•Overlay Multicast•Reliability•Congestion Control14IP Multicast ArchitectureHostsRoutersService modelHost-to-router protocol(IGMP)Multicast routing protocols(various)15Multicast Routing•Basic objective – build distribution tree for multicast packets•Multicast service model makes it hard•Anonymity•Dynamic join/leave16Shared vs. Source-based Trees•Source-based trees•Separate shortest path tree for each sender •DVMRP, MOSPF, PIM-DM, PIM-SM•Shared trees•Single tree shared by all members•Data flows on same tree regardless of sender•CBT, PIM-SM17Source-based TreesRouterSourceReceiverSRRRRRSS18Shared TreeRPRouterSourceReceiverSSSRRRRR19Shared vs. Source-Based Trees•Source-based trees•Shortest path trees – low delay, better load distribution•More state at routers (per-source state)•Efficient for in dense-area multicast•Shared trees•Higher delay (bounded by factor of 2), traffic concentration•Choice of core affects efficiency•Per-group state at routers•Efficient for sparse-area multicast•Which is better? extra state in routers is bad!20Routing Techniques•Flood and prune•Begin by flooding traffic to entire network•Prune branches with no receivers•Examples: DVMRP, PIM-DM•Unwanted state where there are no receivers•Link-state multicast protocols•Routers advertise groups for which they have receivers to entire network•Compute trees on demand•Example: MOSPF•Unwanted state where there are no senders21Routing Techniques•Core based protocols•Specify “meeting place” aka core•Sources send initial packets to core•Receivers join group at core•Requires mapping between multicast group address and “meeting place” •Examples: CBT, PIM-SM22Distance-Vector Multicast Routing•DVMRP consists of two major components:•A conventional distance-vector routing protocol (like RIP) •A protocol for determining how to forward multicast packets, based on the routing table•DVMRP router forwards a packet if•The packet arrived from the link used to reach the source of the packet (reverse path forwarding check – RPF)•If downstream links have not pruned the tree23Example TopologyG GSG24Broadcast with TruncationG GSG25PruneG GSPrune (s,g)Prune (s,g)G26Graft (s,g)Graft (s,g)GraftG GSGGReport (g)27Steady StateG GSGG28Overview•IP Multicast Service Basics•Multicast Routing Basics•Overlay Multicast•Reliability•Congestion Control29Supporting Multicast on the InternetIPApplicationInternet architectureNetwork??At which layer should multicast be implemented?30IP MulticastCMUBerkeleyMITUCSDroutersend systemsmulticast flow•Highly efficient•Good delay31End System MulticastMIT1MIT2CMU1CMU2UCSDMIT1MIT2CMU2Overlay TreeBerkeleyCMU1CMUBerkeleyMITUCSD32•Quick deployment•All multicast state in end systems•Computation at forwarding points simplifies support for higher level functionalityPotential Benefits Over IP MulticastMIT1MIT2CMU1CMU2CMUBerkeleyMITUCSD33Concerns with End System Multicast•Self-organize recipients into multicast delivery overlay tree•Must be closely matched to real network topology to be efficient•Performance concerns compared to IP
View Full Document
Unlocking...