Contents Motivation Overview Implementation Issues Ethernet Multicast IGMP Routing Approaches Reliability Application Layer Multicast Summary TOC IP Multicast Motivation ISPs charge by bandwidth Broadcast Center Backbone ISP They make more money without multicast TOC IP Multicast Motivation Overview Multicast Send to a group of hosts Key ideas Replace multiple unicasts by a tree good algorithms for building tree Multiple Unicasts TOC IP Multicast Overview Multicast Tree Overview Key ideas Subscribe to a group soft state Join Group TOC IP Multicast Overview Overview Key Ideas MBONE When only a subset of routers multicast multicast router non multicast router TOC IP Multicast Overview Implementation Issues Multicast can be implemented at different layers data link layer network layer e g IP multicast application layer e g Ethernet multicast e g as an overlay network like Kazaa Which layer is best TOC IP Multicast Implementation Implementation Issues How are multicast packets addressed How is join implemented How is send implemented How does multicast traffic get routed This is easy at the link layer and hardest at the network layer How much state is kept and who keeps it TOC IP Multicast Implementation Ethernet Multicast Reserve some Ethernet MAC addresses for multicast To 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 To 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 Limited to single LAN More generally Mapping of IP Group address to LAN group address TOC IP Multicast Ethernet Internet Group Management Protocol IGMP Operates between Router and local Hosts typically attached via a LAN e g Ethernet 1 Router periodically queries the local Hosts for group membership information 2 3 4 Query response architecture Can be specific or general Hosts receiving query set a random timer before responding First host to respond sends membership reports All the other hosts observe the query and suppress their own repots Report To Join send a group send an unsolicited Join Query to 224 0 0 1 Start a group by joining it To leave don t do anything Soft state TOC IP Multicast IGMP Suppresses Report Routing Approaches Kinds of Trees Source Specific Trees Shared Tree Tree Computation Methods Intradomain Interdomain BGMP This is still evolving TOC IP Multicast Approaches Source Specific Trees 5 7 Each source is the route of its own tree 4 8 6 11 2 1 10 3 13 TOC IP Multicast Approaches Source Specific 12 Source Specific Trees 5 7 Each source is the route of its own tree One tree for each source 4 8 6 11 2 1 10 3 13 Can pick good trees but lots of state at the routers TOC IP Multicast Approaches Source Specific 12 Shared Tree 5 7 One tree used by all 4 8 6 11 2 1 10 3 13 Can t pick good trees but minimal state at the routers TOC IP Multicast Approaches Shared 12 Tree Computation 2 4 A tree which connects all the group nodes is a Steiner Tree Finding the min cost Steiner Tree is NP hard 2 5 1 7 2 8 2 12 6 15 2 2 12 7 11 3 1 11 10 2 3 2 2 1 13 12 12 2 group member TOC IP Multicast Approaches Tree Computation Tree Computation 2 4 A tree which connects all the group nodes is a Steiner Tree Finding the min cost Steiner Tree is NP hard 2 5 1 7 2 8 2 12 6 15 2 2 1 12 7 11 3 11 10 2 3 2 2 1 13 12 TOC IP Multicast Approaches Tree Computation 12 2 Tree Computation 2 4 A tree which connects all the group nodes is a Steiner Tree Finding the min cost Steiner Tree is NP hard The tree does not span the network Heuristics are known 2 5 1 7 2 8 2 12 6 15 2 2 1 12 7 11 3 11 10 2 3 2 2 1 13 12 TOC IP Multicast Approaches Tree Computation 12 2 Tree Computation 2 4 A tree that connects all of the nodes in the graph is a spanning tree Finding a minimum spanning tree is much easier 2 5 1 7 2 8 2 12 6 15 2 2 1 12 7 11 3 11 10 2 3 2 2 1 13 12 TOC IP Multicast Approaches Tree Computation 12 2 Tree Computation 2 4 A tree that connects all of the nodes in the graph is a spanning tree Finding a minimum spanning tree is much easier 2 5 1 7 2 8 2 12 6 15 2 2 1 12 7 11 3 11 10 2 3 2 2 1 13 12 TOC IP Multicast Approaches Tree Computation 12 2 Tree Computation 2 4 A tree that connects all of the nodes in the graph is a spanning tree Finding a minimum spanning tree is much easier Prune back to get a multicast tree 2 5 1 7 2 8 2 12 6 15 2 2 1 12 7 11 3 11 10 2 3 2 2 1 13 12 TOC IP Multicast Approaches Tree Computation 12 2 Tree Computation 2 4 A tree that connects all of the nodes in the graph is a spanning tree Finding a minimum spanning tree is much easier Prune back to get a multicast tree 2 5 1 7 2 8 2 12 6 15 2 2 1 12 7 11 3 11 10 2 3 2 2 1 13 12 TOC IP Multicast Approaches Tree Computation 12 2 Intradomain Multicast Routing Build on unicast Link State MOSPF Build on unicast Distance Vector DVMRP Protocol Independent PIM Problems TOC IP Multicast Approaches Intradomain Link State MOSPF Use in conjunction with a link state protocol for unicast Enhance the LSP updates with group membership Compute best tree from source Flood Membership in link state advertisements Dynamics are a problem TOC IP Multicast Approaches Intradomain LS Distance Vector DVMRP An elegant extension to DV routing Use shortest path DV routes to determine if link is on the source rooted spanning tree tree of shortest paths to source break ties with lowest router ID Prune back if no group members down the subtree Improve scalability Multicast to a shared tree core and from there to rest of hosts TOC IP Multicast Approaches Intradomain DV PIM Popular intradomain method Recognizes that most groups are very sparse UUNET streaming using this Why have all of the routers participate in keeping state Two modes Dense mode flood and prune Sparse mode Core based shared tree approach TOC IP Multicast Approaches Intradomain PIM Problems with Network Layer Multicast Scales poorly with number of groups A router must maintain state for every group that traverses it many groups traverse core routers Supporting higher level functionality is difficult …
View Full Document
Unlocking...