網路管理中可靠度的有效計算方法

Abstract

在網路管理中，網路的可靠度分析已經廣泛地被注意，特別是端點間可靠度 (Terminal-pair Reliability，TR）及可靠度邊際效益 (Marginal Reliability Importance，MRI)是兩個非常重要的測量值。當給定網路所有連線的故障率，TR決定在此網路中兩端點間可連通的機率值；而MRI則是指改進某一條連線的成功率時，TR隨之改變的速率值，它反映了每一條連線對網路可靠度的貢獻量。本論文針對交換網路和ATM VP網路的端點間可靠度計算與Reducible+網路的可靠度邊際效益計算分別提出有效的演算法。從文獻中我們知道利用網路簡化技術可以有效地計算交換網路的TR；然而，目前的簡化通則只限制於一些簡單的法則。在本論文中，我們首先提出一個新的簡化法則，稱之為三角簡化法，這個法則是將含有三角子圖的網路轉換成另一個TR值相等的網路圖，這個新的網路圖是將原本網路中的三角子圖之底移除，並給於此三角子圖兩個邊新的故障率值。使用三角簡化法則的TR演算法來計算精簡格子網路（simplified grid network）的TR值，能減少所產生的子問題個數達O(((1+SQR(5))/2)^n)倍；我們更進一步透過實驗來驗證三角簡化法的效率，實驗結果顯示：使用了三角簡化法則在計算測試基準網路與隨機產生的網路之TR值時，能大幅地降低所產生的子問題個數，進一步減少所需的計算時間。對於ATM VP網路，由於計算的複雜度與VP間故障的相依性，使得現有的TR演算法都不適用於計算ATM VP網路的TR值，因此本論文提出兩個有效的演算法，分別利用了路徑基礎和切集基礎的TR分割技術來計算兩個VP端點間的TR值。經由實驗的結果顯示，與現有演算法作比較，這兩個演算法能大幅地減少計算所需的時間，使得即時評估ATM VP網路的可靠度變得可行。一個網路若可以經由簡化法則（含三角簡化法則）簡化成一個來源—目的網路時，這種網路定義為reducible+網路。為了有效率地計算reducible+網路中所有連線的可靠度邊際效益，本論文也提出一個兩步驟的演算法，第一個步驟先將網路簡化成來源—目的網路；在第二個步驟中，倒推簡化程序來計算所有連線的可靠度邊際效益。使用這個演算法可以在線性時間內計算出reducible+網路中所有連線的可靠度邊際效益。

The analysis of network reliability has been given considerable attention in network management. In particular, Terminal-pair Reliability (TR) and Marginal Reliability Importance (MRI) are two major merits in network design problem. TR determines the probabilistic reliability between two nodes (the source and sink) of a network, given failure probabilities of all links. MRI of a link with respect to TR has been defined as the rate to which TR changes in association with the modification of the success probability of the link. The thesis aims to propose efficient TR algorithms for the switched networks and ATM VP networks, and an efficient algorithm for the computation of MRI of a given reducible+ network. For the switched networks, it has been shown that TR can be efficiently by means of the network reduction technique. Existing reduction axioms, unfortunately, are limited to trivial rules. In the thesis, we propose a novel reduction axiom, referred to as triangle reduction. The triangle reduction axiom transforms a graph containing a triangle subgraph to that excluding the base of the triangle. With triangle reduction, the number of subproblems generated by partition-based TR algorithms, for simplified grid networks, can be reduced to O(((1+SQR(5))/2)^n). The thesis further provides an assessment of the effectiveness of triangle reduction on partition-based TR algorithms with respect to the number of subproblems and computation time through experimenting on published benchmarks and random networks. Experimental results demonstrate that, incorporating triangle reduction, the path-based (cut-based) partition TR algorithm yields a substantially reduced number of subproblems and computation time for all (most of the) benchmarks and random networks. For ATM VP networks, existing TR algorithms are shown to be unviable for ATM VP networks owing to either high complexities or failure dependency among VPs. The thesis presents two efficient algorithms for the computation of TR between two VP terminators by means of variants of path-based and cut-based partition methods. The two algorithms and their promising results consequently facilitate the real-time computation of the reliability or robustness of ATM VP networks. Networks which can be fully reduced to source-sink networks by the triangle reduction axiom, in addition to the six reduction rules, are defined as reducible+ networks. For efficient computation of MRI for reducible+ networks, this thesis further proposes a Two-Phase algorithm. The algorithm performs network reduction in the first phase, and backtracks the reduction steps and computes MRIs in the second phase. The Two-Phase algorithm, as will be shown, yields a linearly bounded complexity for the computation of MRI for reducible+ networks.