自相似模型下的交换式网络仿真

卢 颖，钟联炯，王智广

（1.西安工业大学 计算机科学与工程学院，陕西 西安 710032；2.中国石油大学 计算机系，北京 102200）

网络业务量特性是网络性能分析和网络规划设计的基础，而传统模式下的交换式网络仿真，报文的到达模型均是假设整个排队系统中顾客流的到达服从泊松过程，而泊松过程具有Markovian特性，即一种短相关过程[1]。随着网络研究的深入，发现实际上网络中的业务流在几毫秒至几小时甚至几天的时间段上，均表现出很强的突发特性，这说明报文的到达具有长相关属性。因此，泊松到达的仿真模型已不符合网络的实际情况。笔者在考虑报文的到达服从长相关过程的情况下，利用能描述长相关特性的自相似模型，借助计算机仿真法对交换式网络进行了仿真，并对仿真结果作出了分析及评价。

1 自相似的数学定义

计分布。其离散时间数学定义为：离散时间随机过程X（t）定义为{Xt，t=0，1，2，…}是一广义平稳随机过程，均值 μ，方差σ2，且自相关函数为 r（k），k≥0。假设 X 的自相关函数形式如下：当 k→∞ 时，r（k）～k-βL（t）。 参数 β（0＜β＜1），且 L 是缓慢变化至无穷的，即对所有 x ＞0，L（tx）/L（t）=1。 定义 X 上的 m重聚集时间序列 x（m）={，k=0，1，2，…}，它可以表示为：=（Xkm-m+1+…+Xkm）/m，过程 X 称为精确二阶自相似序列[2]，且具有自相似系数H=1-β/2。参数H为自相似参数，它是自相似程度的一个重要度量，是描述自相似特性的唯一参数。H的取值范围是（0.5，1），H=0.5表示不具备自相似性（如泊松分布），H值越接近1，过程的自相似程度就越高[3]。

2 自相似业务模型的建立

笔者所研究的网络业务流在数学上等效为一离散时间序列，下面给出自相似过程的离散时间定义。自相似性从统计意义上可以理解为局部适当放大后，与整体具有相同的统

网络中自相似流量序列的产生可采用分数布朗运动模型、ARIMA模型、ON/OFF模型和小波变换模型[4]。其中分数布朗运动模型易于合成仿真数据，便于计算机仿真研究。因此，实验采用了能够近似生成分数布朗运动的RMD（Random Midpoint Displacement）算法。

RMD算法的设计，是一个不断调整，不断修正的过程，其关键在于偏移量的选取。偏移量是一个与原序列有关的函数。原序列的参数主要有自相似参数H和自相关函数r（k）。其中自相关函数 r（k）=1/2[（k+1）2H-2k2H+（k-1）2H]，k=1，2，3，...，给定一个序列，其自相似参数H为定值，但其自相关函数是随k值不断变化的。由于网络业务流量的自相似性主要是由H参数为描述的，因此决定使用原序列的H参数来建立偏移量值函数D。生成序列在某点的值等于前后两点的算术均值再加上在此点的偏移量函数值，即X[n]=（X[n-1]+X[n+1]）/2+D（n）。因此可以通过迭代法产生自相似序列。

由于偏移量将会产生一个0均值的高斯分布序列，那么首先需要产生一个正态分布随机数组G（n），其均值为0方差为1。令H为原序列的自相似参数，为生成序列的自相似参数，ΔH=（Hˆ-H）/H为生成序列与原序列的自相似参数偏离的程度。ΔH的值越小，说明模拟的序列的特性越接近原序列的特性。

选取偏移量函数为 D（i）=G（n）θi，其中为迭代次数。由于正态分布随机数组的方差为1，即δ=1，那么则迭代i次可生成背景序，算法流程如图1所示。

图1 RMD算法流程图Fig.1 Flow chart of RMD algorithm

RMD生成法理论时间复杂度为O（n），且生成自相似随机序列的速度较快，能够满足实际仿真中快速产生较长自相似序列的需求。

3 交换策略及建模仿真

3.1 交换策略

本文所研究的交换式网络，其核心设备为输入缓存式交换机，原理是利用输入缓存来防止阻塞，它使得所有端口的访问总和可以超过交换体本身的交换能力。缓存位于交换机的输入部分，报文进入交换机后首先在这里暂存，然后交换机中的一块特定集成电路（ASIC）对到达交换结构的访问进行仲裁并将报文交换到输出端口[5]。

对交换策略的分析描述如下：假设该交换机的交换结构为N×N，每个输入端口对应有N个虚输入队列（分别对应N个输出端口）。报文按自相似序列到达后会根据自己的目标端口号在不同虚输入队列中排队，当它排至队首，而输出端空闲则进行交换并输出。在此过程中，若出现多个虚输入队列的排头同时竞争同一输出端口的情形，则还需要在相应输出端的虚队列中排队等候输出，如图2所示。

图2 输出虚队列示意图Fig.2 Schematic diagrum of the output virtual queue

3.2 仿真建模

仿真网络中的交换机节点采用N×N交换结构（N为输入输出端口数）。报文的到达时间服从自相似特性，包长大小随机并服从负指数分布。相对各端口，报文的到达是均匀的。每个输入端口对应N个FIFO虚输入队列，每个输出端口设一个虚输出队列，容量为N。

3.3 仿真分析

仿真系统中时间以毫秒为单位，业务流分别在自相似参数选用经验值H=0.85和H=0.5（H=0.5为泊松业务模型[6]）下进行。仿真过程如下：在给定系统模型的基础上，报文按自相似序列到达端口，然后进行相应的加工处理，如加入队列、排队、交换输出等，直到规定数量的报文全部发送完毕则仿真结束。

仿真结果统计的是网络利用率、平均队长及平均延迟特性。其中报文平均时延的统计是通过报文到达时在报文对象中记录其到达时刻，离去时用当前时刻减去到达时刻获得。平均队长计算公式为f（t）为 t时刻队长，T为系统仿真时间）。仿真每次运行时间为1 000 s，在经过多次变换仿真时间尺度，增强网络负载的情况下，得到统计数据如表1所示。

表1 仿真结果数据Tab.1 Result data of simulation

对表1中仿真结果进行分析可得，在相同负载条件下，H值越大，网络的平均延迟、吞吐量就越大。自相似业务对于网络的性能影响非常显著。而在H=0.5的泊松业务模型下的队长、网络延时及吞吐率较自相似的要小些。泊松和自相似两个不同业务流模型下的网络平均延迟对比如图3所示。

图3 泊松和自相似流量模型下的网络延迟比较Fig.3 Time-delay comparison under Possion and self-similar model

可以看出，不同流量模型下的网络性能差别很大。原因是，流量的自相似性具有一种长相关和慢衰减方差特性[7]，因此在突发性和长相关性的共同作用下，网络性能会急剧下降。在报文突发到达时期，信道冲突概率增大，节点不能及时竞争到有限的信道资源，从而造成高层数据包队列积压过多的包使缓存迅速充满，导致数据丢失。同时队列中等待服务的时间增加，导致分组端到端传输平均延时加长。而传统泊松流量模型的短相关性和较弱的长相关性则对缓冲区的需求不高。因此，要提高系统性能就需要根据网络业务流的特点，确定所需的各种资源，例如可以增加更多的缓存，但需要考虑到，增大缓存虽然能降低丢包率，却会导致端到端排队时延的加长，这在对响应时间要求高的系统中并不适用。因此，在做网络规划设计时，需要平衡排队延迟、丢包率、吞吐率等各项网络性能指标之间的关系。此外，还可以考虑在性能要求较高的网络中适量增加带宽资源，来提高吞吐量，减小延迟及包丢失率。

4 结束语

对交换式网络进行仿真测量是检验网络性能优劣，协议设计及网络配置是否合理的重要步骤。其中，业务流量模型是网络设计、管理和控制的基础。因此，在对网络仿真和性能检验过程中，必须首先对流量进行正确建模才能较大程度地反映实际流量的特性，才不会对网络性能造成过高或过低的估计。

[1]Paxson V，Floyd S.Wide area traffic:the failure of Poisson modeling[J].IEEE/ACM Trans.on Networking， 1995，3（3）:226-244.

[2]Leland W E.On the self-similar nature of ethernet traffic（extended version） [J].IEEE/ACM Trans.on Networking，1994，2（1）:1-15.

[3]肖志新，杨岳湘.网络流量的自相似特性[J].吉首大学学报，2004，25（2）:75-77.XIAO Zhi-xin，YANG Yue-xiang.Self-similar characteristic of network traffic[J].Journal of Jishou University，2004，25（2）:75-77.

[4]张鹏.自相似业务量的多重分形分析[J].电子学报，2000，28（1）:96-98.ZHANG Peng.Multifractal analysis of self-similar traffic[J].Acta Electronica Sinica，2000，28（1）:96-98.

[5]卢颖，钟联炯.以太网交换机运行机制及其仿真研究[J].西安工业学院学报，2004，24（1）:53-56.LU Ying，ZHONG Lian-jiong.Operation mechanism and computer simulation of the ethernet switch[J].Journal of Xi’an Institute of Technology， 2004，24（1）:53-56.

[6]Leland W E，Taqqu M S，Willinger W，et al.On the selfsimilar nature of ethernet Traffic （extended version） [J].IEEE/ACM Trans.on Networking， 1994，2（1）:1?15.

[7]Crovella M，Bestavros A.Self-similarity in world wide Web Traffic: evidence and possible causes[J]. IEEE/ACM Transactions on Networking， 1997，5（6）:835-846.