基于多尺度小波变化的自相似网络流量预测

何凯霖，丁晓峰

（电子科技大学 成都学院 计算机系，四川 成都611731）

0 引 言

Leland W E等［1］在大量的业务流量监测过程中发现了网络流量具有自相似 （self－similarity）特性，指出实际流量序列的自相关函数随时间尺度的增大呈渐近双曲线衰减而非负指数衰减，流量表现出重尾分布的长相关性 （longrange dependence，LRD）特征，并且不论网络的拓扑结构、用户数量、服务类型如何变化，这种自相似性是始终存在的。这宣告了具有短相关特征的流量模型已不能充分反映网络流量的高可变性，不再适合于网络流量的分析和建模［2，3］。

后续研究结果表明［4－6］，传输层协议本身就是导致网络流量出现自相似性的决定因素之一，特别是占整个网络流量的90%左右的TCP协议，其拥塞控制中的超时重传和指数退避机制会使分组到达时间间隔呈重尾分布；反言之，网络流量自相似性的存在又给网络管理和网络协议的运行增加了复杂性［7］，如大尺度上的突发性会造成网络资源严重过利用率和欠利用率时间的增大，而且随自相似程度的增加，丢失率、重传率以及平均队列长度和响应时间均随之增长［8］；路由器中包序列的排队问题也受网络流量在小尺度时间范围内波动的影响，而尺度的划分通常正是以拥塞控制机制中的RTT为基准［9，10］。所以，网络流量尺度特性和不同尺度上的自相似特征必然影响到TCP的拥塞控制机制，这使传统模型下所沿用的如下结论都不再适用：缓存线性增长导致报文丢失按指数规律减少以及传输带宽利用率成比例增长等。这直接导致网络拥塞不可避免，从而造成TCP难以有效地实施网络控制和QoS保证。因此针对具有自相似特性的流量，网络协议的优化尚需更多的研究。

本文提出以DWT多尺度分析为依据建立网络流模型并进行流量预测。把利用该模型计算得到的预测流量相似性程度值Hurst引入路由器的主动队列管理算法 （AQM）中，采用AQM算法形成的严谨的响应方案对异常的估计流量进行处理，可以提高动态流量控制的有效性，实现了网络协议的优化。

1 流量数据基于DWT的多尺度分析

考虑到网络流量具有较高的复杂性和不平稳特性，本文首先利用DWT对原始流量数据进行多尺度分解，以获得包含不同频率特性的近似分量与细节分量。所谓近似分量是指与分解前的网络流量基本性质一致的分量，即基本不包含高频的短相关特性而保留着未分解流量的长相关性等；所谓细节分量是指反映细节特性如动态流量的短期依赖关系即短相关性。因此通过小波变换不仅保持原流量的趋势并减少突发，能有效达到消噪预处理的效果，且使网络业务流量的复杂性得到分解。之后在特性相对单一的小波分量上建立刻画网络流量特性的序列模型，可实现以较快的收敛性、较高的平稳性和较低的误差来进行流量预测。基于DWT的多尺度分析方法在网络流量预测和控制中极具有效性。并且通过分析论证可得网络协议性能优化空间与预测流量自相似程度密切相关。大的相似性在适当条件下可以提供更优越的性能。

1.1 自相似程度的判断

为达到对网络流量自相似性程度进行判断的目的，本文选取研究者普遍认同的用以刻画自相似性程度的Hurst参数H，当H取值在1／2＜H＜1之间时，则认为随机过程具有自相似性，其程度大小随H值的增大而增加。这种现象映射到实际网络中就叫做网络流量突发，目前网络实际流量的H估计值通常在0.7～0.9之间。以上用于求解Hurst值的方法需要较强的稳定性，故采用R／S法 （resealed adjusted range statistic）。

1.2 基于DWT的多尺度分析过程

要将小波变换应用于网络流量分析中，需要采用离散小波变换 （DWT）以更好地处理离散数据信号［11，12］。这里将信号f（t）的连续小波变换 （CWT）定义为

图1 j层小波分解过程

Aj＝ ｛aj，1，aj，2，…，aj，k｝为第j层的尺度系数，反映第j层的低频近似分量，表达序列的大致趋势；Dj＝ ｛dj，1，dj，2，…，dj，k｝为第j层的小波系数，反映第j层的高频细节分量，表达序列在细节上的差异。直观上，DWT把一维网络流量信号分解为两维信号。原始信号A0分解为A1和D1，低频部分进一步分解，即：A1再分解为A2和D2，…，如此进行可得到任意尺度 （或分辨率）上的近似分量和细节分量，力求构造一个频率上高度逼近L2（R）空间的正交小波基。而Mallat中的单支重构则是对小波分解的小波系数和尺度系数进行小波逆变换，形成与原始序列等长度的单支序列。

1.3 DWT的具体实施

本文以MATLAB为流量小波变换的辅助工具，作为母小波的函数必须具有很好的时、频局部特性，以更好地刻画信号的突变信息。因此这里选取Haar小波、Daubechies小波系 （DbN）、Coiflets小波系 （CoifN）和Symlets小波系 （SymN）等常见小波基进行测试，将原始流量与合成流量分别用相应的小波进行分解，并统计各尺度上小波系数的标准差，最终选择支集长度较小的、仿真流量性能与原始流量性能较为接近的Db4为实验用小波基函数。对流量数据的DWT一维多尺度分解、消噪与重构在MATLAB中的实现代码如下：

2 流量序列预测模型

2.1 FARIMA

网络流量的建模选用分形自回归求和滑动平均模型，简称 FARIMA （fractional auto－regressive integrated moving average）。在建模过程中使用了3个参数p、d和q，其中d可以体现所要估测流量的长相关性，而p、q则反映所含部分流量的短相关性，所以该方法生成的预测序列能保持与真实序列一致的长相关和短相关特征，具有较高的灵活性。FARIMA是ARIMA （p，d，q）模型的自然扩展，后者可表示为φ（B）（1－B）dXt＝ Θ（B）at，其中B 是滞后算子，1－B为差分算子，｛at｝为白噪声序列。FARIMA与ARIMA的唯一区别在于参数d允许使用非整数，此时d阶差分算子其 中 参 数参数d可由式H＝d＋0.5求得，H 为序列的Hurst参数，即可利用Hurst参数计算间接对d进行近似估计。

2.2 模型整体功能结构

这里将所设计的流量序列预测模型的整体功能进行算法描述，如图2所示。

（1）为了对网络自相似性进行估测，需要计算表征其程度大小的H值。这里求解采用的方法是R／S法，其应用对象是代表待测流量的序列f（t），由关系式d＝H－0.5获得对预测模型FARIMA （p，d，q）中差分参数d的有效估计。

（2）对于带有明显相似性和长相关特征的初始流量数据f（t），采用Db4DWT方法予以分解，规定其分解尺度为J，该过程结束后输出量分别为近似以及细节分量。前者以AJ表示，后者以D1，D2，…，DJ表示。

图2 基于DWT多尺度分析的协议优化模型

（3）将分解后的近似分量使用FARIMA模型进行预测得到a’j；同理，对 （2）中D1，D2，…，DJ予以相同处理后记所得结果为a’1，a’2，…，a’j。

（4）利用Mallat算法对 （3）中所得两类分量予以重构，具体公式如下：a′j－1＝

（5）经 （4）得到新的流量序列f′（t），为了明确新的网络自相似性程度亦即H’值，对f′（t）施以FARIMA模型预测初始流量。一般情况下参数p、q随现实状况而定，本文p赋值2，q赋值1。

（6）最后得到FARIMA （p，d，q）拟合流量，进一步以均方误差来定量评估预测效果，M为数据总量。对比分析利用计算机仿真所得结果与真实流量状况，总结本文估测结果在变化趋势等方面对真实状况的趋近程度。进一步分析当前时刻过后网络流量在各方面可能发生的变化，以辅助实施网络协议的拥塞控制策略。

3 网络协议优化策略及仿真实验

3.1 网络拥塞和流量控制机制分析

网络中经常出现拥塞甚至系统崩溃等情况，用以解决这一问题的方案基本都是在网络中建立拥塞控制机制，以最具代表性的TCP协议为例 （根据MCI的统计，网络中总字节数的95%和总报文数的90%均使用TCP传输），TCP采用慢启动、拥塞避免、快速重传、快速恢复、选择性应答 （SACK）等算法确保网络的传输性能。然而网络中不存在专门的连接通道供端系统查明网络状况，因此端系统采取控制网络传送数据等行动的根据唯有来源于ACK、RTO超时等信息。这就造成反映不及时进而可能导致反馈延迟和网络抖动等问题［11］。而作为网络状态最直接感受者的路由器，如果能在IP层参与拥塞控制，必然成为端系统的有力补充。路由器通过检测当前负载状况，可以在网络设备的缓冲溢出之前丢弃或标记报文，以降低排队延迟，并形成拥塞指示以辅助端系统进行流量控制［12］。

在流量估算和控制中，当前网络协议常选择的是EWMA法。该方法可以满足低通滤波的要求，相邻两个时刻的流量速率估算方式为。应注意，EWMA算法对于只存在短相关性的传统泊松过程是合理的，即作为短相关流量，其自相关函数呈指数衰减，距当前分组到达时间越近的速率值对于当前速率估算值的影响越大；当时间间隔Ts足够大时，R（t＋Ts）与R（t）的流量速率是不相关的。这与实际自相似网络流量中大量存在的长相关特征并不相符，显然并不适合在拥塞控制协议中用作网络流量控制的关键手段。

此外，我们通过实验统计了在不同自相似参数下分组丢失率随缓冲区容量的变化情况，如图3所示。可观察到在缓冲区容量相同时，长相关业务在H值越大时分组丢失率越高。这证实了自相似程度增加时，网络流量突发性增强，重传率、平均队列长度和响应时间均增大，网络性能下降。

图3 自相似性程度对不同缓冲区容量下的分组丢失率的影响

综合上述分析，本文尝试将基于DWT的流量预测模型的结果引入到路由器的主动队列管理算法 （AQM）中，利用自相似流量的统计规律和预测特征，以拥塞预警而非“被动响应”的方式，形成对网络协议中的拥塞控制机制的有效优化。

3.2 协议优化策略

在改进AQM算法时，这里选择基于优化流控思想OFC得到的REM算法作为改进依据，利用FARIMA模型计算Hurst值H’来表征相似性程度大小，根据实际状况适当改变拥塞控制机制中的参数标记概率，按以下步骤进行：

（1）利用下式求解REM算法中的参数Price：pl（t＋1）＝［pl（t）＋γ（al（bl（t）－b＊l）＋xl（t）－cl））］＋，可以看出该计算公式包含参数al以实现调节功能，此外路由器使用状况以及带宽占用情况也是需要考虑的因素。

（2）以标记概率代表拥塞控制机制的拥塞指示，队列1的计算公式为是常量。其中t代表一段时间。从而得到端到端报文标记概率为引入H’的调节作用，将标记概率计算公式调整为为权重参数，h0为阈值，通常取0.8～0.9之间。

3.3 算法复杂度分析

由于小波变换的计算效率很高，对含N个采样数据的信号进行Mallat离散小波变换的时间复杂度仅为0（N），对分解后的流量分量采用FARIMA过程进行线性预测时，FARIMA算法乘法操作次数为0（N2），因此对网络流量进行预测的时间复杂度为0（N2）；空间复杂度上，如果选择的小波长度为N，那么本算法中进行小波分解和重构所需存储空间大小是0（N），对分解后流量进行预测时，FARIMA过程需要存储p、d、q等中间变量，其中d的大小为N，p、q的大小为N2，因此总的空间复杂度为0（N2）。

3.4 实验仿真与结构分析

（1）实验方案：本文采用MATLAB软件和C＋＋语言编程实现该模型，以NS为仿真环境，以Pareto模型产生自相似输入流量，实验过程如图4所示。网络协议选取目前网络中应用最广的TCP版本：TCP New Reno，在尺度为J＝3上运行Mallat算法对网络流量进行多尺度db4小波分解和重构。

图4 仿真实验运行过程

（2）流量分析结论及流量预测模型效果检验：首先我们统计了原始流量与合成流量的自相似特性表征值H，经R／S估值，发现在原始流量的H为0.8319时，合成流量的H’值为0.8298，这表明DWT多尺度变换能近似表征出原始流量的LRD特性。此外，多个不同流量样本数据展现出如下特点；①网络流量在1秒级以上的尺度上，表现出明显的LRD特性；②网络流量在多种时间尺度上表现出非平稳特性。

图5是一段TCP流经过流量预测模型处理、重构叠加后的流量特征与实际流量的对比，测试显示模型具有较高的预测精度。

（3）优化后协议性能仿真结果

图5 流量模型的预测值与实际流量对照

1）在有干扰背景流震荡的情况下，模拟优化后协议的运行情况。如图6所示：Flow1为原始流量，Flow2是运行模型拟合、经协议优化后的流量。结果表明这种新的拥塞控制机制可以预测并抑制自相关流量在大尺度上的固有突发，能够在一定程度上有效保证网络性能的稳定性。

图6 仿真结果1

2）图7是协议间公平性实验，TCP1和TCP2是运行优化后协议的两个共享同一瓶颈链路的同等条件流量，60s时刻启动该链路上的一个UDP流。此实验同时测试TCP流之间的公平性以及TCP流与无拥塞控制机制的UDP流之间的公平性。结果表明，经优化后，协议间公平性特征良好，具有较好的可扩展性。

图7 仿真结果2

4 结束语

就网络流量而言，是否可对其进行预测有赖于自身性质。如果对自相似性网络进行流量预测，了解其长相关性非常重要，况且网络流量的尺度特性对于网络效率的提高和网络协议的设计均具有重大的影响，因此本文进行以DWT多尺度分析为基础的网络流量建模和预测，并在预测基础上改变传统的控制方式，于传统网络协议的基础上改进算法进而实现对自相似网络的流量预测，对提高资源利用率、进一步实施流量控制工程、网络性能更优都具有显著的研究意义。

［1］Leland WE，Gao L，Zhang X L.A network traffic analysis and forecast based on wavelet technology ［J］.Computer Applications and Software，1992，25 （8）：70－72.

［2］WANG Junsong，GAO Zhiwei.Network traffic modeling and forecasting based on RBF neural network ［J］.Computer Engineering and Application，2011，44 （13）：6－11 （in Chinese）.［王俊松，高志伟.基于RBF神经网络的网络流量建模及预测［J］.计算机工程与应用，2011，44 （13）：6－11.］

［3］Bai X Y，Ye X M，Jiang H.Network traffic predicting based on wavelet transform and autoregressive model ［J］.Computer Science，2013，34 （7）：47－49.

［4］Chen X T，Liu J X.Network traffic prediction based on wavelet transformation and FARIIMA ［J］.Journal on Communications，2011，32 （4）：153－157.

［5］YIN Bo，XIA Jingbo，FU Kai，et al.Based on IPSO chaos of support vector machine （SVM）network traffic prediction research ［J］.Computer Application Research，2012，29 （11）：4293－4295（in Chinese）. ［尹波，夏靖波，付凯，等.基于IPSO混沌支持向量机的网络流量预测研究 ［J］.计算机应用研究，2012，29 （11）4293－4295.］

［6］Yang X S，Deb S.Engineering optimization by cuckoo search［J］.International Journal of Mathematical Modeling and Numerical Optimization，2012，1 （4）：330－343.

［7］LI Dandan，ZHANG Runtong.Cognitive network in network traffic prediction model based on ant colony algorithm ［J］.Journal of Electronics，2011 （10）：100－103 （in Chinese）.［李丹丹，张闰彤.认知网络中基于蚁群算法的网络流量预测模型 ［J］.电子学报，2011 （10）：100－103.］

［8］BAI Xiangyu，YE Xinming，JIANG Hai.Based on wavelet transform and autoregressive model of network traffic prediction ［J］.Journal of Computer Science，2011，34 （7）：47－49 （in Chinese）.［白翔宇，叶新铭，蒋海.基于小波变换与自回归模型的网络流量预测 ［J］.计算机科学，2011，34 （7）：47－49.］

［9］Li Chunfu，Zheng Guangjun，Li Yanqi，et al.Study on control strategy of lockup process of torque converter ［J］.Automobile Technology，2013 （10）：15－17.

［10］MO Yuanbin，LIU Fuyong，ZHANG Yunan.With gauss mutation of artificial fireflies optimization algorithm ［J］.Computer Application Research，2013，30 （1）：121－124 （in Chinese）.［莫愿斌，刘付永，张宇楠.带高斯变异的人工萤火虫优化算法 ［J］.计算机应用研究，2013，30 （1）：121－124.］

［11］Yang S M，Guo W，Tang W.A collision resolution algorithm based on time－series forecasting for cognitive wireless networks ［J］.Journal on Communications，2011，32 （11）：51－58.

［12］WANG Fan，HE Xingshi，WANG Yan.The cuckoo search algorithm based on gauss perturbation ［J］.Journal of Computers，2011，25 （4）：566－569 （in Chinese）.［王凡，贺兴时，王燕.基于高斯扰动的布谷鸟搜索算法 ［J］.计算机学报，2011，25 （4）：566－569.］