15-441 Computer NetworkingCaching, CDN, Consistent Hashing, P2P Web history• 1945: Vannevar Bush, “As we may think”, Atlantic Monthly, July, 1945.• describes the idea of a distributed hypertext system.•a“memex”that mimics the“web of trails”in our•a memex that mimics the web of trails in our minds.• 1989: Tim Berners-Lee (CERN) writes internal proposal to develop a distributed hypertext system• connects “a web of notes with links”.•intended to help CERN physicists in large projects•intended to help CERN physicists in large projects share and manage information • 1990: Tim BL writes graphical browser for Next machines.215-441 S'10Lecture 21: CDN/Hashing/P2PWeb history (cont)• 1992• NCSA server released• 26 WWW servers worldwide• 1993• Marc Andreessen releases first version of NCSA Mosaic Mosaic version released for (Windows, Mac, Unix).• Web (port 80) traffic at 1% of NSFNET backbone traffic.(p )• Over 200 WWW servers worldwide.• 1994Andreessen and colleagues leave NCSA to form "Mosaic•Andreessen and colleagues leave NCSA to form "Mosaic Communications Corp" (Netscape). 315-441 S'10Lecture 21: CDN/Hashing/P2PTypical Workload (Web Pages)• Multiple (typically small) objects per page • File sizes• Heavy-tailedf• Pareto distribution for tail• Lognormal for body of distribution• Embedded referencesbedded e e e ces• Number of embedded objects also paretoPr(X>x) = (x/xm)-k•Lots of small objects • This plays havoc with performance. Why?• Solutions?jmeans & TCP•3-way handshake•Lots of slow starts415-441 S'10Lecture 21: CDN/Hashing/P2PLots of slow starts•Extra connection stateWeb Proxy Caches• User configures browser: Web accesses via cache•Browser sends all HTTPProxyorigin serverBrowser sends all HTTP requests to cache• Object in cache: cache returns object clientProxyserver• Else cache requests object from origin server, then returns object to clientclientorigin server5server15-441 S'10No Caching Example (1)Assumptions•Average object size=100,000 bitsoriginAverage object size 100,000 bits• Avg. request rate from institution’s browser to origin servers = 15/sec• Delay from institutional router to originserverspublicInternetyany origin server and back to router = 2 secConsequencesInternet15Mb• Utilization on LAN = 15%• Utilization on access link = 100%• Total delay = Internet delay + access delay+LAN delayinstitutionalnetwork10 Mbps LAN1.5 Mbps access linkdelay LAN delay= 2 sec + minutes + millisecondseo10 Mbps LAN615-441 S'10No Caching Example (2)Possible solution•Increase bandwidth of access linkoriginIncrease bandwidth of access link to, say, 10 Mbps• Often a costly upgradeoriginserverspublicInternetConsequences• Utilization on LAN = 15%• Utilization on access link = 15%Internet10 Mb• Total delay = Internet delay + access delay + LAN delay= 2 sec + msecs + msecsinstitutionalnetwork10 Mb LAN10 Mbps access linknetwork10 Mbps LAN715-441 S'10W/Caching Example (3)Install cacheShitti4origin•Suppose hit rate is .4Consequence• 40% requests will be satisfied almost immediately (say 10 msec)originserverspublicInternetimmediately (say 10 msec)• 60% requests satisfied by origin server• Utilization of access link reduced to 60%, resulting in negligible delaysInternet15Mb• Weighted average of delays= .6*2 sec + .4*10msecs < 1.3 secsinstitutionalnetwork10 Mbps LAN1.5 Mbps access linkeo10 Mbps LAN8institutionalcache15-441 S'10HTTP Caching• Clients often cache documents• Challenge: update of documents• If-Modified-Since requests to check•HTTP 0 9/1 0 used just dateHTTP 0.9/1.0 used just date• HTTP 1.1 has an opaque “entity tag” (could be a file signature, etc.) as well•When/how often should the original be checked forWhen/how often should the original be checked for changes?• Check every time?C???•Check each session? Day? Etc?• Use Expires header• If no Expires, often use Last-Modified as estimate9p,15-441 S'10Lecture 21: CDN/Hashing/P2PExample Cache Check RequestGET / HTTP/1.1Accept: */*Accept-Language: en-usAccept-Encoding: gzip, deflateIf-Modified-Since: Mon, 29 Jan 2001 17:54:18 GMTIfNoneMatch: "7a11f10ed3a75ae4a"If-None-Match: "7a11f-10ed-3a75ae4a"User-Agent: Mozilla/4.0 (compatible; MSIE 5.5; Windows NT 5.0))Host: www.intel-iris.netConnection: Keep-Alive1015-441 S'10Lecture 21: CDN/Hashing/P2PExample Cache Check ResponseHTTP/1.1 304 Not ModifiedDate: Tue, 27 Mar 2001 03:50:51 GMTServer: Apache/1.3.14 (Unix) (Red-Hat/Linux) mod_ssl/2.7.1 O SSL/095 DAV/102PHP/401 l2 d l/124OpenSSL/0.9.5a DAV/1.0.2 PHP/4.0.1pl2 mod_perl/1.24Connection: Keep-AliveKeep-Alive: timeout=15 max=100Keep-Alive: timeout=15, max=100ETag: "7a11f-10ed-3a75ae4a"1115-441 S'10Lecture 21: CDN/Hashing/P2PProblems• Over 50% of all HTTP objects are uncacheable – why?Nt il l bl•Not easily solvable• Dynamic data Æ stock prices, scores, web cams• CGI scripts Æ results based on passed parameters• Obvious fixes• SSL Æ encrypted data is not cacheable• Most web clients don’t handle mixed pages well Æmany generic objects transferred with SSLobjects transferred with SSL• Cookies Æ results may be based on passed data• Hit metering Æ owner wants to measure # of hits for revenue, etc.What will be the end result?•What will be the end result?1215-441 S'10Lecture 21: CDN/Hashing/P2PCaching Proxies – Sources for Misses• Capacity• How large a cache is necessary or equivalent to infinite• On disk vs. in memory Æ typically on disk• Compulsorypy• First time access to document• Non-cacheable documents•CGI-scripts•CGI-scripts• Personalized documents (cookies, etc)• Encrypted data (SSL)•Consistency•Consistency• Document has been updated/expired before reuse• Conflict13• No such misses15-441 S'10Lecture 21: CDN/Hashing/P2PContent Distribution Networks (CDNs)()• The content providers are the CDN customersorigin server customers.Content replication• CDN company installs hundreds of CDN servers throughout Internetin North AmericaCDN servers throughout Internet• Close to users• CDN replicates its customers’ content in CDN servers When providerCDN distribution nodein CDN servers. When provider updates content, CDN updates serversCDN serverin S AmericaCDN serverCDN server14in S. AmericaCDN serverin Europein Asia15-441 S'10htt // k i /ht l/t h l / i/ /i d ht l15-441 S'1015http://www.akamai.com/html/technology/nui/news/index.htmlContent
View Full Document
Unlocking...