基于排队论模型的网络拥塞率研究

+ 但 虽然当 =0时可以容易求出瞬时拥塞率的解析表达式， 是 随着 的增 大， 瞬 时拥塞率 的解析表达 式将很难得 到， 不过 我 们可以利用 微分方程组 的数值解法 求得其数 值解。下 面给 出 利用四阶龙 格－库塔法 求解微分方 程组 (2) 的 算法 [8]： 步骤 1 步骤 2 +
3
=
1
0
=lim
0
=lim
1
+
=
－ 4173 －
表 1 路由器缓存和 CPU 处理速度对拥塞率的影响
(%)
式， 利用所得拥塞率， 可以准确刻画 一些传统拥塞控制方法的 绩效 ， 从而使这 些拥塞控 制方法更为 精确。 在 此基础上， 通过 数值结果， 指出路由器缓存的 适当增加可以降低拥塞率， 但过 渡增 加反而会 增加拥塞率 ； 增加 路由器的 CPU 处理速度 可以 降低 拥塞率。
发送 方发 度 对拥塞率 的影响。给定分 组到达率 =1 分组 / 秒， 出分 组后平均 1/ =5 秒 未收到确认 将再次发 送副本。 表 1 给出 了当 路由器缓 存分别为 1, …, 20 分组及 CPU 处 理速度分 别为 2.5, 2.7, 2.9, 3.1, 3.3, 3.5 分组 / 秒时的拥塞 率 。 由表 1 可以看出， 最 初增加路由器缓存可以减少 拥塞， 但 随着 缓存的继 续增加， 反而会加 剧拥塞。比 如当 CPU 处 理速 度为 2.5 分 组 / 秒时， 缓存为 1 时的 拥塞率为 12.1%， 随着 缓存 的逐 渐增加到 7， 拥塞 率降低到 1.7%， 随着缓 存的继续增 加， 拥 塞率 又开始 逐渐 上升 ，当缓 存增 加到 20 时 ，拥塞 率变 为 当缓存过大 时， 会使等 待队 40.9%。造成 这种结果 的原因是： 长过 长， 当一 个分组到达 队列前面时 ， 它很可 能已经过时 了， 副本 已经被重 发了。 另外， 从 表 1 中可以明 显看出， CPU 处理速度 u 的增 加可 以降 低拥塞率 。当路由器 缓存为 20 时 ，CPU 处理速度 从 2.5 分组 / 秒增加到 2.5 分 组 / 秒使得拥 塞率从 40.9% 降低到 0.3%。
[2-3]
统， 它具有以下 特性： (1) 分组流从若 干个输入线路达 到， 为一到达率为 的 Poisson 流； (2) 路由器对每 个分组的 处理时间相 互独立， 并有相 同的 负指 数分布， 平 均处理时 间为 1/ ； (3) 路由器缓存 为 ， 若某一分组 到达时， 等待的分 组队长 已达 到 ， 则该 分组丢失； (4) 分组到达 时 间后发送 方仍然未收 到确认， 则认 为该 分组 已经丢失， 其副本将 被重发， 其中每个分 组的等待时间 服从 独立同分 布的负指数 分布， 均值 为 1/ ； (5) 到达过 程和处理过 程相互独 立。 记 为 时刻 系统队长 ( 包括正 在处理的 分组和等 待分 =
－ 4172 －
质 [7]， 可得其 转移强度矩 阵为
第 二 种 方 法 是 通 过 队 长 的 稳 态 分 布 得 到 ， =lim
=
=
｛
｛
0 +1 0
+ +
+ + +2 +2 + + +
｝
+1 +1
lim
+1
=
+1
。由马氏过 程的性质可 知， 队长的 稳态分布 可以
+1 =0
通过 求解下面 的线性方程 组得到 =0, 式中 ： =
=
1
+
｛
+ +
1 2
1
+
2
=0
2
+ +2
0
+ +2 3 =0
+
3
=0
+ 1+ 2+ 3=1
求解可得
2
= 3=1
+ +2
1
+
1
1
0
+
… 依此类推， 归纳可得系统 缓存为 ≥2 时的稳态拥塞 率为 (4) + + + 1 1 1 1 2+ 利用拥塞 率公式 (4)， 我们可以 准确刻画一 些常用拥 塞控 =
2.3
路 由器缓 存和 CPU 处理 速度 对拥 塞率的 影响
本小节将 通过数值结 果观察路 由器缓存 和 CPU 处 理速
当 =0 时 ， 采用四阶 龙格－库塔 法理论误差 为
， 例如
步 长取 0.01 时， 其理论 误差不超过 0.014=0.000 000 01。随 着 的 增加， 理论 误差会有所 增加， 但总 的来说还是 相当精确地 。
Study of network congestion rate based on queuing theory model
XIE Zheng-long1, LI Xiang-jun2,3
(1. Department of Computer Science, Xianyang Normal College, Xianyang 712000, China; 2. College of Electrical-Mechanic Engineering, Xidian University, Xi'an 710071, China; 3. Department of Computer Science, Xi'an University of Arts and Science, Xi'an 710065, China )
Abstract：The problem existing in congestion control is analyzed. The network congestion rate is researched based on queuing theory model, a basic model is proposed by studying the problem of network congestion from router, an algorithm for solving the instantaneous congestion rate is presented and the analytical formula of stable congestion rate is obtained. The numerical result shows that we can properly decrease the congestion rate by increasing cache memory, however, overage cache memory may increase the congestion rate. Furthermore, by increasing the speed of CPU of the router can also decrease the congestion rate. Key words：networks; congestion; congestion control; congestion rate; queuing theory
+1
初始化： 给出步长 及终止时刻 ； =0， 0 = 1, ,0 ，
1
=1
=
， 2= +
+
2
1
， 3=
+
2
2
， 4=
， + =
步骤 3 步 骤 2。
+2 2 +2 3 + 4 ； 6 1 则运算 结束， 输出 结果； 否则 返回 = + 。若 ≥ ，
5
制方 法的绩效 。 下面 我们介绍通 过控制路由 器缓存和 CPU 处 理速 度来进行 拥塞控制。
2.2
系 统的稳 态拥 塞率
对于排队系统， 人们更关心的是稳态性指标， 即经过足够
长 的运行时间 后系统的工 作状态渐趋 稳定，从 而各项特 性指 标 与时间 无关 。而一般 提到的拥塞 率， 通常也 指的是稳 态拥 塞 率， 其定义 如下 =lim 同时， 记 =lim 为稳 态队长分 布。
稳态拥塞 率的求解 通常有两种 方法： 第一 种是根据 其定 义， 先求出瞬时拥塞率， 然后对其取极限， 例如 =0时的稳态拥 塞 率为 + + 由于求解瞬时拥塞率本身就很繁琐， 所以该方法并不常用。
(2) ， 求解可得
｛
0
0
+ +
1 2
1
+
2
=0
+
0
=0
+ 1+ 2=1 + + +
=
1
= 2=
+
即路由器 的缓冲内 存为 0 时， 式 (2) 变为 当 =0 时 ，
0 =1, 1 0 =0 求解这个 微分方程 组， 可得瞬 时拥塞率为
0
｛
0
0 1
= =
0
0+ຫໍສະໝຸດ 11当 =2 时 ， 方程组 (3 ) 变为 0+ 1 =0
0
即 可。根据 马氏过程 的性质可 知， + 1
= 1=
+
当 =1 时 ， 方程组 (3 ) 变为 0+ 1=0
1 1
= +
+ +
+
+1
, =1, ,
= + +1 0 =1, 2 0 = 3 0 = = +1 0 =0 式中： = 式 (2) 的矩阵形式为 / ，=0, , +1。 0 = 1, ,0 。