EECS 122: Introduction to Computer Networks Overlay Networks, CDNs, and P2P NetworksOverlay Networks: MotivationsMotivations (cont’d)GoalsSolutionExamplesMotivation Example: Internet RadioThis approach does not scale…Multicast Service ModelInstead build treesMulticast PrimerSource Specific TreesSlide 13Shared TreeIP Multicast ProblemsOverlay ApproachNarada [Yang-hua et al, 2000]Narada: End System MulticastPerformance ConcernsSlide 20PropertiesSlide 22Content Distribution Networks“Base-line”Reverse CachesForward ProxiesContent Distribution Networks (CDNs)CDNs (cont’d)Example: AkamaiSlide 30Slide 31How Did it Start?ModelMain ChallengeOther ChallengesNapsterNapster: ExampleGnutellaGnutella: ExampleTwo-Level HierarchySkypeDetour: NAT (1/3)Detour: NAT (2/3)Detour: NAT (3/3)BitTorrent (1/2)BitTorrent (2/2)Distributed Hash TablesContent Addressable Network (CAN)CAN Example: Two Dimensional SpaceSlide 50Slide 51Slide 52Slide 53Slide 54CAN: Query ExampleChordData StructureChord ExampleSlide 59Slide 60Chord ExamplesQueryDiscussionSlide 64Slide 65Katz, Stoica F04EECS 122: Introduction to Computer Networks Overlay Networks, CDNs, and P2P NetworksComputer Science DivisionDepartment of Electrical Engineering and Computer SciencesUniversity of California, BerkeleyBerkeley, CA 94720-17762Katz, Stoica F04Overlay Networks: MotivationsChanges in the network happen very slowlyWhy?-Internet network is a shared infrastructure; need to achieve consensus (IETF)-Many of proposals require to change a large number of routers (e.g., IP Multicast, QoS); otherwise end-users won’t benefit Proposed changes that haven’t happened yet on large scale:-Congestion (RED ‘93); More Addresses (IPv6 ‘91)-Security (IPSEC ‘93); Multicast (IP multicast ‘90)3Katz, Stoica F04Motivations (cont’d)One size does not fit allApplications need different levels of-Reliability-Performance (latency)-Security -Access control (e.g., who is allowed to join a multicast group)-…4Katz, Stoica F04GoalsMake it easy to deploy new functionalities in the network accelerate the pace of innovation Allow users to customize their service5Katz, Stoica F04SolutionDeploy processing in the networkHave packets processed as they traverse the networkAS-1IPAS-1Overlay Network(over IP)6Katz, Stoica F04ExamplesOverlay multicastContent Distribution Networks (CDNs)Peer-to-peer systems7Katz, Stoica F04Motivation Example: Internet Radiowww.digitallyimported.com (techno station)-Sends out 128Kb/s MP3 music streams-Peak usage ~9000 simultaneous streams•Only 5 unique streams (trance, hard trance, hard house, eurodance, classical)-Consumes ~1.1Gb/s•Bandwidth costs are large fraction of their expenditures (maybe 50%?)-If 1000 people are getting their groove on in Berkeley, 1000 unicast streams are sent from NYC to Berkeley8Katz, Stoica F04This approach does not scale…BackboneISPBroadcastCenter9Katz, Stoica F04Multicast Service ModelReceivers join a multicast group which is identified by a multicast address (e.g. G)Sender(s) send data to address GNetwork routes data to each of the receiversSR0R1...R0 joins GR1 joins GRn-1 joins G[R0, data][R1, data][Rn-1, data][R0, data][R1, data][Rn-1, data]UnicastRn-1NetSR0R1...[G, data][G, data][G, data][G, data]MulticastRn-1Net10Katz, Stoica F04Instead build treesBackboneISPBroadcastCenterCopy data at routersAt most one copy of a data packet per link•Routers keep track of groups in real-time•“Path” computation is Tree computation•LANs implement layer 2 multicast by broadcasting11Katz, Stoica F04Multicast PrimerType of trees-Source Specific Trees-Shared TreesExamples-Distance Vector Routing Multicast Protocol (DVRMP) – Source specific trees-Core Based Tree (CBT) – Shared trees-Protocol Independent Multicast (PIM)•Sparse mode Shared trees•Dense mode Single source trees12Katz, Stoica F04Source Specific Trees6785431212101311Each source is the route of its own tree13Katz, Stoica F04Source Specific Trees6785431212101311Each source is the route of its own tree. One tree for each sourceCan pick “good” trees but lots of state at the routers!14Katz, Stoica F04Shared Tree6785431212101311One tree used by all Can’t pick “good” trees but minimal state at the routers15Katz, Stoica F04IP Multicast ProblemsFifteen years of research, but still not widely deployedPoor scalability-Routers need to maintain per-group or even per-group and per-sender state!-Aggregation of multicast addresses is complicatedSupporting higher level functionality is difficult-IP Multicast: best-effort multi-point delivery service-Reliability and congestion control for IP Multicast complicated•Need to deal with heterogeneous receiver negotiation hardNo support for access control-Nor restriction on who can send very easy to mount Denial of Service (Dos) attacks!16Katz, Stoica F04Overlay ApproachProvide IP multicast functionality above the IP layer application level multicastChallenge: do this efficientlyProjects:-Narada-Overcast-Scattercast-Yoid-…17Katz, Stoica F04Narada [Yang-hua et al, 2000]Source Speific TreesInvolves only end hostsSmall group sizes <= hundreds of nodesTypical application: chat18Katz, Stoica F04Narada: End System MulticastStanfordCMUStan1Stan2Berk2Overlay TreeGatechBerk1BerkeleyGatechStan1Stan2CMUBerk1Berk219Katz, Stoica F04Performance ConcernsStretch-Ratio of latency in the overlay to latency in the underlying networkStress-Number of duplicate packets sent over the same physical link20Katz, Stoica F04Performance ConcernsDuplicate Packets:Bandwidth WastageCMUStan1Stan2Berk2GatechBerk1Delay from CMU to Berk1 increasesStanfordBerkeleyGatechStan1Stan2CMUBerk1Berk221Katz, Stoica F04PropertiesEasier to deploy than IP Multicast-Don’t have to modify every router on pathEasier to implement reliability than IP Multicast-Use hop-by-hop retransmissionsCan consume more bandwidth than IP MulticastCan have higher latency than IP MulticastNot clear how well it scales-Neither has been used for a group with 1M receivers or 1M groupsCan use IP Multicast where available to optimize performance22Katz, Stoica F04ExamplesOverlay MulticastContent Distribution Networks (CDNs)Peer-to-peer systems23Katz, Stoica F04Content Distribution NetworksProblem: You are a web content provider -How do you handle millions of web clients?-How do you ensure that all clients experience
View Full Document
Unlocking...