Internet Radio www digitallyimported com techno station sends out 128Kb s MP3 music streams peak usage 9000 simultaneous streams only 5 unique streams trance hard trance hard house eurodance classical consumes 1 1Gb s bandwidth costs are large fraction of their expenditures maybe 50 if 1000 people are getting their groove on in Berkeley 1000 unicast streams are sent from NYC to Berkeley EE122 Multicast Kevin Lai October 7 2002 laik cs berkeley edu Multicast Service Model 1 Unicast S R1 data Rn 1 data R0 R1 Net R n 1 dat a S G data Rn 1 Motivation Multicast ata R 0 d R1 data R0 data Net RG n 1d a jotina sG Rn 1 Conserve bandwidth use same bandwidth link to send to n receivers as 1 receiver internet radio example reduce bandwidth consumed by 9000 5 1800 deals with flash crowds e g video audio conferencing streaming news dissemination file updates tas G R dain 0 G R 1 jo G data G s in R1 R 0 jo Separate identifier from address logical addressing receiver can change location dependent addresses without notifying sender sender doesn t need to know about receivers e g service location mobility anonymity naming 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 laik cs berkeley edu 2 3 laik cs berkeley edu 4 1 Multicast Service Model 2 Multicast and Layering Membership access control open group anyone can join closed group restrictions on joining data link layer e g Ethernet multicast network layer e g IP multicast application layer e g as an overlay network like Kazaa Sender access control anyone can send to group anyone in group can send to group only one host can send to group Packet delivery is best effort laik cs berkeley edu Which layer is best 5 laik cs berkeley edu Multicast Implementation Issues Multicast can be implemented at different layers 6 Ethernet Multicast How are multicast packets addressed How is join implemented How is send implemented How much state is kept and who keeps it Reserve some Ethernet MAC addresses for multicast join group G 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 so efficient send to group G packet is flooded on all LAN segments like broadcast can waste bandwidth but LANs should not be very large laik cs berkeley edu 7 only host NICs keep state about who has joined scalable to large number of receivers groups laik cs berkeley edu 8 2 Problems with Data Link Layer Multicast IP Multicast single data link technology single LAN limited to small number of hosts limited to low diameter latency essentially all the limitations of LANs compared to internetworks Overcomes limitations of data link layer multicast Performs inter network multicast routing relies on data link layer multicast for intra network routing Portion of IP address space defined as multicast addresses Open group membership Anyone can send to group broadcast doesn t cut it in larger networks 228 addresses for entire Internet flexible but leads to problems laik cs berkeley edu 9 laik cs berkeley edu IP Multicast Routing Distance Vector Multicast Intra domain Distance vector multicast DVM Link state multicast LSM Extension to DV unicast routing Routers compute shortest path to each host s 3 s 3 necessary for unicast delivery Inter domain No join required every link receives a copy even if no interested hosts Protocol Independent Multicast PIM Single Source Multicast SSM 11 s 2 s 2 s 3 s 3 s 1 s 1 s 2 s 2 ss rr Packet forwarding iff incoming link is shortest path to source out all links except incoming Reverse Path Flooding RPF packets always take shortest path assuming delay is symmetric link may have duplicates laik cs berkeley edu 10 laik cs berkeley edu 12 3 Truncated Reverse Path Broadcasting TRPB Reverse Path Broadcasting RPB Extend DV to eliminate duplicate packets Combine DV and spanning tree Choose parent router for each link router with shortest path to source lowest address breaks ties each router can compute independently from already known information each router keeps a bitmap with one bit for each of its links Only parent forwards onto link s 3 s 3 s 2 s 2 C s 2 s 2 ss rr laik cs berkeley edu 13 Multicast address scarcity L r1 r1 14 Internet Radio using IP Multicast Model One sender Someone other than Digitally Imported can send to group does not use multiple sender capability of model open group membership clog 9000 clients links with useless data Denial ofService attack 228 addresses may not be enough for entire Internet how prevent collisions laik cs berkeley edu L laik cs berkeley edu difficult to construct optimal tree for many senders Hard to implement sender control any node can send to the group NL r2 r2 Packet forwarding iff not a leaf router or have members out all links except incoming Few groups have many senders NL Explicit group joining members periodically with random offset multicast report locally hear an report then suppress own Problems with IP Multicast Model NL routers announce that a link is their next link to source S parent router can determine that it is not a leaf s 3 s 3 P s 1 s 1 SS Extend DV RPB to eliminate unneeded forwarding Identify leaves How can Digitally Imported get and keep a multicast address central organization to manage addresses adds overhead 15 laik cs berkeley edu 16 4 Single Source Multicast SSM SSM Join Network layer multicast SSM service model only one sender can send to a group any number of receivers Addressing SSM address S G S IP address of source G 24bit group address each sender has its own G space SS receiver sends join to source routers on the path read the join packet they note a receiver on the incoming link r2 r2 r1 r1 laik cs berkeley edu 17 laik cs berkeley edu SSM Send SSM v s IP Multicast S1 S1 router checks that packet is coming from direction of S if so forward it down links that have receivers 18 SS Restricted to one sender per group Can prevent denial of service attacks on group Senders can independently allocate multicast addresses Much simpler than other network layer multicast routing schemes for multiple senders make multiple groups r2 r2 r3 r1 r1 laik cs berkeley edu 19 laik cs berkeley edu 20 5 Problems with Network Layer Multicast NLM NLM Reliability Scales poorly with number of groups A router must
View Full Document
Unlocking...