115-744 Computer NetworkingMulticast(some slides borrowed from Srini Seshan)Multicast Routing• Unicast: one source to one destination• Multicast: one source to many destinations• Main goal: efficient data distribution – Avoid data duplication within networkMulticast – Efficient Data DistributionSrc SrcOverview• IP Multicast Service Basics• Routing: MOSPF/DVMRP• Reliability: SRM• Overlay Multicast2Example Applications• Broadcast audio/video• Push-based systems (e.g., BGP updates)• Software distribution• Web-cache updates • Teleconferencing (audio, video, shared whiteboard, text editor)• Multi-player games• Other distributed applicationsIP Multicast ArchitectureHostsRoutersService modelHost-to-router protocol(IGMP)Multicast routing protocols(various)IP Multicast Service Model• Each group identified by a single IP address• Variable Size:– Groups of any size; sparse or dense• Variable Location:– Members may be located anywhere on Internet • Dynamic membership:– Members can join and leave at will• Many-to-many– Not only one-to-many• No central state– Group membership not known explicitly • Analogy:– Each multicast address is like a radio frequency, on which anyone can transmit, and to which anyone can tune-in.IP Multicast Addresses• Class D IP addresses– 224.0.0.0 – 239.255.255.255• How to allocate these addresses?– Well-known addresses: IANA– Transient addresses: e.g., by “SDR” program• Assigned and reclaimed dynamically, 1 1 1 0Group ID3IP Multicast API• Sending – same as before• Receiving – two new operations– Join(group)– Leave(group)– Receive multicast packets for joined groups via normal IP-Receive operation– Implemented using socket optionsMulticast Router Responsibilities• Learn of the existence of multicast groups– (through advertisement)• Identify links with group members• Establish state to route packets– Replicate packets on appropriate interfaces– Routing entry:Src, incoming interface List of outgoing interfacesOverview• IP Multicast Service Basics• Routing: MOSPF/DVMRP• Reliability: SRM• Overlay MulticastRouting Techniques• Basic objective – build distribution tree for multicast packets• Link-state multicast protocols– Routers advertise groups for which they have receivers to entire network– Compute trees on demand– Example: MOSPF• Flood and prune– Begin by flooding traffic to entire network– Prune branches with no receivers– Example: DVMRP4Multicast OSPF (MOSPF)• Add-on to OSPF–Recall: flood routing announcements, each node gets entire topology–Now each router also keeps track of multicast group members–Routers mark link-state advertisement with groups that it has members for• Source-based trees–Shortest paths to a node form a spanning tree–Routing algorithm augmented to compute shortest-path distribution tree from a source to any set of destinations–Packets from each source are forwarded on this treeSource-based TreeGSGShortest path to S Has group membersImpact on Route Computation• Problems?– O(N2) state: one tree per potential sender– Can’t pre-compute multicast trees for all possible sources• One solution: Compute on demand – When first packet from a source S to a group G arrives– Slow if sources send infrequently• Another solution: Shared trees– One tree per multicast group– Requires a rendezvous point• Unicast to RP, then RP multicasts it along tree– E.G., PIM Sparse ModeDistance-Vector Multicast Routing• Add on to DV routing (e.g., RIP)– Recall: each node locally determines shortest-path “next hop” for each destination• Router forwards a packet if– The packet arrived from the link used to reach the source of the packet • Reverse path forwarding check (RPF)• Shortest-paths to a source form a spanning tree– If downstream links have not pruned the tree• Initially send to all routers then prune away branches5Reverse Path ForwardingGSGNext-hop to SPruneGSPrune (s,g)Prune (s,g)GGraft (s,g)Graft (s,g)GraftGSGGReport (g)Overview• IP Multicast Service Basics• Routing: MOSPF/DVMRP• Reliability: SRM• Overlay Multicast6Multicast Transport Properties• IP Multicast service guarantees?– Best effort• What other properties would applications want?– Reliability– Congestion/Flow Control– In-order delivery– Etc.• Why doesn’t IP Multicast provide these?– End-to-end principle: Can build other properties on top just like IP unicast• SRM tackles reliabilityStraw man Reliability Solutions• Why not have each member ACK the sender?– ACK implosion: each packet sent generates N ACKs!– Requires sender to track all receiver state• Why not have each member NACK the sender?– If data rate is slow, may not know that we’re missing the last packet– Loss near the sender generates lots of NACKs; many receivers could share a bottleneck– SRM uses NACKs but in a more intelligent fashionSRM Design Assumptions• Example Application: digital whiteboard• Many-to-many– Any one in the group can send• Named data units– E.G., 0000 => “point (3,4)”, 0001 => “line (3,4)-(1,2)”– Each object sent has globally unique name• Cooperative recovery– Any member can supply lost data to any other member– E.g., each member buffers all dataSRM Basic Operation• Multicast periodic session messages telling everyone the “latest seqno”– Aside: can use these to estimate RTT between members• Loss detected (missing seqno) => multicast repair request (NACK)– Request sent after a timer with time picked from uniform distribution: 2i[C1*dSA, (C1+C2)*dSA]– Suppress request if we see a request and i++– => nodes closer to loss send request sooner (on expectation)– => first request likely to suppress others (with reasonable C1,C2)• Receive repair request && we have the data item => multicast repair response– Request sent after a timer picked from uniform distribution: [D1*dAB, (D1+D2)*dAB]– => nodes closer to requestor will respond sooner (on expectation)• Goal: Have few repair request/responses for the entire group when loss7SRM Operation ExampleS L1 R1 R2 R3timeloss detectedC1*dSR1C2*dSR1R1’s request timerin this intervalC1= 1C2= 2R2R3R1Inter-node delay =1 time unitAdaptive Parameter Adjustment• Can trade-off higher delay for lower request/response duplicates• Probabilistic Suppression: Higher C2=> higher expected delay, but less likely to have