基于馬爾可夫鏈與服務質量的網絡可用性

唐俊勇，田鵬輝，王 輝

(西安工業大學 計算機科學與工程學院，西安 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與性能成正比的假設，該值越大表示該指標可用性能越好，即維護該業務運行的花費越高。針對向量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指標所構成的特征狀態，其狀態變化所構成的遍歷性模型存在平穩分布；并且隨著指標的變化，所提出的模型均衡了特定業務運行開銷和特定業務最低需求而進行收斂，在評判網絡可用性方面更加合理。