在真實世界中，多數的網路系統是由處於不同狀態的元件所組成，它們有各種的效能狀態、也可能部份或全部失效，我們稱之為隨機流量網路。網路可靠度的定義是由來源端到終點間處於隨機流量狀態的各元件的最大傳輸量不低於特定需求量的機率。本論文專注於研究現時提供台灣學術界網路連結之用的台灣高等學術網路(TWAREN)國際段的效能。使用有效的評估工具以做出適當決策並改善網路效能是國家高速網路與計算中心的主要工作之一，我們提出了一種修正後的隨機流量網路模型，用來評估透過光通道傳輸資料的 TWAREN 網路可靠度、並做為計算其服務水準的績效指標。本論文研究 TWAREN 由台灣到美國間國際段陸面及海底線路的網路可靠度，並從單起點到單終點、多起點到單終點及多起點到多終點等三種面向及模型分析了解 TWAREN 的效能。並透過我們所研發的最小光路徑(minimal light paths)及演算法、與使用國外的研究先進在數年前所發展的遞迴不交和法(Recursive Sum of Disjoint Products) 來整合分析了解 TWAREN 國際段的整體網路效能。

In real-world, many systems are composed of some units of different states, which have various performance level, and may fully or partial fail which we call it stochastic-flow network (SFN). Network reliability is defined as the probability of delivering a maximal flow of no less than a specified requirement from source to sink. In this dissertation, we like to dedicate on the network reliability of a practical system - Taiwan Advance Research and Education Network (TWAREN), which is Taiwan’s academic research network that mainly provides network communication services for Taiwan’s research and academic society. We propose a modified SFN model to evaluate the network reliability of computer networks where data is transmitted through a light path (LP). It is taken as a performance index to measure the service level of TWAREN. This dissertation studies the network reliability of the international portion of TWAREN from Taiwan to the United States that goes through the submarine and the land surface cable. Using efficient evaluation tools to understand TWAREN’s performance in order to make proper decision and improve its infrastructure is the major tasks of Taiwan’s National High Performance Computing Center (NCHC). We analyze TWAREN in 3 models: 1) single source to single sink, 2) multiple sources to single sink, and 3) multiple sources to multiple sinks, to realize its performance. The problem formulations and SFN models are constructed in this dissertation, and in terms of minimal light paths and the algorithms that developed here, also integrate the Recursive Sum of Disjoint Products, we analyze the whole performance of TWAREN international scope in this paper.

Al-Khateeb, W. and Al-Irhayim, S., Reliability enhancement of complex networks through redundancy scaling, International Conference on Computer and Communication Engineering, Kuala Lumpur, Malaysia, pp.11-13 (2010).
Alexopoulos, C., A note on state-space decomposition methods for analyzing stochastic flow networks. IEEE Transactions on Reliability , 44: 354-7 (1995).
Aven, T., Reliability evaluation of multistate systems with multistate components. IEEE Transactions on Reliability, 34: 473-9 (1985).
Chen, I. and Ito, MR., A study of unreserved backup paths for reliable QoS under single link failure. Computer Communications and Networks, ICCCN, Proceedings of 17th International Conference, St. Thomas, U.S. Virgin Islands, pp.459-464 (2008).
Chunghua Telecommunication(CHT) International. http://www.twgate.net
Cormen, T., Leiserson, C., Rivest, R. and Stein, C., Introduction to algorithms, second edition. MIT Press, pp.145-146 (2001).
Gebre, B.A. and Ramirez-Marquez J.E., Element substitution algorithm for general two-terminal network reliability analyses. IIE Transactions on Reliability, 39: 265-75 (2007).
Haque. A., A study on the design of survivable optical virtual private networks (O-VPN). IEEE Transactions on Reliability, 55: 516-24 (2006).
Ho. P.H.. Spare capacity reprovisioning for shared backup path protection in dynamic generalized multi-protocol label switched networks. IEEE Transactions on Reliability, 57: 551-63 (2008).
Hudson, J.C. and Kapur, K.C., Reliability bounds for multistate systems with multistate components. Operations Research, 33: 153-60 (1985).
Internet2 Network. http://www.internet2.edu
Jane, C.C., Lin, J.S. and Yuan, J., Reliability evaluation of a limited-flow network in terms of minimal cutsets. IEEE Transactions on Reliability, 42: 354-61 (1993).
Koide, T., Shinmori, S. and Ishii, H., Efficient computation of network reliability importance on k-terminal reliability. International Journal of Reliability, Quality and Safety Engineering, 39: 213-26 (2007).
Lee, R.C.T., Tseng, S.S., Chang, R.C. and Tsai, Y.T., Introduction to the design and analysis of algorithms, McGraw-Hill Education (Asia), pp. 167-170, (2005).
Lin, J.S., Jane, C.C. and Yuan, J., On reliability evaluation of a capacitated-flow network in terms of minimal pathsets. Networks, 25: 131-8 (1995).
Lin, Y.K., A simple algorithm for reliability evaluation of a stochastic-flow network with node failure. Computers & Operation Research, 28: 1277-85 (2001a).
Lin, Y.K., Study on the multicommodity reliability of a capacitated-flow network. Computers and Mathematics with Applications, 42: 255-64 (2001b).
Lin, Y.K., Reliability of a stochastic-flow network with unreliable branches & nodes under budget constraints. IEEE Transactions on Reliability, 53: 381-7 (2004).
Lin, Y.K., On a multicommodity stochastic-flow network with unreliable nodes subject to budget constraint. European Journal of Operational Research, 176: 347-60 (2007a).
Lin, Y.K., System capacity for a two-commodity multistate flow network with unreliable nodes and capacity weight. Computers and Operations Research, 34(10): 3043-54 (2007b).
Lin, Y.K., Time version of the shortest path problem in a stochastic-flow network. Journal of Computational and Applied Mathematics, 228: 150-7 (2009).
Lin, Y.K., A stochastic model to study the system capacity for supply chains in terms of minimal cuts. International Journal of Production Economics, 124: 181–7 (2010a).
Lin, Y.K., Reliability evaluation for overall-terminal multistate flow networks with bi-directed arcs. Expert Systems with Applications, 37: 6669-74 (2010b).
Lin, Y.K. and Yeh, C.T., Optimal resource assignment to maximize multistate network reliability for a computer network. Computers and Operations Research, 37(12): 2229-38 (2010).
Lin, Y.K. and Yeh, C.T., Maximizing network reliability for stochastic transportation networks under a budget constraint by using a genetic algorithm. International Journal of Innovative Computing, Information and Control, 7: 7033-50 (2011a).
Lin, Y.K. and Yeh, C.T., Using minimal cuts to optimize network reliability for a stochastic computer network subject to assignment budget. Computers and Operations Research, 38(8): 1175-87 (2011b).
Nakagawa T. Maintenance Theory of Reliability. London: Springer, (2005).
Park, K.I., QOS in Packet Networks. The MITRE Corporation USA: Springer; (2005).
Ramirez-marquez, J.E., Coit, D.W. and Tortorella, M., A generalized multistate-based path vector approach to multistate two-terminal reliability. IIE Transactions on Reliability, 38: 477-88 (2006).
Sharafat, A.R. and Ma’rouzi, O.R., All-terminal network reliability using recursive truncation algorithm. IEEE Transactions on Reliability, 58: 338-47 (2009).
Taiwan Advanced Research and Education Networks (TWAREN). http://www.twaren.net
Wang, S. and Watada, J., Reliability optimization of a series-parallel system with fuzzy random lifetimes. International Journal of Innovative Computing, Information and Control, 5: 1547-58 (2009).
Xue, J., On Multistate System Analysis. IEEE Transactions on Reliability, 34: 329-37 (1985).
Xie, M., Dai, Y.S. and Poh, K.L., Computing System Reliability Models and Analysis, Kluwer Academic/Plenum Publishers, New York, (2004).
Yarlagadda, R. and Hershey, J., Fast algorithm for computing the reliability of communication network. International Journal of Electronics, 70: 549-64 (1991).
Yeh, F.M., Lu, S.K., and Kuo, S.Y., OBDD-Based Evaluation of k-terminal network reliability. IEEE Transactions on Reliability, 51: 443-51 (2002).
Zuo, M.J., Tian. Z. and Huang, H.Z., An efficient method for reliability evaluation of multistate networks given all minimal path vectors. IIE Transactions, 39: 811-7 (2007).