1. 引言
随着网络技术的飞速发展,网络从单一的数据网络向集成数据、语音、视频等的多业务网络转变,用户对网络质量的要求也随之增加。时延作为QoS的重要指标,可评价网络性能。文献 [1] 指出传统的分析方法主要基于排队论,当网络规模较大时,存在分析过程复杂、不准确等缺点。由文献 [2] 得由于网络情况比较复杂,排队论需要与其他数学理论结合使用。
上世纪七十年代起,网络队列模型的研究分析中开始引用鞅理论。将排队系统模型中的组成元素利用鞅理论进行建模,然后利用鞅理论的性质分析网络性能。NG Duffield等使用指数鞅建模系统队长并分析系统性质,为日后使用鞅理论分析排队系统性能打下基础,见文献 [3] [4] 。鞅理论是一种重要的随机过程,在现代概率论中经常使用,可以用来描述一类统计期望关于时间变化的随机变量。针对使用鞅理论分析时延的研究,可见文献 [5] - [11] ,Ciucu F, Poloczek F团队创造性的提出了关于鞅的一系建模研究成果以及首次提出鞅包络、到达鞅和服务鞅的概念。其中文献 [8] 中,Ciucu F等利用鞅包络的方法,把业务累计到达过程转化成指数上鞅结构。文献 [10] 中,由于随机网络演算的排队方法并不利于研究,为了避免这种情况,Ciucu F等使用鞅排队来代替,并设置合理的鞅参数和定义队列溢出停时事件。服务鞅理论为不同类型终端到达过程转化成鞅过程提出了全新的方法,具体可见文献 [11] 。文献 [12] 对无线资源进行有效的切片管理。通过构建每个切片上到达过程的超鞅,证明基于鞅理论为业务提供的统计型QoS保障可以使得排队系统性能概率界更加紧致。由于现实中的业务流量具有复杂性和突发性,可将业务的流量建模为马尔可夫调制过程,文献 [13] 证明在鞅理论的SFC逐跳带宽方案下,得到的时延违反概率界优于基于EB/EC理论所得。综上,到达鞅和服务鞅等鞅理论为时延可靠性分析框架提供了全新思路。
本文基于统计型QoS保障,在排队论的基础上研究分析突发性情况下的系统特性,并与鞅论相结合,针对指定的到达与服务模型提供了精确的可靠性分析保障框架。到达选择马尔可夫,调制机制选择Aloha。利用鞅的停时定理推导时延违反概率,仿真不同负载率下的鞅论时延违反概率界。
2. 理论基础
2.1. 排队论和排队基础
排队论是一个独立的数学分支,是专门研究由于随机因素的影响而产生的拥挤现象(排队、等待)的科学,也称为随机服务系统理论或拥塞理论(Congestion Theory)。排队论是对通信网内的流量进行分析的数学工具。利用排队论中的ErlangB公式和ErlangC公式以及鞅论,就可以计算出网络的呼损和时延,用它们来评估通信网的性能。在通信时间内,对用户提供良好的服务,需要有足够的线路(信道)容量。线路容量不够,将导致拥塞现象,出现“排队问题”,本文利用排队系统来描述这一问题。本文中建立包级别的排队系统,即终端用户的数据以数据包的形式到达系统,等待服务,如图1所示。
1) 到达:终端业务的到达过程是可以用各种不同分布来建模的随机过程。根据不同的业务数据包到达方式,有一般突发性低的周期性发包业务和紧急事件触发的突发性较强的业务,本文主要研究后者,建模为MMOO过程。
2) 排队:排队系统分为两种:拒绝系统和非拒绝系统。在拒绝系统中,根据系统允许的排队队长和窗口数的大小关系,又分为即时拒绝和延时拒绝。非拒绝系统,即系统允许的排队队长没有限制,当数据包到达且没有空余窗口时,数据包加入排队行列等待服务,也由此产生了时延。
3) 服务:本文采用先到先服务,服务过程为伯努利,作为拓展,加入了在ALOHA接入机制下网络的时延性能。
4) 离去:离去过程是一个随机过程,与到达过程和服务过程均有联系。
2.2. 队长
队长全称排队长度,是在某时刻系统内滞留的数据包数量和正在被服务的数据包数量。队长的定义如下:
(1)
其中
是队长,
,为n时刻的累计到达,
,为n时刻的累计服务。
2.2.1. QoS简介
所谓网络QoS,即服务质量(Quality of Service),是网络在其传输数据流时需要满足的一系列的服务请求,也是服务性能的反映,是一种综合性指标,主要取决于用户对服务性能的满意程度的总体表现。
时延是QoS的重要指标,是指将数据包从发送端传输到接收端的时间,本文主要使用虚时延理论。虚时延定义如下:
(2)
其中,D(n)为系统离去过程,虚时延可以理解为进入缓存排队中的数据经历的系统服务,直到离去所需的最少时间
2.2.2. QoS保障
QoS服务可分为确定性QoS、统计型QoS以及“尽力而为”型QoS。其中“尽力而为”型QoS最简单,在该类型下的QoS不为网络系统中的信息传输提供任何QoS指标保证,通常使用在对时延等级要求不高的通信系统中。
本文主要使用统计型QoS。即对承诺的QoS服务在允许在一定范围内波动,但是不会造成不良后果。与确定型服务的“硬”保证不同,统计型服务提供QoS“软”保证,它允许对通信各方已协商好的各项QoS参数值有一定程度的违反。
基于大偏差理论,在稳态遍历到达和服务过程的排队系统中,队列长度
收敛至
。
2.3. 鞅理论
2.3.1.鞅理论的定义与基本性质
鞅理论其实是一种重要的随机过程,在现代概率论中经常使用。起初人们常用“公平赌博”来直观诠释“鞅”,假设赌局是公平的,也就是输赢概率各半。此时,下一步损失的期望值就等于赌徒当前的损失,所以。当一个人参加n轮赌博后,继续第n + 1轮时,若他在第n轮结束后所剩赌资
与第n + 1轮赌资的均值相等,即第n + 1轮不输也不赢,则可以称这种赌博在统计学角度上是公平的。
由于鞅是一种特殊的随机过程,所以常用数学条件期望来描述。假设已知当前n时刻之前的全部信息,若随机过程n时刻的值等于n + 1时刻的条件期望,则可称此随机过程为鞅,用数学可表示为:
定义1 (离散时间鞅):假设有随机过程
,若满足:
1)
;
2)
则过程
称为鞅。有时
不能直接观察,只能观察另一个过程
,因此将鞅的定义进行推广。
定义2 (离散时间鞅):设两个随机过程
,
,若满足:
1)
;
2)
则称
关于
是鞅,即已知n时刻以及之前的值
,于是可以得出
时刻的值
对
的条件期望与
无关,只和
有关且等于
。针对这种特殊的随机过程——鞅,有以下几种性质:
1) 性质1:
,再推广可以有
2) 性质2:
,则
,此性质在鞅的应用过程中最常见;
3) 性质3:若
关于
是鞅且相互独立,则随机过程
关于
是鞅,此性质常用于随机过程的鞅构造。
2.3.2. 鞅的举例与构造方法
为了能进一步了解并运用鞅理论,现举例说明:
若
,
独立同分布,
,
,取
,
,则
关于
是鞅。若
为Markov链,状态空间为
,转移矩阵为P,定义
为右特征向量,
。令
,则
关于
是鞅。
证明:
,
。
2.3.3. 上鞅、下鞅的定义及基本性质
定义3:随机过程
满足下列条件:
(3)
是
的函数
则称
关于
是上鞅,且由上鞅的定义可知上鞅满足单调递减,同理(3)可定义下鞅。
下面是上(下)鞅的一些重要性质:
性质1:上鞅
,则
;
性质2:上鞅
,则
,上鞅在0时刻的期望值取最大,所以在许多关于上鞅的不等式证明过程中都会使用到0时刻的期望值;
性质3:若随机过程
都关于
是上鞅,且随机过程
相互独立,则
关于
是上鞅,此性质可用于随机过程的上鞅构造。
2.4. 停时和停时理论
为了可以进一步了解鞅论,下面引进鞅的停时与停时定理。
鞅的停时:令
,
表示随机变量
可提供的全部信息,称为
生成的
域。设有非负随机变量
和随机序列
,若
则称
是
的停时。其中,若
是一个停时
,那就可以导出事件
,且这些事件均只由
确定,即截止到n时刻,根据已有的信息可以完全确定停时所对应的事件是否已经发生。
停时定理1:令
是鞅,
是停时,当
(4)
成立时,则
,由于公式(4)
对停时点T的均值
的存在有限制作用,现推导出停时定理2。
停时定理2:令
是鞅,
是停时,当
(5)
成立时,
,其中
是停时定理1的增强型条件,该停时定理在证明过程中经常使用。
3. 基于鞅论的时延分析
本文研究的到达过程选用MMOO过程,服务过程选择ALOHA机制建模为伯努利。建立MMOO到达的排队系统模型,采用ALOHA机制,利用鞅论进行分析,得到对应的时延违反概率。其中,使用鞅理论对概率域上的随机过程转换时,得到其对应的在鞅域中的“服务鞅”和“到达鞅”。
3.1. 到达鞅和服务鞅
定义1 (到达鞅)在到达过程A中,对于任意
,都对应的
和函数
,得到到达过程
在鞅域中对应的到达鞅:
(6)
其中,
表示瞬时到达,
表示瞬时到达,
表示累积到达,
代表衰减指数,决定参数
和
。
定义2 (服务鞅)在服务过程S中,对于每一个
,都对应
和
,得到服务过程
在鞅域中对应的服务鞅:
(7)
其中,
表示瞬时服务,
表示累计服务,
决定参数
和
。
3.2. 随机过程的鞅变换
本文用MMOO过程来建模到达服务,MMOO到达的马尔可夫链如图2所示。
当系统为ON状态时到达速率为R,Off状态时无数据到达。pa表示Off到On的转变概率,qa表示On状态到Off状态的转变概率。此马尔科夫链状态空间
,其对应的概率转移矩阵T与对角速率矩阵∆为:
,
(8)
根据到达鞅定义,可将MMOO过程的鞅构造为:
(9)
其中
表示对应的右特征向量,
表示谱半径。
当MMOO过程建模为到达鞅时,系统的累计到达
。为了保证到达鞅满足指数上鞅的要求,需确保下式成立:
(10)
指数列变换矩阵
可表示为:
(11)
则MMOO的到达鞅参数
的定义为:
(12)
若服务是MMOO过程,根据服务鞅定义为:
(13)
为保证服务鞅满足指数上鞅要求,服务鞅也需满足下式定义:
(14)
与到达鞅同理,此时的指数列变换矩阵
为:
(15)
则服务鞅参数
3.3. 基于鞅的时延违反概率
根据上鞅的性质,两个上鞅过程的乘积还是上鞅过程。因为服务鞅和到达鞅均是上鞅结构,已知队长为
,所以构造出队列长度的鞅:
(16)
其中
(17)
当
取极值时有
,则队长
化简为:
(18)
根据鞅的停时理论:在鞅过程中,在停时时刻的期望小于或等于其初值的期望,由此可得时延违反概率界:
(19)
其中
为系统队长的阈值,H是阈值,由下式确定:
(20)
当
时,有
。停止时间N第一次超过
表示为:
(21)
根据停时理论和文献 [8] 得下式:
(22)
4. 仿真结果与分析
1) 图3为Matlab仿真的系统到达是MMOO过程,服务为伯努利业务流,负载率
时的时延违反概率仿真结果。
![](//html.hanspub.org/file/4-1543144x161_hanspub.png?20240417092607376)
Figure 3. Probability of delay violation under different load rates
图3. 不同负载率下的时延违反概率
由图可知,负载率越大,时延违反概率也越大,对网络的影响也随之增加。
2) 图4为引入了ALOHA机制下仿真生成的MMOO流的时延违反概率,负载率
。在ALOHA机制下时延违反概率界同样随着负载率的减小而紧致,且更加接近实测值。
![](//html.hanspub.org/file/4-1543144x163_hanspub.png?20240417092607376)
Figure 4. Delay violation under Aloha mechanism
图4. ALOHA机制下的时延违反
3) 为了进一步证实鞅理论有望成为网络性能评估与分析的新理论,图5是图4的延伸,ALOHA机制下仿真生成的MMOO流的时延违反概率,利用鞅理论和EB-EC两个理论,负载率仍选择
。
由图可知,在同一负载率的情况下,鞅理论得出的时延违反概率明显优于EC-EC推导的时延违反概率,即利用鞅理论推导的时延界更加紧致
综上,在鞅域中,时延界随着负载的减小更加紧致,且在同一负载率下鞅理论推导的时延违反概率要比EB-EC理论推导的紧致,更加接近实测值。
参考文献
NOTES
*通讯作者。