DPNM Lab, GSIT, POSTECH Email: shk@postech.ac.kr 1
2
(1) Internet World-Wide Web Web traffic Peak periods off-peak periods peak periods off-peak periods 3
(2) off-peak peak Web caching network traffic peak periods off-peak periods peak periods off-peak periods Web caching fetch. off-peak periods peak periods peak periods. 4
- Server-initiated prefetching (Azer Bestavros, 1996) Client-initiated prefetching (V. Padmanabhan, 1996) Proxy-initiated prefetching (Li Fan, 1999) Deterministic prefetching (Z. Wang, 1996) Statistical prefetching (Tomas M. Kroeger, 1997) Prefetching for Response Time Reduction (V. Padmanabhan, 1996) Prefetching for Balanced Bandwidth Usage A Statistical, Proxy-initiated and Batch Prefetching for Balanced Bandwidth Usage 5
6
(expiration time) (reference count),, 7
Web Traffic Trace(1) : 16 subnet : 1999.10.15 ( ) - 1999.10.28 ( ), 2 : CacheRaQ (Cobalt Network) : 447 : 54.96 % : 31.42 % : 4,077,308 : 50.2 Gbyte (%) (%) 1 86,227 (70.75 %) 1479.75 Mbyte (68.12 %) 2 16,690 (13.69 %) 310.79 Mbyte (14.31 %) 3 6,462 (5.3 %) 118.20 Mbyte (5.44 %) 4 3,451 (2.83 %) 74.01 Mbyte (3.41 %) 5 9,053 (7.43 %) 189.52 Mbyte (8.72 %) Total 121,883 (100 %) 2172.27 Mbyte (100 %) 8
Web Traffic Trace(2) 9
1 day off-peak periods 80% 04:00-13:00, 9 off-peak periods 10
Prefetching System Caching Server Prefetchable Object List Generator prefetchable object list Request Generator access.log store.log Caching Server (squid) cache clients request request request Internet response response response 11
Prefetchable Object List Generateor prefetchable object list access log Squid refresh algorithm refresh algorithm store log. prefetchable object list Reference Count URL Byte Access Log Time Elapsed Remotehost Code/Status Byte Method URL Store Log Time Action Status OBJ_DATE OBJ_LASTMOD Expires Type Len Method URL 12
Refresh Algorithm(2) Is CLIENT_MAX_AGE present in the request? yes Is OBJ_AGE more than CLIENT_MAX_AGE? yes STALE(1) STALE(1) CLIENT_MAX_AGE : 100 (sec) OBJ_AGE : 120 (sec) no Is Expires present in the response? yes no Is Expires less than NOW? yes no STALE(2) FRESH STALE(2) Expires : Fri, 01 Oct 1999 16:00:00 GMT NOW : Sun, 03 Oct 1999 12:01:20 GMT no Is OBJ_AGE more than CONF_MAX? yes STALE(3) STALE(3) OBJ_AGE : 5760 min (4 days) CONF_MAX : 4320 min (3 days) no Is OBJ_DATE more than OBJ_LASTMOD? no Is OBJ_AGE less than CONF_MIN? yes LM_FACTOR less than the CONF_PERCENT? yes no yes no FRESH STALE(4) FRESH STALE(5) STALE(4) OBJ_LASTMOD : Wed, 29 Sep 1999 16:00:00 GMT OBJ_DATE : Fri, 01 Oct 1999 16:00:00 GMT LM_FACTOR : 30 % CONF_PERCENT : 20 % STALE(5) OBJ_AGE : 5760 min (4 days) CONF_MIN : 0 min 13
Freshness Squid refresh algorithm CLIENT_MAX_AGE. CLIENT_MAX_AGE. NOW = Current Prefething Time + Prefetching Frequency Current Prefetching Time : Prefetching Frequency : Last prefetching time Currnt Prefetching time Next prefetching time Input data(logs) Prefetching Frequency 10/15 4:00 10/16 4:00 10/17 4:00 14
Request Generator Prefetchable Object List HTTP off-peak periods HTTP requests Web server Web client wget HTTP command-line Web client Crontab off-peak periods 15
Input Parameter Logs : access log and store log (1999.10.15-1999.10.28, 2 ) : Off-peak periods (04:00-13:00) : 1 day : 1, 2, 3, 4, 5 : off-peak peirods refresh algorithm parameter OBJ_DATE, Expires, OBJ_LASTMOD, NOW, CONF_MAX, CONF_MIN, CONF_PERCENT Simulation Model access.log store.log Prefetchable Object List Generator Prefetchable Object List Performance Analyzer Performance Metrics With Prefetching Performance Metrics Without Prefetching 16
- Performance Metrics Request Saving Bandwidth Saving Accuracy Wasted Bandwidth 17
- Accuracy & Wasted Bandwidth Accuracy Wasted Bandwdith 18
- Request Saving & Bandwidth Saving Request Saving Bandwdith Saving 19
- Summary E p E? B / B p s w E B p : B : ( Mbyte) s w : ( Mbyte) Bandwidth Saving B s (Mbyte) B w (Mbyte) E p Bandwidth Saving Wasted bandwidth 1 189.16 670.72 0.28 5.01 % 17.8 % 2 141.82 172.65 0.82 3.78 % 4.6 % 3 85.65 74.47 1.15 2.27 % 2.0 % 4 60.08 35.91 1.67 1.59 % 1.0 % 5 45.06 16.97 2.66 1.19 % 0.5 % 2 20
Off-peak periods peak periods. 2 Request saving Bandwidth saving Wasted bandwidth Prefetched object hit rate Accuracy Prefetched byte hit rate 2 3.53 % 3.78 % 4.6 % 64.3 % 45.1%. peak periods : 20.52 Kbps add-on feature. real-time list Prefetching Object List Generator 21