Slide 1Motivation Example: Internet RadioThis approach does not scale…Instead build treesMulticast Service ModelMulticast Service Model (cont’d)Multicast and LayeringMulticast Implementation IssuesData Link Layer MulticastProblems with Data Link Layer MulticastNetwork Layer (IP) MulticastIP Multicast RoutingDistance Vector Multicast Routing Protocol (DVRMP)Reverse Path Flooding (RPF)ExampleReverse Path Broadcasting (RPB)Don’t Really Want to Flood!Truncated Reverse Path Broadcasting (TRPB)Pruning DetailsPruning DetailsDistance Vector Multicast ScalingCore Based Trees (CBT)ExampleDisadvantagesProblems with Network Layer Multicast (NLM)NLM Reliability(N)ACK ImplosionNACK ImplosionBarriers to MulticastApplication Layer Multicast (ALM)Narada: End System MulticastAlgorithmic ChallengeAdvantages of ALMPerformance ConcernsPerformance ConcernsWhat Do You Need to Know?1EE 122: MulticastIon StoicaTAs: Junda Liu, DK Moon, David Zatshttp://inst.eecs.berkeley.edu/~ee122/fa09 (Materials with thanks to Vern Paxson, Jennifer Rexford,and colleagues at UC Berkeley)2Motivation Example: Internet RadioLive 8 concertSend ~1,000 Kb/s video streamsPeak usage > 100,000 simultaneous usersConsumes > 100 GbpsIf 1000 people are in Berkeley, and if the concert were broadcast from a single location, 1000 unicast streams are sent from that location to Berkeley3This approach does not scale…BackboneISPBroadcastCenter4Instead build treesBackboneISPBroadcastCenterCopy data at routersAt most one copy of a data packet per link•LANs implement link layer multicast by broadcasting•Routers keep track of groups in real-time•Routers compute trees and forward packets along them5Multicast Service ModelReceivers join a multicast group which is identified by a multicast address (e.g. G)Sender(s) send data to address GNetwork routes data to each of the receiversNote: multicast vs. broadcastBroadcast: packets are delivered to all end-hosts in the networkMulticast: packets are delivered only to end-hosts that are in (have joined) the multicast groupR0 joins GR1 joins GRn-1 joins GSR0R1...[G, data][G, data][G, data][G, data]Rn-1Net6Multicast Service Model (cont’d)Membership access controlOpen group: anyone can joinClosed group: restrictions on joiningSender access controlAnyone can send to groupAnyone in group can send to groupRestrictions on which host can send to group7Multicast and LayeringMulticast can be implemented at different layersdata link layere.g. Ethernet multicastnetwork layere.g. IP multicastapplication layere.g. End system multicastWhich layer is best?8Multicast Implementation IssuesHow are multicast packets addressed?How is join implemented?How is send implemented?How much state is kept and who keeps it?9Data Link Layer MulticastRecall: end-hosts in the same local area network (LAN) can hear from each other at the data link layer (e.g., Ethernet)Reserve some data link layer addresses for multicastJoin group at multicast address GNetwork interface card (NIC) normally only listens for packets sent to unicast address A and broadcast address BTo join group G, NIC also listens for packets sent to multicast address G (NIC limits number of groups joined)Implemented in hardware, thus efficientSend to group GPacket is flooded on all LAN segments, like broadcastCan waste bandwidth, but LANs should not be very largeOnly host NICs keep state about who has joined scalable to large number of receivers, groups10Problems with Data Link Layer MulticastSingle data link technologySingle LANLimited to small number of hostsLimited to low diameter latencyEssentially all the limitations of LANs compared to internetworks11Network Layer (IP) MulticastOvercomes limitations of data link layer multicastPerforms inter-network multicast routingRelies on data link layer multicast for intra-network routingPortion of IP address space defined as multicast addresses228 addresses for entire InternetOpen group membershipAnyone can send to groupFlexible, but leads to problems12IP Multicast RoutingIntra-domainSource Specific Tree: Distance Vector Multicast Routing Protocol (DVRMP)Shared Tree” Core Based Tree (CBT)Inter-domainProtocol Independent Multicast Single Source Multicast13Distance Vector Multicast Routing Protocol (DVRMP)An elegant extension to DV routingUse shortest path DV routes to determine if link is on the source-rooted spanning treeThree steps in developing DVRMPReverse Path FloodingReverse Path BroadcastingTruncated Reverse Path Broadcasting14Reverse Path Flooding (RPF)Extension to DV unicast routingPacket forwardingIf incoming link is shortest path to sourceSend on all links except incomingPackets always take shortest pathassuming delay is symmetricIssuesSome links (LANs) may receive multiple copiesEvery link receives each multicast packet, even if no interested hostss:2s:2sss:1s:1s:3s:3s:2s:2s:3s:3rr15Example Flooding can cause a given packet to be sent multiple times over the same linkSolution: Reverse Path Broadcasting xxyyzzSSabduplicate packet16Reverse Path Broadcasting (RPB)Chose parent of each link along reverse shortest path to sourceOnly parent forward to a link (child link)Identify Child Links1. Routing updates identify parent2. Since distances are known, each router can easily figure out if it's the parent for a given link3. In case of tie, lower address winsxxyyzzSSab56child link of xfor Sforward onlyto child linkParent of z on reverse path17Don’t Really Want to Flood!This is still a broadcast algorithm – the traffic goes everywhere Need to “Prune” the tree when there are subtrees with no group membersSolution: Truncated Reverse Path Broadcasting18Truncated Reverse Path Broadcasting (TRPB)Extend DV/RPB to eliminate unneeded forwardingIdentify leavesRouters announce that a link is their next link to source SParent router can determine that it is not a leafExplicit group joining on LANMembers periodically (with random offset) multicast report locallyHear and report, then suppress ownPacket forwardingIf not a leaf router or have membersOut all links except incomingr1r1r2r2SSNLNLNLL LL – leaf nodeNL – Non-leaf node19Pruning DetailsPrune (Source,Group) at leaf if no membersSend Non-Membership Report (NMR) up
View Full Document
Unlocking...