ѧ
JOURNAL OF SOFTWARE
1999ꡡ1011ڡVol.10No.111999



ڿͻΪģʽWebĵԤ
ධ ¬ 
ժҪԤΪcache,cacheʱֲռֲԵչ.Ԥ͵ģʽ.ڵURLģʽÿͻɷȡĵʱģ,ɽж༶Ԥ.ڻỰģʽĵԺͻỰ;,صоĵԵ;,ľۼ㷨,̽ĵȤĶ,ӳʱ㷨.ԤܵĶ,ʡỰʡԤЧʺԤʹ۵ȶ.ͬʱ,ɴʵ,ԿͻΪģʽбȽ.ɷʼ¼ȡͻΪģʽķ,ĵԤ,ڷվƺISP(internet service provider)ķ滮ҲҪֵ.
 ؼʡWWWӦ,Ԥ,,ɷ,Ựۼ,ĵ,Ԥ.
ͼšTP393
Web Document Presending Based on User Behavior Patterns
ZHU Pei-dong LU Xi-Cheng ZHOU Xing-ming
(School of Computer National University of Defense Technology Changsha 410073)
Abstract Presending is an active service which extends caching mechanism from temporal locality to spatial locality. Two modes of extracting user behavior patterns are proposed to predict future requests from clients for efficient presending. URL-based mode exploits the Markov-chain features of request series, and can be used for hierarchical presending. Session-based mode captures more semantics, and the authors' work emphasizes the clustering algorithm, feasible document weight definition, and attribute-vector-distance computation representing order of accesses. Their performance is evaluated using appropriate metrics such as request hit rate, session hit rate, presending efficiency and presending cost. Numerous experiments are carried out to compare the two modes. These methods are used for web presending, while they are helpful to web server design and ISP (internet service provider) service planning.
Key wordsWWW responsiveness, presending, request dependency, Markov chain, session clustering, document attribute, presending performance.
cacheֻWWWģʽʱֲ,δʹ޷,ӦȻò,һڿͻһµȵҳ澭ʱ,о.,ͻ򱾵شWWWݻĿռ䲻,ʹݱ,cacheҲõӦ.
Ԥͻܷķ,ڿͻǰĵʱ,Ԥݷͳȥ,ҪЩĵʱ,ֻɱcacheȡ.Ԥͼ(presending)ĵĿռֲ,cache,cacheʱֲռֲԵչ.
ף1еķʼ¼,ĵƽʱΪ1.37s,ƽΪ44.59s,ɼ㹻ʱԤ,ܹ֤Ԥ͵ʱЧ.35 290ȡĵƽΪ8 241ֽ,ΪСļ;WWWӦýǿ,ļʱֽҪ,Ԥ͵Ĵʧ.ƽһλỰ15,224,30ĻỰռ13.4%,õԤԤͼֵ.
ԤͷΪԤͺԤ.ԤԤⲢԤȡ,Էݺĵ֯ȱ˽,ֻܸݼ򵥵ĵǶϵ.Ԥ,ڷӵдķʼ¼,ԼĵϤ,˽ͻķģʽ,,ԸЧԤԤ.
1 ԺԤͼϹ
1.1 ԤͼϹ
Ԥ͹̰ѧϰƥͷ3׶.ѧϰǷʷΪͻΪ,ȡͻһ»Ϊģ;ƥȷڽеĿͻΪģ,ݹͬģʽƶϽ;ָ,ԤݸԤͲԴͻ,ԤͲ԰Ԥ͵ĲΡĿֵͷʵѡ.
ѧϰƥԤ,Ԥԭԭ.һֿռϵչ,ָµĿͻΪģʽеĶͻ;ԭʵʱչָͻδȥķģʽ.ֻۻڷʼ¼ѧϰ.
1.2 
HTTP״̬ӦЭ,ͻͷһλỰڷǳһʱ䣨3СʱĿͻ,һλỰڿͻķΪȷ.ķʼ¼LogʾΪỰ,Log=S1,S2,....ỰSΪͻ,S=Client,Req1,Req2,....
Էǳ2,ԤйصԿʱTrĵDoc,ôԱʾΪReq=S,Tr,Doc,SΪĻỰ.ԵķҪоỰԡʱĵ,RRʾ,ôRR(Req1,Req2)=RS(S1,S2),RT(Tr1,Tr2),RD(Doc1,Doc2).RSΪ,RTΪʱ,RDΪṹ.
2 URLķģʽ
2.1 ɷԤ
{(n),n=0,1,2,...}״̬ռΪIΪǸ.
P{(n+1)=j(0)=i0,(1)=i1,...,(n-1)=in-1,(n)=i}=P{(n+1)=j(n)=i}
(1)
Ʀ(n)Ϊɷ.P{(k+1)=j(k)=i}ΪʱkʱһתƸ,ΪPij(k).P{(k+1)=j(k)=i}=Pij,״̬iתƵjĸk޹,ƸùΪɷ.תƾP=pij.
ͻɢռһ¼,̾ɷ.ͻtʱѾĵDi,ʱ(t,t+TWڶһĵDjʵĸΪPij,TWΪԤʹ,PijΪԤ͸,Pij(0i,jN)ԤⷽP,NΪеĵĿ.
mתƸ,õĵĶ༶ؾP(m),ڶ༶Ԥ.

(2)
P(m)P(m-1)P(1).
(3)
2.2 Ԥ
ͻAreqiҪĵdoci,Ԥ,ʵԤ͵ЧĵɵļΪP(doci).ûURLԤģʽ,P(doci)cacheеЧͻreqi+1Ϊֹ,ô,reqi+1Ϊ

(4)
reqi+1ĵP(doci)ĸ.ԤĵĿԽ,Խ,ԤͼP1(doci)P2(doci),Ӧʱضhr1hr2;Խ,ͻӷĵͻصһεȴʱTaccess=hr*Tcache+(1-hr)(Tcache+Tremote)ͿͻϻʱTclient=Tread+TaccessԽС,ЧʿԽһ,TcacheΪcacheʱ,TremoteΪӷԶ̻ȡĵʱ,TreadΪĵĶʱ.ͻAһλỰsڼϷM,hit-num,ôỰsʱʾΪhs(s)=hit-num(s)/M.
ͻĵdociзԤ,ԤЧur(doci)=hr(reqi+1)/#P(doci),Ԥʹqr(doci)=Sp(doci),Sp(doci)ΪԤͼP(doci)ĵĴС֮.ͻĵdocûд͵,ڱcacheõӦ,Ե֪һϢ,ôڿͻĶdocʱ,ͬԽлdocԤ.ỰsԤЧ,ʾһỰԤһĵпͻƽ,Խƿʽ(4)hit(d,reqi+1)Ӧĺ.ỰsԤʹ
2.3 ʵ 
зķʼ¼(log file),Ǽÿһĵ,Nͬĵͻ.ʹÿĵDi,ĵпͻʵĴΪMi.֮ʱܴ,Ӽ뵽ǧ벻ȣ1,ԲʱԤʹ,ѡĵĿΪTw,Ԥ͸PijΪDiͬһͻʵTwĵгDjĸ.ʱ˳ʼ¼,TwDiʼĸͻķĵDjֵܴΪQj,ô,Ԥ͸ʿͨPij=Qj/MiƼ.Di,iʣ1,NݽƷ,ӶõؾP.
ף1еķʼ¼Ϊ2 286Ự,ʹ1 000Ựļ¼ԤͱĹ,1 286Ựļ¼֤.ף1ֻ24Сʱķʼ¼,ʵʹԤͱҪʮĻỰ¼,㹻׼ȷذտͻΪģʽ.
ԤʹTw=5,Թڱ1Ԥͱ,ͼ1Ӧĵͼ,1ͼ1бʶСΪԤ͸.ʵʵ,Ԥֵkp=35%,Ԥ͸ʴkpĵԤͱѡ.,ͻԷʼ¼гֵĵֱ𷢳,ͳƿ֪,ĵԤͱѡƽ3ĵ,Ϊ12.Ԥͱ֮,ʵԤʱ,ֻԤͱѡѡԤ͸ĵ,ҲѡһĿĵ,TwڰԤ͸ʴkpС250KBĵȫԤ,ƽỰhs=42.5%,hs85%ĻỰռỰ18.6%.ỰƽԤЧus=13.2%,ƽԤʹqs=410KB.

ͼ1 ĵͼ
1 ĵԤͱ
+home1.htm
-image1.gif0.8
-image2.gif0.6
-home2.htm0.7
+home2.htm
-a.txt0.5


3 ڻỰķģʽ
ԻURLķģʽķ,пͻURLеͳ,Ԥĵ.ַ򵥡ֱ,ûбỰͻỰ֮Ĺϵ,ϢȡӦ.,ÿͻԤһĿĵ,ʹؼ,ʧȽϴ.
ģʽԤͱĹԤͲԵƶǻһ:Ԥڿͻʵʵ֮.,һ,ڿͻʵʷʱ޷Ԥ,ʹɹԤܼʱ˷;һ,ʹѾδĵЧ,ĵԤͼϰһĵ,ȻٴԤ͸ͻ,ܿڷ״̬Ϣ֪һϢ,ⲻǻURLģʽеĻ.
ڻỰģʽķԤͿԱURLʽ.ȡỰỰϷ,жڽеĿͻỰ,ݸỰĹͬԤÿͻڻỰʣʱ佫Ҫʵĵ,һԤ.ַʵָ߲εΪ,Ľ,ԷվƺISP(internet service provider)ķ滮Ҳһļֵ.
ڻỰķģʽڻỰͻڸĵԵķ.ڻỰķҪԷĵժҪ,ȡͻڻỰѷĵĹؼ,ԴΪͻȤıʶ,ΪؼԶͬȤĵ,Ҫ֪ͨͻ,ڵ򽫲ҽҪ̶Ԥ͸ͻ.ף3,ԶԿͻȤվĸ.Ԥδ̺ڷʼ¼֮,˷ȽʺڿͻӶѼȤ,,صоǻڸĵԵķ.
3.1 ۼ(clustering)㷨
ۼǸӼԶݼϷ,һ޽(unsupervised)Ļѧϰ.ͻͷһλỰv=a1,a2,...,aNʾ,ԪaiʾͻԷĵiȤ̶,NΪеĵĿ.Ựpqֱʾ:p=p1,p2,...,pN ,q=q1,q2,...,qN.ÿỰΪռһ,pq֮Կŷþ(Euclidian distance)d,

(5)
жϻỰpǷھۼc,Ҫpcmľ.ڲǰ,d(p,c)d(p,m).c={v1,v2,...,vk},mmiΪ

(6)
ۼΪηͷǲη,ѡLeader㷨4.
㷨1. ỰۼLeader㷨.
: һV
: һۼC={C1,C2,...},CiV.
:
(0) CֵΪ.
(1) Vÿv:
ѰҾۼcʹvcľ,Ϊdmin;
dminСھֵDistanceThresh,
vc,
,{v}C.
3.2 ڸĵԵľۼ
vΪϵĵ,ֵΪͻԸĵȤĳ̶val.Ựv1v2ʵĵвͬ,ͬĵȤҲС,ҷ˳һ,v1v2Ӧͬһۼ.
3.2.1 Ȥ
.ף5ݽĵķʴֵval,,ʹͻһλỰжͬһĵȤǳŨ,Ķ,ڷ¼Ҳ޷ӳһ.:һλỰ,ͻһ㲻ӷͬһĵ;cache֤ѡ,²Ϊÿηʶ֤;ʹÿ֤,cacheʹù֤ģ(expiration model)2,ҲԴͨ.
,ɷͳƳĵdocĶĵķܴRnum.ɳıṹ,docֱӵһ(physically linked)ĵʵĴ,ͻdocȤŨ.
.ĵĴСvalֵ,ͬһĵڲͬỰдС.,ǿͻĶٶȵĲ,ĵĶʱԶͻȤ̶.ͬһĵĶʱTread仯ܴ,ף1вͬͻڶĳ4KBĵĶʱ,10sΪСֵλ,Tread6s1297s֮43ֿ,ֿͻȤȺ.ĵʱֱΪTinter-requestTon,Tread=Tinter-request-Ton.ڿͻĶʱ,ܱж,TreadΪ1 800s,Tread>1 800s,ͼΪ1 800s.ף1ƽTinter-request=44.59s,ƽTon=1.37s,ƽTread=43.22s.
,ͻĵȤĳ̶val=f(Rnum,Tread).ΪȨȤ,f(Rnum,Tread)=,ĵdoc1Rnum1=3,Tread1=160s,val1=7;ĵdoc2Rnum2=6,Tread2 =10s,val2=7.ֶϿͻж.
3.2.2 ˳
ʽ(5),˷˳.,ͻAķΪ(8,19,4,...),ͻBķΪ(4,8,19,...).ڽԤʱ,A,ĵ8ʱԤ194;B,8ĺ̾Ͳ4.ʽ(5)Ự,ֲ޷,Ԥͱ뷴ӳʵʱϵ.
ͳף1ݵķʼ¼,ͻʹĲͬĵ5 104,ƽÿỰ13ĵ,85ĵ,ɲýʽʾΪżpos,val,posΪĵ,valֵ.Ựv1v2Ӧʾ,ԪΪpos,val.·.
㷨2. ӳ˳:distance(v1,v2).
: pair*v1,*v2
: sqrt(sum)
:
(0) sum=0.
(1) ѭ1: ʼ:p=v1,q=v2;ֹ:pqΪ
pposqpos,sum+=(pval)2,p++;
pposqpos,sum+=(qval)2,q++;
,sum+=(pval-qval)2;p++;q++.
(2) ѭ2: v1Ԫ,sum+=(pval)2.
(3) ѭ3: v2Ԫ,sum+=(qval)2.
,v1=(8,119,14,2),v2=(4,28,119,1),ô,v3=(4,28,1)v1ľd31=3v2ľd32=1,ܺõطӳ˷ʵʱ.
3.3 ƥԤ
յͻAL1ʱʼԺԤ,L1󹹳ɻỰsһ,Ϊv1.ۼ㷨лỰ,C={C1,C2,...},Ci={vi1,vi2,...,vik}.
iۼжϺΪfi,Բָ꼫Сжϱ׼.ik,
fk(v1)fi(v1)
(7)
v1Ck.,fi(v1)=d(v1,Ci).ֻԤCkȤֵlҲv1е,巽.CkΪmk,ȥmkȤֵСlĵ,õv2,v2=hl(mk).hl(p)=q:pĵiֵpil,qӦֵqi=pi;qi=0.Ȼųv1еĵ,ô,ԤĵP(v1)=sub(v2)-sub(v1),sub(p)={npn0}.
ʵʻỰ,ͻAϷL2,Ựsʾv=v1+v2,Ựhs(s)=#sub(P(v1))sub(v2)/#sub(v),ỰԤЧus(s)=#sub(P(v1))sub(v2)/#sub(P(v1),Ԥʹqs(s)=Sp(v1).
3.4 Ԥʵ
ɷʵ,ʹף11 000Ựļ¼ڻỰۼ,1 286Ự¼֤.ʵ²:(1) Ԥ:Լ,Ựʾ;(2) ۼ;(3) ƥ;(4) Ԥ.
˵4ĻỰ,760Ựۼ,68Ӽ,ȥֻ1ỰӼ,37ӼԤ.L1=3,ͻ3֮ƥ,ƥɹ,ԤȤֵΪ1,ÿỰƽԤĵ14,ƽỰhs=37.6%,ƽԤЧus=40.3%,ƽԤʹqs=130.2KB.
ɷķ,hs(Ϊ0.88),usȴ߳ܶ(Ϊ3.05),qsͺܶ(Ϊ0.32).ɼ,ڻỰķԽСԤʹۻȡ൱̶ȵĻỰ.
4 ع
ԤȡǲкͷֲʽļϵͳߴȡЧʵͨ÷,ļΪλԤȡ,ͨӦʾԤȡ.ף6еԤⷽнܵһ,ʹöģͶļϵͳ¼и,ƥǰ¼,籾Ļɷķ.
WWWǷֲʽϵͳӦ,HTTPЭʹͻķΪõ׼ȷļ¼,ڷ.ף7,8ݶWebԤȡм򵥵Ľ,û漰Ԥʹ۵ܶ,ûпǻڻỰ;.ף5ݶԿͻģʽ,ڶ̬Ĺ,δշʵʱ,ͻĵȤĶ÷ʼǲǡ.ף9ͨͳĵҳʹڷŴ,ȡͻֽ߱ĳһϲó̶,ʵΪ,Ҳǻڷʼ¼.
ھԴӴģݿзǱڵģʽ10,ĶWWWʼ¼ķھĻԭ,˻.еķ¼,WWWStat,WusageWebLog11ݵ,֧ĵԺͻỰ,޷ԤͺʵʵĿͻΪԤ.
5  
ԤֻҪcacheЧΪ֮ļһλỰʱ,ԿͻδݿԻ岢Ӧ,ͬʱĻռ.URLɷģʽ򵥡ֱ.ڻỰۼ;,ԽСԤʹۻȡ൱̶ȵĻỰ,Ϊḻ.ΪһͻԤ,ĵԤͶڸӦܺǿISPҪ.
Ŀоõ863߿ƼĿ.
߼飺ධ,1971,ʿ,ҪоΪЭ.
¬,1946,ڣʿʦ,ҪоΪܼ,Ƚ,ֲ.
,1938,,ʿʦ,йѧԺԺʿ,ҪоΪܼ,⻥,ݿ.
ߵλѧѧѧԺ ɳ 410073
E-mail: pdzhu@nudt.edu.cn
ͨѶϵ:ධɳ 410073,ѧѧѧԺ
ο
1 ftp: //ita.ee.lbl.gov/traces/epa-http.txt.Z. Downloaded at April, 1998
2 Feilding R et al. Hypertext transfer protocolHTTP/1.1. IETF RFC 2068, Jan. 1997
3 Ackerman M et al. Learning probabilistic user profiles. AI Magazine, 1997,18(2):4856
4 Hartigan J. Clustering Algorithms. New York: John Wiley Press, 1975
5 Yan T W et al. From user access pattern to dynamic hypertext linking. Computer Networks and ISDN Systems, 1996,28(1):10071014
6 Kroeger T M, Long D D. Predicting file system actions from prior events. In: Gray R ed. Proceedings of the 1996 USENIX Annual Technical Conference. Monterey, CA: Usenix Association, 1996. 319328
7 Mroz M. A client based prefetching implementation for the world-wide-web. Technical Report, Computer Science Department, Boston University, Jan. 1996
8 Padmanabhan V P, Mogul J. Using predictive prefetching to improve world-wide-web latency. ACM Computer Communication Review, 1996,26(3):2226
9 Sakagami H, Kamba T. Learning personal preference on online newspaper articles from user behaviors. Computer Networks and ISDN Systems, 1997,29(1):14471455
10 Fayyad U et al. From data mining to knowledge discovery in databases. AI Magazine, 1996,17(3):3754
11 http: //awsd.com/scripts/weblog/. July 1998
1998-07-14յԭ,1998-12-07յ޸ĸ
