具有可靠度限制條件之網路設計

Abstract

如何連線是網路設計中的一個重要問題。連線的好壞影響一個網路作業的性能，像時 間延遲（time delay），單位時間內能處理的輸出入量（throughput），以及可靠度 （reliability） 等。如何以最少的金錢建立一個合乎我們需求的網路就稱為一個〞 網路最佳化問題〞。 這個問題非常龐大、複雜，因此這個問題常被分成幾個較小的問題（subproblems） 來討論。本論文所探討的網路最佳化問題僅考慮可靠度一個限制條件，但即使是這樣 ，因為計算網路可靠度本身即是一個非常難的問題（NP-hard） ，所以對這樣一個僅 考慮可靠度限制條件的網路最佳化問題，至今仍沒有一個適用大型網路的方法來尋得 真正的最佳解。 可靠度有非常多種度量方法，例如原點－終點可靠度（s-t reliability） ，局部可 靠度（K-terminal erliability），和整體可靠度（overall reliability） 等。本 論文僅考慮整體可靠度。我們所考慮的模式假設每個網路節點（node）的位置都定好 ，任意兩點連線所需的花費和可以工作的機率也已估計好，每條連線都是雙向通行（ bidirectional） ，同時每兩點之間最多可連一條線。我們的目標乃是以最少費用建 立一網路，使其整體可靠度不能低於某一個程度。 我們提出一種方法可以很快地算出一個每條連線良好之機率均相同的網路，其連線數 目在一定限制之下可達到的可靠程度。如此我們可以很快地淘汰一些不需要的網路， 再根據節點連線數（node degree） 和網路連線數設計一種分解法（decomposition method）來解決這個問題。最後我們實際測試一些例子並分析實驗的結果。