现在位置: >

网络流量行为分析的一维元胞自动机模型

元胞自动机

微电子学与计算机2007年第24卷第10期

点处理后又转发到下个节点。以此类推,这样,源端

和目的端之间的分组传输可以看作一个一维过程。

假设所有节点的输入过程都也是相互独立的,从而

就可将网络系统中流量的传输抽象为一维元胞自

动机模型,并且用该模型的演化过程来描述流量的

传输行为。

将M个网络节点随机的分布在具有L(M≤L)

个格点的一维直线上。如图1所示,格点用长矩形

来表示,一个节点占据一个格点,长矩形又划分成

一定数量的小方格,小方格数代表该节点缓存区的

存储单元。小方格有分实方格和空方格两类,其中

实方格代表有分组占据该存储单元,空方格表示该

单元还没有被分组占据,这样,缓存区中分组的队

列长度可用实方格的数量来表示。

2.2模型的演化规则

用J

i节点i的最大缓存空间,V

(t)表示第i节

点在t时刻的吞吐来量即成功发送的分组数。如果节点i的最大吞吐量为V

i_max

,应该有Vi_max≤Ji(t)。用Gi(t)表示在t时刻节点i的缓存器中的用分组队列长度(长矩形的实方格数),在t时刻节点i向节点i+1发送的吞吐量应该满足条件应该Vi(t)≤Ji+1-Gi+1(t),即发送分组的个数不能超过第i+1节点所能接纳的分组个数,否则的话就会有出现丢包现象。

元胞自动机模型的演化规则定义如下:

(1)若Vi(t)≤Ji+1-Gi+1(t)

①当Gi(t)≤Vi(t)时

Vi(t+1)=min{Vi(t)+1,Vi_max}。该规则模拟了所有节点都期望能以最高的效率来发送分组。

②当Gi(t)≥Vi(t)时

Vi(t+1)=

min{Vi(t)-1,Vi_max},以概率p

min{Vi(t),Vi_max},以概率1-

#

。该规

则模拟了节点根据流量控制策略来减少吞吐量的随机行为。参数p称为减速概率,在仿真时可通过随机数生成器来实现以概率p来更新节点的吞吐量。

(2)若Vi(t)>Ji+1-Gi+1(t),则Vi(t+1)=0。

(3)队列长度的更新规则用下列方程来表示:

Gi+1(t+1)=min{Gi(t)+Vi-1(t+1)-Vi(t+1),Ji};

i=2,…,M。

该规则模拟了根据前面(1)、(2)的规定,节点通过接纳控制等方法来对负载的更新。

在某一个时刻t,节点i是否发生拥塞可以用V

(t)是否等于零来表示。所有节点的平均吞吐量V=1

i=1

$Vi(t)可以用来描述整个系统的拥塞程度,在t时刻系统的平均队列长度为G=

i=1

$Gi(t);令ρ=

%&γ,其中,J=1

i=1

’Ji为所有节点的最大缓存空间的平均值,由于

J表示被数据分组占领的实方格在系统的整个缓存空间中所占的比例,取值在0和1之间,所以ρ实际上刻画了网络系统中流量负载的大小程度,把它称为归一化的网络负载。

在t时刻网络节点的减速概率p应该随网络负载ρ增大而增大,考虑到幂函数变化相对比较缓慢,为了使系统能在一个比较大的可选范围内来调整减速概率p,从而具有更好的适应性,以便更好地模拟现实网络流量的随机行为,为此设p和ρ的满足幂函数关系:p=ργ,其中0≤γ≤1。

3模型数值模拟结果及其讨论

下面将通过对模型的仿真来研究网络流量的典型现象与行为特征。在模拟过程中,上述流量元胞自动机模型采用周期性边界条件。对于一维空间,周期性的边界条件意味着元胞的结构表现为和一个首尾相接的圆周拓扑同胚,因而,当i=M时,第i+1个节点则表示第1个节点。

选取模拟参数值:G

(t=0)=32,γ=0.8,M=50;所

有节点的最大缓存空间相等,都取J

(t)=200,最大

吞吐量都统一取V

i_max

=160。在进行数值模拟时,去掉1到3000时步的所得的数据,以便消除暂态过程中某些随机因素的影响,等到系统进入稳态以后,按每100个时间步进行统计,即将经过100时间步的吞吐量进行平均,这样就得到每一次运行的平均吞吐量。样本容量为20,即每一个点是20次运行的平均值,如图2所示。

图2中颜色越深的区域,表示在该区域内所对应节点的拥塞情况越严重。颜色深的部分表示出现了网络拥塞的队列长度较大,等待转发的数据分组聚集,称为拥塞相。随着节点吞吐量增大,队列长度变小,节点逐渐恢复自由转发分组,图像颜色也随之变浅。当系统进入运动相时,可以看到,

网络流量行为分析的一维元胞自动机模型

黑色区域100

相关文档
相关主题
返回顶部
热门文档