Web流量模型研究和应用

博士论坛

Web流量模型研究和应用

ModelingofWebTrafficandItsApplication

(1.郑州大学;2.河南省信息网络重点开放实验室)

石磊

1,2

刘全

1,2

黄中州

1,2

SHILeiLIUQuanHUANGZhong-zhou

摘要:Web缓存技术是提高Web性能的一种有效方法,缓存管理是Web缓存技术的核心,研究Web访问特征的数学模型是有效进行Web缓存管理的基础。本文根据Web缓存流量访问特征建立数学模型,设计实现了Web缓存流量特征模拟生成器(WebTraffsim),利用两层代理缓存结构,对Web缓存流量的访问特征和性能进行测试,对Web缓存替换算法(LRU,LFU,LRV)进行了性能评价和分析。

关键词:Web缓存;Web访问特征;缓存替换算法;模拟器中图分类号:TP393文献标识码:A

Abstract:WebcachingtechnologyisaneffectiveapproachtoimprovingWebperformance.ThemanagementofWebcachingisthekeyissueofWebcachingtechnology,andthestudyofmathematicalmodelofWebreferencecharacteristicsisthebasisofeffectivemanagementofWebcaching.AsyntheticWebworkloadgenerator(WebTraffsim)wasdesignedandimplementedbasedonthemathe-maticmodelestablishedbyWebcharacteristicsinthispaper.Thesimulatedexperimentsmadeuseoftwo-levelproxycachingtoe-valuatethereferencecharacteristicsandperformanceofsyntheticWebworkload,Webcachereplacementalgorithms(LRU,LFU,LRV)arealsoevaluatedusingsyntheticworkloadgeneratedbyWebTraffsim.Keywords:WebCaching;WebReferenceCharacteristics;CacheReplacementAlgorithm;Simulator

1引言

如何缩减Web访问延迟是Web研究中的一个重要方面。

次数、大小等方面进行考虑,以适用于不同的环境。

Web访问延迟依赖诸多因素如网络带宽、发送延迟、传播延迟

等。目前解决该问题的主要方案是缓存技术和预取技术。

Web缓存是处于用户和Web服务器之间的信息缓冲机制,该技术的基本思想是:把经常访问的信息(Web文档)存放到用户的附近(或本地),以便后续的访问能够从客户机或本地服务器

获得该信息,而不必访问远地Web服务器。研究表明Web缓存命中率可以达到30%--50%。研究Web访问特征的数学模型是有效进行Web缓存管理的基础,通过对Web用户的行为跟踪,对Web对象访问特征的深入研究分析表明:(1)Web对象流行度满足Zipf定律;(2)Web对象大小服从重尾分布;(3)Web对象访问具有局部性特征等。所以如何准确而简单地对用户序列进行建模显得尤为重要。Web缓存模型优化的关键点之一在于替换算法的优化。本文根据Web环境下用户的访问特征,利用Web-

Traffsim模拟器生成的访问日志对常用的Web缓存替换算法(LRU,LFU,LRV)进行了性能分析和评估。

2缓存替换策略

由于缓存存储容量是有限的,这时需要按某种策略将某些文档替换出去,替换策略好坏决定了缓存文档命中率(Hit-Ri-

2.1多层缓存结构替换算法描述

根据数学模型结合Web缓存特点,其基本思想是:将新请求的文档放到Cache中,如果没有足够的空间,就把权值(k)最小的文档替换出来,直到Cache有足够的容量容纳新的文档。

Method:Step1轮流对请求的文档对象进行处理,令当前请求的对象是d;

Step2if(IsInCache(d))//如果d已经存在缓存

更新d所对应的键值K(d);Else

While(缓存没有足够空间保存对象d)

For(缓存中所有对象di)D=Min(K(di));

替换D所对应的对象;

Step3将d装入缓存;

Step4设置d对应的键值K(d);

2.2网络流量特征模型

Web缓存的主要研究方面是提高Web缓存的性能从而解决网络拥塞等网络问题,很多研究表明,网络流量的不同特征对Web缓存性能有不同的影响,对缓存替换策略也有一定的影响。在多层次缓存结构中,可以在不同层次用不同的缓存策略来提高网络性能,为了研究哪几种策略结合起来能达到性能最优,需

要有灵活的具备各种访问特征的日志。但这种日志一般不存在。通过研究Web缓存流量特征模型,设计实现了一个日志模拟器WebTraffsim,可以生成所期望的模拟日志,为进一步的缓存及预取技术研究提供了重要研究。

技术创新

tio)、文档字节命中率(ByteHit-Ratio)等指标,从而在很大程度上

决定缓存系统的性能。典型缓存替换策略算法有基于访问时间间隔的LRU算法、基于频率的LFU算法、基于对象大小的SIZE算法以及基于目标函数的LRV算法等,它们分别从时间、访问石磊:教授博士

2.2.1文档流行度模型

网络流量的一个常见特征是文档访问高度不平衡,即有的

邮局订阅号：82-946360元/年-11-

《PLC技术应用200例》

博士论坛

文档访问次数很多,而有的文档仅被访问一次。齐普夫第一定律对高频对象有效,而采用齐普夫第二定律对低频对象进行模拟。

《微计算机信息》(管控一体化)2010年第26卷第1-3期

3实验及分析

实验使用了两层的代理服务器。缓存替换算法采用LRU、

Zipf第一定律:认为一个对象的访问频度值与其位次之间

的关系表现为幂函数关系。即假设一个单词在文章中出现次数为Pi,出现次数排名为i,那么遵循下面的关系:

,K为常数,α∈[0.5,1].

Zipf第二定律:

In指出现频次为n的词汇数量,I1为出现频次为1的词汇

数量。

为了模拟文档的流行度,可以先根据齐普夫第二定律求出常数K,然后根据第一定律求出高频区的流行度P。

2.2.2文档大小分布模型

对于文档大小分布的研究表明,采用两部分分别模拟比较准确:一是体分布,二是尾分布。一般用对数正态分布来模拟体分布,用Pareto分布来模拟尾分布。双指数的Pareto分布是重尾分布的,它的密度函数为:P(x)=akax-a-1,a、k>0,x≥k.它的累计分布函数为:F(x)=P[X≤x]=1-(k/x)a。对数正态分布的定义:如果X

LFU和LRV三种算法。在图1中图(a)显示了当低层代理采用LRU替换算法,高层代理分别用LFU和LRV替换算法时的命中率;图(b)显示了当低层代理采用LFU替换算法时的性能结果;图(c)显示了当低层代理采用LRV替换算法时的性能结果。

从图1可以看到,不管是在低层代理还是在高层代理,当采用LRV替换算法时得到的性能比其它替换算法的性能要好,这是因为LRV算法结合了前两种算法的优点,从而更能发挥前两种算法的优点,但这结果只是针对单层(低层)的缓存结构。而且也可以看到,低层代理缓存用LRU或者LFU替换算法时,则高层代理缓存用LRV替换算法能达到较好的性能。由此可看出,替换算法在提高代理缓存性能方面起着很重要的作用,可以通过对网络流量特征的深入研究来提出性能更好的替换算法,从

而可以更好地提高代理缓存的性能。

4结语

本文研究了Web缓存以及Web缓存在提高Web系统性能上的所起的作用,对常用的Web缓存替换算法进行分析,并采用数学模拟方法分别模拟了Web对象流行度特征、Web对象大小重尾分布特征、Web对象访问的时间局部行特征。最后,利

技术创新

~N(μ,σ2),(即X是正态分布),那么еx是对数正态分布,用Ln(μ,σ2)来表示,它的概率密度函数是:

2.2.3时间局部性模型

可以通过时间距离模型来描述。时间距离d所定义的实际上就是访问同一文件的时间间隔长度。对于请求序列Ri=r1,r2,…,ri,时间间隔d有相应的序列Di=d1,d2,…,di,其中di为请求ri的时间距离。从时间距离d的定义可以看出,时间距离序列Di中不为0的元素代表的是客户请求同一文件的时间间隔,也就是请求序列Ri的时间局部性。因此分析时间距离Di中不为0的元素的统计特性也就是分析原请求序列的时间局部性。Di的平均值越小,说明请求序列的时间局部性就越强。

用WebTtraffsim模拟器生成的访问日志作为数据来源,对两层的代理缓存进行了模拟,并利用Web缓存替换算法进行了细致的性能评估,通过实验进一步证明:在多层次代理服务器中,低层缓存用LRU或LFU替换算法,高层的缓存用LRV替换算法,这样的结合能得到更好的性能。

2.3.4验证模拟日志的性能

实验模型采用两层结构的网络缓存代理配置,每一层的缓存文档由该层缓存替换策略所决定。为了比较模拟流量和实际流量的性能差别,用命中率作为评测标准。缓存替换算法采用

(a)命中率(低层代理:LRU)(b)命中率(低层代理:LFU)

LRU、LFU和LRV三种算法,综合表1、表2、表3可分析出模拟和真实日志的类似的趋势,即:(1):低层缓存用LRU或LFU替换算法,高层缓存用LRV替换算法,这样的结合能得到更好的性能。(2):都是随着缓存的增长模拟的和真实的日志的命中率也随之而增长。(3):低层缓存的命中率一般比高层缓存命中率要高。上述特征也验证了由WebTraffsim生成的模拟日志可以代替真实日志进行缓存方面的研究。(Mlrv和Zlrv,其中M代表模拟日志,Z代表真实日志;ClruPlrv代表低层缓存采用Lru替换算法而高层缓存采用Lrv替换算法,以下相同。)

(c)命中率(低层代理:LRV)

图1两层代理缓存结构的性能(模拟日志)

表1低层缓存的命中率

(下转第29页)-12-360元/年邮局订阅号：82-946《现场总线技术应用200例》

您的论文得到两院院士关注博士论坛

(710055西安西安建筑科技大学管理学院)黄光球朱擎

(Xi'anUniversityofArchitecture&Technology,Xi'an710055,China)HUANGGuang-qiuZHUQing

通讯地址:(710055西安西安建筑科技大学管理学院)黄光球

(收稿日期:2009.01.20)(修稿日期:2009.04.20)

将所有标记为t时刻的入侵类送入决策层进行处理,利用用模糊和证据理论的方法,具体算法步骤如下:

设M为数据源列数,N为数据源行数,V为攻击类型数。输入:数据层每5s收集之前100s的数据并做处理;特征层处理后得到新的数据集DataSet

输出:攻击类型

Step1:初始化i=0,j=0,k=0;

Step2:FORk=1TOV,计算网络安全态势库中第j个属性属于第k种攻击的Ukj与σkj;

Step4:FORj=1TOM,计算数据源中每一个Xi(j)属于攻击类型V的正态隶属度AkXi(j);

Step5:FORi=1TON,计算数据源正态隶属度×权重wj,;Step6:对Step4求和;

Step7:得到模糊隶属度集合mi(A);

Step8:FORi=1TON,对隶属度集合进行融合得到m(A);Step9:找到最大的m(A),并得到所属攻击类型;

通过以上每层融合方法,动态计算某天各个时刻的攻击类型,可得这段时间的攻击图,可反应出攻击严重度、攻击种类。本文在Snort用户手册对攻击分类与优先级划分来确定攻击的严中、低3个等级.重度,其根据攻击类别把严重度划分为高、

在测试数据集中共有37种入侵行为,这些入侵行为被分成4大类:probe,denialofservice(DOS),user-to-root(U2R)和re－mote-to-local(R2L),选择10组不同入侵行为的数据集,在一天内分别在不同的时刻进行攻击,根据本文的信息融合的动态安全态势评估模型,可得这段时间的攻击图,如图3所示。

(上接第12页)本文作者的创新点:一个好的Web缓存替换算法来源于对

Web对象访问特性的深刻认识,本文设计并实现了一个Web日

志模拟生成器WebTraffsim,并通过模拟多层Web缓存结构的各种替换算法的结合来研究怎样更好的提高缓存的命中率,取得了一定的研究成果。通过实验进一步证明:在多层次代理服务器中,低级缓存用LRU或LFU替换算法,高一级的缓存用LRV替换算法,这样的结合能得到更好的性能。

图3网络攻击态势图

4结论

本文的创新点:(1)采用多源传感器技术,能更多的收集和捕获数据。(2)采用动态数据处理的方法,能快速发现攻击。(3)采用信息融合模型采用分层融合的方法避免了单一分析方法的不确定性。(4)通过模糊聚类和模糊模式识别的方法进行数据的分类,结合D-S证据组合对数据分析结果进行融合,并引入粗集理论计算各属性的权重,进一步提高了识别效果。参考文献

[1]邓维斌,朱振国,融合网络安全信息的网络安全态势评估模型,微计算机信息.2007,8-3.

[2]孙全,叶秀清,顾伟康,一种新的基于证据理论的合成公式,电子学报,2000.8.

[3]http://www.snort.org/docs/SnortUsersManual.pdf

作者简介:黄光球(1964-),男,湖南桃源人,汉,西安建筑科技大学管理学院教授,博士,从事电子商务与网络安全研究工作。Biography:HUANGGuang-qiu,male,bornin1964,Hanna-tionality,ProfessorofSchoolofManagement,XianUniversityofArchitecture&Technology,ResearcherofElectronicCommerce&NetworkSecurity.《PLC技术应用200例》

参考文献

[1]L.Breslau,P.Cao,L.Fan,G.PhillipsandS.Shenker.WebCachingandZipf-likeDistributions:EvidenceandImplications,InProceedingsofInfocom’99,1999,126-134.

[2]1.A.Mahanti,D.Eager,C.Williamson.TemporallocalityanditsimpactonWebproxycacheperformance.PerformanceEvaluation,2000,42(2-3):187-203

[3]L.Xiao,X.Chen,X.Zhang,etc.Onscalableandlocality-awareWebdocumentsharing.J.ofParallelandDistributedComputing,2003,63(10):945-962

[4]M.Arlitt,T.Jin.Aworkloadcharacterizationstudyofthe1998WorldCupWebSite.IEEENetwork,2000,14(3):30-37

s[5]LeiShi,ZhiminGu,LinWe,etc.AnApplicativeStudyofZipf’

LawonWebCache.InternationalJournalofInformationTechnolo－gy,2006,12(4):49-58.

[6]K.Wong.WebCacheReplacementPolicies:APragmaticAp－proach.IEEENetwork,2006,20(1):28-34.

[7]WenyuQu,KeqiuLi,MsaruKitsuregawa,etc.AnOptimalSolu－tionforCachingMultimediaObjectsinTranscodingProxies.Com－puterCommunications,2007,30(8):1802-1810.

[8]于国良,汪远征,韩文报.建立高性能扩展的WEB应用系统.[J]微计算机信息1008-0570.0.2006-18-022.

作者简介:石磊(1967-)男,教授,博士,研究方向:高性能计算、Web

预取与挖掘、中间件技术。

技术创新

Biography:SHILei(1967-),Male,Professor,Ph.D,Majorin:HighPerformanceComputing,WebPrefetchandMining,Mid-dleware.(450001河南郑州郑州大学信息工程学院)石磊刘全

黄中州

(450052河南郑州河南省信息网络重点开放实验室)石磊

刘全黄中州

(SchoolofInformationEngineering,ZhengzhouUniversity,Zhengzhou,Henan,450001,China)SHILeiLIUQuanHUANGZhong-zhou

(HenanProvincialKeyLabonInformationNetwork,Zhengzhou,Henan,450052,China)SHILeiLIUQuanHUANGZhong-zhou

通讯地址:(450001郑州市科学大道100号信息工程学院(研究生)8106信箱)刘全

(收稿日期:2009.02.07)(修稿日期:2009.05.07)

邮局订阅号：82-946360元/年-29-