EECS 122 Introduction to Computer Networks Overlay Networks CDNs and P2P Networks Computer Science Division Department of Electrical Engineering and Computer Sciences University of California Berkeley Berkeley CA 94720 1776 Katz Stoica F04 Overlay Networks Motivations Changes in the network happen very slowly Why 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 Katz Stoica F04 2 Motivations cont d One size does not fit all Applications need different levels of Reliability Performance latency Security Access control e g who is allowed to join a multicast group Katz Stoica F04 3 Goals Make it easy to deploy new functionalities in the network accelerate the pace of innovation Allow users to customize their service Katz Stoica F04 4 Solution Deploy processing in the network Have packets processed as they traverse the network AS 1 AS 1 IP Overlay Network over IP Katz Stoica F04 5 Examples Overlay multicast Content Distribution Networks CDNs Peer to peer systems Katz Stoica F04 6 Motivation Example Internet Radio www 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 Berkeley Katz Stoica F04 7 This approach does not scale Broadcast Center Backbone ISP Katz Stoica F04 8 Multicast Service Model Unicast ata R 0 d R1 data R0 data S R1 data Rn 1 data Multicast Net R n 1 da ta R0 R1 S G data Net djoaitnas G R0 G R1 G data sG R 1 R 0 join R G n 1 da joitna s Rn 1 G Rn 1 Receivers join a multicast group which is identified by a multicast address e g G Sender s send data to address G Network routes data to each of the receivers Katz Stoica F04 9 Instead build trees Copy data at routers At most one copy of a data packet per link Broadcast Center Routers keep track of groups in real time Path computation is Tree computation Backbone ISP LANs implement layer 2 multicast by broadcasting Katz Stoica F04 10 Multicast Primer Type of trees Source Specific Trees Shared Trees Examples 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 trees Katz Stoica F04 11 Source Specific Trees 5 4 7 Each source is the route of its own tree 8 6 11 2 1 10 3 13 12 Katz Stoica F04 12 Source Specific Trees 5 4 Each source is the route of its own tree One tree for each source 7 8 6 11 2 1 10 3 13 12 Can pick good trees but lots of state at the routers Katz Stoica F04 13 Shared Tree 5 4 7 One tree used by all 8 6 11 2 1 10 3 13 12 Can t pick good trees but minimal state at the routers Katz Stoica F04 14 IP Multicast Problems Fifteen years of research but still not widely deployed Poor scalability Routers need to maintain per group or even per group and persender state Aggregation of multicast addresses is complicated Supporting 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 hard No support for access control Nor restriction on who can send very easy to mount Denial of Service Dos attacks Katz Stoica F04 15 Overlay Approach Provide IP multicast functionality above the IP layer application level multicast Challenge do this efficiently Projects Narada Overcast Scattercast Yoid Katz Stoica F04 16 Narada Yang hua et al 2000 Source Speific Trees Involves only end hosts Small group sizes hundreds of nodes Typical application chat Katz Stoica F04 17 Narada End System Multicast Gatech Stanford Stan1 Stan2 CMU Berk1 Berk2 Berkeley Overlay Tree Gatech Stan1 Stan2 CMU Berk1 Berk2 Katz Stoica F04 18 Performance Concerns Stretch Ratio of latency in the overlay to latency in the underlying network Stress Number of duplicate packets sent over the same physical link Katz Stoica F04 19 Performance Concerns Gatech Delay from CMU to Berk1 increases Stan1 Stan2 CMU Berk1 Duplicate Packets Bandwidth Wastage Gatech Stanford Berk2 Stan1 Stan2 CMU Berk1 Berkeley Berk2 Katz Stoica F04 20 Properties Easier to deploy than IP Multicast Don t have to modify every router on path Easier to implement reliability than IP Multicast Use hop by hop retransmissions Can consume more bandwidth than IP Multicast Can have higher latency than IP Multicast Not clear how well it scales Neither has been used for a group with 1M receivers or 1M groups Can use IP Multicast where available to optimize performance Katz Stoica F04 21 Examples Overlay Multicast Content Distribution Networks CDNs Peer to peer systems Katz Stoica F04 22 Content Distribution Networks Problem You are a web content provider How do you handle millions of web clients How do you ensure that all clients experience good performance How do you maintain availability in the presence of server and network failures Solutions Add more servers at different locations If you are CNN this might work Caching Content Distribution Networks Katz Stoica F04 23 Base line Many clients transfer same information Generate unnecessary server and network load Clients experience unnecessary latency Server Backbone ISP ISP 1 ISP 2 Clients Katz Stoica F04 24 Reverse Caches Cache documents close to server decrease server load Typically done by content providers Server Reverse caches Backbone ISP ISP 1 ISP 2 Clients Katz Stoica F04 25 Forward Proxies Cache documents close to clients reduce network traffic and decrease latency Typically done by ISPs or corporate LANs Server Reverse caches Backbone ISP ISP 1 ISP 2 Forward caches Clients Katz Stoica F04 26 Content Distribution Networks CDNs Integrate forward and reverse caching functionalities into one overlay network usually administrated by one entity Example Akamai Documents are cached both As a result of clients requests pull Pushed in the expectation of a high access rate Beside caching do processing e g Handle dynamic web pages Transcoding Katz Stoica F04 27 CDNs cont d Server CDN Backbone
View Full Document
Unlocking...