CS433/533 Computer Networks Lecture 13 CDN & Unstructured P2P 2/21/2012 1Outline q Admin and recap o Case studies: Content Distribution o Forward proxy (web cache) o Akamai o YouTube o P2P networks 2Admin ❒ Programming assignment 1 questions? ❍ Please refresh class home page for QAs. 3Recap: Load Direction 4 server state net path property between servers/clients server selection algorithm specific request of a client notify client about selection (direction mech.) server routingRecap: Direction Mechanisms 5 DNS name1 IP1 IP2 IPn Cluster1 in US East Cluster2 in US West Load balancer Load balancer proxy Cluster2 in Europe Load balancer Load balancer servers DNS name2 - Rewrite - Direct reply - Fault toleranceOutline q Admin and recap q Case studies: Content Distribution o Forward proxy (client site web cache) o Akamai o YouTube 67 Initial Approach: Forward Cache/Proxy ❒ Web caches/proxy placed at entrance of an ISP ❒ Client sends all http requests to web cache ❍ if object at web cache, web cache immediately returns object in http response ❍ else requests object from origin server, then returns http response to client client Proxy server client origin server origin server8 Benefits of Forward Web Caching Assume: cache is “close” to client (e.g., in same network) ❒ smaller response time: cache “closer” to client ❒ decrease traffic from distant servers ❍ link at institutional/local ISP network often bottleneck ❍ Cache Hit ratio increases logarithmically with number of users ❒ Web protocols evolved extensively to accommodate caching, e.g. HTTP 1.1 origin servers public Internet institutional network 1 Gbps LAN 10 Mbps access link Institutional proxy cacheWhat Went Wrong with Forward Web Caches? ❒ However, client site (forward) Web caching was developed with a strong ISP perspective, leaving content providers out of the picture ❍ It is the ISP who places a cache and controls it ❍ ISP’s main interest to use Web caches is to reduce bandwidth 9Content Distribution Networks ❒ CDN Design Perspective: service to content publishers o performance scalability (high throughput, going beyond single server throughput) o geographic scalability (low propagation latency, going to close-by servers) o content publisher control/access 10Akamai q Akamai – original and largest commercial CDN operates around 91,000 servers in over 1,000 networks in 70 countries q Akamai (AH kuh my) is Hawaiian for intelligent, clever and informally “cool”. Founded Apr 99, Boston MA by MIT students q Akamai evolution: o Files/streaming (our focus at this moment) o Secure pages and whole pages o Dynamic page assembly at the edge (ESI) o Distributed applications 11Akamai Scalability Bottleneck 12 See Akamai 2009 investor analysts meetingBasic of Akamai Architecture q Content publisher (e.g., CNN, NYTimes) o provides base HTML documents o runs origin server(s) q Akamai runs o edge servers for hosting content • Deep deployment into 1000 networks o customized DNS redirection servers to select edge servers based on • closeness to client browser • server load 13Linking to Akamai q Originally, URL Akamaization of embedded content: e.g., <IMG SRC= http://www.provider.com/image.gif > changed to <IMGSRC = http://a661. g.akamai.net/hash/image.gif> q URL Akamaization is becoming obsolete and supported mostly for legacy reasons o Currently most content publishers prefer to use DNS CNAME to link to Akamai servers 14 Note that this DNS redirection unit is per customer, not individual files.15 Akamai Load Direction Flow Internet Web client Hierarchy of CDN DNS servers Customer DNS servers (1) (2) (3) (4) (5) (6) LDNS Client requests site Client gets CNAME entry with domain name in Akamai Client is given 2 nearby web replica servers (fault tolerance) Web replica servers Multiple redirections to find nearby edge servers More details see “Global hosting system”: FT Leighton, DM Lewin – US Patent 6,108,703, 2000.Exercise: Zoo machine q Check any web page of New York Times and find a page with an image q Find the URL q Use %dig +trace +recurse to see Akamai load direction 16Akamai Load Direction 17 If the directed edge server does not have requested content, it goes back to the original server (source) .Two-Level Direction 18 proximity: high-level DNS determines client location; directs to low-level DNS, who manages a close-by cluster LB: maps request to individual machines inside clusterLocal DNS Alg: Potential Input o p(m, e): path properties (from a client site m to an edge sever e) • Akamai might use a one-hop detour routing (see akamai-detour.pdf) o akm: request arrival rate from client site m to publisher k o uk: service rate for requests for publisher k o xe: load on edge server e o caching state of a server e 19Local DNS Alg q Details of Akamai algorithms are proprietary q A Bin-Packing algorithm (column 12 of Akamai Patent) every T second o Compute the load to each publisher k (called serial number) o Sort the publishers from increasing load o For each publisher, associate a list of random servers generated by a hash function o Assign the publisher to the first server that does not overload 2021 Experimental Study of Akamai Load Balancing q Methodology o 2-months long measurement o 140 PlanetLab nodes (clients) • 50 US and Canada, 35 Europe, 18 Asia, 8 South America, the rest randomly scattered o Every 20 sec, each client queries an appropriate CNAME for Yahoo, CNN, Fox News, NY Times, etc. Akamai Low-Level DNS Server Akamai Web replica 1 Akamai Web replica 2 Akamai Web replica 3 .…… Web client See http://www.aqualab.cs.northwestern.edu/publications/Ajsu06DBA.pdfClient 2: Purdue Web replica IDs 06/1/05 16:16 22 Server Pool: to Yahoo day night Client 1: Berkeley Web replica IDs Target: a943.x.a.yimg.com (Yahoo)23 Server Diversity for Yahoo Majority of PL nodes see between 10 and 50 Akamai edge-servers Nodes far away from Akamai hot-spots24 Server Pool: Multiple Akamai Hosted Sites Number of Akamai Web Replicas Clients25 Load Balancing Dynamics Berkeley Brazil Korea26 Redirection Effectiveness: Measurement Methodology Planet Lab Node Akamai Low-Level DNS Server 9 Best Akamai