(8)
3.1
系统状态转移概率矩阵 令 Ln 表示第 n 个数据帧完成传输离开服务台时系统中的 数据帧数， Jn 表示第 n 个数据帧完成传输离开服务台时系统 所处的状态 (Jn =0 表示系统处在工作休假期 V ， Jn =1 表示系
由 Little 公式 [7]，数据帧的平均等待时间表示为：
λθ S ′ θ 1 − λθ SV ′ θ V 1 1 E [W ] = P + − V 1− γ S θ 1 − SV θ λ V
π ij = lim P { Ln = i, J n = j} = P { L = i, J = j} , ( i, j ) ∈ Ω
设稳态下系统处于 i 水平概率为 π i ，则 π 00 为：
π 00 =
(1 − ρ ) (1 − SV (θ ) )
λθ 1 − SV (θ ) − (1 − γ ) ρ SV (θ ) − 1 − SV (θ ) θ
P {S B = k } = sBk , E [ S B ] = 1
排队模型分析
µB
(1)
λθ 1 − SV (θ ) − (1 − γ ) SV (θ ) − 1 − SV (θ ) θ PB = λθ 1 − SV (θ ) − (1 − γ ) ρ SV (θ ) − 1 − SV (θ ) θ 设嵌入点处的稳态队长为 L ，其均值表示为：
λE S B ( S B − 1) E QB ( QB − 1) PB + ρ λ 2 1 − 2 E Q ( ) [ ] B
(9)
令 ai 为 SB 内有 i 个数据帧到达的概率， vi(1)表示 T V>V 时传输时间 SV 内有 i 个数据帧到达的概率， vi(2)表示 T V≤ V， 且在随后传输时间 SB 内有 i 个数据帧到达的概率。则有：
(
)
稳态下数据帧离去后系统处在工作休假期 V 和正规忙期 B 的概率分别为： (1 − ρ )(1 − γ ) (4) P { J = 0} = λθ 1 − SV (θ ) − (1 − γ ) ρ SV (θ ) − 1 − SV (θ ) ) ( θ
λθ 1 − SV (θ ) − (1 − γ ) 1 − ρ + ρ SV (θ ) − 1 − SV (θ ) θ P { J = 1} = λθ 1 − SV (θ ) − (1 − γ ) ρ SV (θ ) − 1 − SV (θ ) θ
( ) ( )
( ) − 1 + µ ( )
V
统处在正规忙期 B )，则 {( Ln , J n ) , n ≥ 0} 构成二维 Markov 链， 状态空间为：
Ω = {( i, j ) : i = 0, j = 0} ∪ {( i, j ) : i ≥ 1, j = 0,1}
84
计 算 机
工 程
n→∞
2012 年 5 月 5 日
在 E-DBA 策略中，第 I 类业务分配固定带宽，第 II 类 业务和第 III 类业务依第 II 类业务的负载情况动态获得剩余 带宽。若第 II 类业务的负载重时，系统将全部剩余带宽分配 给第 II 类业务，保证第 II 类业务更好的服务；待第 II 类业务 负载轻时，系统设置一段时间 T V，在 T V 内为第 II 类业务保 留一部分剩余带宽，为其提供最低的保证带宽，其余剩余带 宽分配给第 III 类业务使用。当 T V 结束，如果第 II 类业务负 载仍然轻时，系统仍分配部分剩余带宽给第 II 类业务。当 第 II 类业务负载较重时， 重新将全部剩余带宽分配给第 II 类 业务。 排队模型的建立 将 E-DBA 中第 II 类业务占用全部剩余带宽的状态抽象 为正规忙期 B ，第 II 类业务占用部分剩余带宽的状态抽象为 工作休假期 V ，其工作休假长度为 T V，第 II 类业务缓冲区抽 象为排队场所，传输数据帧的链路抽象为服务台，可以建立 起遵循先到先服务排队规则的，具有多重工作休假机制的排 队模型。设第 II 类业务的到达服从参数为 λ 的 Bernoulli 过 程，正规忙期 B 和工作休假期 V 内的数据帧传输时间分别服 从参数 µ B 和 µV 的一般分布，设数据帧的到达间隔和传输时 2.2 间相互独立，该排队模型可以表示为基于 Geom/G/1 的多重 工作休假排队模型。
一种动态带宽分配策略及其 一种动态带宽分配策略及其性能分析
金顺福 1，吕 倩 1，王 朋 1，李小良 2
(1. 燕山大学信息科学与工程学院，河北 秦皇岛 066004；2. 开滦(集团)有限责任公司信息与控制中心，河北 唐山 063018) 摘 要：针对当前网络中不同业务的服务质量需求，综合考虑业务优先级及业务负载，提出一种动态带宽分配策略——E-DBA。建立具有 多重工作休假机制的 Geom/G/1 排队模型， 使用嵌入式马尔可夫链导出排队模型的稳态指标。 给出 E-DBA 的平均响应时间和信道利用率等 系统性能指标表达式，并通过实验分析了第 II 类业务的保障带宽对系统性能的影响。 关键词： 关键词：动态带宽分配；服务质量；排队模型；多重工作休假；马尔可夫链
Strategy of Dynamic Bandwidth Allocation and Its Performance Analysis
JIN Shun-fu1, LV Qian1, WANG Peng1, LI Xiao-liang2
(1. College of Information Science and Engineering, Yanshan University, Qinhuangdao 066004, China; 2. Information and Control Center, Kailuan Group Co., Ltd., Tangshan 063018, China) 【Abstract】Aiming at Quality of Service(QoS) requirements of different traffics in the current network, a dynamic bandwidth allocation strategy named E-DBA is proposed by taking into account both the traffic priority and system load. Geom/G/1 queuing model with multiple working vacations mechanism is established. By using the method of embedded Markov chain, the steady-state measures of the queueing model are derived. The performance measures in terms of the average response time and system utility of E-DBA are given. With experiments, the influence of the guaranteed bandwidth of class II traffic on the system performance is illustrated. 【Key words】dynamic bandwidth allocation; Quality of Service(QoS); queuing model; multiple working vacation; Markov chains DOI: 10.3969/j.issn.1000-3428.2012.09.025
(3)第 III 类业务对时延和带宽没有要求，优先级最低，机会 式占用系统剩余带宽，保障系统的公平性。 E-DBA 策略的工作流程如图 1 所示。
2
2.1
E-DBA 策略及排队模型
E-DBA 策略 按照不同业务的 QoS 要求，将业务分为 3 类：(1)第 I 类 业务实时性比较强，对时延非常敏感，必须保证带宽，按时 送达，采用资源预留的方式 [6]为其分配固定的带宽，保证其 服务质量。(2)第 II 类业务对时延有一定的要求，带宽要求也 比较高，采用具有最低带宽保障方式进行带宽的动态分配。
图1
E-DBA 策略工作流程
基金项目： 基金项目：河北省自然科学基金资助项目(F2009000475) 作者简介： 作者简介 ： 金顺福 (1966 － )，女，教授、博士生导师、CCF 高级 会员，主研方向：系统建模与仿真；吕 生；李小良，工程师 收稿日期 收稿日期： 日期：2011-06-30 E-mail：jsf@ 倩、王 朋，硕士研究
(
)
(
)
(7)
工作休假期的工作休假长度 TV 服从参数为 θ 的几何分 布，在工作休假期 V 的一个数据帧传输时间为 SV，SV 的概率 分布和均值分别为：
P {SV = k} = sVk , E [ SV ] = 1
µV
(2)
λθ S ′ (θ ) 1 − λθ SV ′ (θ ) 1 V + E [ L] = P + − V SV (θ ) 1− γ 1 − SV (θ ) λ 2 E [ S B ( S B − 1)] E [QB (QB − 1) ] PB + ρ + 2(1 − ρ ) 2 E [QB ]
(
)ቤተ መጻሕፍቲ ባይዱ
(
)
(5)
数据帧以工作休假期传输率 µV 及正规忙期传输率 µ B 传 输的概率分别为：
P V =
(1 − ρ )(1 − γ ) SV (θ )
λθ 1 − SV (θ ) − (1 − γ ) ρ SV (θ ) − 1 − SV (θ θ