Slide 1Outline todayLimitations of DNS-based failoverMotivation for IP anycastIP anycast in actionSlide 6Slide 7Slide 8Slide 9Slide 10Slide 11Downsides of IP anycastMulticast protocolsMulticasting messagesAnother way to slice itSlide 16IP MulticastIGMP v1IGMPSlide 20So far, we’ve been best-effort IP multicast…Challenges for reliable multicastSlide 23Scalable Reliable MulticastSlide 25Pragmatic General Multicast (RFC 3208)A stronger “reliability”?“Virtual synchrony” multicast performanceSlide 29Slide 30Slide 31Slide 32Slide 33Slide 34Delivery? Garbage Collection?OptimizationsSlide 37Why “bimodal”?Idea behind analysisSlide 40Epidemic algorithms via gossipingProbability of InfectionTwo prevailing stylesStill several research questionsSummaryIP ANYCAST AND MULTICASTREADING: SECTION 4.4 COS 461: Computer NetworksSpring 2009 (MW 1:30-2:50 in COS 105)Mike FreedmanTeaching Assistants: Wyatt Lloyd and Jeff Terracehttp://www.cs.princeton.edu/courses/archive/spring09/cos461/1Outline today•IP Anycast•Multicast protocols–IP Multicast and IGMP–SRM (Scalable Reliable Multicast)–PGM (Pragmatic General Multicast)–Bimodal multicast–Gossiping2Limitations of DNS-based failover•Failover/load balancing via multiple A records;; ANSWER SECTION:www.cnn.com. 300 IN A 157.166.255.19www.cnn.com. 300 IN A 157.166.224.25www.cnn.com. 300 IN A 157.166.226.26www.cnn.com. 300 IN A 157.166.255.18•If server fails, service unavailable for TTL–Very low TTL: Extra load on DNS–Anyway, browsers cache DNS mappings •What if root NS fails? All DNS queries take > 3s?3Motivation for IP anycast•Failure problem: client has resolved IP address–What if IP address can represent many servers?•Load-balancing/failover via IP addr, rather than DNS•IP anycast is simple reuse of existing protocols–Multiple instances of a service share same IP address–Each instance announces IP address / prefix in BGP / IGP–Routing infrastructure directs packets to nearest instance of the service•Can use same selection criteria as installing routes in the FIB–No special capabilities in servers, clients, or network4Client Router 1IP anycast in actionServer Instance AServer Instance BRouter 3Router 2Router 410.0.0.110.0.0.1192.168.0.1192.168.0.2Announce 10.0.0.1/32Announce 10.0.0.1/32Router 1IP anycast in actionClientServer Instance AServer Instance BRouter 3Router 2Router 410.0.0.110.0.0.1192.168.0.1192.168.0.2Routing Table from Router 1:Destination Mask Next-Hop Distance192.168.0.0 /29 127.0.0.1 010.0.0.1 /32 192.168.0.1 110.0.0.1 /32 192.168.0.2 2Client Router 1IP anycast in actionServer Instance AServer Instance BRouter 3Router 2Router 410.0.0.110.0.0.1192.168.0.1192.168.0.2DNS lookup for http://www.server.com/produces a single answer:www.server.com. IN A 10.0.0.1Router 1IP anycast in actionClientServer Instance AServer Instance BRouter 3Router 2Router 410.0.0.110.0.0.1192.168.0.1192.168.0.2Routing Table from Router 1:Destination Mask Next-Hop Distance192.168.0.0 /29 127.0.0.1 010.0.0.1 /32 192.168.0.1 110.0.0.1 /32 192.168.0.2 2Router 1IP anycast in actionClientServer Instance AServer Instance BRouter 3Router 2Router 410.0.0.110.0.0.1192.168.0.1192.168.0.2Routing Table from Router 1:Destination Mask Next-Hop Distance192.168.0.0 /29 127.0.0.1 010.0.0.1 /32 192.168.0.1 110.0.0.1 /32 192.168.0.2 2Router 1IP anycast in actionClientServer Instance AServer Instance BRouter 3Router 2Router 410.0.0.110.0.0.1192.168.0.1192.168.0.2Routing Table from Router 1:Destination Mask Next-Hop Distance192.168.0.0 /29 127.0.0.1 010.0.0.1 /32 192.168.0.1 110.0.0.1 /32 192.168.0.2 2Router 1IP anycast in actionClient ServerRouter 3Router 2Router 410.0.0.1192.168.0.1192.168.0.2Routing Table from Router 1:Destination Mask Next-Hop Distance192.168.0.0 /29 127.0.0.1 010.0.0.1 /32 192.168.0.1 110.0.0.1 /32 192.168.0.2 2From client/router perspective, topology could as well be:Downsides of IP anycast•Many Tier-1 ISPs ingress filter prefixes > /24–Publish a /24 to get a “single” anycasted address: Poor utilization•Scales poorly with the # anycast groups–Each group needs entry in global routing table•Not trivial to deploy– Obtain an IP prefix and AS number; speak BGP•Subject to the limitations of IP routing–No notion of load or other application-layer metrics–Convergence time can be slow (as BGP or IGP convergence)•Failover doesn’t really work with TCP –TCP is stateful; other server instances will just respond with RSTs–Anycast may react to network changes, even though server online•Root name servers (UDP) are anycasted, little else12Multicast protocols13Multicasting messages•Simple application multicast: Iterated unicast–Client simply unicasts message to every recipient–Pros: simple to implement, no network modifications–Cons: O(n) work on sender, network•Advanced overlay multicast–Build receiver-driven tree–Pros: Scalable, no network modifications–Cons: O(log n) work on sender, network; complex to implement•IP multicast–Embed receiver-driven tree in network layer–Pros: O(1) work on client, O(# receivers) on network–Cons: requires network modifications; scalability concerns?14Another way to slice itBest effort ReliableIterated Unicast UDP-based communicationTCP-based communication; Atomic broadcastApplication “Trees” UDP-based trees (P2P) TCP-based trees; Gossiping;Bimodal multicast *IP-layer multicast IP multicast SRM;PGM;NORM;Bimodal multicast *15Another way to slice itBest effort ReliableIterated Unicast UDP-based communicationTCP-based communication; Atomic broadcastApplication “Trees” UDP-based trees (P2P) TCP-based trees; Gossiping;Bimodal multicast *IP-layer multicast IP multicast SRM;PGM;NORM;Bimodal multicast *16IP Multicast•Simple to use in applications–Multicast “group” defined by IP multicast address•IP multicast addresses look similar to IP unicast addrs•224.0.0.0 to 239.255.255.255 (RPC 3171)–265 M multicast groups at most–Best effort delivery only•Sender issues single datagram to IP multicast address•Routers delivery packets to all subnetworks that have a receiver “belonging” to the group•Receiver-driven membership–Receivers join groups by informing upstream routers–Internet Group Management Protocol (v3: RFC 3376)17IGMP v1•Two types of IGMP msgs (both have IP TTL of 1)–Host membership query: Routers query local networks to discover which groups have members–Host membership report: Hosts
View Full Document