о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 9 Vol.36 No.9 1999



罻ͨԵķӦáеһ¼ĻȺ
־ΰ
ժҪƹ̺ܺõķģͣҲΪģͲصϵͳṩһܺõۻ.ӦõĲϷչٽ˻ȺϵͳӦ.ƹķʹָ̣ȺرǷһ¼ϵͳƣϵͳ.ȽܻȺûģ͡ƹ̣ȻͨϢĹ켣ȷӰϵͳܵ.ЩĻϣݼON/OFFźԴģͣ򵥶ʵõɾԵĲݣݶһ12̨ݼɵġеһ¼ĻȺϵͳܲ.
ؼʡһ¼㣬ƹ̣ParetoֲȺ
ͼšTP393
ANALYSIS AND APPLICATION OF THE SELF-SIMILARITY IN NETWORK TRAFFICTHE PERFORMANCE TEST OFCLUSTERED WWW SERVERS WITH A SINGLE ENTRY POINT
ZHAO Xiao-Fang, LIU Xin, and XU Zhi-Wei 
(Institute of Computing Technology, The Chinese Academy of Sciences, Beijing 100080)
AbstractNetwork traffic process is not the same with the traditional Poisson process but behaves like self-similar. This fact offers a different theoretical foundation in developing, simulating, and testing network service systems. Also, network applications' further expansion implies cluster of multiple servers to be adopted to fit its needs. Being put to use self-similar model in the access process of network service can guide the design of the clustered network servers, especially for the strategy of single entry point of the cluster. In this paper, the network traffic modelself-similar process is introduced first, and then a simple and useful method is presented for generating the self-similar network traffic, then some network traffic traces in order to get some features which do effect on performance are analyzed. Finally, a set of data with self-similar is generated, and used in testing the performance of clustered WWW servers with a single entry point. 
Key wordssingle entry point, self-similar process, WWW server, Pareto distribution, cluster
1
Ӧõķչ쳣ѸͣûָܺѸһٶ.ȺһͨߴĽ濪ļϣÿΪһ.ȺϵͳĿչԵڿҪʱӽϵͳ.һչĻȺЧм͸ƽϼѡ.
ȺϵͳΪһҪṩû͸ԣûһеһIPַķһľһ¼㼼ĲΪһĿ.һ¼ʵּм֣DNSNATRouterȺϵͳв·ɷпʵһܣǳΪPowerRouter.
·ɵķڻȺϵͳʵֵĵһ¼㼼ΪûṩһIP𵽼ϵͳ͸ƽ.ΪȺΪһ¼ûʻȺΨһڣͬʱȺڲԴڵһ¼ķɣˣֻеһ¼ϵͳڸ״̬ʵʵĸƽƣȺŻкܸߵ.
Ӧ̽ϵͳǲʵʵ.ֻڶӦ͸ĻϲƳܵϵͳ.罻ͨӦòͬص.ĺܶ๤˵罻ͨģ봫ͳֲָϣǱΪƹ̣self-similar process12.ƹѺŶֱӽнģͷˣҪ罻ͨģͣģʵǿѡַ.ڱĵĹв˺һַ˹ɾԵĲݲһ12̨ݼɵϵͳƽ̨ϽܲԺͷ.
ĵĵ23ֽ̺ݵɷ.4ַӦù켣.5ǲϵͳʵʵĲͷ.ڵ6.
2ƹ
,ӦģʽķSelf-SimilaṟȴͳĲɹܸõط̵ͳƹ.Self-Similarģ͵ŵܸõĳ(long-range-dependence).ͳĲɹӦõĶ(short-range-dependence).ǽҪؽSelf-SimilarԼ紫еSelf-Similar.
ν,ֱ۵˵һںܳʱ䷶Χڱֳṹϵ. ͼ1EthernetӦù켣ͿԷ. ͼеǴף3гȡģͼ1(a)ͼ1(b)ֱΪ10ں30ڷ󵽴Ŀ.

ͼ 1EthernetӦù켣
1.. Xһƽֵ̣Ϊ,Ϊ2غΪ().()ʽ
()-L(), as ӡ
(1)
L() һʱ仯ĺеx0(: L()=limӡConst L()=log()).ֽXΪСΪmǽӿ(ۺϹ)ñʾÿӿľֵɵ̣
X(m)(t)=(1/m)(Xtm-m+1+Xtm-m+2++Xtm)
ÿһmX(m)ʾһƽ̣(m)()ʾX(m)غ.еmۺϹX(m)źXȫͬغ
(m)()=(), еm=1,2
XΪһ(ϸ)Ƶ̣ϵΪH=1-/2.仰˵XľۺϹ̾һס˵XûвģǾͿԳXΪ(ϸ)Ƶ.
2.(long-range-dependence).һʽ(1)Ǿͳƴг.̵غڦʱ˫˥.Ǻ֤غǲۼӵģ ƦӦ()=.ǾʹõĶ̵غڦʱָ˥(()c-,ӡ)ǿۼӵ,ƦӦ()<.ϵĲۼǳ̵ֱ۱: ȻڦӺܴʱĦ()ҲСǵۻЧӦǲɺӵģۻЧʹǺͶкܴ.
罻ֳͨԵ.ܶƵоҲEthernet罻ͨȷʵԵԣIPĵTCPĵTCPӵĳʱ.Ϊʲôԣô? ʵǺڱ۲оƹ̣Ҳڼֹ۵㣬ûкʵͣף4ݣƹ紫ܷδܵõ㷺Ӧã5.ף6һϸON/OFFԴĵģͣЧĽEthernet罻ͨԣҲǱ罻ͨݵ.
ƹܸõ罻ͨlong-range-dependentԣܶϵͳƺܷʲôôأƹȻǺܸӣʹͳĲɷֲֲָоǺ͸.ĿǰһЩо.
罻ͨеԽʹϵͳеŶ(еĳȷֲ)ʹͳ罻ͨģ(ɷģ)Ĳͬ.ڴͳɷģУгȵķֲָ(-t, t->)ѸټСģУԶΪݺ(t-H, 0<H<2, t->)С˥ٶHurstЧ.ϵͳģУԽ¶ϵͳܵĹֹ۹ƣϵͳܲҲݵĲЧزϵͳܣӶʵϵͳнܴﵽԭƵķ(quality-of-service) Ҫ.
3 ݵ
Ethernet罻ͨԿɺܶͬ(independent and identically distributed)źԴĽͨĵ.ÿźԴشON/OFF״̬ON״̬źԴչ̶Ƶʲ罻ͨOFF״̬źԴκ罻ֲͨ.ЩźԴON״̬ʱֲ(ON-period)ʹOFF״̬ʱֲ(OFF-period)ֱǻͬ(ON״̬ʱֲԺOFF״̬ʱֲͬ).WillingerTaqqu6ݵģУǶֳһ֡NoahЧӦON-periodOFF-periodпܷǳҳֵĸʹܱ.NoahЧӦʹöON/OFFźԴĵ罻ֳͨ.ѧǿParetoֲʾNoahЧӦ.ParetoֲܶȺΪ
f(x)=x-(+1)
ЦΪNoahЧӦһ.ңNoahЧӦĶƹ̵ĶH֮¹ϵ

ЦminΪONperiodOFFperiodNoahЧӦСֵ.EthernetON/OFFģǷǳֱ۵ģΪEthernetϵĽͨһźԴɵģֻǺײMAC.ǣΪʲôON/OFFźԴON-periodOFFperiodֳNoahЧӦ? ҪӦüԾģ
(1) һЩļеļСֲNoahЧӦ7ݣ
(2) һ͵UNIXCPUʱParetoķֲ8ݣ
(3) йISDN칫ԶӦñ˻ںܳһʱڳ,ûģʽ޷ֲ
(4) WWWϵļСֲNoahЧӦû˵CacheʹϴļСҲֳNoahЧӦ2.
ЩԾ˵ON/OFFźԴON-periodOFF-periodNoahЧӦͬʱҲǵĵӵEthernet罻ͨJosephЧӦ().
ӹɣǰļ罻ͨǷǳӵ.ǺȻΪΪЧرʾ۲쵽ĸԣ罻ͨѧģͱǳӣҪϸ.ȻָӵѧģͽԺɺܴѣʹ޷ĲȷĹ.ڸON/OFFģֻͣҪNoahЧӦĶһЧıﵱǰ罻ͨһ.ͬʱʹöNoahЧӦON/OFFźԴĵģΪ罻ͨģ, ǸһֺȻ罻ͨ˹ϳɷ.PowerRouterܲ, ǽʹ˹ɵ罻ͨΪϵͳ.ɵ㷨£
(1) Paretoֲе()
ParetoֲĸܶȺΪ
f(x)=x-(+1)
ֲΪ
F(x)=1-x-
ֲķΪ

xΪ(0,1)ϵľȷֲʱF-1(x)ΪParetoֲ.
(2) NoahЧӦĵON/OFFźԴ
ON/OFFźԴON-periodOFF-periodǽֵģON-periodNoahЧӦΪONӦΪ X0X1X2XnOFF-periodNoahЧӦΪOFFӦΪ Y0,Y1,Y2,Yn.򵥸ON/OFFźԴĽͨ(Ӧûķʱ){Zn}Ϊ

ʵʼ,Ǹݶеݣ39ݵķͼ򵥵ϼ⣬ȷON=1.75, OFF=1.25.
(3) ON/OFFźԴĵ
MON/OFFźԴӦĽͨ(Ӧûķʱ)Ϊ
Z(m)n,m=0,1,M-1
Щʱ̵㶼Ӧһû.ʵʼУȡM=500n=20000msΪλӦԼ4СʱĲʱ.ͼ2Ϊݵʾͼ.

ͼ2ʾͼ
4Ӧù켣ķ
ף3EPA WWWһĹ켣ݣף9SDSC WWW serverһ.ЩݽзӦõΪݴ˵ںϵͳĸƽ.Ľ£
Ӧóֽ׶εĲԣǼ.Ϊ֪һҳһHTMLļͶǶͼ񣬶ÿͼWebϾһĶ.һûͨΪȡHTMLļЩǶĶ󣬶Щͨͬһ.һƾеһ¼ĻȺʱṩϢӦһûһβʣɵͬһиõЧ.ܵĸأ֮صĸزƽ.ԴˣֲԣһǷĸطһַǵһ¼ÿиԤ.ַԵĲ֮.ǰһַķϢһ֡ͺϢѷɸһĴڡ̬ûܽٷָĽ㣬ʱڵĲƽǲɱģһַԤǵĿļĴСûиˣʵʵĸشһƫ.
һȤǣ󲿷ֵûԷһηʵ٣ǵͳƵУEPAһû110֮䣬SDSCһûķʴ14֮䣬ŷʴĳɱӣߵûΪӦĵݼ.һļʵĸʺС3оС5%.
ǷֵһһûļľʱһĹϵ.ǰĲ.һоǰѸӵĸƽ㷨ͷɷ򻯣ļһôǿ԰һܳûֽɶԼСĿ飬ֵͬķϣĳ㸺عصʾ.Ҫͣ
(1) ļ. ļָļ乲ͬСļУļȵķֲȨ.Ȩķ2ָݼ
(2) . ָһʱtֳɶжεһûڶ֮ļ֮ɵݼ.
ܺܺõر֤ûġֲԡһӰС֮Ĳúܴ󣬲ڸƽ.ˣѡһʵʱֵǺҪ.
ǣHTMLͼļռļ90%90%ķڱļ10%ڣµļԼ1/3ļһ.ЩݶԵһ¼Ӱڻѽʲôãʵֺ͸ЧķǷǳҪ.

5Ⱥܲ
ϵͳԭͼͼ3ʾȺϵͳkServerɣÿ϶ͬHTTP ServerClientn̨ɣÿ϶mWebclienṭЩWebclientͬʱPowerRouterHTTP.ϸһ¾WebclientHTTPĲ.

ͼ 3 ϵͳԭͼ
(1) ǰйƹ̵Ľܣʹ50050000NoahԵON/OFFźԴ(ON=1.75ON=1.25)ĵӵõʱʾûĿʼʱ.ηWebclienṭָʱ̷HTTPʱPowerRouterľһ͵ľԵķ.ʵʵʱWebclientĳʱ̵㷢ɺ˯ߵһʱ̵㣬ٷһ.ͨıźԴĸԸı为صĴС.
(2) ǰWWWϵļСķֲNoahԣClient˵CacheЧӦʵϴļСķֲҲNoah.ɴǶÿWebclientHTTPӦļСһParetoֲУף10ָ0.4ܦ0.63ǵһҳڶĿЩĴСȴƽСΧˣͨʵȷ=0.65õܱȽϺõطӳ.ϣڽһʱܵõһЩµtraceһе.ʵϣһҳ֯صҲкܴĹϵ.ļСΪ־., ļĴСΪ1.2K, ӦHTTPΪ GET/file1200.html HTTP/1.0 .
(3) WebclientӦļеܼHTTP ServerϵļServerϵļ̫Ǳ뽫ļĴС(120312141208ֽڵļΪfile1200.html).ͬʱǻҪļСֲNoah,ǲܼ򵥵ĹҪ.(/file800.htmlļ200/file1200.htmlļ300/file10000ļ20ǹõļΪ800ֽڵ10file8000.htmlfile8009.html1200ֽڵļ15file12000.htmlfile120014.html10000ֽڵļ1file100000.html).ĳ߶ļĴСļĴСΪ300MB.
(4) ܲԵָ
ƽӦʱ䣺ƽClient/Serverӽʱ䣬ָҪϵͳʱ.
λʱڷָҪϵͳϵͳ.
λʱƽ.
(5) Խ
ѡĲϵͳ£12̨ݷԣPowerRouterΪ1̨ƵΪ166MHzPowerPC604Ϊ3̨ƵΪ300MHzPowerPC604ͻΪ4̨ƵΪ200MHzPowerPC604һ̨166MHzPowerPC6043̨133MHzPowerPC604.еĻAIX4.2.еĻͨһ100Mbpsswitch HUB.һ¼ֱת.Խͼ4ͼ6ʾЩͼĺΪϵΪӦĲָ.ĸزǸػֵΪʱ䵥λ500źԴĸı.

ͼ4ƽʱ渺زı仯

ͼ5

ͼ6λʱĴƽ
ͼпԿһ3£3Եı͵.3ķܵʺ͵λʱ䴦ƽӦһ2.62.8ļٱȣõ൱õܣݿԿϵͳĸػƽ.
6ܽ
ƹ̺ܺõķģͣҲΪģͲصϵͳṩһܺõۻ.ʵõɾݵķų˲Դͻģ.һ¼ǻȺϵͳʵֵһϵͳӳͶû͸ԵĹؼ㣬ҲǷܵĹؼأ⿪ĵһ¼Prouterƹоһʵ.ֻʹƹ̵ԹPowerRouterϵͳܲ, Դ˱֤ܲԵЧԣPowerRouterĸƽ.ĵɺͲԷһԣù㷺Ӧϵͳ.
ĵĹвƵĵطϵĲļϵͳȻ˲δûڶڵļ֮ľϵģͻ˵ķûֳ.жͬһҳаĶԤȡĹܣϵͳܽ᲻һ.
߼飺Ů19673ʿоҪоΪȺϵͳ.
У19741ʿоҪоΪм.
־ΰУ19569оԱʿʦҪоΪ粢м.
ߵλйѧԺ㼼о100080
ο
1Walter W, Verv P. Discussion of heavy tail modeling and teletraffic data. The Annals of Statistics, 1997, 25(5): 18051869
2Crovella M E, Bestavros. Self-similarity in world wide web traffic evidence and possible causes. In: International Conference on Measurement and Modeling of Computer Systems, Philadelphia, 1996. 160169
3Laura B. The Internet Traffic ArchiveEPA. ftp://ita.ee.lbl.gov/traces/epa-http.txt.Z
4Fast V P. Approximate synthesis of fractional gaussian noise for generating self-similar network traffic. Computer Communication Review, 1997, 27(5): 518
5Chris H. Tuning WEB Site Performance. http://www.networkmagazine.com/9711/11wan.htm
6Walter W, Murad S T, Robert S et al. Self-similarity through high-variability: Statistical analysis of Ethernet LAN traffic at the source level. IEEE/ACM Trans on Networking, 1997, 5(1): 7186
7Vern P, Sally F. Wide-area traffic: The failure of possion modeling. IEEE/ACM Trans on Networking, 1995, 3(3): 226244
8Leland W E, Ott T T. UNIX process behavior and load balancing among loosely-coupled computers. Teletraffic Analysis and Computer Performance Evaluation. Amsterdam: Elsevier Science Publishers B U, 1986. 191208
9Joshua P. Hans-Werner B, Claffy K. The Internet Traffic ArchiveSASC. ftp://ita.ee.lbl.gov/traces/sasc-http.txt.Z
10 Carlos R C, Azer B, Mark E C. Characteristics of WWW Client-based Traces. Boston University, Tech Rep: BU-CS-95-010, 1995 
ԭյڣ1998-12-21޸ĸյڣ1999-04-15.
