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

姜 禹 胡愛群

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

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

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

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

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

1 效能模型

1.1 初始故障率模型

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

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

1.2 使用期故障率模型

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

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

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

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

1.3 節點和鏈路效能模型

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

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

若故障率α與t無關，則

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

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

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

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

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

1.4 網絡效能模型

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

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

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

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

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

2 應用實例

對于不可修復系統，利用圖2給出的無向網絡G1 對本文算法進行說明.節點 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)得節點vi的MTBF為

圖2 無向網絡G1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結語

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

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］劉愛民，劉有恒.可修復網絡穩態可用度分析［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］劉愛民，劉有恒.關于可修復系統的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.