基于效能分析的網絡可靠性評估模型

姜 禹 胡愛群

(東南大學信息科學與工程學院，南京210096)

網絡可靠性分析涉及到現實網絡系統(tǒng)的設計、維護及修復，正在受到越來越多的關注.網絡系統(tǒng)的部件都有一定的內在失效概率，部件的失效會導致網絡無法完成預先設定的任務.因此，如何定量評價一個網絡的可靠性具有重要的意義.IEEE 90標準將可靠性定義為“某個系統(tǒng)或部件在規(guī)定狀態(tài)和時間下能執(zhí)行其功能的能力”［1］.

目前，網絡可靠性的評價方法通常使用如下的常用網絡模型，通信網用圖G=(V，E)表示，為無自環(huán)的無向連通圖，其中，V={x1，x2，…，xn}表示網絡中的 n 個節(jié)點集合，E={e1，e2，…，em}表示網絡中的m條鏈路集合.每條鏈路和每個節(jié)點的失效是隨機和相互獨立的，并具有一個已知的失效概率.網絡可靠性的評價方法通常用于研究兩終端可靠性［1-2］、多終端可靠性［3-4］及全網可靠性［5］等問題.上述問題的分析是假定網絡的鏈路和節(jié)點具有固定的可靠性，通過布爾代數和概率論得到網絡的可靠性值.

在實際網絡系統(tǒng)中，對于不可修復系統(tǒng)，網絡部件經歷可靠性下降的過程，直到損壞和失效;對于可修復系統(tǒng)，故障后會進入修復過程，在正常運行和失效2種狀態(tài)之間轉換.有些研究者［6-8］提出了基于可修復網絡的穩(wěn)態(tài)可靠性分析方法，在得到網絡部件穩(wěn)態(tài)可靠性的情況下求得網絡的穩(wěn)態(tài)可靠性.

對于固定可靠性和穩(wěn)態(tài)可靠性的網絡分析，僅通過固定的或穩(wěn)態(tài)的可靠性值是無法有效地評估網絡的，這是因為網絡的可靠性與網絡的運行時間密切相關［9-10］.本文在故障率模型的基礎上提出了鏈路和節(jié)點效能的概念，建立與時間相關的效能模型，并根據全網可靠性方法得到整個網絡的時間效能模型，通過網絡效能的變化動態(tài)評價網絡的可靠性.

1 效能模型

1.1 初始故障率模型

隨著硬件組件可靠性的提高，其MTBF(mean time between failure，平均無故障時間)也在不斷增加.CPU、內存、硬盤等都具有以年為單位的可操作生命期.但是當這些硬件組件集成起來組成網絡中的鏈路(光纜、電纜等)和節(jié)點(工作站、PC、路由器等)時，集成系統(tǒng)的MTBF定義為［11］

式中，Rk為系統(tǒng)中組件k的MTBF;N為系統(tǒng)中的組件數量.直觀上可以看出，最不可靠的組件決定了整個系統(tǒng)的可靠性.盡管硬件組件的可靠性不斷提高，但系統(tǒng)的集成度也在不斷加大，即使組件中個體的可靠性非常高，由式(1)可知，大量的系統(tǒng)組件也會造成系統(tǒng)可靠性的下降.

1.2 使用期故障率模型

在網絡部件正式使用前，必須經過試用或老化過程，以便篩選合格的網絡部件.大量的網絡部件同時啟動，由圖1可見，在起初的0～t0時間內，無網絡部件失效，故障率為0;在t0～t1時間內，網絡部件失效較多，但故障率α逐漸下降，這個階段就是部件的試用或老化過程;在t1～t2時間內，網絡部件失效的較少，故障率α接近常量，這可作為正常使用期;在t2以后，失效的組件又較多，故障率α上升，這是衰竭期.在實際應用中，這時網絡部件已超過正常使用壽命，應予更換，以保證系統(tǒng)的正常運作.

圖1 網絡部件故障率的時間曲線

為了能定量描述圖1的曲線，使用Weibull函數表示故障率曲線α(t)，即

式中，a，b，c為形狀系數，可以根據實際測量某時刻的故障率計算獲得.α由α(t)在t1處的連續(xù)性獲得，即

1.3 節(jié)點和鏈路效能模型

在實際網絡中，節(jié)點和鏈路效能指節(jié)點和鏈路當前能完成網絡任務的能力占其最大有效能力的比值，部件效能與部件的故障率密切相關.節(jié)點的效能表現為節(jié)點處理能力的大小，鏈路的效能表現為鏈路所承擔流量的大小.

不可修復系統(tǒng)中，根據系統(tǒng)可靠度定義方法［12］，定義效能為

若故障率α與t無關，則

根據故障率α(t)的表達式(2)，得到效能函數為

現實網絡系統(tǒng)中，部件經過老化期和試用期后，進入正常使用期.以此時的部件效能E(t1)=1，作為考慮部件效能變化的起點.

對于可修復系統(tǒng)，根據系統(tǒng)可靠度定義方法［12］，定義效能為

式中，β為修復率，與時間無關.如果α與t無關，則從式(7)可得到E的穩(wěn)態(tài)效能為

實際應用中，α與t相關且滿足式(2)的故障率模型，則E的穩(wěn)態(tài)效能為

1.4 網絡效能模型

本文采用常用的網絡模型表示方法來分析網絡效能，而計算網絡效能的前提是網絡有效.網絡有效指網絡中的所有節(jié)點能夠通過有效鏈路進行通信.網絡效能由網絡中節(jié)點和鏈路效能經過拓撲關系獲得.網絡效能EN(t)表示為

式中，Ev(t)為網絡總的節(jié)點效能，網絡有效必須保證網絡中的節(jié)點均有效.當網絡中的某個節(jié)點效能為0，則網絡失效.因此，Ev(t)可以表示為

式中，Evi(t)為節(jié)點i的效能;n為網絡中的節(jié)點個數.

Ee(t)是網絡總的鏈路效能，網絡有效必須保證網絡中i條鏈路有效且與所有節(jié)點相連，其中i≥n－1.因此，Ee(t)可以表示為

式中，Ci表示i條鏈路連接所有節(jié)點且其余m－i條鏈路無效的網絡狀態(tài)個數;Eei(t)為鏈路i的效能.當鏈路效能Eei(t)與時間無關，且將Eei(t)用鏈路可靠性pi代替時，則式(12)等價于在節(jié)點完全可靠的前提下求解固定可靠性的全網可靠性問題.

2 應用實例

對于不可修復系統(tǒng)，利用圖2給出的無向網絡G1 對本文算法進行說明.節(jié)點 vi(i=1，2，3，4)表示網絡終端，其MTBF由其組件的MTBF共同決定.假設組件包括CPU(C)、硬盤(D)、主板(M)、內存(R)，它們的MTBF分別為RC=5×105，RD=1 ×105，RM=2 ×104，RR=1 ×105.由式(1)得節(jié)點vi的MTBF為

圖2 無向網絡G1

在故障率時變系統(tǒng)中，Rvi為節(jié)點正常使用期的 MTBF，t1為起始使用點，此時節(jié)點效能為Evi(t1)=1，t2時刻進入衰竭期，根據式(2)得到節(jié)點故障率表達式為

根據式(6)和(13)，得到時變系統(tǒng)的節(jié)點效能表達式為

在故障率時不變系統(tǒng)中，由式(5)得

根據式(14)和(15)分別得到故障時變和時不變系統(tǒng)的節(jié)點效能曲線(見圖3).

根據可靠性理論中的節(jié)點MTBF定義［13］，時變故障系統(tǒng)中的節(jié)點效能曲線更接近于現實模型.

邊ei(i=1，2，…，5)作為網絡中的通信鏈路，其MTBF受到交換機處理能力、鏈路線纜質量等因素的影響，這里假設鏈路的MTBF為 Rei=1×104.對于故障率時變系統(tǒng)，αei=1/Rei，a=1.5，c=500，由式(3)得當 t1=0，t2=7 000 h 時，

圖3 節(jié)點效能隨時間的變化曲線(t1=0)

根據式(2)得到鏈路的故障率表達式為

根據式(5)和(6)可分別得到故障時不變和時變系統(tǒng)的鏈路效能表達式為

假設鏈路和節(jié)點均服從統(tǒng)一的效能模型，根據式(11)得到圖2中網絡G1總的節(jié)點效能為

根據式(12)得到網絡G1總的鏈路效能為

采用文獻［14］中的方法，可以得到C3=8，C4=5，C5=1，則

當鏈路服從統(tǒng)一的效能模型時，可以根據全網可靠性的求解方法得到總的鏈路效能Ee(t)的表達式，目前最有效的算法為文獻［3］提出的BDD算法.

根據式(10)得到網絡效能為

圖4(a)為 1.5Rvi，1.5Rei，10Rvi和 10Rei下時變和時不變故障率系統(tǒng)的網絡效能隨時間變化曲線.由圖可以看出，當R較小時，即MTBF較小時，2種故障率系統(tǒng)描述的網絡效能隨時間的變化基本一致，但當R較大時，2種故障率系統(tǒng)描述的網絡效能隨時間的變化出現了很大差別，時不變故障率無法描述網絡部件進入衰竭期的效能變化，時變故障率更加接近現實網絡系統(tǒng).隨著部件MTBF的提高，時變故障系統(tǒng)更加適合于實時的網絡效能分析.

圖4 網絡效能隨時間的變化曲線

下面分析可修復系統(tǒng)中網絡效能隨時間的變化，假設鏈路和節(jié)點均服從統(tǒng)一的效能模型，失效部件失效后馬上進入修復狀態(tài).對于時變故障率系統(tǒng)，節(jié)點和鏈路的故障率曲線和不可修復系統(tǒng)中的曲線相同，分別由式(13)、(7)以及式(16)、(7)得到節(jié)點和鏈路的效能表達式.其中MTTR(mean time to restoration，平均修復時間)是MTBF的1/4，節(jié)點和鏈路的修復率分別為 βvi=4αvi，βei=4αei.圖4(b)為 1.5Rvi，1.5Rei，10Rvi和 10Rei下時變和時不變故障率系統(tǒng)的網絡效能隨時間變化的曲線.由圖可以看出，對于故障率時不變系統(tǒng)，網絡效能隨著時間增長將趨于穩(wěn)定值.而對于故障率時變系統(tǒng)，隨著時間的增長，網絡效能將趨于0.對于實際網絡系統(tǒng)，當部件進入衰竭期后，其效能必定趨于0，這樣使得整個網絡效能為0.因此，時變故障系統(tǒng)模型更準確地刻畫了網絡效能隨時間的變化.

3 結語

本文在故障率模型的基礎上提出了鏈路和節(jié)點效能的概念，建立了與時間相關的效能模型.并根據全網可靠性方法得到整個網絡的時間效能模型，根據網絡效能的變化動態(tài)評價了網絡的可靠性.實例分析說明，本文提出的網絡效能模型客觀描述了網絡效能隨時間的變化，為網絡可靠性分析提供了更加有效的方法.

References)

［1］Gebre B A，Ramirez-Marquez J E.Element substitution algorithm for general two-terminal network reliability analyses［J］.IIE Transactions，2007，39(3):265-275.

［2］Satitsatian S，Kapur K C.An algorithm for lower reliability bounds of multistate two-terminal networks［J］.IEEE Transactions on Reliability，2006，55(2):199-206.

［3］Yeh F M，Lu S K，Kuo S Y.OBDD-based evaluation of k-terminal network reliability［J］.IEEE Transactions on Reliability，2002，51(4):443-451.

［4］Hardy G，Lucet C，Limnios N.K-terminal network reliability measures with binary decision diagrams［J］.IEEE Transactions on Reliability，2007，56(3):506-515.

［5］Younes A，Girgis M R.A tool for computing computer network reliability［J］.International Journal of Computer Mathematics，2005，82(12):1455-1465.

［6］劉愛民，劉有恒.可修復網絡穩(wěn)態(tài)可用度分析［J］.通信學報，1997，18(7):15-19.Liu Aimin，Liu Youheng.On the steady-state availability of repairable network［J］.Journal on Communications，1997，18(7):15-19.(in Chinese)

［7］劉愛民，劉有恒.關于可修復系統(tǒng)的MTBF和MTTR［J］.電子學報，1998，26(1):70-72.Liu Aimin，Liu Youheng.On the MTBF and MTTR of repairable system［J］.Acta Electronica Sinica，1998，26(1):70-72.(in Chinese)

［8］Shi Jian，Wang Shaoping.Integrated availability model based on performance of computer networks［J］.Reliability Engineering＆System Safety，2007，92(3):341-350.

［9］Braverman J I，Miller C A，Hofmayer C H，et al.Degradation assessment of structures and passive components at nuclear power plants［J］.Nuclear Engineering and Design.2004，228(1/2/3):283-304.

［10］Torres M A，Ruiz S E.Structural reliability evaluation considering capacity degradation over time［J］.Engineering Structures，2007，29(9):2183-2192.

［11］Reed D A，Lu C D，Mendes C L.Reliability challenges in large systems［J］.Future Generation Computer Systems，2006，22(3):293-302.

［12］周炯槃.通信網理論基礎［M］.北京:人民郵電出版社，1991:20-33.

［13］王少萍.工程可靠性［M］.北京:北京航空航天大學出版社，2000:89-110.

［14］Neufeld E M，Colbourn C J.The most reliable seriesparallel networks［J］.Networks，1985，15(1):27-32.