1EE122: MulticastKevin LaiOctober 7, [email protected] 2Internet Radiowww.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 [email protected] 3Multicast Service Model 1receivers 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 receiversSR0R1...R0joins GR1joins GRn-1joins G[R0, data][R1, data][Rn-1, data][R0, data][R1, data][Rn-1, data]UnicastRn-1NetSR0R1...[G, data][G, data][G, data][G, data][email protected] 4Motivation 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 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, [email protected] 5Multicast Service Model 2Membership access control- open group: anyone can join- closed group: restrictions on joiningSender access control- anyone can send to group- anyone in group can send to group- only one host can send to groupPacket delivery is best [email protected] 6Multicast and LayeringMulticast can be implemented at different layers- data link layer• e.g. Ethernet multicast- network layer• e.g. IP multicast- application layer• e.g. as an overlay network like KazaaWhich layer is [email protected] 7Multicast Implementation IssuesHow are multicast packets addressed?How is join implemented?How is send implemented?How much state is kept and who keeps [email protected] 8Ethernet MulticastReserve 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 largeonly host NICs keep state about who has joined → scalable to large number of receivers, [email protected] 9Problems with Data Link Layer Multicastsingle data link technologysingle LAN- limited to small number of hosts- limited to low diameter latency- essentially all the limitations of LANs compared to internetworksbroadcast doesn’t cut it in larger [email protected] 10IP MulticastOvercomes limitations of data link layer multicastPerforms inter-network multicast routing- relies on data link layer multicast for intra-network routingPortion of IP address space defined as multicast addresses-228addresses for entire InternetOpen group membershipAnyone can send to group- flexible, but leads to [email protected] 11IP Multicast RoutingIntra-domain- Distance-vector multicast (DVM)- Link-state multicast (LSM) Inter-domain- Protocol Independent Multicast (PIM)- Single Source Multicast (SSM)[email protected] 12Distance Vector Multicast Extension to DV unicast routing Routers compute shortest path to each host- necessary for unicast delivery No join required- every link receives a copy, even if no interested hostsPacket 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 duplicatess:2s:2sss:1s:1s:3s:3s:2s:2s:3s:[email protected] 13Reverse 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 links:2s:2sss:1s:1s:3s:3s:2s:2s:3s:[email protected] 14Truncated Reverse Path Broadcasting (TRPB) 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- members periodically (with random offset) multicast report locally- hear an report, then suppress ownPacket forwarding- iff not a leaf router or have members- out all links except [email protected] 15Problems with IP Multicast ModelFew groups have many senders- difficult to construct optimal tree for many sendersHard to implement sender control Æ any node can send to the group - open group membershipMulticast address scarcity-228addresses may not be enough for entire Internet- how prevent [email protected] 16Internet Radio using IP Multicast ModelOne sender- does not use multiple sender capability of modelSomeone other than Digitally Imported can send to group- clog 9000 clients’ links with useless data (Denial-of-Service attack)How can Digitally Imported get and keep a multicast address?- central organization to manage addresses adds [email protected] 17Single Source Multicast (SSM)Network layer multicastSSM service model- only one sender can send to a group- any number of receiversAddressing- SSM address = (S, G) S: IP address of source, G: 24-bit group address- each sender has its own [email protected] 18SSM Joinreceiver sends join to sourcerouters on the path read the join packetthey note a receiver on the incoming [email protected] 19SSM Sendrouter checks that packet is coming from direction of Sif so, forward it down links that have [email protected] 20SSM v.s. IP MulticastRestricted to one sender per group- for multiple senders, make multiple groupsCan prevent denial-of-service attacks on groupSenders can
View Full Document