通訊網路之可靠度評估

Abstract

給予一網路及其中各連結 (link) 之障礙或擁塞的發生機率，端點可靠度 代表網路中某兩節點間建立或維持通訊成功的機率值。本論文分別針對交 換網路、階層式網路、以及非同步傳輸模式 (ATM) 之虛擬路徑 (Virtual Path, VP) 網路提出了數個高效率的端點可靠度分析演算法。針對交換網 路，首先本論文評估了兩類用以計算端點可靠度的分割 (partition) 技 術在所需計算時間以及所產生子問題數目方面的效率，它們分別是路徑式 (Path-Based, PB) 與切割式 (Cut-Based,CB) 分割。實驗結果顯示在大 部份的例子中，CB的表現較PB好。我們並且進一步針對CB方法的缺點利用 網路簡化 (network reduction) 技術加以改進。結果顯示，結合網路簡 化技術的CB方法在所有例子中的效率表現均較PB(結合網路簡化技術)好。 接著，我們即以此CB方法為基礎，針對階層式網路提出一高效率的CB* 演 算法。藉著利用網路分解 (network decomposition) 技術，CB* 不僅大 幅提高計算效率，且於網路組態更改時可將分析端點可靠度所需的重新計 算工作減至最小。最後，針對ATM VP網路，本論文提出了兩個用以評估兩 VP終點間可靠度的演算法。這兩個演算法分別利用了PB與CB的分割技術。 實驗結果顯示，與現有演算法比較，這兩個方法大幅減少了所需的計算時 間，使得即時計算ATM網路的可靠度此一目標變得可行。 Terminal-pair Reliability (TR) determines the probabilistic reliability between two nodesof a network, given failure (blocking) probabilities of all links. The goal of the thesis is topropose efficient algorithms for the computation of TR in three types of networks: theswitched networks, the hierarchical networks, and the Asynchronous Transfer Mode (ATM)Virtual Path (VP) networks. For the first type of networks, the thesis first provides anassessment of two categories of partition techniques for computing TR, namely thePath-Based (PB) and Cut-Based (CB) algorithms, in terms of the number of subproblemsand computation time. Results show the superiority of the CB algorithm over the PBalgorithm with respect to the computation time for most benchmarks and random networks.Furthermore, we observe that a refinement of the CB algorithm using network reductionprofoundly outperforms the PB algorithm (with reduction) for all benchmarks and random networks. Based on the CB algorithm, the thesis then presents an efficient TR algorithm,called Cut-Based star (CB*), for hierarchical networks. By using the networkdecomposition method, the CB* algorithm not only drastically reduces the computationalcomplexity but also results in minimal recomputation of TR should the networkconfiguration change. Finally, for the third type of networks, the ATM VP networks, thethesis presents two efficient algorithms for the computation of TR between two VPterminators by means of variants of PB and CB algorithms. The two algorithms and theirpromising results consequently facilitate the real-time computation of the reliability orrobustness of ATM VP networks.