大规模网络模拟的背景流量建模*

钱亚冠，王 滨，关晓惠

（1.浙江科技学院理学院 杭州310023；2.浙江大学计算机学院 杭州310027；3.浙江水利水电专科学校计算机系 杭州310018）

1 引言

随着Internet的快速发展，大规模分布式应用出现在互联网上，如P2P、Grid等，这些应用协议在正式部署前需要在大规模网络模拟环境下测试，验证在各种动态条件下的正确性和容错性。对于路由协议，同样需要在大规模环境下测试其路由性能。大规模网络模拟面临的一个重大挑战是对计算资源的巨大消耗，不仅需要大量的CPU时间，而且对主存容量也提出了极大的挑战。解决这个问题通常采用并行化和模型抽象，本文正是采用模型抽象的方式解决大规模网络模拟下的背景流量建模问题。

[1]统计了2004-2007年在SIGCOMM、SOSP/OSDI和NSDI上发表的论文，发现25.6%的论文在其模拟实验中没有采用背景流量。根据参考文献[1]的研究，真实的背景流量对应用和协议行为产生的影响远超过简单的流量模型，因此建立真实的背景流量模型对于实验的验证和可信度具有重要意义。由于Internet广泛使用TCP协议，传输层流量明显受网络拥塞的影响，因此采用tracedriven的方法建立的流量模型不具有普遍意义[2]。为此，采用简单的ON/OFF模型[3～5]在应用层建立背景流量模型，但Vishwanath K V[1]也指出，合理的背景流量必须同时具有真实性和响应性，能对前景流量的变化作出反馈响应。因此，在传输层建立采用fluid表示的微分方程模型表示这种反馈机制。为了降低时空复杂度，采用fluid[6,7]的概念对流量进行抽象。fluid流量表示与packet表示的区别在于，前者将连续的突发包看成一个整体，由此带来的好处就是大大降低模拟事件的数量和存储开销，缺点是降低了模拟精度，但实验者一般不关心背景流量的包级行为。因此选用fluid表示背景流量是合适的。

以往的流量模型，主要集中在单一的packet级或fluid级模拟，缺少综合用户行为和网络动态特征的表达。本文的主要贡献是提出了运用结构化的方式建立背景流量模型，即在应用层建立用户的行为模型，在传输层建立带拥塞反馈的流模型。这种模型的优点是既体现了应用层的用户特征，又反映了流量模型对网络拥塞的反馈机制，同时兼顾了真实性和模拟效率。

2 相关工作

流量模型从驱动方式上可分为两类。一类是通过数学方法合成流量，试图解析自相似或长相关特征（LRD）的形成机理，典型的模型有分形布朗运动 （FBM）[8]、F-ARIMA过程[9]、MMP[10]、ON/OFF 过程[3]，但 FBM 等模型的条件假设过于理想，目前能对LRD合理解析的是ON/OFF过程。另一类是根据测量数据生成流量，最简单的方法是重新将这些数据包按序发送一次，但这种简单方式并不能反映网络的普遍特征，而只反映数据采集时刻的网络状况[2]，更普遍的方法是对测量数据进行统计分析，获得流量的统计特征，再合成流量，如 Harpoon[11]、Tmix[12]、Swing[13]。

流量模型从控制方式上可分为开环和闭环两类。所谓开环，就是没有流控机制；而闭环，其发送速率会根据网络的拥塞程度调整。目前大多数模型并没有考虑反馈机制。Swing是考虑了反馈机制的流量模型，但其属于包级模型，不适合作为大规模的背景流量模型。

流量模型从模拟粒度上又可分为基于包级和基于fluid。基于fluid的模型在模拟效率上要优于包级，但由于抽象了一些特征，使得模拟精度下降。为了获得fluid模型和包级模型的交互能力，通常采用微分方程表达fluid模型在TCP上的流控和拥塞避免行为，从而使其具有对网络动态性的响应能力。尽管fluid模型很适合大规模的背景流量发生器，但目前只局限在对TCP层的行为模拟，并没有考虑应用层的用户行为特征。

3 背景流量模型

本文提出的模型是将流量的产生机制分多个尺度（session、flow、fluid）构建，分别表达独立于网络条件的用户行为特征和对网络动态变化敏感的传输层响应机制，尽可能地接近流量源产生流量的结构化机理。模型框架如图1所示。

为了满足大规模网络模拟的需要，建立这个背景流量模型的目标如下。

·简单，计算复杂度低。选择简单的ON/OFF模型作为流量源模型，用流体作为抽象级的流量表示。作为背景流量的源节点，简化其协议栈，只保留应用层和传输层，通过静态路由简化掉网络层。

·在用户端建立多类型的流量源，尽可能反映网络的真实情况，尤其是流量的突发特征。为此，提出长流（P2P）和短流（Web）组合、TCP 流和 UDP 流并存的方式，在多个层次上建立模型，分别反映用户的行为特征和网络的动态特征。

·具有自适应带反馈控制的速率调整机制。Vishwanath[13]等研究发现，如果流量模型不具有对网络动态变化的响应能力，那么相关的实验结果与真实情况就很难相符。

3.1 ON/OFF模型

ON/OFF模型是一种表示流量源的两状态模型，该模型将激活状态持续阶段称为ON周期，而将空闲状态持续阶段称为OFF周期。大量独立的ON/OFF信源(ON周期服从重尾分布)在流量汇聚后形成了自相似性[4]。多分辨率下的ON/OFF过程如图2所示，其作为一种基于用户行为模拟的产生方法，适合模拟实际环境中的自相似业务流量。

3.1.1 Web类型的ON/OFF流量模型

Web用户产生流量的行为过程为：点击超链接和思考这两个过程交替进行，分别映射应用层的ON阶段和OFF阶段；点击超链接后会产生一个新的session，一个session至少包含一个TCP flow，当session结束后，进入下一个思考阶段（OFF阶段）。在TCP flow层面，又构成自己的ON/OFF过程。根据参考文献[14]和[15]的研究结论，对Session长度的分布、到达过程、TCP flow长度的分布等作出合理假设。

session：连续的session之间是独立不相关的，即session到达过程服从Poisson分布，session长度服从Pareto分布，每个session中包含的TCP Flow个数服从Possion随机分布。

TCP flow：flow长度分布特征是大量的短流（mice flow，≤10 KB）、少量的大流（elephant flow，≥5 MB），采用混合的Pareto和Weibull分布：

式（1）中的参数 α1、α2、α3分别取 0.38、1.05、2.35；参数β1、β2、β3分别取 2.7、3、200。

flow的到达间隔 （inter-arrival time，IAT）采用分段Weibull分布：

式（2）中的参数 α1、α2分别取 0.76、0.15；参数 β1、β2分别取 0.01、3×10-5。

flow的持续时间服从分段Pareto分布：

式（3）中的参数 α1、α2分别取 0.43、1.5；参数 β1、β2分别取 0.1、10。

3.1.2 P2P类型的ON/OFF流量模型

P2P应用是典型的Internet范围内的分布式文件共享系统，P2P区别于Web的重要特征是：主机系统同时充当内容提供者和消费者。

目前P2P应用的流量已经超过Web流量[14]。根据参考文献[14]的测量发现，P2P流同时存在很多细小流和巨量流，流的持续长度和流之间的间隔呈重尾分布。因此在flow这一级别采用混合的Weibull-Pareto分布：

式（4）中的参数 α1、α2、α3分别取 0.81、0.35、1.42；参数β1、β2、β3分别取 1.36、0.005、400。

flow的到达间隔采用混合的Weibull-Pareto分布：

式（5）中的参数 α1、α2、α3分别取 0.87、0.65、0.97；参数β1、β2、β3分别取 0.35、0.45、0.18。

flow的持续时间服从混合的Weibull-Pareto分布：

式（6）中的参数 α1、α2、α3分别取 0.35、0.55、1.53；参数β1、β2、β3分别取 88.3、57.2、1.53。

3.2 fluid表示

将连续的突发数据包看成一个整体，并假设该整体内的所有数据包速率相同，这样表示的flow称为fluid flow[3]。假设fluid flow在缓冲队列中按FIFO方式获得服务。队列中汇聚速率恒定部分称为fluid chunk，通常在队列中会有多个fluid chunk。队列中的fluid和fluid chunk如图3所示。当汇聚流量速率大于服务速率时，就会在队列中产生滞留量，并会改变各个fluid flow的离开速率。网络模拟器只跟踪fluid flow的速率变化，并产生相应的事件，这样就可避免对数据包的跟踪，从而大大减少事件数，提高模拟效率。

图3 队列中的fluid和fluid chunk

3.2.1 拥塞避免的微分方程模型

发送端对网络动态变化的响应是通过TCP协议的拥塞避免算法实现发送速率的调整，对流量采用fluid的表示形式就是跟踪flow速率的变化，而这种变化正是由于网络拥塞引起的。因此，首先采用微分方程为TCP拥塞避免算法建立模型：

在 t时 刻 ，TCPflowi：Wi(t)表示拥塞窗口（congestion window）的大小，Ri(t)表示往返时延，λi(t)表示丢包率。表示算法的加性增加部分，而表示算法的乘性减少部分。式（7）是TCP协议对网络拥塞状况的响应行为，由此可对发送速率作出调整：Ai=Wi/Ri。这里假设接收窗口无限大，发送速率仅受冲突窗口的影响。

3.2.2 背景流与前景流的交互

前景流量与背景流量之间的互相影响是通过在交换节点的缓冲队列中竞争带宽引起的。这种竞争会导致过队列长度、丢包率等参数的变化，可以为前景流量提供排队信息。为t时刻队列l建立如下的微分方程模型：

其中，ql(t)为 t时刻的队列长度为背景流和前景流的速率总和，pl(t)为丢包概率，由具体的服务策略决定，Cl为队列的服务速率（带宽）。

用微分方程表示的fluid表示的背景流，可以通过固定时间步长，用Runge-Kutta法求解，但前景流量一般为离散事件模拟，并没有固定的时间步长。为了保持两者队列变化信息的一致性，采用参考文献[16]提出的影子变量方法，即在fluid的固定时间步长之间保存最近的包事件对队列的改变信息。

3.3 模型实现

通过 DaSSFNet[17]提供的 API实现了fluid和 packet混合模型。DaSSFNet是用C++实现的一个模拟引擎，提供了如 下 的 核 心 类 ：Entity、Process、Input、Output、Link、Event。利用这些类，可以进一步构造网络元素，如Host、Router、Linker等。模拟过程并没有真实的数据包产生，而是一系列模拟事件，如包发送事件、包接收事件等。对于fluid表示的流量，是将多个连续的数据包看成整体产生事件的。为了产生一定分布的fluid，按升序定义了两个向量，每个向量元素代表一个Web文件或P2P文件的大小，通过产生满足§3.1定义的随机数选择fluid的流量持续时间。

4 实验分析

4.1 实验建立

硬件平台为 Intel Core2，1.66 GHz，1 GB 内存，操作系统为Linux Fedora2,Kernel 2.6.29。实验拓扑采用典型的哑铃型拓扑，如图4所示，包含两个路由器，路由器之间的链路bottleneck带宽为 10 Mbit/s，链路时延 5 ms，路由器缓冲队列容量500 KB，采用FIFO的服务策略。

4.2 自相似分析

随着网络测量研究的不断深入，大量文献证明从LAN[18]到WAN[19]，网络流量呈现自相似或分形特征。通过R/S方法估计表征自相似度的Hurst参数[18]。具有自相似特征的时间序列，其Hurst参数的范围为1/2

20个ON/OFF源汇聚后在不同时间尺度的H参数分别为 0.8415、0.8502、0.8521、0.7776。不同时间尺度下的流量和R/S图如图5所示，可以看出，当20个ON/OFF源聚合后，其自相关性是很明显的。通过进一步测试不同数量的ON/OFF源会聚后的H参数变化，发现随着源的数量的增加，H参数增大，也就意味着自相关程度的加强，但并不是线性增加，而是在某种程度上服从幂律分布，H参数的变化趋势如图6所示。这也进一步验证了无限个ON/OFF源的汇聚趋向于长相关的理论，同时也说明5～20个ON/

OFF源的聚合已经能满足实验的需要。

4.3 与包级发生器的性能比较

不同的ON/OFF源数量在相同的模拟时间（取10 000 s）下测量CPU时间。fluid表示的模型CPU时间与ON/OFF源的数量基本呈线性关系递增，且斜率非常小；而packet表示的模型CPU时间与ON/OFF源的数量基本呈指数关系递增，如图7所示。同样，fluid表示的模型，其存储消耗量与ON/OFF源的数量基本呈线性关系递增，而packet表示的模型基本呈指数关系递增，如图8所示。由此可以得出一个结论，无论从实际模拟需要的时间看，还是从对存储器的消耗看，包级流量生成模型是不适合作为背景流量发生器的。

5 结束语

本文提出的背景流量模型，主要针对大规模网络模拟环境，不但适用于不需要考虑包级细节的分布式应用模拟，而且适用于需要考虑底层网络细节的协议性能测试。为了实现这个目标，选择了ON/OFF模型作为用户层的行为建模，传输层采用fluid抽象表示模型，大大缩短了模拟执行时间，节省了大量存储空间。把这两种模型结合在一起，不但能更好地描述流量的自相似特征，同时能对网络动态变化作出速率调整，更加接近真实的网络环境。通过实验模拟，取得了比较好的效果，证实了最初的设想。将来进一步需要研究的问题是在分布式大规模环境下继续验证结论，同时对如何使背景流量快速收敛到稳定状态的问题作进一步的研究。

参考文献

1 Vishwanath K V,Vahdat A.Evaluating distributed systems:does background traffic matter. In: Proc USENIX Technical Conference,2008

2 Floyd S,Paxson V.Difficulties in simulating the Internet.IEEE/ACM Trans on Networking,2001,9(4):392～403

3 Jong Suk Ahn,Peter B Danzig.Packet network simulation:Speed up and accuracy versus timing granularity.IEEE/ACM Transactions on Networking,1996,4(5):743～757

4 WalterWillinger,Murad S Taqqu，RobertSherman.Selfsimilarity through high-variability：statistical analysis of ethernet LAN traffic at the source level.IEEE/ACM Transactions on Networking,1997,5(1):71～86

5 Taqqu M S,Willinger W,Sherman R.Proof of a fundamental result in self-similar traffic modeling.Computer Communications Review,1997

6 Liu Y,Presti F L,Misra V,et al.Fluid models and solutions for large-IP networks.In:Proc ACM/SIGMETRICS,2003

7 Liu Y.Scalable fluid models and simulations for large-scale IP networks.ACM Trans on Modeling and Computer Simulation(TOMACS),2004,14(3):305～324

8 Norros I.On the use of fractional brownian motion in the theory of connectionless networks.IEEE JSAC,1995,13(6):953～962

9 Jose C Lopez-Ardao,Candido Lopez-Garcia,Andres Suarez-Gonzalez.On the use ofself-similarprocessesin network simulation.ACM Trans on Modeling and Computer Simulation,2000,10(2):125～151

10 Clegg R G.Simulating Internet traffic with Markov-modulated processes.In:ProceedingsofUK Performance Engineering Workshop,2007

11 Sommers J,Barford P.Self-configuring network traffic generation.In:Proc IMC,2004

12 Weigle M C,Adurthi P,Hern F,et al.Tmix:a tool for generating realistic TCP application workloads in ns-2.CCR,2006,36(3):67～76

13 Vishwanath K V,Vahdat A.Realistic and responsive network traffic generation.In:Proc ACM SIGCOMM,2006

14 Basher N,Mahanti A,Mahanti A,et al.A comparative analysis of Web and peer-to-peer traffic.In:Proc WWW’08,Beijing,China,2008

15 Feldman A.Characteristics of TCP connection arrivals.J Wiley&Sons,2000

16 Liu J,Li Y.Parallel hybrid network traffic models.Transactions of the Society for Modeling and Simulation,2009,85(4):271～286

17 Liu J.Dartmouth S S F (2002),http://www.cs.dartmouth.edu/research/DaSSF/intro.html,2004

18 Leland W E,Taqqu M S,Willinger W,et al.On the self-similar nature of ethernet traffic (extended version).IEEE/ACM Trans on Networking,1994,2(1):1～15

19 Paxson V,Floyd S.Wide-area traffic:the failure of poisson modeling.IEEE/ACM Trans on Networking,1995,3(3):226～244