《武汉工程大学学报》  2009年09期 66-68   出版日期：2009-09-28   ISSN:1674-2869   CN:42-1779/TQ

---

一种基于总线的传输流量估算方法


0引言传输流量分析和建模对网络性能评价具有重要的意义,完全符合传输流量复杂统计特性的模型,能够帮助对网络流量进行精确的分析和仿真,非常有助于网络的设计和控制. 网络传输预测分析及建模一直是分析网络性能的重要研究课题,流量预测结果为网络管理中带宽分配、流量控制、选路控制、接纳控制和差错控制等提供主要参考依据.网络流量具有一定的动态性、实时性、相关性、随机性和含噪声性［1］ .流量控制与某个发送方和接收方之间的点到点的通信量控制有关,即解决网络中出现快发慢收的问题,还受到通信线路容量的限制［2］.公共总线在通信和多处理器系统中是一种重要的一维互联网［3］.它是一种高效动态互联模式，可使系统的任意两个部件临时互联.它能够动态连接系统中的任意两个部件，而且成本很低.公共总线在每个可能的发送者与每个可能的接收者之间确保“直接连通”，其成本是线性结构的.在一条公共总线上插着许多部件（子系统，比如处理器、缓存、I/O集成设备），而增加部件的数量并不增加共享总线的代价.但是多个应用子系统共享总线会因冲突而受到强烈的限制［4］.显然，随着连接在公共总线上部件的数量增加，传输冲突的概率也相应按比例增加，直到耗尽公共总线的全部带宽.一个重要的设计问题是去估算公共总线的平均带宽，以便在系统设计早期减少潜伏问题［5］.为此，本文提出了一个估算模型和一种有效的概率预测方法.这个模型含有大量共享着公共总线的相同部件.一种传输流量的概率模型能使设计者迅速预测公共总线的带宽.一束总线是一种通信信道，一个数据包被定义成一种在公共总线上传送的基本数据帧.本文研究的问题是：在从部件发出的数据包流服从泊松过程的条件下，确定公共总线数据流量的分布，从而估算公共总线的平均带宽.论文的组织如下：第二部分定义了一个总线模型；第三部分确定了公共总线带宽估算的结果；第四部分展示了一些用这个模型演算的实验结果；第五部分是论文的结论.1总线模型一个系统模型是部件之集合，一条总线是建立必要连结的线路之集合，所有的部件连在公共总线上，以便提供独占的交互方法.一条公共总线是数据包流能通过的线路.假定每一个包有同样的大小和速度，并且部件在不同的时间占用带宽进行传输；假设一种调度机制可以使传送没有冲突，即是没有两个终端在同一个时间传送，这种调度叫预定存取或仲裁存取通信；假设每个部件以一个不变的比特率传送，每个部件能够按照参数为α的泊松过程发送数据包.一个指定节点的数据流量是通过这个节点的包的数量.图1一种曲型的公共总线结构
Fig.1A typical bus structure不失一般性，假定包总是从左边传到右边，同时从一个给定的部件产生的源数据包的数量符合参数为α的泊松过程，这里α是每个部件发出源数据包的平均数.图2一个部件的数据流
Fig.2Data flows for a module第9期邹金安：一种基于总线的传输流量估算方法
武汉工程大学学报第31卷
2流量估算设X(L)为终止于所研究的部件的数据包数量，X(R) 为产生于这个部件本身的数据包数量，X(LR)是经由公共总线穿过这个部件的数据包数量，假定X(R)符合参数为 的泊松过程（α是每个部件产生数据包的平均数），一个数据包的行程是源部件与目的部件之间的部件数量.假定Poisson(λ)表示参数为λ的泊松过程，数据包可以产生自任意部件，然后移动到右边.定理1如果X(R)符合Poisson(α)，那么对平均行程为δ的任意行程分布，X(L) and X(LR)是独立的泊松分布即 X(L) =Poisson(α) ，X(LR) = Poisson(α(δ-1))证明：假定包有一长度为l概率为ql的行程，那么∑∞i=1qi=1.考虑部件x，一个从部件j发出的数据包有下列三种情况: (1)它以概率qj 行程j终止于部件x，形成Xj(L)(2)它以概率∑∞i=j+1qi穿过部件x（行程大于j），形成X j(LR)(3)它以概率∑i-1i=1qi终止于部件x的左边某部件（行程小于j）图3一个源自部件j的数据包的三种可能目的地
Fig.3Three possible destinations for a
packet originating from module j计算下面的联合概率
P(Xj(L)=n1^Xj(LR)=n2)=
∑∞r=n1+n2e-α·αrr!·（（rn1)·((r-n1n2)·
(∑∞i=j+1)n2)·((r-n1-n2r-n1-n2）·(∑j-1i=1qi)r-n1-n2)=
∑∞r=0e-α·αn1+n2+r·qn1jn1！·n2！.r!·
∑∞i=j+1n2·∑j-1i=1qir=
(α·qi)n1n1！·(α·∑∞i=j+1qi)n2n2！·e-α·
∑∞r=0αrr!·1-∑∞i=jqir=
e-α·qj·（α·qj)n1n1!·e-α·∑∞i=j+1qi·a·∑∞i=j+1qin2！n2=
Poisson(α·qj)·Poissonα·∑∞i=j+1qj=
P(xj(L)=n1)·(P(xj(LR)=n2))(1)这意味着经由部件x的左边部件j发出，终止于部件x的数据包数量Xj (L)独立于穿过部件x的数据包数量Xj (LR).而且，Xj (L) 和Xj (LR)都独立地分别符合参数为α·qj 和α·∑∞i=j+1qi的泊松过程.假定数据包在不同的部件里独立地产生.假定X(L)是终止于一个给定的部件的数据包总数，那么显然，X(L)=∑∞j=1Xj(L).因为每一个符合泊松过程的随机变量之和的分布，同样是参数为单独参数之和的泊松过程［6］.所以，X(L)符合Poisson(α)，因为∑∞j=1=α·qj=α.假定X (LR)是通过这个部件的数据包总数，同样地，X( LR)=∑∞j=1Xj(LR)并且X(LR)符合：
Poisson∑∞j=1α∑∞i=j+1=
Poissonα∑∞j=1∑∞i=j+1qi+∑∞j=1qi-∑∞j=1qi=
Poissonα∑∞j=1jqj-1=
Poisson(α(δ-1))（δ=∑∞j=1jqi）(2)这就得到期望的结果.基于以上结果，通过下面的定理给出一个重要的结果.定理2Y(L)流是以中间值β=αδ 为参数泊松分布.证明：这可以直接从Y(L)=X(L)+X(LR)观察到，因为Y(L)符合泊松过程，所以能通过计算Y(L)的以中间值β为参数的Poisson来估算公共总线的平均带宽.3实验及结果分析为了测试方法的有效性，对这个模型进行了一些实验验证.验证是通过模拟如模型假定的数据包和部件的系统来执行模型的演算过程，并且和公式预测的估算结果比较.模拟程序的输入是m维，参数为α（泊松分布）和ε（几何分布），用一个几何分布作为行程分布.程序模拟了从部件产生的N个包的线路，并且有一个几何分布的行程.估算是通过计算公共总线平均带宽来完成的.实验在一台128 m内存的SPARC station 20工作站上完成.表1给出了模拟的一些结果，其中ε=0.3.从表1中可以看出，理论估算的带宽与模拟实验测到的带宽是相近的.表1模拟结果对比表
Table 1Simulation Results
数据包
数量Mα模拟估算
(平均带宽)理论估算
(平均带宽)1345411.2713.672768513.9112.56342366.0915.085646418.4719.625928619.3420.876732519.9721.678317621.2823.384结语以上为估算一条总线的带宽提出了一种随机模型.模型是基于统计分布的，并且估算的是公共总线的平均带宽.实验证明了这种方法的有效性.更进一步的研究方向是：从实际的设计过程结合更多的知识研究估算模型，并开发一种预先、在线或滞后的估算模型，考虑分等级的公共总线组织，以构建一个可扩展的共享系统.