CS514: Intermediate Course in Operating SystemsIP multicastUnicast to multiple hostsMulticast to multiple hostsWhy do multicast?Logical addressingApplicationsMulticasting for resource locationTime-to-live and hop countsExpanding-ring searchSlide 11Multicast addressesMulticast at the LAN levelMulticast beyond the LANA naive approachMulticast by floodingSlide 17Why simple flooding doesn’t workSlide 19Multicast floodingMulticast treesA multicast treeSlide 23IGMPSlide 25Slide 26Slide 27Slide 28Avoiding overloadingBuilding multicast treesReverse shortest-path forwardingSlide 32Pruning nodes from the treePruningSlide 35Slide 36Rejoining a groupThe MBONEMulticast reliabilityUDP fragmentationInterlinked failuresSlide 42Multicast behaviourMulticast problemsMulticast stormsRetransmission requestsMaking IP multicast a good citizenForward error correction (FEC)Combining retransmission requestsFurther readingCS514: Intermediate Course in Operating SystemsProfessor Ken BirmanBen Atkin: TALecture 5: Sept. 7IP 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 reliabilityUnicast to multiple hostsMulticast 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” mechanismApplications•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-to-live (TTL) valuesTime-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=1Expanding-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 ignoredMulticast 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) multicastMulticast by floodingnon-membergroup memberrouterMulticast by floodingnon-membergroup memberrouterWhy simple flooding doesn’t worknon-membergroup memberrouterWhy simple flooding doesn’t worknon-membergroup memberrouterwasted!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 multicastMulticast 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 leavesA multicast treeA multicast treeIGMP•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 pagingIGMP•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 inIGMPInternet“Who is a member?”IGMPInternet“I am” “I am” “I am”IGMPInternet“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 expirationBuilding 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 sourceReverse shortest-path forwardingReverse 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 sourcePruning 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–recursivePruningPruningPruningRejoining 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 membersThe 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 consumptionMulticast reliability•Best-effort reliability, “as good as UDP”•But has some additional problems not shared by unicast UDP–fragmentation–interlinked failuresUDP 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
View Full Document
Unlocking...