Transcript Multicast
CSE679: Multicast and Multimedia Basics Addressing Routing Hierarchical multicast QoS multicast Multicast -motivation Point-to-point delivery not efficient for events/transmissions of general interest Examples News multicast IETF sessions/rock concerts Many receivers may share the same path Point-to-point delivery too expensive Multicast motivation Multicast issues In point-to-point delivery, receiver address is known => routing is straightforward In Multicast, many receivers How to transmit data to all the receivers? How to identify the group of receivers? At the sender? In the network? Multicast issues Identify multicast by a group/multicast address The membership changes as the receivers join/leave the group Routers/Network need to recognize the multicast address Receivers need to receive on their own IP address and on the multicast address Multicast addressing A multicast sender uses the group address as the receiver’s address when sending packets Network/routers keep track of actual receiving subnets/paths for this group address (not the actual receivers) Receivers can reply to sender’s address or to group address Multicast addressing Part of IP address space reserved for multicast Multicast routers recognize multicast addresses Need to get a multicast address for a transmission before multicast can start Protocols exist for obtaining multicast addresses and finding out a multicast address Class D addresses High order 4 bits = 1110, followed by a 28-bit multicast group ID. 224.0.0.0 - 239.255.255.255 224.0.0.1 - all systems on this subnet 224.0.0.2 - all routers on this subnet 224.0.0.4 - all DVMRP routers 224.0.0.5 - all OSPF routers IGMP Internet Group Membership Protocol Used to join a multicast group and to check on the current status of receivers on a subnet IGMP -join message propagated up the routers until the multicast tree reached. Routers periodically poll hosts on subnets to see if any active receivers remain If no active receivers remain, routers propagate leave messages upstream to reduce unnecessary traffic Frequent polling can increase overhead Separate protocols for finding group membership address - sd Multicast routing For point-to-point delivery, a router looks up routing table and knows how to forward For multicast, many receivers may have to forward packets on multiple outgoing links too hard to keep track of individual receivers at each router for each multicast group remember just the links on which to be forwarded change as receivers join/leave Multicast routing Need to recognize multicast addresses The routing tables change as the receivers join/leave a multicast group Every router keeps track of “downstream” links on which to forward a packet Routing table and multicast address “expire” at the end of session Multicast Routing Protocols DVMRP - Distance Vector Multicast MOSPF - Multicast Extensions to OSPF PIM - Protocol Independent Multicast Multicast routing approaches Flooding send on all links to reach the receivers not efficient Spanning tree efficient could concentrate traffic on a few links Spanning tree based routing Spanning trees rooted at the sender When a receiver wants to join a group, may have to broadcast on all upstream links to find a path to the sender could cause a lot of overhead in sparse groups need better solutions Sparse Mode routing Use a Core-based tree (CBT) Use a rendezvous point or a core router Direct all joins to RP which knows how to reach the sender can avoid broadcasting multicast group information to all routers in the network can result in non-optimal paths would need to modify multicast tree over time Reliable Multicast In unicast, receiver ACKs give feedback ---Sender takes responsibility in transmitting data In Multicast, many receivers -- too difficult for sender to keep track of every receiver’s status ACK Implosion Receiver-driven Multicast Sender based schemes don’t scale well as number of receivers increase Receiver based schemes scale better Receivers can decide the level of reliability needed as well as the level of quality desired etc. Send NAKs Sender keeps no information of receivers’ status Receivers send NAKs to reduce ACK implosion problem How to send NAKs? Unicast NAKs to sender Multicast NAKs Unicast NAKs to sender Reduces overhead when packet losses are isolated and rare Packet loss early in the tree will result in too many NAKs Multicast NAKs Others missing packets need not send NAKs if every receiver, sends a NAK immediately after getting an out-of-sequence packet, too many NAKS at once! Wait for a random time, send a NAK If some one else sends a NAK, suppress your NAK Getting random timers tricky business Could cause burden on receivers if only one receiver doesn’t get the packet Hierarchical Multicast Organize multicast into a number of groups One Designated Receiver (DR) takes responsibility for reliability On packet loss, NAK propagated to DR If DR has data, retransmits or re-multicasts with limited scope to the group If DR doesn’t have data, sends NAK to sender Hierarchical Multicast More scalable than other multicast protocols Specially useful when multicast over wide geographic boundaries, keep one DR in each country for example DR nodes may need more power than other receivers Need mechanisms to find out DR Need mechanisms to delegate DR function to another node as primary DR node leaves multicast RMTP: Reliable Multicast Transport Protocol - Bell Labs Congestion control Layered multicast Arrange layers in an exponentially increasing data rates TCP-friendly Multicast In steady state, packet drop => congestion, drop a layer If layers are doubling in data rates, dropped layer = reducing multicast rate by half => TCP friendly QoS-Sensitive Multicast The key issue is to construct a multicast tree with QoS constraints Goal is to build a tree of paths to destinations such that sum of link costs (e.g. consumed bandwidth) is minimum and QoS constraints (e.g. delay) are satisfied Exact solutions to such multi-constrained optimization problems are prohibitively expensive Need heuristics that provide fast solutions of high quality An Example for Constructing A Tree Application QoS requirements: end-to-end delay 13, jitter 7 example 1 10 10 10 example 2 2 6 6 10 10 Mbone Multicast Backbone Consists of all the multicast-enabled routers If two multicast routers are not directly connected, uses tunneling over non-multicast routers Allows gradual deployment Conclusion Multicast basics Motivation and Issues Addressing Routing Hierarchical multicast QoS multicast