Motivation Example Internet Radio EE 122 Multicast Ion Stoica TAs Junda Liu DK Moon David Zats http inst eecs berkeley edu ee122 fa09 Materials with thanks to Vern Paxson Jennifer Rexford and colleagues at UC Berkeley 1 This approach does not scale Live 8 concert Send 1 000 Kb s video streams Peak usage 100 000 simultaneous users Consumes 100 Gbps If 1000 people are in Berkeley and if the concert were broadcast from a single location 1000 unicast streams are sent from that location to Berkeley 2 Instead build trees Copy data at routers At most one copy of a data packet per link Broadcast Center Broadcast Center Backbone ISP Routers keep track of groups in real time Routers compute trees and forward packets along them 3 Backbone ISP LANs implement link layer multicast by broadcasting 4 1 Multicast Service Model S G data tas G dain G R 1 jo G data G ins Net R 0 jo R G n 1 d joaita ns G R0 Note multicast vs broadcast Membership access control Rn 1 R1 Receivers join a multicast group which is identified by a multicast address e g G Sender s send data to address G Network routes data to each of the receivers Multicast Service Model cont d Open group anyone can join Closed group restrictions on joining Sender access control Anyone can send to group Anyone in group can send to group Restrictions on which host can send to group Broadcast packets are delivered to all end hosts in the network Multicast packets are delivered only to end hosts that are in have joined the multicast group 5 Multicast and Layering data link layer network layer application layer Multicast Implementation Issues Multicast can be implemented at different layers 6 e g Ethernet multicast How are multicast packets addressed How is join implemented How is send implemented How much state is kept and who keeps it e g IP multicast e g End system multicast Which layer is best 7 8 2 Problems with Data Link Layer Multicast Data Link Layer Multicast Recall 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 multicast Join group at multicast address G Single data link technology Single LAN Network interface card NIC normally only listens for packets sent to unicast address A and broadcast address B To join group G NIC also listens for packets sent to multicast address G NIC limits number of groups joined Implemented in hardware thus efficient Limited to small number of hosts Limited to low diameter latency Essentially all the limitations of LANs compared to internetworks Send to group G Packet is flooded on all LAN segments like broadcast Can waste bandwidth but LANs should not be very large Only host NICs keep state about who has joined scalable to large number of receivers groups 9 Network Layer IP Multicast Intra domain 228 addresses for entire Internet Source Specific Tree Distance Vector Multicast Routing Protocol DVRMP Shared Tree Core Based Tree CBT Inter domain Open group membership Anyone can send to group Relies on data link layer multicast for intra network routing Portion of IP address space defined as multicast addresses IP Multicast Routing Overcomes limitations of data link layer multicast Performs inter network multicast routing 10 Protocol Independent Multicast Single Source Multicast Flexible but leads to problems 11 12 3 Distance Vector Multicast Routing Protocol DVRMP Reverse Path Flooding RPF An elegant extension to DV routing Use shortest path DV routes to determine if link is on the source rooted spanning tree Three steps in developing DVRMP Reverse Path Flooding Reverse Path Broadcasting Truncated Reverse Path Broadcasting Extension to DV unicast routing Packet forwarding If incoming link is shortest path to source Send on all links except incoming Packets always take shortest path assuming delay is symmetric Issues Some links LANs may receive multiple copies Every link receives each multicast packet even if no interested hosts s 3 s 2 s 3 s 1 s 2 s r 13 14 Example Reverse Path Broadcasting RPB Flooding can cause a given packet to be sent multiple times over the same link S x y a duplicate packet z b Solution Reverse Path Broadcasting 15 Chose parent of each link along reverse shortest path to source Parent of z on 5 Only parent forward to a link child reverse path link x forward only Identify Child Links to child link 1 Routing updates identify a parent child link of x for S 2 Since distances are known each router can easily figure out if it s the parent for a given b link 3 In case of tie lower address wins S 6 y z 16 4 Truncated Reverse Path Broadcasting TRPB Don 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 members Solution Truncated Reverse Path Broadcasting Extend DV RPB to eliminate unneeded forwarding Identify leaves Routers announce that a link is their next link to source S Parent router can determine that it is not a leaf Explicit group joining on LAN Members periodically with random offset multicast report locally Hear and report then suppress own Packet forwarding If not a leaf router or have members Out all links except incoming S NL NL NL L L r2 r1 L leaf node NL Non leaf node 17 Pruning Details Send Non Membership Report NMR up tree How to pick prune timers Too long large join time Too short high control overhead Propagate prune for S G to parent R On timeout If all children of router R send NRM prune S G Pruning Details Prune Source Group at leaf if no members 18 Prune dropped Flow is reinstated Down stream routers re prune What do you do when a member of a group re joins Issue prune cancellation message grafts Note a soft state approach 19 20 5 Distance Vector Multicast Scaling State requirements O Sources Groups active state How to get better scaling Core Based Trees CBT Hierarchical Multicast Core based Trees Pick a rendevouz point for the group called the core Shared tree Unicast packet to core and bounce it back to multicast group Tree construction is receiver based Joins can be tunneled if required Only nodes on One tree per group tree involved Reduce routing table state from O S x G to O G 21 Example 22 Disadvantages Group members M1 M2 M3 M1 sends data Sub optimal delay root M1 M2 Need good core selection Optimal choice computing topological center is NP hard M3 control join messages data 23 24 6 Problems with Network Layer Multicast NLM Scales poorly with number of groups A router
View Full Document
Unlocking...