一种随机离散模型及其应用于通信网络中的信息流测评算法

摘要

本发明公开了一种随机离散模型，包括在网络通信中数据发送端与数据接收端之间的R个路由器或无线节点，R为自然数；所有路由器或无线节点的缓存器拉直平铺，并依次连接成一条直线，形成通信网络数据传输的一维点阵模型。相应地，本发明还公开了应用上述随机离散模型来评估通信网络性能的算法，通过该算法，不仅简化了网络性能评估模型，还可以对通信网络性能实现定量评估，使得网络性能评估更加简单，更加精确，具有很大的应用价值和研究意义。

说明书

技术领域

本发明涉及一种通信网络性能的估算方法，具体地说，是涉及一种随机离 散模型及其应用于通信网络中的信息流测评算法。

背景技术

目前，对于网络性能评估，理论上都是采用克劳德·香农理论估计网络的 最大数据率。但是，由于网络拓扑结构的不规则和不均衡、网络传输协议的复 杂性、使用者的集体性行为、网络节点的快速增加、数据要求的不同以及网络 动态的高度非对称性等原因，克劳德·香农的这种估计并不能地很好反映网络 的实际性能。在实际应用中，采用数据包队列模型只能定性地估计通信网络的 性能和定性地估算平均时延。该方法虽然具有通用性，但是只能进行定性分析 和在时间领域内评估，难以满足当今社会对网络性能的定量评估要求。

在实际应用中，绝大多数情况下都是通过试测一段含有多个路由器(或无 线节点)的网络性能来评估整个网络的性能(每个路由器含有固定的缓存大小)， 因此，为定量评估整个网络的性能，研究在该情况下数据包的队列长度和队列 密度的定量测算便具有了很大的现实意义。

发明内容

本发明的目的在于提供一种随机离散模型及其应用于通信网络中的信息流 测评算法，通过定量测算数据包的队列长度和队列密度来定量评估整个网络的 性能，解决现有技术中难以解决的定量评估网络性能的问题。

为了实现上述目的，本发明采用的技术方案如下：

一种随机离散模型，包括在网络通信中数据发送端与数据接收端之间的R 个路由器或无线节点，R为自然数；所有路由器或无线节点的缓存器拉直平铺， 并依次连接成一条直线，形成通信网络数据传输的一维点阵模型。

相应地，本发明提供的基于离散随机模型的信息流测评算法，包括以下步 骤：

(1)将数据发送端与数据接收端之间的所有缓存器拉直平铺，按照上一个 缓存器尾部接下一个缓存器首部的方式，将所有缓存器依次连接成一维点阵模 型；

(2)根据缓存器数量和各个缓存器的大小确定所述一维点阵模型的缓存大 小L；

(3)数据包离开数据发送端之后，进入所述一维点阵模型的第一个缓存位 置，并在所述一维点阵模型的缓存中依次连续向前移动，直到数据包到达的缓 存位置当前被占据；

(4)数据包在移动过程中遇到当前缓存被占据时停止向前移动，直到该缓 存位置为空时继续向前移动，以此类推，直接所有数据包均到达数据接收端；

数据包的队列密度ρ_i为

${\rho }_i=\frac{\underset{j=0}{\overset{T}{\Sigma }}{v}_i}{T}(1\le i\le L)---\left(2.1\right)$

其中，i为缓存数，υ_i表示第i(1≤i≤L)个缓存的存储状态，υ_i＝1表示第i个缓 存被占据，υ_i＝0表示第i个缓存为空；j为数据包的流量，T为时间步数；

数据包的队列长度为

${\Gamma }_k=\underset{l=(k-1)*B+1}{\overset{k*B}{\Sigma }}{v}_l(k=\mathrm{1,2,3},...)---\left(2.2\right)$

其中，k为路由器或无线节点的序号，B为缓存器大小，l为第k个路由器或无线 节点中第l个缓存的位置。

进一步地，所述数据包在网络中向前平移服从先入先出原则。

再进一步地，所述缓存器为路由器缓存器和/或无线节点缓存器。

更进一步地，所述数据发送端与数据接收端之间的缓存流量为最后一个缓 存器的密度与数据包到达数据接收端的概率之积。

本发明以现有通信网络中数据传输方式为原型，对其进行巧妙地变形，从 而将原本复杂的网络性能评估模型变成简单易算的一维点阵模型，从而为网络 性能的定量评估奠定了切实可行的基础。

与现有技术相比，本发明具有以下有益效果：

(1)本发明对现有的网络性能评估模型进行巧妙地简化，将原本单个独立 的缓存器在评估模型上形成了一个整体，从而使网络性能评估变得简单易行， 使网络性能的定量评估成为了可能。

(2)本发明通过对一维点阵模型进行数据包的队列密度和队列长度进行定 量估算，从而体现整个网络性能的定量评估，与现有的定性评估方式相比，其 评估更利于计算机实现，使得评估过程更加方便，评估结果更加精确。

(3)本发明解决了现有技术中长期存在但一直无法解决的网络性能定量评 估问题，为通信网络的监控与改进提供了一条新的发展方向，具有十分明显的 技术进步，行业意义十分重大。

附图说明

图1为现有技术中网络传输数据包的示意图。

图2为本发明将图1简化为一维点阵模型的示意图。

图3为数据包在相邻路由器或无线节点的缓存器之间的移动示意图。

图4为数据包在同一个缓存器内部的移动示意图。

具体实施方式

下面结合附图和实施例对本发明作进一步说明，本发明的实施方式包括但 不限于下列实施例。

实施例

本发明主要用于网络信息的数据传输，通过本发明，达到定量评估网络性 能好坏的目的。

众所周知，在现有技术中，网络信息的传输过程如图1所示：一个网络信 息从数据发送端传输到数据接收端，通常需要一个发送端路由器和一个接收端 路由器，而在发送端路由器和接收端路由器之间，视情况而定，可能还需要其 他路由器进行信息的转发；信息传输时，网络信息首先通过分片技术被分为多 个较小的数据包，然后通过一个或多个路由器或无线节点到达目的终端。当这 些数据包到达目的终端时，在网络协议的控制下，由数据接收端将所有数据包 按照正确的顺序组装好，重现原始的网络信息。

在图1中，数据发送端发送网络信息时，首先通过分片技术将网络信息分 成多个较小的数据包，图1中黑点为分片后的数据包，一个网络信息分割成多 个数据包后，所有数据包在网络中传输时排成一个数据包队列；方格代表路由 器或无线节点的缓存器，每个路由器或无线节点的缓存器大小假设为5，即如图 1所示的一个路由器对应的5个方格，p_i(i＝1,2,3,4,5)代表了相应的网络可靠性 和可利用带宽。为了简化，我们假设p_i＝1(i＝2,3,4),即假设路由器或无线节点间 的连接和带宽完好无损；而p_i(i＝1,5)来表征数据包离开数据发送端和进入数据 接收端的概率。所述数据接收端负责接收数据包并还原网络信息。

为了定量测算数据包的队列长度和队列密度，以定量评估整个网络的性能， 将图1所示的网络信息传输过程转化为图2所示的一维点阵模型，具体方式是 将数据发送端和数据接收端之间的路由器或无线节点间的缓存器按照先后顺序 拉直连成一条直线，如此，假设整个一维点阵的缓存大小为L,路由器或无线节 点的数目为R，每个路由器或无线节点的缓存器大小为B，则

L＝R*B     (1)

为了简化说明，引入一个占有变量υ_i来表征第i(1≤i≤L)个缓存器的存储状 态：υ_i＝1表示第i个缓存被占据，υ_i＝0表示第i个缓存为空。

所有缓存器中数据包的传输采用平移方式，其传输过程包括以下两方面：

(1)数据包在相邻两个路由器或无线节点之间进行传输

如图3所示，如果υ_i＝1(i＝n*B,n＝1,2,…),而且下一个路由器或无线节点的缓 存器(从i+1到i+B)的依次连续缓存存在空，则在第i个缓存的数据包可以运动 到第i+M(1≤M≤B)缓存。反之，第i个缓存的数据包则停止平移。所有数据包向 前平移时服从先入先出(FIFO)原则，即当一个数据包作为某一个数据包队列 的头部从一个路由器或无线节点移动到下一个路由器或无线节点后，其仍然是 该数据包队列的头部，或者成为前一个数据包队列的尾部。

(2)数据包在同一个路由器或无线节点的缓存器内部传输

如图4所示，如果υ_i＝1(i≠n*B,n＝1,2,…),而且缓存i+1为空，则缓存i的数据 包可以平移到缓存i+1，否则，不移动。数据包在每个单位时间只能向前移动一 步。

为便于描述数据发送端与数据接收端之间的网络性能，先作以下定义：

系统缓存数据流量J：考查网络段内数据包的流量；

数据包总数N：考查网络段内的数据包总数；

缓存器总数L：考查网络段内的缓存器总数，计算方式见公式(3)；

系统密度ρ：考查网络段内数据包总数与缓存器总数的比值；

数据包的队列密度ρ_i：每个缓存器中数据包的实际密度；

数据包的队列长度Γ_k：每一个路由器或无线节点中数据包的队列长度，k为 路由器或无线节点序号；

时间步数T：考查总的单位时间步数。

根据以上图2的模型，并结合以上定义，可以得知数据包总数为：

$N=\underset{i=0}{\overset{L}{\Sigma }}{v}_i---\left(3\right)$

系统密度为：

$\rho =\frac{N}{L}---\left(4\right)$

当网络达到平衡状态时，尽管系统的密度已知(见公式4)，但是每个缓存 的数据包密度可能是不同的。每个缓存的数据包密度和数据包在每个缓存的延 时相对应的。数据包的队列密度越大，说明网络延时越大，网络性能越差。

数据包的队列密度为：

${\rho }_i=\frac{\underset{j=0}{\overset{T}{\Sigma }}{v}_i}{T}(1\le i\le L)---\left(2.1\right)$

在一个路由器(或无线节点)内连续缓存的数据包密度与队列长度相对应； 数据包的队列长度越大，说明路由器或无线节点内数据包越多，相应地说明网 络中数据总流量越大，网络性能越差。无线节点或路由器中数据包的队列长度 为：

${\Gamma }_k=\underset{l=(k-1)*B+1}{\overset{k*B}{\Sigma }}{v}_l(k=\mathrm{1,2,3},...)---\left(2.2\right)$

系统缓存流量即可考虑为最后一个缓存器的密度与数据包离开缓存器到达 接收主机的概率之积，即：

J＝ρ_N*P₅     (5)

通过上述实施例，可以明确地实现数据包的队列密度和队列长度的定量估 算，从而轻松地对网络性能进行评估，与现有的定性评估相比，其估算过程更 加简单，估算结果更加精确。

上述实施例仅为本发明的优选实施例，并非对本发明保护范围的限制，但 凡采用本发明的设计原理，以及在此基础上进行非创造性劳动而作出的变化， 均应属于本发明的保护范围之内。