Web访问特征模型建模

开篇：润墨网以专业的文秘视角，为您筛选了一篇Web访问特征模型建模范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要:web访问特征模型建模是进行有效Web缓存管理的基础。该文根据Web访问的四个典型特征建立综合的数学模型,实现了

>> 各种数据库访问方法存在的缺点与新型的通用Web数据库访问模型 基于Web2.0 UML Profile的计量系统模型架构建模 访问控制模型研究 组合Web服务访问控制策略合成 Web客户访问模式算法的分析 Web服务访问控制策略研究 Web访问保护拒绝网络挂马 基于XML与FILTER的WEB访问 自适应学习系统中学习者特征模型及建模方法述评 ILASII OPAC系统访问日志建模初探 GIS模型与建模 基于特征点加细的多分辨率人脸形变模型及人脸建模 构建模型,拓展应用 构建模型解难题 基于Web的数字资源远程访问实现探究 浅谈Expression Web 中的数据访问技术 浅谈基于ASP的WEB数据库访问技术 Android客户端访问Web Service的实现 在Web项目服务端访问Office文件 基于WEB数据库安全的访问技术 常见问题解答 当前所在位置：l(htm)。其中,.img占60%左右,.html (htm) 占30%左右[1];2)文档的访问频率服从类齐普夫法则[6];3)文档的大小分布尾分布服从重尾分布,体分布服从对数正态分布[1,3];4)许多文档(大约50-70%)仅被访问一次[1,5];5)约10%的访问文档占了总的访问的90%[1,5];6)Web对象访问具有时间局部性和空间局部性[2,4,7,8]。了解这些特征对于网络访问建模起着很重要的作用。

1.3 文档的访问距离模型(IAD)

访问距离[6]指某个Web文档两次访问之间被其它Web文档隔开的文档总数, 利用N={1,…,n}即i=1,…,n来代表N个可缓存文档,到达缓存的一系列请求用{Rt,t=0, 1, …}来表示,如果Rt=i,那么第t个访问文档是i,{Rt, t=0, 1, …}的流行度被定义为:P=(P(i),…P(N)),

请求序列的时间相关性被定义为:

r(s,t) = Cov[Rs, Rt], 其中s,t=0,1,…。

1.4 IRM模型

IRM[2]模型是指一个访问流中的所有对象都完全不相关,每个请求都独立于其他任何访问请求,这个模型其实是一个理想模型,由于每个文档之间都会有一些相关性,所以没有访问流是符合这种分模型的。在IRM模型中,它的IAD分布服从几何分布,几何分布是个无记忆分布。根据1.3定义的访问概率P=(P(i),…P(N)),可知IAD为k的概率di(k)为:

di(k)=Pi(1-Pi)k-1 (1)

总的IAD概率函数为:

(2)

1.5 文档的访问相关性

变异系数[8]可以用来度量访问局部性的相关性。变异系数为它的标准方差除以它的均值,变异系数是对一个分布的相对分散度的一个简单度量的方法。

如1.3所描述,IRM模型的IAD分布服从几何分布,对于一个给定的几何分布,均值是:μ=1/p,方差是:σ2=(1Cp)/p2,则它的变异系数为:

CV= (3)

当访问文档间没有访问相关性时,CV值很接近于1,它的相关分布可以认为是IRM,而值大于1时代表分布具有访问相关性。

2 网络流量特征建模

WebGenM分为四个建模部分,通过对四个主要访问特征的建模来模拟网络访问流。

2.1 文档流行度建模

当前很多文献采用齐普夫第一法则对文档流行度建模,但齐普夫第一法则模拟流行度比较高的对象比较准确,而对流行度比较低的对象模拟不准确[7],为此引入齐普夫第二法则对低频对象建模。

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

算法1:模拟文档的流行度:

已知文档的总请求数N,不同的访问文档数,低频区文档数,齐普夫参数β,根据以上分析可求出高频区文档的流行度。方法如下:

1)根据Im/I1=2/m(m+1)可求出低频区各个流行度的文档个数;

2)根据K=Pm(高频区不同的文档数+Im/2)β来估计K的值;

3)根据Pr=K/rβ求出高频区文档的流行度P;

2.2 文档大小分布模型

对于文档大小分布的研究表明,采用两部分分别模拟比较准确:一是体分布,二是尾分布。本文用对数正态分布来模拟体分布,用Pareto分布来模拟尾分布,最后把重尾分布的尾分布与体分布连接起来。

算法2:模拟文档的大小分布:

已知α(尾参数),k(尾起始点),μl(对数正态分布的均值),σl(对数正态分布的方差),根据这些参数和下面的算法可求出各个文档的大小。

2.2.1 模拟尾分布

当小于或等于尾部文档的个数时,循环执行下面n次:

1)生产一个随即值y';

2)用计算文档的大小;

2.2.2 模拟体分布

根据已知的对数正态分布的均值和方差求出正态分布的均值μ和方差σ;当小于或等于体分布的个数时,循环执行下面n次:

1)根据Polar方法求出符合标准正态分布的变量值对x和y;

2)Return ;

2.2.3 连接

把前面一和二求得体分布和尾分布连接起来得到Web对象大小分布。

2.3 时间局部性建模

Web访问时间局部性指访问过的对象在将来的短时间内很可能将会被再次访问。在对时间局部性的建模中,时间局部性模型就是根据算法1生成的文档流行度对访问序列进行排序,使用动态LRU栈方式进行生成。

算法3:模拟时间局部性:

根据算法1求出的文档流行度,下面的算法输出文档的访问顺序。

当总的访问次数大于0时,循环执行下面算法n次:

2.3.1 栈不空并且要访问的对象在栈中

1)把文档赋给输出流Refstream;

2)判断文档的剩余访问次数是否为0,如果为0,则将此对象从堆栈中移出,其下面的对象顺序上移;如果不为零,则将此对象移至栈顶,其它对象顺序下移。

2.3.2 栈为空或要访问的对象不在栈中

1)随即生成一个访问并把它赋给输出流 Refstream;

2)如果文档的剩余访问次数为零,则不入堆栈,否则将此对象存入栈顶,其它对象顺序下移.

最后得到输出流Refstream。

2.4 访问相关性模型

变异系数可以为空间局部性的相同文档建模,通过变异系数来反映相同文档间的空间局部性的强弱。变异系数的计算方法可以参考1.5的描述,每个不同的访问文档都有自己的访问距离变异系数,由于中间值稳定,且独立于日志的总长度,可以用中间值描述文档访问相关性整体的特征。

算法4:模拟Web对象相关性

已知文档的总请求数N,不同的访问文档数,下面的算法输出Web对象变异系数值。

1)根据日志求出不同文档的IAD分布;

2)对每个不同文档,求出其IAD分布的变异系数;

3)对变异系数排序之后,就可求出变异系数的中间值,则得出日志的总的变异系数。

3 实验

本实验测试建模的流量特征是否和真实的特征一致,是否可以代替真实日志应用到实际应用中。

3.1 实验目的

为了对建模的网络流量性能进行测试,在实验中验证模拟日志的访问流行度特征和文档大小特征,实验分析表明Web访问特征建模符合前面1.2所描述的特征,表明建模能仿真真实日志,能够替代真实日志用于Web性能研究等方面。其中,模拟日志生成的依据是建立在第二部分的基础上。

3.2 实验结果

流量的特征主要集中在文档流行度和文档大小分布方面,通过验证这两方面的建模来验证模拟日志的整体建模。

3.2.1 模拟日志的流行度建模

建模的日志根据流行度和排名关系(取对数后)画出图1,从图中可以看到图形接近于一条直线,可知访问频率符合齐普夫法则。

3.2.2 模拟日志的文档大小建模

根据文档大小的分布画出图2,可以看到图形接近于一条直线,且图中测量到的斜率值(大约为-1.2左右)和输入的尾参数值(α=1.2)匹配,可知它的大小分布符合重尾分布。

4 结束语

根据网络访问特征进行建模,可以解决实际中真实日志面临的收集难等问题,实验表明WebGenM能较好地对网络流量特征进行建模,具有较大的灵活性。建模可以用于测试和预测缓存性能,从而提出更有利于缓存性能提高的算法和思想。

参考文献:

[1] Shudong Jin and Azer Bestavros.Temporal locality in web request streams[R].Technical Report, Boston University Computer Science Department,2002.

[2] Fonseca R,Almeida V,Crovella M,et al.On the intrinsic locality properties of web reference streams[C].In Proc. of IEEE INFOCOM Conference,2003.

[3] Busari M, Carey L.Williamson.ProWGen: a synthetic workload generation tool for simulation evaluation of web proxy caches[J].Computer Networks,2002,38(6):779-794.

[4] Breslau L,Cao P,Fan L,et al.Web caching and Zipf-like distributions: evidence and implications[C].In Proceedings of IEEE Infocom. New York: IEEE Computer and Communications Societies,1999:126-134.

[5] Arlitt M and Williamson C.Internet Web Servers: Workload Characterization and Performance Implications[J].IEEE/ACM Trans,on Networking,1997,5(5):631-645.

[6] Roadknight C,Marshall I,Vearer D.File Popularity Characterization[C].Proceedings of the Second Workshop on Internet Server Performance,1999.

[7] Lei Shi,Yingjie Han,Xiaoguang Ding,et al.An SPN based Integrated Model for Web Prefetching and Caching. Journal of Computer Science and Technology[J].2006,21(4):482-489.

[8] Vanichpun S,Makowski A M.The output of a cache under the independent reference model - where did the locality of reference go[C].Proceedings of the joint international conference on Measurement and modeling of computer systems.New York: ACM Press,2004:295-306.