15 WWW 501
1 W4C WG 1 WWW (HTTP[53, 22]) WIDE WWW 1997 3 WIDE WWW WIDE CacheBone WG 2 WWW WG WWW W4C WG 2 WIDE CacheBone 3 4 5 6 WWW 1 W4C WG:WIDE World-Wide Web Cache Working Group 503
2 WIDE CacheBone W4C WG HTTP WIDE CacheBone WIDE CacheBone 2.1 WIDE CacheBone WIDE CacheBone 1997 4 Squid[3] ICP(Internet Cache Protocol)[126] Squid WIDE CacheBone 2.1.1 Squid Squid National Laboratory for Applied Network Research (NLANR) WWW Harvest Project Harvest Cached Harvest Cached NetCache Cached Network Appliance Squid CERN httpd (W3C httpd) fork() I/O (DNS FTP ) ICP ( ) SSL 504
15 WWW 505 2.1.2 ICP ICP (Internet Cache Protocol) WWW RFC2186[126] ICP version 2 ICP 1. neighbor URL query 2. neighbor URL hit miss response 3. hit neighbor HTTP Squid neighbor ICP hit neighbor HTTP neighbor hit hit neighbor neighbor neighbour hit parent HTTP 2.1.3 W4C WG WWW WWW WIDE NOC ICP NOC NOC NOC sibling NOC 2 NOC sibling
506 1998 WIDE Aomi Kyushu-U Fukuoka Komatsu Otemachi Sapporo NCA5 KARRN Hachioji Tokyo Nezu Hiroshima Kyoto.net.com Fujisawa Nihon-U Osaka Nara AIII.org Gifu Hamamatsu.edu Sanfrancisco Sendai NOC WWW Cache Node Parent Cache Node Leaf Site Other Network 2.1: WIDE CacheBone NOC parent WG ICP sibling WWW ICP sibling parent parent 2.2 WIDE CacheBone WIDE CacheBone 2.2 11 WWW NOC NOC NOC NOC parent
15 WWW 507 2.3 WIDE WIDE CacheBone W4C WG WIDE WIDE CacheBone WWW WIDE CacheBone WIDE WIDE WWW WWW parent parent
3 WWW WWW 1 WWW WWW 3.1 1) 2) 508
15 WWW 509 3.2 WWW 3.3 WWW Squid Squid Referer Referer URL Referer WWW Netscape Internet Explorer Referer 3.3.1 Content-type Referer Content-type text/html text/plain Referer Referer HTML( Text)
510 1998 WIDE Referer 3.3.2 IP Referer Referer Referer URL Referer 3.4 Squid 2.0 1998 12 1 GET 430 100 1 5 30 3 3.1 80% 10 1 3.2 80% 10 3.3 3.1 39.6% 4.5% 3.4 10 1
15 WWW 511 100 80 timemout=1min timeout=5min timeout=30min sec 0.1 1 10 100 1000 CDF (%) 60 40 20 0 100msec 1sec 1min 1hour page response time 3.1: 100 80 timeout=1min timeout=5min timeout=30min CDF (%) 60 40 20 0 1 10 100 the number of objects in a page 3.2: 1 3.1: 1 5 30 4.6 % 4.4% 4.6% 39.6%
512 1998 WIDE 100 80 KBytes 0.1 1 10 100 1000 "object_size" page_size (timeout=1min) page_size (timeout=5min) page_size (timeout=30min) CDF (%) 60 40 20 0 1KB data size 1MB 3.3: / CDF (%) 100 80 60 40 sec 0.1 1 10 100 1000 request_interval (timeout=1min) request_interval (timeout=5min) request_interval (timeout=30min) thinking_time (timeout=1min) thinking_time (timeout=5min) thinking_time (timeout=30min) 20 0 100msec1sec 1min 1hour request interval/thinking time 3.4:
15 WWW 513 3.5 1 5 30 1 HTTP 1 10 HTTP 1 PHTTP PHTTP 1 1 HTTP 1 HTTP WWW 3.6 WWW WWW HTTP WWW
4 WWW WWW 1 SPEC web[6] WWW SPEC web WWW WWW WWW WWW WWW WWW WWW WWW WWW WWW 4.1 TCP WWW WWW HTTP HTTP TCP TCP HTTP HTTP TCP WWW 514
15 WWW 515 Client SYN_SENT SYN ( ) ESTABLISHED ack REQ SYN+ack Server listen() i LISTEN ii ( ) accept() iii ESTABLISHED accept read()... DATA write() close() CLOSE_WAIT ( ) LAST_ACK CLOSED ack FIN... FIN ack iv v vi vii FIN_WAIT_1 ( ) FIN_WAIT_2 TIME_WAIT 4.1: TCP 4.1.1 TCP TCP [118] 1. (ISN) SYN ( 4.1 i) 2. SYN ISN+1 ack SYN ( 4.1 ii) 3. SYN ISN+1 ack ( 4.1 iii) 3 FIN FIN FIN FIN ( 4.1 iv) FIN ack( 4.1 v) FIN ( 4.1 vi) +1 ack ( 4.1 vii) TIME WAIT
516 1998 WIDE FIN ( 4.1 iv) +1 ack( 4.1 v) FIN ( 4.1 vi) ack ( 4.1 vii) ack CLOSE 4 4.1.2 WWW WWW WWW WWW WWW WWW 4.2 WWW WWW WWW 4.2 OS WWW 4.1 accept close ack 4.3 WWW WWW WWW WWW
15 WWW 517 server host server program user side kernel kernel side 4.2: 4.1 accept close i vii WWW 4.3.1 HTTP TCP WWW HTTP 80 TCP 4.3.2 SYN SYN+ack SYN+ack ack 4.3.3 HTTP
518 1998 WIDE BPF IP TCP 4.3: FIN FIN ack FIN FIN ack ack 1 RST RST 4.4 4.4.1 (BPF)[88] BPF libpcap libpcap C UNIX 4.4.2
15 WWW 519 router 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 server 00000000 11111111 00000000 11111111 host 00000000 11111111 11111111 00000000 monitor 00000000 11111111 00000000 11111111 host 00000000 11111111 11111111 00000000 4.4: 4.3 BPF IP IP IP TCP ack TCP SYN FIN ACK RST 4.5 4.5.1 80 Internet WWW 4.5.2 IBM-PC CPU PentiumII 300MHz 64MBytes OS FreeBSD 2.2.6-Release 100Mbit Ethernet Interface Card WWW Sun Enterprise 450 2 Ultra SPARC 300MHz 512MBytes OS SunOS 5.6 4.5.3
520 1998 WIDE 1e+07 1e+06 monitor host WWW server 100000 frequency 10000 1000 100 10 1 0.00010.001 0.01 0.1 1 10 100 1000 10000 time(sec) 4.5: 4.4 WWW WWW 4.5.4 4.5 WWW 4.5 WWW 0.001 0.02 0.1 WWW 4.5 WWW 4.6 WWW SYN+ack ack accept read HTTP request write 8/17 90% 4.7 5Kbytes OS socket buer 8KBytes socket buer write write close 4.6 WWW TCP 1 4.5KBytes
15 WWW 521 Client SYN ack REQ ack ack FIN SYN+ack DATA FIN ack Server accept() i ii iii read() write() close() iv v vi vii 1RTT accept 1RTT 1RTT WWW 4.6: 1 0.8 CDF 0.6 0.4 0.2 0 100 1000 10000 100000 object size(bytes) 4.7:
522 1998 WIDE 15000 number of connections 10000 5000 0 0 20000 40000 60000 80000 time(sec) 4.8: 1 4 4 2RTT FIN 1RTT ack SYN 4RTT WWW 1RTT IP 3RTT 0.2 WWW 0.001 WWW 0.001 OS 0.001 0.001 WWW 0.001 0.001 WWW 4.8 4.8 1 13000 4.9 WWW 1 4.9 550 4.8 4.9 WWW WWW 4.10 4.10 WWW WWW
15 WWW 523 600 number of connections 400 200 0 0 20000 40000 60000 80000 time(sec) 4.9: WWW 400000 Server log Monitor log number of connections 300000 200000 100000 0 0 20 40 60 80 100 120 140 160 180 time(10minute) 4.10: 8/17
524 1998 WIDE 4.6 WWW OS OS 4.7 TCP HTTP WWW WWW 4.8 WWW WWW WWW WWW WWW WWW
5 WWW 1 Harvest[32] Squid[3] sibling parent Internet Cache Protocol (ICP)[126] ICP UDP 2 1 HTTP 1 sibling parent ICP sibling ICP 1 ICP [12, 44] [21, 146, 167] ICP sibling 1 525
526 1998 WIDE ( ) 5.1: 5.1 ICP UDP URL 20 URL 50byte 2 ICP 100byte WWW 10kbyte [167] ICP ICP 2 1 1 sibling ICP HTTP ICP ICP ICP 2 98 5 343
15 WWW 527 UDP sibling HTTP 5.2 1 HTTP ICP 1 5.2.1 1 HTTP HTTP TCP 5.2 HTTP 3-way GET FIN 3-way 3 GET URL 50byte 1 Maximum Transmission Unit(MTU) MTU 1500byte [166] IP TCP 1460byte 10kbyte 7 ACK 3 3 FIN FINACK FIN FINACK 4 HTTP IP 18 3 delayed ack ACK
528 1998 WIDE Client SYN ACK SYNACK Server REQ DATA... FINACK FIN FIN FINACK 5.2: HTTP ( DATA ACK ) Local Query Sibling Reply 5.3: ICP 5.2.2 1 ICP ICP UDP ICP 5.3 sibling ICP ICP sibling ICP 20byte URL URL 50byte 1 2 5.3
15 WWW 529 WWW Server Internet Sibling Sibling Proxy Client 5.4: 5.3.1 5.4 LAN LAN WWW sibling sibling 5.3.2 HTTP ICP 5.5 C = C 1 ;:::;C w HTTP P HTTP P P sibling S = S 1 ;:::;S u ICP ICP sibling O HTTP sibling S 0 = S 0 1 ;:::;S0 v P S 0 sibling P sibling sibling ICP
530 1998 WIDE S = {S1,..., Su} Sibling ICP HTTP C = {C1,..., Cw} P O Client HTTP Caching Proxy HTTP Origin Server ICP HTTP Sibling S = {S1,..., Sv } 5.5: P P HTTP P 5.3.3 HTTP ICP T ( 1 ) P N C HTTP N 1 sibling S 0 ICP HTTP N 2 N 1 N 2 HTTP HTTP 1 N 1 R : T HTTP
15 WWW 531 5.1: HTTP C $ P (HTTP) 1 n P $ S (ICP) 1 0 p um P $ S i (HTTP) q n P $ O (HTTP) 1 0 p 0 q n p : P ( HTTP ) q : P ( HTTP ) u : P sibling n :1 HTTP m :1 ICP C HTTP HTTP n P p (1 0 p) u sibling ICP q sibling HTTP (1 0 p 0 q) HTTP ( parent) 5.1 N1 N1 = Rfn +(10 p)um + qn +(10 p 0 q)ng = Rf(2 0 p)n +(10 p)umg sibling ICP N2 P parent parent ICP HTTP P R 0 i : T sibling S 0 HTTP (i =1;:::;v) i v : P sibling p 0 : sibling S 0 (i =1;:::;v) i i
532 1998 WIDE q 0 : sibling S 0 (i =1;:::;v) i i u 0 i k i : sibling S 0 sibling (i =1;:::;v) i : sibling S 0 P (i =1;:::;v) i A : P sibling S 0 ICP B : P sibling S 0 HTTP S 0 HTTP S 0 i R0 i p0 i i HTTP ICP u 0 sibling P i P ICP A vx A = m (1 0 p 0 i)r 0 i i=1 S 0 ICP S 0 HTTP i q0 i i P HTTP k i P HTTP B N2 vx B = n (1 0 p 0 i)r 0 q 0 k i i i i=1 N2 = A + B vx = (1 0 p 0 i)ri(m 0 + nq 0 k i i) i=1 5.4 N N = N1 + N2 = Rf(2 0 p)n +(10p)umg vx + (1 0 p 0 (m + k i )R0 i nq0 i i) i=1 P
15 WWW 533 5.2: R, R 0 i n m p 0 i q 0 i k i 1 2 10 5 18 2 0.4 0.1 0.25 p : u : sibling v : sibling P R, R 0 : i n : m :ICP p 0 i, q 0 i, k i : S 0 i R R 0 10 i n m 5.2.1 5.2.2 18 2 p 0 i q0 i [127] 30-50% 10% 4 p 0 0.4 0.1 k i q0 i i P sibling sibling 0.25 5.2 N N =12 10 5 f36 0 18p +2(10 p)u +1:47vg 2 1 sibling sibling v =0 1 sibling sibling v >0 5.4.1 1 sibling (v =0) 4
534 1998 WIDE 5.3: N v =0 ( 100 ) p n u 0 2 4 6 8 10 0.3 3.06 3.34 3.62 3.90 4.18 4.46 0.4 2.88 3.12 3.36 3.60 3.84 4.08 0.5 2.70 2.90 3.10 3.30 3.50 3.70 sibling sibling sibling sibling 5.3 sibling sibling 5.4.2 2 sibling (v >0) sibling sibling 1 sibling v sibling u sibling 5.4 v = u v =0 sibling sibling sibling sibling 5.5 5.3 98 5 31
15 WWW 535 5.4: N v = u ( 100 ) p n u 0 2 4 6 8 10 0.3 3.06 3.63 4.21 4.78 5.36 5.93 0.4 2.88 3.41 3.95 4.48 5.02 5.55 0.5 2.70 3.19 3.69 4.18 4.68 5.17 5.5: R p u q N1 A B N X 106545 0.34 8 0.065 4308680 2254 1530 4312464 Y 173750 0.53 2 0.011 4924075 182920 292824 5399819 Z 4857 0.26 5 0.020 188063 136012 32904 356979 1 5.5.1 ( 5.5) n m 18 2 sibling ICP HTTP A B q 5.5.2 5.5 X sibling sibling 5 1 10% 0% 5% 10% p u N 5.6 8 sibling 6.5% sibling 319 431 35% 5
536 1998 WIDE 5.6: X( 100 ) p n u 0 2 4 6 8 0.34 3.19 3.47 3.75 4.03 4.31 0.39 3.09 3.35 3.61 3.87 4.13 0.44 3.00 3.23 3.47 3.71 3.95 5.7: Y( 100 ) p n u 0 1 2 0.53 5.07 5.24 5.40 sibling 10% 6-9% Y sibling sibling 2 X 53% u 5.7 1.1% sibling 540 507 6.1% Z sibling ICP ICP 2.7% HTTP Z parent HTTP
15 WWW 537 5.6 sibling X sibling sibling sibling ICP sibling sibling HTTP ICP HTTP ICP Z 1 ICP sibling ICP 5.7 parent parent ICP HTTP parent
538 1998 WIDE 5.1 HTTP UDP 5.8 ICP ICP sibling ICP HTTP ICP 1 sibling sibling ICP ICP
6 WebCache WWW WWW (cache) WWW 6.1 Internet reachability Internet WWW WWW WWW ( ) ( CPU ) 6.2 WWW 6.2.1 WWW 539
540 1998 WIDE (locality) WWW Zipf (Zipf's law) ( Zipf ) 1 (reload) 60% 70% 20% 40% 20% 40% WWW WWW 6.2.2 WWW (proxy server) WWW Internet
15 WWW 541 : Zipf's law Zipf's law (6.1) (6.1) (6.2) f 1 r (6:1) f(r) =Cr 0k (6:2) f: frequency f(r)=c*r^(-k) r: rank of objects C k k 1.1 1.0 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.0 1 2 3 4 5 6 7 8 9 10 11 log10(c) hit rate [%] 100 90 80 70 60 50 40 30 20 10 0 WAN LAN
542 1998 WIDE 6.2.3 6.2.4 WWW HyperText Transfer Protocol (HTTP) I/O Domain Name Service (DNS)
15 WWW 543 6.2.5 Harvest 5 6.3 1) 2) Internet 3) CPU 4)
544 1998 WIDE 6.3.1 6.3.2 LAN NetNews anonymous FTP 6.3.3 Zipf's law 10 100
15 WWW 545 64 256 ( 20 ) 6.3.4 Zipf 6.4 WWW (prefetching) (replication) WWW WWW Internet 6.5 WWW WWW WWW
546 1998 WIDE
7 2 WWW WWW WIDE CacheBone WWW WWW proxy [139] 6 WWW WG WWW WIDE CacheBone WIDE 1998 W4C WG ICP WWW W4C WG WWW Cache \ " WWW WIDE CacheBone WWW \ " \WWW " Web W4C WG 1998 WWW proxy WWW 547
548 1998 WIDE