о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999ꡡ3611ڡVol.36No.111999



ڷûΪʵִ
ׯΰǿơˡ֣γ
ժҪһWWWṹվͼSite-Graphģͣڴ˻ϽûΪӶһʵʷģʽĴϵͳURAC.ϸURACĹԭԴʱҪʡһԺ滻㷨ҪۣܷõURACʺͽͷӳΪĿһʵõĴϵͳĽ.
ؼʡ棬ûΪվͼģͣһԣ滻㷨Ч
ͼšTP393.09
PROXY CACHE IMPLEMENTATION BASED ON USER
REQUESTS ANALYSIS
ZHUANG Wei-Qiang, LI Chang, WANG Ding-Xing, ZHENG Wei-Min, and SHEN Mei-Ming
(Department of Computer Science and Technology, Tsinghua University, Beijing 100084)
AbstractA site-graph model to describe the logic structure of World Wide Web is introduced in this paper. Based on this model, the behavior pattern of user requests for home pages is discussed and thus a proxy cache system URAC (user request attentive cache) is implemented. The working principles of URAC and the issues on hit rate, cache coherence, and replacement strategy are addressed in details. Furthermore, the performance of URAC is predicted through simulation. It is concluded that URAC is a practical proxy cache system that can improve valid hit rate and reduce access delay.
Key wordsproxy cache user request analysis site-graph model cache coherencereplacement strategy valid hit rate
1
Internet淢չWorld Wide WebѾΪInternetϵҪӦ.ȻϢҲͻInternetĿǰڵ⣬ʹûĳվҳϢӳʱ䳤ò.һ취ǻûʹҳҳΪһţ´ηʱûӵҳפվϴαĸṩӶͷӳ٣Webأͬʱͷ˱ռõ.
һ˵3ֻʵַʽͻˡԼ˻ƣ1.ͻ˵ĻͨϵģNetscape˾NavigatorCommunicatorMicrosoft˾Internet Explorerṩ˻ûһʱڷʹҳϢĻ.ֻƵҪصǻÿҳϢޡʵֵһԲԺ滻ԶȽϼ򵥣ṩûһЩʧЧ˵ĳ¾(stale)ϢһֲɿĻ.˵ĻǺWebһģͨڷʵֶcacheΪռ䣬ȴҳӲ̾иߵķٶ.ӦûĳҳķҲڻռ䱣һһͬķ󣬾ֱӽռ䱣ĸṩû.ֻܹʵؽͷӳ٣ǶԷҪϸߣ˷ĸӶ.һֻ淽ʽǴƣΪ2.ûĳվҳ󵽴һиҳĸֱṩûΪӦûиҳĸضפվøҳûڷϱһ.ֻƵĹʽͼ1ʾжûԹҳص㣬˷ӳٺͷ.ͬʱЩṩĻ񻹿һ𣬹ɲͻģͣInternetЭ(internet cache protocol, ICP)3ϸģ͵Ĺ淶.͵ĴColoradoѧʵֵHarvest Object Cache4ݡNetscape˾Netscape Proxy ServerԼHarvestNLANRSquidϵͳ.


ͼ1Ӧʽ
Ƚ3ֻ淽ʽǽWorld Wide Webٶغ÷.зӳٵ͵ŵ㣬ΪͨǺͿͻͬһڣҳϢӴͻӳʱԺԲ.ΣڻרŵĴʵֺάƿռýϴĴ̿ռ䣬ڴĴýϢ.һάԺ滻ԿԱȽϸӣӶʺͼٵ.дɵĲͻ棬ԽӽûҳظûϢıػ(locality)Ҳ˷ӳ.
ǣĿǰһЩϵͳǻûĳҳķʽлģԴʣӳûķΪȻȽϵֻͣͨ40%ң1.ΪһЧʵõĴƱ¼ͷûķΪʵͬʱҲҪǽûҳķӳ.ڷûΪĻϣһվͼģ͵ĴϵͳURACuser request attentive cache.һϵͳУÿվһûʹĸվҳΪԪصһάɷ̨еģ滻㷨Ϊм.ͬʱĳվҳĿ¼ṹʽУṩû̷·ҳ.
ڵ֯£2վͼģͣ3ڶûΪзURAC˼룻4ڽURACĹԭϵṹ5ڽURACۣĸ.
2վͼģSite-Graph
HTTPЭ齫WWWеϢԴһͳһԴʶʾURI(uniform resource identifier)ûÿURIΪַģһHTTPַ£
http_URI = http// host port ݣabs_path 
abs_path = /rel_path
rel_path =  path ݣ  params ݣ ?query 
hostĳվIPַportṩHTTPЭTCP/IP˿ںţȱʡʱΪ80abs_pathǷľ··ɡ/ͷλĳվάĳҳ·ͷûС/ĳվҳĿ¼ṹͬʱͨ롰͡?ַṩHTTPЭGETȷҪĲ봮.
еһЩϵͳûʵĳҳл棬ʵҪûһηҳʱҲҳURI⽫ӰϵͳṩԴ.WWWԣҳṩĳӣhyperlinkʵҳĻãʹûһURIתһURIûWWWط.ΪˣWWWվͼģSite-Graphͨģ͵ʵֿڴȻҳԭʼվ໥ùϵָûҵҪϢ.
һ˵ṩHTTPڷʱҪһҳԼҳŵ·CERN HTTPDsrm.confļͨDirectoryIndexDocumentRootҳaccess.confļͨDirectory/Directoryô·.վҳϢͨHTMLAnchor־(A/AHREFSRC)һһվͿԿһͼWn=(P,E)Ķ(piP,i=0,,s)Ǵվϵһҳp0ҳ.(eijE,i,j=0,,s)ʾͨҳpiԷʵҳpj.һ5ɷҳվͼ2(a).WWWһWnһ״ͼݶHTMLAnchor־зһ㶼ܴ·ɸöıԼöı.
ʵÿվǶڵģվַΪhost1ڵĳҳͨhttp_URIʵվַΪhost2ĳҳʹͼ2(b)ʾһWnĶp2WmĳıߣǳվΪվ֮ԵģֻվڲӵľͳΪվ.ڱģҪ۹վĴϵͳ.ǶpjǰPVSΪpjΪյߵԴpiļϣpjĺ̼SVSΪpjΪԴߵյpiļ.ͬʱЩվпԵվĶ㼯Ϊ㼯һվͬһվڲзʱP(Wn)O(Wn)վڶ㼯.


ͼ2һ嶥վͼ
һһ·ʾվͼУ

mΨһʾվͼWmpjP(Wm)ʾpjWmһ.pipjߣͽaijֵΪ1ȡ·.⣬Ϊÿpiһʼc(pi)ںķΪ滻.
վͼɺά㷨.һûύ󵽴ʱǶһµվķʣһµվͼʹӴ˽ԭվͼϽӶĲ.ͼ3һվͼɹ̺͵·.



ͼ3վͼɹ
㷨
if pj in V then c(pj)++/* access times increases */
else{ /* a new page copy is added to the site-graph */
pj adds to V
c(pj)=1
}
if (pi,pj) not in E then /* a new edge comes from i to j */
for any neighbor vertex pl of pj in V
RECALCULATE aij and ajl
ͬʱи滻ʱһЩվͼΪĳЩ㽫ɾɾ㷨
if subsequent set of pj is null then /* has no page followed */
Remove j column and j row from the matrix
else { /* a useful page has some hyperlinks */
for any vertex pl in subsequent set of pj in V
aij=1 /* add an edge from pi to pl
RECALCULATE all vertex value in the matrix recursively
}
3ûΪ
ڶûʹҳлʱͨΪûһη󵽴ҳ뻺. ʵϣһ裬ûʵҳṩһȷURIURIӷҳŵλö.磬Ϊwww.myweb.edu.cnվһ980531.htmlҳŵ·selfish/paper/980531.htmlôΪ׼ȷûҳûṩURIӦhttp://www.myweb.edu.cn/selfish/paper/980531.html.Ȼּ貢ûķΪʽ.ʵǣûֻ֪ͨĳվҪϢĵһhttp://www.myweb.edu.cnͨҳ𲽽ӽҪҳ.ûʹҳл棬ͻûĵмҳϢռ޵Ļռ.һ棬һһϵͳܣЩмҳĿҳʵĴȵģɵ˳ɱдӶʹָò.ڴ˵أΪûṩϢЩҳɱԽͷӳ٣ظʹ÷Ļʺܸ. ʵϣȵһʱڣûͨõЧϢ.
ԭһ㻺ϵͳԹҳвЩҳڻռǻصشŵģԲԶطЩϢãЩϢԱ滻ȥ.ֻͬصĴŷʽܰû̵ķ·Ϣʹûҳѱ棬εӵòܵõҳδٷӳʱ.ˣҪ¼ûķΪзԴָûĿҳ.ǵûķʾоֲص㣬һķʹУͨǵͬһվģվΪλûΪΪϵͳЧϢҲƵĴϵͳĻ˼.
涨վͼԶûķΪиټ¼ͷ.ÿ޸ĵ·ʵǶûΪһμ¼ַͨʽͿ𲽽ûĳվķʹ켣ͼ.һr0, r1,, rnʾûķʹ̣ĳʱΣǶλͬһϵ.һͨȽÿpiʼc(pj)жĳҳǷΪûʵĿ.pjpiSVSУc(pj)c(pj)/k,k=#SVSôpjֵڴл.ˣͨûΪиٺͷʹôбмֵҳ˿ռʺ.ͬʱڷĻϣڶĳӦͬʱҲҳpiڽӶpk1,pk2,,pkl,pjURIдΪΪϢصûϣûĿҳǣͿʡȥpk1,pk2,,pklķʣֱѡpjURI룬˷ʹ̣Ӷ󽵵˷ӳ.
4URACԭ
URACһչWebȺϵͳʵֵģƵĻռ൱ԴŴҳݣһЩýϢ.WebȺصÿ̨ԶṩһЩڲͬķϽд.ΪڷȺֻһݻ渱ҪзĿռй.ڷȺϵͳϽһļϵͳṩURIͬĿ¼ṹļϵͳԼӿ渱ٶȣӶӦʱ䣻һ棬ʹƽ̨URAC͸ϵͳڷļʱؿļʵʴ̨.ͼ4ϵͳȺеλ.ĲļϵͳۣṹһԲԺ滻㷨3URACн.


ͼ4URACWebȺλ
4.1ṹ
HTTP/1.01.1Эй涨ֻЩGETHEADķԻ棬URACĿǰʵ涨ԺӶԶ̬ҳĻ.URACǽվͼϵģӦĳվͼWn̬һCn±ӦW\-nÿpi. CnĳǶ̬仯ģӵWnĶ.CniݳֵΪ0piһӵվͼУԺûpiԶһCniݾִмһ㣬Ϊpiм.ͬʱ̬һÿURIַUn.ڶԷӦ󣬻ڴȺϱһӦᵽĲļϵͳURIƵĿ¼ṹţͼ5ʾ.һĿ¼ҶӽڵҳݣӸҶӾһhttp_URI.Ŀ¼ṹڻϵͳٻṩӦҳͷӳ.


ͼ5Ŀ¼ṹ
ڷûΪʱڵһνվͼʱҪжڴǷѾиվĻݣͨĿ¼ʵֵ.Ϊ˼̣ƶԸĿ¼µһĿ¼վIPַHindexhostṩķӺǰƥ䣬IPַǰƥ.HindexǶӦڸվΨһֵWn±n.
URACԷӦ̣
IF http_REQUEST THEN
{//ʼ
http_REQUEST = http://host/pathݣ/file
IF (host IN Hindex) THEN
{//ڴȺѾվĳҳ
WHILE (http_REQUEST!= Uni) i++;
 IF (i > LENGTH(Un)) THEN
{//δʹҳչUnCn
LENGTH(Un) ++;
Uni=http_REQUEST;
LENGTH(Cn) ++;
Cni= 0;
ADD_URI_TO_Hindex; //
//ɴתפ
Ӧû
http_RESPONSE=proxy_REQUEST
(http_REQUEST); 
//ڴ
SAVE_RESPONSE(http_RESPONSE);
}
ELSE 
{//Ѿҳĸ
Cni++;
//ӴȡӦ
http_RESPONSE=LOAD_RESPONSE
(http_REQUESE);
}
}ELSE
{//һηʸվ
n=LAST_VALID_SITE_IDENTIFIER ++;
//ҳ
FORK() 
{ //̨
LENGTH(Un) ++;
Un0=http://host/;
LENGTH(Cn)++;
Cn0=0;
ADD_URI_TO_Hindex; //
proxy_RESPONSE=proxy_REQUEST
(http://host/); 
//ڴ
SAVE_RESPONSE(proxy_RESPONSE);
}
LENGTH(Un)++;
Uni=http_REQUEST;
LENGTH(Cn)++;
Cni=0;
ADD_URI_TO_Hindex; //
//ɴתפӦû
http_RESPONSE=proxy_REQUEST
(http_REQUEST);
//ڴ
SAVE_RESPONSE(http_RESPONSE);
}
}
̲ʱЧ滻潫URACһάԺ滻㷨.
4.2һԲ
HTTP/1.1Эһҳĸ(time to live, TTL)Ϊ
(1) ӦСCache-Control:max-age=...ͨͷô=max-ageֵ
(2) ӦExpiresʵͷô=ExpiresֵDateֵ
(3) CacheԸĳʽ㷨һ.ǣ¸ڳ24СʱӦ24СʱСڣӶ϶ʱӦһΪ13WaringӦͷ.
ͬʱṩAgeӦͷ¼ĳҳĵǰ.οЩ涨URACжԻ渱趨ǰpCurrentAgeΪηʱHTTP_dateȥҳפվʱDate.ÿ渱ڰϵĹ壬ӦûExpiresʵͷʱ趨pTTLΪ渱ǰ(ڵһηʱ趨Ժʱ޸).жһ渱ǷЧΪӦظͻpCurrentAge<pTTLһ渱ɳ¾ɣҪפվάһԵpTTL > pCurrentAge.
ȻpTTL>pCurrentAge£һҪǿƴפվҳ.פվLast-Modifiedʵͷָҳ޸ʱ䣬ɴķIf-Modified-SinceͷʹGETΪȡ京ǵGETȷԴָʱȷʵıˣGETĹܣ򣬷һ304ûиı䣩Ӧ.Ӧ304ǲʵ.ҳʵûиıʱԽʡ.ʱ޸Ļ渱pTTLΪǰpCurrentAge1.5.
ϽURACУڴϼӦûҳʱȽлһжϣ渱ȻЧֱΪӦأ򣬽ȡҪʱ´ϵĻ渱.վWnĶpiһ¾ɸȡפվõ304ӦôȻpiмCniݣõӦһµpiڴϱµҳCniΪ0õ404Ӧ(Ҳ)ܸҳפվѱɾʱӦpiվͼɾCnɾCniݣUnɾUni.
4.3滻㷨
ڴϵĻռ޵ģһҳΪ˱µķӦֻܽѾһЩ滻ȥڳռ.õCache滻㷨иÿ渱ļѡʵĸ滻SIZE㷨¼ÿ渱ʱѡδʵĸ滻LRU㷨Լ¼ÿ渱дѡеĸ滻LFU㷨ȣ56.Щиȱ㣬HarvestϵͳвLRU㷨ͨģķЩ㷨ܱȽϣף1ݶԴ˽˷ȽϣóۣԾĻϵͳӦӦ滻㷨.
վͼģУĳҳǷڴϱʱжṩЧϢ.URACõ滻㷨ۺϿ˸ŵֵ桢ƵȺʱ⼸Ҫ.·ЩĶ£
(1) piֵ
e(pi)=(k+s-(pi))/2s,
У
l=#{aji|aji}>1, piP(Wn)\P(On)}.
(2) piֵ
p(pi)=(k+s-(pi))/2s,
У
l=#{aij|aij>1, piP(Wn)\P(On)}.
(3) piʱ
t(pi)=(t-t0)mod/,
, õˢ¼.
(4) piıƵȣ

УpjPVS(pi); k(pj)=#PVS(pi).
ֵָpiõĿܣǰֵָͨpiԷʵϢĺ̼ʱpiڻռδеĴʱ䣻Ƶ÷ӳpiṩЧϢĸ.УֵֵԼƵԽ󣬱øеĿԽ˲ñ滻ȥ.෴ʱԽ󣬱øûбļֵԱ滻ȥ.һԭǶ滻ΪR=R(e,p,t,f)ÿpi滻Ϊ

ĳ滻ֵԽ󣬱滻ĿҲԽ.
5
ʵһԭϵͳURAC˸ģ⣬óʽLRU˱Ƚ.ÿҳĳΪ32KBռΪ300MB(Ա100վ9600ҳ) ģгΪ192000.ģеķֲ״̬Ϊ߶ȼСԼ3ͣõĽ1ʾ.ǲõЧʲǵͳʼ㷽ҳҲڣǶûΪķЧУռ˴Ŀռ䣬˷ӳ٣ЧVHRvalid hit rateϵͳ.ЧָЩеҳܹṩӽûĿϢ.VHRΪЧкзıֵ.
ЩURACбLRUõܣÿվ192ҳֻ40%ЧϢʱǿԵõ70%ʣͬʱռʿɴ80%.һ棬Ҳ˵վĿЧϢʱURACܽ͵ñLRU.Ϊռޣ滻㷨վ滻ȥӶ.İ취ÿϱ޵վĻ渱ʵֶĴ湲ǽиһЭ.
1URACLRUVHRȽ

ṩЧϢĸռ
иı (%)URAC (%)LRU (%)
߶ȼм߶ȼ*
40706765403415
60706560403415
80655045403415
100605040403415

ϵͳܵһǷӳ٣URACķӳ¼ر֤.һĴϵͳȣURACһЩص㣬ʹϵͳķӳٺܵ.ȣڷȺϵͳÿ̨ܶûķдɽӶ࣬Ա֤ûķʱõȴͳʱΣͨûʹ̽м¼ṩڽӶϢûĿҳ·Ӷͷӳ٣ڴϵĸURIʽŵģļķٶȿ죬Ҳûҳķӳ.⣬ڻ滻ڷάʱڽеģɷϵͳڴĳʱֿռ䲻ŽУ˲Ӷķӳ.
Ȼڻ渱Ƿֲڶ̨ϴŵģĳ̨ڴʱҪϻȡݣһЩӳ.Ϊ˲ļϵͳɸӵķȺϵͳУӳ൱Сģļϵͳ͸طģгֿ˱ȵķŻ渱ķԽͷӳ. 
6ᡡ
ƺʵURACϵͳ֮ǰͨԺܶ໺ϵͳзΪͳĻϵͳŴ˷ѻռ.⣬վͼģͣûΪ˷һµĴϵͳƣҪ˴滻.ͬʱǶ˸ӽӳϵͳܵЧʲ.ģURACĿǰĻϵͳȣˣӳٽˣһЧܵĴϵͳ.
*õҡƻ(Ŀ863-306-01-03)IBMйоԼΪƼ.
߼飺ׯΰǿУ19715ʿоҪоΪֲ/дܼ.
ƣŮ19746˶ʿоҪоΪֲ/дܼ.
ˣУ193710ʿʦҪоΪֲ/дܼ.
֣γУ19463ʿʦҪоΪֲ/дܼ.
Ů19382ʿʦҪоΪֲ/дܼ.
ߵλ廪ѧѧ뼼ϵ100084
ο
1Wooster R P. Optimizing response time, rather than hit rates of WWW proxy cachesmaster dissertation. Virginia Polytechnic Institute and State University, 1996
2Abrams M, Standridge C R et al. Caching proxies: Limitations and potentials. In: Proc of the 4th WWW Conference, Elsevier, Amsterdam, 1995. 119133
3Wessels D, Claffy K. Internet Cache Protocol (ICP), Version 2, Tech Rep: RFC 2186
4Chankhunthod A, Schwartz M F et al. A hierarchical internet object cache. Computer Science Department, University of Southern California, Los Angeles, California, Tech Rep: 95-611, 1995
5Lorenzetti P, Rizzo L. Replacement policies for a proxy cache. University di Pisa, Tech Rep: LR-960731, 1996
6Williams S, Abrams M. Removal policies in network caches for World-Wide Web documents. SIGCOMM, 1996, 8: 293305 
ԭյڣ1999-01-22޸ĸյڣ1999-07-11.
