基于马尔可夫链与服务质量的网络可用性

唐俊勇，田鹏辉，王 辉

(西安工业大学 计算机科学与工程学院，西安 710021)(*通信作者电子邮箱tjy112@hotmail.com)

0 引言

随着通信网络的规模化，几乎所有与用户服务相关的业务都在网络中存在，从而形成网络化的服务环境。对作为业务支撑平台重要基础架构的网络而言，所提供服务业务中断，或者达不到用户业务要求的服务标准所造成的代价和影响是巨大的。因此，对复杂网络可用性的评估是掌握网络是否准确及时进行信息交换的基础，是网络系统适应面向各类用户业务提供高可靠服务和减少网络运维代价的需求。复杂通信网络的一大特点是传输路径的多样化和冗余化，涉及到多个网络设备和链路，其中任何一个环节故障都会导致网络拓扑结构的变化，使得节点与链路的负载、吞吐量、传输速率等也相应地发生变化，从而导致具体用户业务的传输质量发生改变。这种变化有可能使得传输质量下降从而无法满足业务传输需求，或者虽然网络服务质量(Quality of Service, QoS)满足，但是对于服务业务的网络运行费用增加，致使全局网络处于非经济状态，浪费网络资源。因此，在进行复杂网络可用性评估时，要研究针对具体业务的可用性，避免笼统地判断整个网络可用与否，应当与具体服务业务结合起来，针对具体业务和开销对整个网络进行有效的全局评判，确保网络运行效率最佳。

为了更准确、客观地根据不同业务和网络提供业务服务的最小代价，通过不同QoS的需求来对网络可用性进行评价，本文提出了一种基于马尔可夫链和QoS指标的网络可用性(Markov Chain and QoS based Network Availability, MCQNA)评价方法。不仅将QoS指标作为客观因素，而且认为每个指标在满足特定业务的基础上都是有花费代价的，通过全局经济角度利用具体业务的服务代价去进行网络可用性评价。为了使QoS开销权重能根据网络运行变化而动态改变，将指标的变化特性看作随机过程构建马尔可夫链模型[14]，通过采集关键节点的QoS指标，构建马尔可夫状态转移概率并利用稳态收敛来确定业务服务的QoS开销权重，进而在整体网络范围内针对特定业务，从运行代价角度进行可用性评价。

1 相关工作

目前，传统的网络可用性评估是以局部设备与链路的可用与否为标准，脱离了业务去评价可用性，这种评价的弊端在于局部故障难以准确反映出具有冗余性的网络对业务的可用程度。而QoS指标与网络业务息息相关，可以从整体反映出网络对具体业务的服务程度[1]，利用QoS作为评判因素，网络可用性不仅反映了具体业务服务能力，还因为QoS参量值是需要实际测量的，将网络实际运行状况更加客观表现出来，而不是传统可用性或者可靠性评价依靠设备或者链路的故障概率判断，具有主观性较大的缺点。但是Qos现有的研究多以网络的连通性指标[2]、网络链路重要性或者网络元素的可用概率[3]作为评价，如基于最小生成树的最短路径进行可用性统计等。但是随着随着点到点传输(Point to Point, P2P)、网路协议电视(Internet Protocol Television, IPTV)和基于IP的语音传输(Voice over Internet Protocol, VoIP)等多业务的出现，传统的端到端通信模式向用户获取内容和服务的综合通信模式转变，使得业务对网络可用性的需求呈现出多样化、多变性的发展趋势。文献[4-6]使用模糊推理的方法进行网络QoS的预测，以此判断网络可用性。文献[7]对QoS指标进行区间相似度分类后，利用逼近理想点的方法确定QoS权重，最后再综合进行可用性评判。这些方法均需要大量的历史QoS数据作为训练集来对模型进行优化才能获得较高的准确性，所以并不适合基于业务实时性、变化性的网络评判。文献[8]采用了多种时间序列预测模型进行网络服务的QoS指标变化预测，再对各个指标进行归一化后进行加权平均判断。该方法虽然计算方便，实时性好，但只是整体评判网络可用性，缺乏针对特定的业务需求。文献[9]从业务服务角度入手，首先根据业务需要构造节点与网络服务能力模型，将网络各个节点可用与故障概率看作随机过程建立马尔可夫链，求出故障节点个数的随机概率分布以求得网络可用性，但该模型需要计算网络中每个节点的能力，对于大型复杂网络难以满足实时性评价。文献[10-11]充分考虑了网络状态变化的随机性这一物理性质，但是只是假设了网络节点状态的概率分布，并没有将QoS量化指标作为分析网络系统的可能状态，所以评判缺乏客观性。

综上所述，目前网络可用性评价的研究工作主要集中在网络设备与链路的可用概率，这些概率的获得主要靠经验、历史数据统计或者假定概率分布，缺少对不同业务的不同质量要求的分析，同时未能充分利用QoS指标客观与实时性优点，仅靠统计概率难以适应网络服务不断变化的环境。文献[12]采用层次化马尔可夫模型来描述网络可用性的动态变化，但并不适用于具有冗余度的通信传输网络，因为主干网络的主要目的是提供给特定用户合格的传输服务，并未有效区分不同业务的需求。文献[13]引入了随机收益因素来评判网络可用性，在网络敏感度分析时采用了传输时延这一QoS指标，评判依据具有客观性和实时性。

根据以上分析可知，不同于以往对于网络可用性不区分不同业务对QoS的要求差异，仅从单一的指标层面进行加权平均，缺乏考虑指标权重的变化具有随机性特点，本文提出的MCQNA方法具有指标权重动态适应特定业务的优点。本文通过基于马尔可夫链的网络可用性研究，分析网络可用性、特定业务与QoS指标关系，通过构建满足业务需求并且业务开销最小的指标匹配度函数、代价函数，建立了马尔可夫链模型，验证了该模型中利用马尔可夫平稳性确定指标优先级且用于网络可用评判是可行的。实验结果表明，MCQNA可以根据不同的业务对QoS指标需求，以运行业务花费最小来评价网络，确保网络系统服务效能的发挥及经济运行。

2 业务服务的可用性

构建网络的目的是面向用户业务提供特定的网络服务能力，而构建出来的网络是否能够满足用户需求需要一定的衡量标准。由于QoS指标是网络运行性能的直接反映，是业务的服务能力评判的重要依据，所以用向量ej(n1,n2,…,nn)表示网络对业务j(包含n个QoS指标ni)的服务能力。从网络运维角度而言，关心的是业务服务的代价和质量达标性。在满足业务质量的前提下，高服务代价带来的高质量或者低代价条件下不保证业务达标率都是不可以接受的。所谓基于业务服务的网络可用性，即QoS指标满足业务服务合格标准和最低运行开销的前提下，在一段时间内为业务提供的可用性水平。而本文所提出的网络可用性，正是根据具体业务的QoS量化指标，不仅考虑网络是否满足特定服务需求的能力，还通过QoS运行开销的马尔可夫状态转移概率得到权重系数，同时引入了代价函数，结合运行花费对网络可用性进行评价。根据以上分析，网络可用性可表示为：

A=R·W*

(1)

其中：W*代表业务ej(n1,n2,…,nn)各个特征指标的开销权重向量，由具有遍历性的马尔可夫链平稳概率得到；R为指标代价函数组成的当前代价向量。

2.1 业务开销的马尔可夫链

不同的业务需求、网络负载等因素的影响，导致不同的业务对QoS指标要求存在差异，因此在对网络可用性进行分析时，不仅需要考虑与业务相关的参数指标，还要考虑指标的权重。

(2)

2.2 状态转移概率的计算

(3)

在状态空间S内，构成了一步转移概率矩阵：

定义1 匹配度(Matched Degree)。

定义匹配度函数来表征每个指标满足特定业务可用的属性值。匹配度越大，表明指标不仅满足业务服务要求，而且还接近服务指标标准,降低运行花费。匹配度定义如下：

1)当QoS指标值越大代表越优，则匹配度定义为：

(4)

2)当QoS指标值越小代表越优，则匹配度定义为：

(5)

在当前状态si(si∈S)下，意味着选择了业务向量ej(n1,n2,…,nn)中的ni作为特征指标，下一个时刻应当以较大概率选择匹配度最大的指标主要衡量网络可用性。

定义2 匹配概率(Matched Probility)。

(6)

(7)

式(7)是在假设表征业务能力的网络特征方阵Ai存在可逆条件下得出，如果Ai不可逆，根据行列式为零的条件，表示Ai中至少有两行线性相关，又因为每行的匹配度都进行了归一化处理，所以如果不可逆即在n组的QoS数据集合中状态匹配概率至少有两组相同。根据以上分析，在采集的QoS指标集合中，应避免完全相同的一组数据。

3 可用性特征状态的平稳分布

3.1 网络特征状态转移矩阵

本文定义的网络可用性状态由最能反映业务服务质量和经济性能的指标评价，即网络业务特征指标。这些可用性特征状态的动态变化具有马尔可夫性，所以它们的变化情况用马尔可夫链的状态转移概率矩阵描述。

(8)

基于上述分析，需要得到网络可用性特征状态转移矩阵的平稳概率，而根据马尔可夫链理论，平稳分布存在与否取决于状态转移矩阵是否是遍历的。MCQNA方法中以定义1中QoS匹配度作为网络特征状态，有几个需要衡量的指标就有几个网络特征状态。根据式(4)、(5)，对于达不到业务QoS标准的网络特征状态为零，即意味着MCQNA所构建的马尔可夫链状态转移矩阵并非一定是遍历的。

下面就网络特征状态转移矩阵是否具有遍历性，分两种情况讨论应用于网络可用性评价。

3.2 具有遍历性时的网络可用性评价

当网络特征状态转移矩阵具有遍历性时，矩阵每个元素(状态转移概率)没有零，表示某个业务的QoS指标集的最低标准都能达到，网络对于具体业务是可用的，根据式(1)定义的网络可用性，使用网络特征状态的平稳分布作为式中的W*参与可用性评判。为了得到网络特征状态平稳分布，提出两个定理。

定理1 当网络特征状态具有遍历性时，特征状态绝对概率pj(n)(n→∞)的极限存在且与状态转移概率极限相同，与初始状态无关。

利用全概率公式可得：

即：

(9)

设n=k+l,k≥l,l≥1，根据切普曼-柯尔莫哥洛夫(Chapman-Kolmogorov)方程有:

(10)

将式(10)表示为矩阵形式，并且取l=1，得：

P(k+l)=P(k)P(l)=P(k)P(1)=[P(1)](k+1)

(11)

(12)

所以，对具有遍历性的马尔可夫链，当n→∞时，有：

(13)

得证

定理2 当网络特征状态具有遍历性时，有限状态的转移概率的极限就是平稳分布。

证明 根据定理1和切普曼-柯尔莫哥洛夫方程，由式(9)、(10)，可得：

(14)

从式(14)可以看出，任意状态的极限概率都等于初始概率分布，又因为pj服从概率分布，满足：

所以pj服从平稳分布，即具有遍历性的有限网络特征转移概率的极限分布是平稳分布。

得证

W*=(w1,w2,…,wn)=(p1,p2,…,pn)

(15)

3.3 不具有遍历性时的网络可用性评价

4 网络可用性评判

网络是否能够满足特定服务需求是衡量网络是否可用的标准，所以本文提出了匹配度作为状态转移条件的定量描述，在满足业务指标基本标准前提下，越接近基本标准运行代价越小，匹配度越大。这样，通过马尔可夫链的稳态分布得到的QoS指标权重具有运行代价最小的特点。

对于QoS指标在不同的传输业务需求中会有相应的代价，而该代价仅仅与当前状态有关，针对每个状态构成了代价向量R=(r1,r2,…，rn)。其中，ri表示选择ni作为最重要指标所带来的开销。基于代价与性能成正比的假设，该值越大表示该指标可用性能越好，即维护该业务运行的花费越高。针对向量R中各个指标的运行花费，定义了代价函数。

定义3 代价函数(Cost Function)。

(16)

通过上述方法建立基于马尔可夫链的网络可用性模型，针对业务对各个指标进行质量评估，对可用性能力QoS指标进行量化并获取模型处于遍历性的稳态概率分布，利用式(1)计算网络可用性在评估周期内的数值并更新相应参数：

(17)

5 仿真结果及分析

本文采用Mininet2.0作为网络数据仿真平台，该平台可以利用软件定义的形式灵活地对网络拓扑与流量路径进行配置。

5.1 仿真网络拓扑与场景

在Mininet中搭建数据中心普遍采用的胖树形结构并运行虚拟机，网络拓扑结构如图1所示。

在开放式虚拟交换机(Open Virtual Switch, OVS)中配置流表，实现全网联通。随机取三台虚拟客户机作为iperf客户端，逐步提高发送速率产生用户数据报协议(User Datagram Protocol, UDP)数据流，模拟业务的负载由低变高的过程。一台虚拟机作为iperf服务端，在客户端分别获得实时QoS参数并取平均值，仿真实验中具体采用延迟、传输速率、丢包率、抖动与吞吐量五个指标。网络服务业务QoS标准如表1所示。

图1 仿真网络拓扑Fig. 1 Topology of simulation network表1 不同网络服务业务QoS标准Tab. 1 Standards of QoS for different network services

业务延迟/ms传输速率/(Mb·s-1)丢包率/%抖动/ms吞吐量/(Mp·s-1)Webst2<20>0.05<1<20>5st1<200>0.4<10<75>1图像st2<50>0.05<1<20>5st1<200>0.2<6<60>3视频st2<100>0.4<4<20>5st1<300>0.1<10<75>1语音st2<100>0.4<5<20>5st1<300>0.2<10<70>1

5.2 平稳分布的存在性

在t1时刻，测量六组指标值，使用马尔可夫链模型MCQNA与定义1与定义2，分别使用前、后五组数据计算得到一步状态转移的矩阵。以Web业务为例，其中每列代表每个网络特征指标的匹配度转移概率：

由于Web业务受流量规模和各种因素的影响，QoS指标是不断变化的，根据式(7)得到可用性特征状态一步转移概率矩阵，采集的指标均达到Web业务的QoS标准，P中状态转移概率没有整行或者列为零，表明网络的每个特征状态都可以概率出现，所以本次实验所构建的针对Web业务的马尔可夫链存在遍历性，由定理1可知Web业务中的每个网络特征状态存在平稳分布，结果如图2所示，横坐标为概率转移矩阵P的转移次数，纵坐标为五种特征状态的出现概率。

图2 特征状态的平稳分布Fig. 2 Stationary distribution of characteristic states

从图2可以看出，P经过四步转移后，每个特征状态(延迟、传输速率、丢包率、抖动和吞吐量)都趋向平稳，其平稳分布就是特征指标的权重向量W*=[0.212 7，0.068 7，0.355 4,0.154 2，0.209 0]。图2结果表明,当采集的QoS指标均满足业务需求时，特征状态为遍历的，通过概率转移矩阵的极限概率求得特征状态的平稳分布，作为权重参与网络可用性评判。且图2结果显示，传输速率所占比重最小，表明传输速率普遍高于Web业务标准，但由于从花费代价角度考虑，并不适合给予高权重来评判网络可用性，而应当降低其评判比例。图2中丢包率是即能够满足业务标准又是最经济的指标，所以其比重最高。

5.3 不同业务的可用性评价

MCQNA可用性评价中，如果指标的平稳概率越大，表明该指标在网络特征状态的平稳分布中比重越大，在衡量网络可用性中赋予的权重也越大，并且评价模型是随着时间序列变化的马尔可夫链，可用性特征状态是在综合QoS指标达标性和运行花费的基础上动态改变的。文献[5，7]提出的权重估计法是采用固定加权平均，并没有随着时间序列而发生改变，导致随着指标的连续改变，网络可用性也线性变化。为了研究不同业务的网络可用性受QoS动态变化的影响，在实验中iperf客户端线性增加传输速率，模拟高速网络的场景。采用MCQNA方法对Web和图像(Graph)业务进行网络可用性评价，同时对比随着速率增加(Percentage of Rate)的固定加权平均的评价方法，结果如图3所示。

图3 网络可用性的变化Fig. 3 Variation of network availability

图3结果表明，固定加权平均方法随着控制传输速率线性增加，其网络可用性与动态的速率呈现线性关系，指标越好网络可用度越好，没有体现出业务花费的约束。而采用MCQNA方法分别评价网络对于Web和Graph业务的可用性，虽然在开始的连续运行中，可用性随着传输速率的线性增加而逐步上升，但由于单一指标过于优化导致运行费用增加，不断降低该指标权重，最后可用性趋于定值，所以该方法充分考虑到业务代价的约束。同时由于Graph业务对于QoS指标各项要求也更高，所以对于同样的QoS测量值其评价的可用性低于Web业务的可用性。由图3可以看出，MCQNA针对不同的业务，在不断变化的指标值条件下，更加合理地进行网络可用性评判。

文献[13]提出了一种利用Petri网的随机奖励网络(Stochastic Reward Nets, SRNs)模型作为评价网络可用性方法。在设备故障恢复期中依据设备间的关联度对可用性进行评判，在如图1的具有冗余度的通信网络中，用MCQNA方法在语音与图像(Gragh)业务中与SRNs进行了可用性评判对比分析，网络可用性评判结果如图4所示。

MCQNA区分业务的不同要求，分别对图像和语音业务进行可用性评判,在网络性能稳定后开始降低网络传输速率,同时延迟、吞吐量等其他QoS指标变化，网络服务性能降低。从图4中可以看出，MCQNA对两个业务的可用性评价在服务质量变化的2～15 min逐步下降；随后在满足业务最低标准前提下传输速率下降幅度增加，可以明显看出MCQNA对可用性的评价值也加速下降；而SRNs模型由于采用的是网络设备可用时间概率作为参数，在网络设备没有损坏的前提下对网络性能的下降响应较慢。由此可以看出，MCQNA模型对网络变化的灵敏度优于SRNs。

图4 服务质量下降时MCQNA与SRNs灵敏度对比Fig. 4 Sensitivity comparison between MCQNA and SRNs with service quality degrading

6 结语

针对采用QoS指标衡量网络可用性存在缺少运行开销的问题，本文定义了既满足网络业务需求又考虑最小花费的匹配度，并引入马尔可夫链模型用于网络可用性的研究；根据匹配度生成的概率转移矩阵，提出具有遍历性的马尔可夫链平稳分布作为网络QoS指标权重，通过可用性模型中是否具有遍历性分别阐述了与可用性评判的关系；并根据定义的可用性公式计算模型中的稳态分布，找到满足运行开销与业务需求平衡的指标特征权重并以此计算网络的可用性。仿真实验结果表明：QoS指标所构成的特征状态，其状态变化所构成的遍历性模型存在平稳分布；并且随着指标的变化，所提出的模型均衡了特定业务运行开销和特定业务最低需求而进行收敛，在评判网络可用性方面更加合理。