Transcript CS514-lec
CS514: Intermediate Course in Operating Systems Professor Ken Birman Ben Atkin: TA Lecture 5: Sept. 7 IP multicast • Has already been briefly mentioned by Professor Birman • Today we’ll see how it works – – – – rationale for multicast multicast between LANs multicast on the Internet a few words about reliability Unicast to multiple hosts Multicast to multiple hosts “to group” Why do multicast? • Send to a group, not to individual hosts – Reduces overhead in sender – Reduces bandwidth consumption in network – Reduces latency seen by receivers (all receive “at the same time”, in theory) Logical addressing • Multicast groups “handled by network” • Senders, receivers do not need to know each others’ identities • Group persists as long as it has at least one member • a “rendezvous” mechanism Applications • • • • • Teleconferencing Distance learning Multimedia streaming Directory service lookup ... Multicasting for resource location • Expanding-ring search • We want to find an instance of a resource (database, etc) which is close by • Use multicast with IP time-tolive (TTL) values Time-to-live and hop counts • TTL is a counter in the packet header – Decrement at each “hop” through a router – When TTL reaches zero, the packet is dropped – special values for “global” and “regional” TTL (use with care!) Expanding-ring search “Find me a database”, TTL=1 Expanding-ring search “Find me a database”, TTL=2 “I’m a database, what can I do for you?” Multicast addresses • Class D IP addresses for group – 224.0.0.0 to 239.255.255.255 • Treated like any other IP address: can send from it or listen to it • In practice, use UDP as well (more on this later) Multicast at the LAN level • Ethernet is a broadcast medium: all network cards see all packets • Register the multicast address in the network card – only pass matching packets to OS – all other packets are ignored Multicast beyond the LAN • We would like to multicast between hosts on different LANs – LANs are joined together directly by bridges – or can be connected through the Internet by a sequence of routers – need an inter-LAN (WAN) protocol • (in fact, this is rarely enabled!) A naive approach • We want to send multicasts everywhere where there are group members – use flooding to send multicast between routers – when we get to a LAN, use regular (Ethernet) multicast Multicast by flooding router group member non-member Multicast by flooding router group member non-member Why simple flooding doesn’t work router group member non-member Why simple flooding doesn’t work wasted! router group member non-member Multicast flooding • Not a scalable mechanism – every LAN sees every multicast – every WAN router sees every multicast: wastes bandwidth, CPU • Requires a two-part solution – determining LAN group members – omitting WAN routers from multicast Multicast trees • Shortest-path tree to all multicast members, rooted at sender • But must be computed independently by each router • And must be dynamically adjusted for joins and leaves A multicast tree A multicast tree IGMP • Internet Group Management Protocol (Deering and Cheriton) • Developed from work in V distributed operating system – introduced notion of process groups (Cheriton and Zwaenepol) – groups for services, e.g. name resolution, remote paging IGMP • Detects if a multicast group has any members within a LAN • Query and report messages – router sends query of group membership periodically – hosts report groups they’re in IGMP Internet “Who is a member?” IGMP Internet “I am” “I am” “I am” IGMP Internet “I am” “I am” “I am” Avoiding overloading • Report packets may overload router – upon getting a query, each group member sets a timer – if it sees a report for its group before the timer expires, it suppresses its report – otherwise reports on expiration Building multicast trees • Want to avoid loops, duplicates • Dalal and Metcalfe: reverse path forwarding – relies on existing (point-to-point) shortest-path data for next hops to decide where to forward to – forward a packet only if it arrived on the shortest path to its source Reverse shortest-path forwarding Reverse shortest-path forwarding • Doesn’t eliminate all duplicates • A further enhancement is to only forward a packet to a neighbour if you’re on its shortest-path to the source Pruning nodes from the tree • When they get a multicast, routers decide if they should prune themselves out – LAN routers can use IGMP to find if they have members – tell preceding node on the shortest-path tree not to forward to you – recursive Pruning Pruning Pruning Rejoining a group • A LAN router with a group member may find it has no link into the multicast tree – either sends a graft message to add itself to the tree – or use flood-and-prune: routers are periodically added back into the tree; they prune themselves again if they still have no members The MBONE • Multicast Backbone • Layer over the Internet – – – – – permitted rapid deployment only certain routers participate “tunnel” between MBONE routers has to do its own routing upper limit on bandwidth consumption Multicast reliability • Best-effort reliability, “as good as UDP” • But has some additional problems not shared by unicast UDP – fragmentation – interlinked failures UDP fragmentation • Recall that UDP packets are bigger than IP packets – With a fixed loss probability, more members = more losses – losing one IP packet drops the entire UDP packet – makes repairing failures more expensive, not used in practice (use IP-sized packets) Interlinked failures • Traditionally we assume that packets p, q being lost could be independent events – but with IP multicast they could be very correlated – an omission at a parent node causes all children to miss the packet Interlinked failures Multicast behaviour • • • • A “bad Internet citizen” No backoff, unlike TCP Runs on MBONE, not Internet! Only really usable in an intranet – Problems with bridges – Multicast flooding/storms – Everybody gets them Multicast problems • Even if routers don’t forward multicasts, they still have to process them • Similarly, a network card may be forced to drop packets if it gets too many • So too many simultaneous multicasts can cause problems! Multicast storms • Retransmissions to fix losses must be carefully controlled – too many can just aggravate the problem – and can affect the performance of non-multicasting hosts – Bridges typically drop multicasts to stop storms propagating • Want to avoid “router collapse” Retransmission requests Making IP multicast a good citizen • A hot area for research • Sender-based and receiverbased schemes – forward error correction – combining retransmission requests Forward error correction (FEC) • Sender-based mechanism – repeat multicasts in order to overcome the likelihood of packet loss: anticipate retransmission requests – or use parity, Hamming codes, etc, to generate parity packets, and receiver reconstructs dropped packets Combining retransmission requests • Receivers are more intelligent about when to make requests for retransmissions – e.g. watch to see if others make requests, if so, suppress ours – can still cause storms! • e.g. SRM, RTP2, PGM: we will return to these later Further reading • S. Keshav. An Engineering Approach to Computer Networking. Addison Wesley, 1997 • Internet Group Management Protocol, Version 3 (Cain, Deering, Kouvelas, Thyagarajan) http://www.ietf.org/internet-drafts/draft-ietfidmr-igmp-v3-04.txt • S. Deering. "Host Extensions for IP Multicasting", RFC 1112, SRI "requests for comments" repository, August 1989. • Yogan K. Dalal and Robert M. Metcalfe. "Reverse Path Forwarding of Broadcast Packets". Communications of the ACM 21:12, pp1040-1048, December 1978.