基于NP問題的環網可靠性分析與計算方法

姚 津，孫 乾，郜書洋，陳 華，萬 君

（國核自儀系統工程有限公司，上海 200241）

網絡可靠性是考核網絡性能的重要指標。

1 網絡可靠性概念及相關定義

1.1 網絡可靠性

在許多工程項目中，網絡作為承載各個網絡終端之間數據傳輸和交換的載體起到了重要作用，而網絡可靠性是衡量網絡性能好壞的重要指標之一。它規定了在出現網絡節點或?。ü濣c與節點間的連接路徑）出現失效的情況下，仍能保證網絡連通（各個網絡終端間數據可達）的時間（或概率）。

若在某種網絡節點或弧失效情況下該網絡仍能保證連通，則將這種情況稱為網絡可靠的可用路集。而一種能夠保證網絡連通的最少節點和弧的情況，則稱之為最小路集。網絡可靠性的計算則可以看成是可用路集的合集。

1.2 環形網絡

在實際的網絡中，各組成部分對應的實際設備類型一般如下：

網絡終端——數據產生或接收的終端，往往具備數據處理與顯示的能力，如計算機、控制器等，是網絡服務的對象，以保證其功能正常。

圖1 環形網絡示意圖Fig.1 Schematic diagram of ring network

網絡節點——數據交換與轉發的中間設備，通過各種方式保證數據能正確地在網絡終端間傳輸，包括交換機、路由器等網絡交換設備。

弧——一個網絡拓撲中用于連接兩個相鄰網絡節點的路徑，提供網絡連通的物理鏈路，包括雙絞線、光纖等可用于網絡連接的線纜。

如圖1所示為一個采用了生成樹協議（Spanning Tree Protocol）控制的環形網絡拓撲圖，其包含若干個網絡終端設備——計算機，分別連接至對應的網絡節點——交換機上，交換機采用規格一致的連接線纜進行端對端連接。

以各個網絡終端之間鏈路可達作為判斷網絡連通的標準，則環網在出現網絡節點失效的情況下是不連通的。因此，環網必須保證節點可靠。

但是，由于環網使用STP實現了路徑的冗余，因而允許在出現單弧故障的情況下仍能實現網絡連通。相比一般的單線型連接網絡，環網通過該種方式能夠實現更高的網絡可靠性。

1.3 冗余環網

如圖2所示，為一個典型的雙環網冗余網絡。相比單環網，其終端到兩個環網的交換機均有連接。兩個環網之間為獨立工作（可靠性互不相關）。因此，在以保證各個網絡終端間鏈路可達的前提下，任意一個環形網絡故障均不會引起網絡不可用的狀態，在環形網絡的基礎上能夠進一步提高網絡可靠性。

2 冗余環網的可靠性計算模型建立

2.1 基于單網失效情況的冗余網絡可靠性計算

一個由兩個相互獨立的網絡組成的冗余網絡，按照概率加減法的概念，其網絡可用的定義可以等同為全概率減去兩個網絡均失效的概率，則其可靠性概率為

其中，R為全網可靠性概率；pc1為冗余網絡1故障概率；pc2為冗余網絡2故障概率。

圖2 冗余環網示意圖Fig.2 Schematic diagram of redundant ring network

圖3 冗余環網示意圖2Fig.3 Schematic diagram2 of redundant ring network

2.2 基于單節點或單弧失效情況的單環網可靠性計算模型建立

考慮一個由n個網絡節點組成的環形網絡，將節點與弧抽象化后如圖3所示。

該網絡可靠性的求解問題是一個典型的非確定性多項式（Non-Deterministic Polynomial）求解問題。可以在有限的時間內窮舉每一種能夠連通的網絡情況，并將其相加以得到最后的可靠性數據。

按照環網連通性定義，當出現任一節點故障時網絡不可用，但出現單一弧的故障時網絡仍能保持連通。因此，其最小路集為單一弧故障時的網絡情況，而可用路集可以表示成最小路集（單弧故障、無節點故障）與無故障路集（無節點故障、無弧故障）的概率之和?？紤]節點失效和弧失效的情況，其可靠性為

其中，Rc為全網可靠性；pLi為弧Li失效的概率；pNi為節點Ni失效的概率。

2.3 節點和弧的可靠性

單節點和單弧的可靠性取決于網絡交換設備和所用線纜的質量?？紤]到各個設備個體之間的差異性，在計算時對統一規格的產品可使用廠家提供的MTBF、產品壽命周期等可靠性參數進行近似計算。對于處于“浴盆”曲線穩定期期間的產品，其MTBF數據與失效概率的關系表示為

其中，P為產品失效概率；MTBF為設備廠家提供的MTBF參數；R為產品近似的可靠性概率。

2.4 根據產品MTBF數據推導的冗余環網可靠性概率計算公式

根據上述得出的公式（1）～（4）并逐級代入，可推導冗余環網可靠性關于節點數量和節點MTBF、弧MTBF的數據的關系。

按照網絡采用統一規格的節點設備和連接線纜，對其單點和單弧可靠性作統一處理后，可得到

其中，R(n)為具備n個節點的冗余環網的可靠性；n為節點數量；MTBFline為弧的MTBF數據；MTBFnode為節點的MTBF數據。

3 應用場景示例

在某核電站數字化儀控系統項目中，其數據處理與顯示系統的監控網絡設計采用了雙環網的設計。兩個環網的功能獨立、互不影響，網絡交換機采用了7個統一型號的工業交換機，連接線纜采用統一規格型號的光纖。并且，其交換機采用了類似STP的技術進行環網的冗余路徑控制，其功能和結構符合第2章中所建立的環網模型。

現已知該型號交換機的廠家MTBF數據為371000 h；光纖的MTBF數據為175200 h。

則 根 據 公 式（5）， 現 令 n=7，MTBFnode =371000，MTBFline=175200，代入后，可解得

附上計算的中間過程數，見表1可靠性概率計算表。

由表1中數據可知，單網情況不考慮啟用STP等環網冗余路徑控制協議的情況下，其每小時失效概率將近6‰；啟用了環網冗余路徑控制后能夠降低30%左右的失效概率，使失效概率達到4‰；而啟用了雙網后其失效概率則僅為0.00000016%，使網絡可靠性達到99.999999%以上。

若將MTBFnode和MTBFLine作為常數，建立可靠性R關于節點數量的函數R（n），通過分析其單調性，可以得知R（n）為單調遞減函數，這意味著：

1）全網可靠性隨著節點數量的增多而減小，越多的節點意味著越大的失效概率。

表1 可靠性概率計算示例表Table 1 Reliability probability calculation example table

2）環網冗余路徑控制協議（如STP）其能起到的作用也隨著n的增加而減小。

4 結束語

為了方便模型建立和簡化計算，本文討論的可靠性計算方法是建立在以下3個假設基礎上展開的：

1）以節點設備、弧作為可靠性的最小顆粒度單元，該顆粒度以下所發生的故障均應包含在該節點設備或弧的可靠性數據內。

2）各個節點設備、弧的故障是獨立事件，一個設備或線纜的故障不會影響其他設備或線纜。

3）統一規格、型號的產品其可靠性數據是一致的。本文在討論時統一假定了所有設備處于其產品生命周期中的“浴盆”曲線穩定期。

然而，在實際的工程應用中，由于產品使用時的負荷、業務場景、設備模塊更換、工作時間等均有所不同，即使是一個規格的產品也存在可靠性差異。因此，本文給出的計算方法是實際網絡可靠性的近似計算，在實際設計和集成時應考慮潛在的偏差。

另外，除第3章中所提到的業務場景外，在明確可靠性要求的情況下，還可根據已確定的網絡拓撲來測算需要選型的網絡設備或線纜的可靠性數據，以幫助明確產品選型在可靠性方面的要求；而且，由于可靠性與設備節點數量存在的單調關系，可以推算能夠滿足可靠性要求的節點上限，以幫助確定網絡系統的拓展能力。