# Evaluation of Network Reliability for Computer Networks with Multiple Sources

Authors: Yi-Kuei Lin; Louis Cheng-Lu Yeng
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

Evaluating the reliability of a network with multiple sources to multiple sinks is a critical issue from the perspective of quality management. Due to the unrealistic definition of paths of network models in previous literature, existing models are not appropriate for real-world computer networks such as the Taiwan Advanced Research and Education Network (TWAREN). This paper proposes a modified stochastic-flow network model to evaluate the network reliability of a practical computer network with multiple sources where data is transmitted through several light paths (LPs). Network reliability is defined as being the probability of delivering a specified amount of data from the sources to the sink. It is taken as a performance index to measure the service level of TWAREN. This paper studies the network reliability of the international portion of TWAREN from two sources (Taipei and Hsinchu) to one sink (New York) that goes through a submarine and land surface cable between Taiwan and the United States.


---

## Body

## 1. Introduction

The issue of the QoS [1] of networks has been studied in the past decades. QoS is an important element of understanding the efficiency of real-world computer networks. It refers to the ability to provide a predictable, consistent data transfer service and the ability to satisfy customers’ application needs while maximizing the use of network resources, especially a network reliability analysis. One of the traditional issues in this area of network reliability research is known as the source-sink (s-t) network reliability problem [2–16], which some articles refer to as two-terminal network reliability (TTNR) [14, 15]. In TTNR analyses, it is interesting to compute the network reliability in relation to the connecting paths between two specific network nodes, usually the source-sink (s-t). Generally speaking, people are interested in obtaining the probability that the source connects the sink. Some researchers extend the study of TTNR to the k-terminal network reliability (KTNR) problem [17, 18], which contains at least one path from the source node to other k nodes. Besides TTNR and KTNR, there is an all-terminal network reliability (ATNR) (also called overall or uniform network reliability), which is calculated from the probability that each and every node in the network is connected to each other [19, 20]. In a binary-state flow network, the capacity of each arc has two levels 0 and a positive integer. System with various states is called a stochastic model [21–23]. For a more realistic system, the arc should have several possible states/capacities, and such a network is named a stochastic-flow network (or multistate network). The previous problems, TTNR, KTNR, and ATNR, are discussed for binary-state flow networks. However, this paper addresses the evaluation of the network reliability of a stochastic-flow network with multiple sources.The Taiwan Advanced Research and Education Network (TWAREN) [24] is Taiwan’s academic research network that mainly provides network communication services for Taiwan’s research and academic society. It also offers a tunnel between Taiwan and the United States to connect the global research network through a land surface line and the Asia Pacific region’s submarine cable. Since TWAREN’s resources (i.e., bandwidth) are limited, it is a critical issue to find a technique to optimize its utility. Using efficient evaluation tools to understand TWAREN’s performance to improve its infrastructure is one of the major tasks of Taiwan’s National High Performance Computing Center (NCHC). To measure TWAREN’s capability, network analysis is a useful tool. For a practical computer network, the transmission media (physical lines such as fiber optics or coaxial cables) may be modeled as arcs, while transmission facilities (switches or routers) may be modeled as nodes. In particular, the capacity of each arc should be stochastic due to the possibility of failure, partial failure, or maintenance. Thus, the computer network characterized by such arcs also has stochastic capacities and it is a typical stochastic-flow network [2–13, 25, 26]. Network reliability evaluation of a stochastic-flow network has been studied as a performance index for decades [2–13, 25, 26]. Most of these studies examined the network reliability from source node s to sink node t in terms of minimal paths (MPs), in which an MP is a path with proper subsets which are no longer paths [2–4, 6–9]. This implies that an MP is a set that connects an (s, t) pair, here not limited to one (s, t) pair, without any surplus arcs from the perspective of the network topology.Those previous studies assume that data can be sent through all possible MP froms to t according to the network topology, where each MP is composed of some physical lines (arcs). However, in a real computer system, data can only be sent through some unique light paths (LPs) between specific node pairs, where an LP is a virtual tunnel between two end-to-end nodes which combined by some segments (i.e., arcs or lines) and nodes; however, an MP is a path that connects a specific source and a specific sink, while an LP can be a link between any two nodes (not limited to source and sink pair). That is, data may be transmitted from source node s to sink node t via more than one LP. In particular, any segments that LP goes through cannot be divided during transmission. Therefore, the previous studies [2–4, 6–9] based on MP to transmit data are not appropriate for TWAREN. In TWAREN, each LP is composed of a set of light path segments (LPSs) linking two nodes. In particular, each physical line can be divided into several LPS, and each LPS belongs to only one LP. Since TWAREN involves the light path, which cannot be divided through any part of its nodes or arcs during transmission, this kind of network model is different than the MP concept described in [2–4, 6–9]. Therefore, we implement a minimal light path (MLP) concept to find all LPs to evaluate TWAREN’s network reliability. In this paper, the MLP is defined as a series of nodes and LPSs, from source node to sink node, which contains no cycle.A revised stochastic-flow network with multiple sources is constructed to model the TWAREN in terms of LP. The difference of single source and multiple sources is that previous one only dedicates on the network reliability between one source and one sink. But in real world, system may transfer the real time data to the sink that exceed the total capacity of LPS which are beside the single source node. That is, we need to transfer data from at least two source nodes, where the data from different source might influence each other, the theory that developed in traditional one source and one sink not applicable here. In generally, we have to transfer the real-time data from multiple sources to one sink to handle the practical worlds’ data transmission. Therefore we consider multiple sources and implement the new technique in this paper to realize the operation of real system instead of single source. Besides, we need to deal with the assignment of multiple sources and the flow conflict on the intersectional arcs. The two-source case is firstly addressed for convenience. A general case with multiple sources can be extended by the proposed algorithm. Then we can evaluate the network reliability for the international part of TWAREN whose tunnel mainly connects to the global academic research network, especially the Internet2 Network [27]. Taiwan’s largest network service provider (NSP), Chunghwa Telecom (CHT) [28], integrates those NSPs that the lines pass through to organize the whole portion of TWAREN’s international infrastructure in two areas: on the land surface of both Taiwan and the United States and in the under-sea areas of the Asia Pacific, including the Japan-US submarine cable that disconnected when it was hit by the earthquake and tsunami in Japan on March 11th 2011. Nakagawa [29] has mentioned the influence of that earthquake regarding reliability, so we study this disaster’s effect as well. In fact, when a line breaks, the NSP of these pass-through lines will offer serviceable lines as backups; therefore they offer some degree of the network reliability. However, in this study, we only concentrate on the portion that includes the regular lines to determine the factors that affect TWAREN’s network reliability, as the NCHC’s prime task, aside from improving TWAREN’s overall performance, is to anticipate major factors which could fail the regular lines. The issue of the network reliability of the backup line [30–34] has not been considered yet.This paper mainly emphasizes the network reliability that the network can send specified units of data from two source nodes (Taipei city and Hsinchu city) to a single sink node (New York) through TWAREN’s light path. The remainder of this paper is organized as follows. The TWAREN network is introduced in Section2. The research scope, problem formulation, the concept of the minimal light path and the evaluation technique, recursive sum of disjoint of products, (RSDP [9]) are all described in Section 3. Network reliability of TWAREN is evaluated in Section 4. A summary and conclusion are presented in Section 5.


## 2. TWAREN Network

### 2.1. Introduction to TWAREN

TWAREN has been funded by the National Science Council of Taiwan since 1998 and was built by the NCHC. Construction was completed at the end of 2003, and service and operation started in 2004. Today, more than 100 academic and research institutions connect with TWAREN in Taiwan and this number is increasing continuously. As well, since 2005, over 1,000 elementary schools and junior and senior high schools have been using TWAREN’s internal backbone. TWAREN provides network infrastructure for general use but is also an integrated platform for network research. For instance, TWAREN was instrumental in developing applications and network technology such as IPv6, MPLS, VoIP, e-learning, multicast, multimedia, and performance measurement and has supported GRID computing applications such as e-Learning Grid, Medical Grid, and EcoGrid. As promoting Taiwan as an international R&D center is one of NCHC’s objectives, a stable and reliable TWAREN is the foundation to achieve this goal.Many countries fund national research and education network (NREN) infrastructure. TWAREN, Taiwan’s NREN, connects to the international research community through global advanced networks, specifically the Internet2 Network [27] of the United States, the major NREN in the world. Therefore, network reliability analyses of TWAREN will help to continuously improve its infrastructure so it can continue to cooperate and connect globally.


### 2.2. TWAREN’s Light Path

TWAREN is network that connects to the world-wide research network through light path international tunnel. TWAREN’s physical topology is an optical infrastructure and its virtual topology is constructed by connecting light paths and routers. A light path is a tunnel between two sites connected by various cables and is an end-to-end, preallocated optical network resource, according to users’ needs. It allows signals to be delivered sequentially without jitters and congestion. Each light path is generally a 155 Mbps~10 Gbps dedicated channel that transports various applications.Figure1 is the light path international infrastructure that TWAREN leases from CHT, including major sites located at Taipei and Hsinchu in Taiwan, and Los Angeles, Chicago, and New York in the United States. This infrastructure contains the land surface and submarine cable between these cities. Each light path is denoted by LPi where i is the light path number, i=1,2,…,l with l being the number of light path.Figure 1
TWAREN light path between Taiwan and US.Most of these city sites connect to each other with 2.5 Gbps physical line connections, divided into four light path channels at 622 Mb bandwidths. The research scope of this paper is to study the network reliability of the transmission from two sources (Taipei city and Hsinchu city) to the sink node (New York) by means of the light path tunnel.


## 2.1. Introduction to TWAREN

TWAREN has been funded by the National Science Council of Taiwan since 1998 and was built by the NCHC. Construction was completed at the end of 2003, and service and operation started in 2004. Today, more than 100 academic and research institutions connect with TWAREN in Taiwan and this number is increasing continuously. As well, since 2005, over 1,000 elementary schools and junior and senior high schools have been using TWAREN’s internal backbone. TWAREN provides network infrastructure for general use but is also an integrated platform for network research. For instance, TWAREN was instrumental in developing applications and network technology such as IPv6, MPLS, VoIP, e-learning, multicast, multimedia, and performance measurement and has supported GRID computing applications such as e-Learning Grid, Medical Grid, and EcoGrid. As promoting Taiwan as an international R&D center is one of NCHC’s objectives, a stable and reliable TWAREN is the foundation to achieve this goal.Many countries fund national research and education network (NREN) infrastructure. TWAREN, Taiwan’s NREN, connects to the international research community through global advanced networks, specifically the Internet2 Network [27] of the United States, the major NREN in the world. Therefore, network reliability analyses of TWAREN will help to continuously improve its infrastructure so it can continue to cooperate and connect globally.


## 2.2. TWAREN’s Light Path

TWAREN is network that connects to the world-wide research network through light path international tunnel. TWAREN’s physical topology is an optical infrastructure and its virtual topology is constructed by connecting light paths and routers. A light path is a tunnel between two sites connected by various cables and is an end-to-end, preallocated optical network resource, according to users’ needs. It allows signals to be delivered sequentially without jitters and congestion. Each light path is generally a 155 Mbps~10 Gbps dedicated channel that transports various applications.Figure1 is the light path international infrastructure that TWAREN leases from CHT, including major sites located at Taipei and Hsinchu in Taiwan, and Los Angeles, Chicago, and New York in the United States. This infrastructure contains the land surface and submarine cable between these cities. Each light path is denoted by LPi where i is the light path number, i=1,2,…,l with l being the number of light path.Figure 1
TWAREN light path between Taiwan and US.Most of these city sites connect to each other with 2.5 Gbps physical line connections, divided into four light path channels at 622 Mb bandwidths. The research scope of this paper is to study the network reliability of the transmission from two sources (Taipei city and Hsinchu city) to the sink node (New York) by means of the light path tunnel.


## 3. Problem Description and Model Formulation

### 3.1. Problem Description

This paper describes how the probability that a specified amount of data can be sent from Taipei and Hsinchu to New York via TWAREN is measured. This is referred to as network reliability. Also, Figure1 is transformed into Figure 2 which is constructed by the light path segments and nodes.Figure 2
Revised network from Taipei and Hsinchu to New York using light path segments and nodes connection.


### 3.2. Some Definitions

As Figure2 shows, those cities or site devices defined as nodes are denoted by nk, where k=1,2,…,p with p being the number of nodes. For example, Taipei City is n1 and TP-1 is n2. We denote each LPSs as li,j where li,j∈LPi means the jth segment in LPi (j=1,2,…,ri with ri being the number of LPS in LPi). For example, in Figure 2, LP1 is a tunnel from Taipei (n1) to Chicago (n8), which is combined with three LPS l1,1,l1,2, and l1,3, and goes through two nodes n2 (TP-1) and n6 (San Francisco). Its connection sequence is n1↔l1,1↔n2↔l1,2↔n6↔l1,3↔n8. The capacity of each LP is 622 Mb, and each LP is combined by four 155 Mb channels. As each channel is regarded as one unit, there are 4 units for each LPs.The physical line (PL) is the actual optical cable where the LP is located and used for data transmission. For example, LPSl1,3,l4,4,l11,1 is combined in one PL from San Francisco to Chicago, as shown as PL P10 in Figure 3. The capacity of each PL is 2.5 G and is divided into four 622 Mb LP.Figure 3
Physical line connection.The capacity state of an LPS is the same as a PL either when connected or disconnected. Each LPS has two capacity states: 0 units (0 G) and 4 units (622 Mb with four 155 Mb LP), respectively. That is, once the PL fails, all the LPSs that are located in this PL also fail. Those LPSs located in the same PL have the same disconnection probability (or, conversely, the same connection probability). For example, LPSl1,3,l4,4,l11,1 located in one PL P10 have the same disconnection probability.


### 3.3. Model Formulation

The stochastic-flow network evaluation technology developed in [3] is a method that is not suitable to be applied to TWAREN in Figure 2. There are some differences in this problem, since each LPi is combined with LPS li,j, which cannot be divided through any nodes. To create an easier expression, we re-sort all LPSs as a1,a2,…,an, where n is the total number of LPS, instead of li,j. Let G=(A,N,M) be a stochastic flow network where A={ai∣1≤i≤n} is the set of LPS, N is the set of nodes, and M=(M1,M2,…,Mn) with Mi (an integer) being the maximum capacity of each LPS ai. Such a G is assumed to further satisfy the following assumptions.(1)
Each node is perfectly reliable.(2)
The capacity of each LPS is stochastic with a given probability distribution according to historical data.(3)
The capacities of different LPS are statistically independent.Let Taipei be the first source node denoted bys1, and let Hsinchu be the second source node denoted by s2. Then let S={s1,s2}. A minimal light path (MLP) is a series of LPSs from a source node to a sink node, which contains no cycle. In particular, any segment used by LPi cannot be divided during transmission in LPi. That is, each LPS belongs to only one LP. Suppose ml1,ml2,…,mlr are all MLPs from s1 to t and mlr+1,mlr+2,…,mlq are all MLPs from s2 to t.Then, the stochastic flow network can be described by the capacity vector X=(x1,x2,…,xn) and the flow vector F=(f1,f2,…,fq) where xi denotes the current capacity of ai, and fj denotes the current flow on mlj. The following constraint shows that the flow through ai cannot exceed the maximum capacity of ai:(3.1)∑j=1q{fj∣ai∈mlj}≤Mi.
Let the total demand to New York be p. Then demand set Dp={(d1,d2)∣(d1+d2)=p} where d1 and d2 are the demand from Taipei and Hsinchu to New York, respectively. To meet the demand pair (d1,d2), the flow vector F=(f1,f2,…,fq) has to satisfy(3.2)∑j=1rfj=d1,∑j=r+1qfj=d2.
For convenience, let F(d1,d2) = {F∣F satisfy constraints (3.1) and (3.2)}. For each F∈F(d1,d2), the corresponding capacity vector XF=(x1,x2,…,xn) is generated via(3.3)xi=∑j=1q{fj∣ai∈mlj},xi=1,2,…,n.
Let Ω(d1,d2)={XF∣F∈F(d1,d2)} be such capacity vectors, and let Ω(d1,d2),min={X∣X be ≤ with respect to in Ω(d1,d2)} (where Y≤X if and only if yi≤xi for each i=1,2,…,n and Y<X, if and only if Y≤X and yi<xi for at least one i). For convenience, each X∈Ω(d1,d2),min is named a (d1,d2)-MLP in this paper. Suppose all MLPs have been precomputed. All (d1,d2)-MLP can be derived by the following steps.Step 1.
Do the following steps for each(d1,d2)∈Dp.Step 2.
Find all feasible solutionsF=(f1,f2,…,fq) of the constraints (3.1) and (3.2).Step 3.
Transform eachF into XF=(x1,x2,…,xn) via (3.3) to get Ω(d1,d2).Step 4.
Remove the nonminimal ones inΩ(d1,d2) to obtain Ω(d1,d2),min, that is, (d1,d2)-MLP.Step 5.
Next(d1,d2).Step 6.
End.


### 3.4. Network Reliability Evaluation

Network reliabilityRDp is the probability that the system can transmit p units of data to the sink, that is, RDp=∑(d1,d2)∈DpPr{Y∈Ω(d1,d2)∣Y≥X for a (d1,d2)-MLPX}. If {X1,X2,…,Xh} is the set of minimal capacity vectors capable of satisfying any (d1,d2)∈Dp, then network reliability RDp is(3.4)RDp=Pr{⋃v=1hQv},
where Qv={X∣X≥Xv}, v=1,2,…,h. Several methods such as the RSDP algorithm (Algorithm 1) [9], the inclusion-exclusion method (IEM) [10, 25], the disjoint-event method (DEM) [35], and state-space decomposition (SSD) [11, 12] may be applied to compute RDp. The IEM [10, 25] principle is a simple way to calculate network reliability, which basically is similar to the theorem in traditional probability theory that is recursively plus (inclusion) and minus (exclusion) the intersection portion, but easily results in memory overload as there are lots of input data. SSDs [12] are based upon the decomposition method, in which the state space is decomposed into three sets of states: acceptable (A) sets, nonacceptable (N) sets, and unspecified (U) sets, which recursively decompose the U sets into smaller A, N, and U sets to get the whole system reliability in terms of the summation of the reliability of all A sets. Aven [12] proved that somehow SSD has much better performance than IEM [10, 25]. Zuo et al. [9] implemented a new technique RSDP; it calculates one record’s reliability first and then continuously and, respectively, handles another single record that is minus the intersection portion with previous records that those reliability already been calculated, which quite different than the IEM that recursively plus and minus the intersection portions for all records. It has been proved by Zuo et al. [9] that RSDP has better efficiency than SSD [12] and easier than IEM [10, 25]. Therefore, recently most network reliability evaluation articles apply the RSDP to assess the related issue. It calculates the probability of a union with r vectors in terms of the probabilities unions with (r-1) vectors or less by using a special maximum operator [9] “⊕”, which is defined as(3.5)X1,2=X1⊕X2≡(max⁡⁡(x1i,x2i)),fori=1,2,…,n.
For example, if X1 = (2, 2, 1, 1, 0) and X2 = (3, 0, 1, 0, 1), X1,2=X1⊕X2 = (max(2,3), max(2,0), max(1,1), max(1,0), max(0,1)) = (3, 2, 1, 1, 1). The RSDP algorithm is presented as follows.Algorithm 1:RSDP algorithm.
//Calculate the network reliability RDp for all Ω(d1,d2),minfunctionRDp = RSDP(X1,X2,…,Xh)//Input h vectors (X1,X2,…,Xh) and connection probability of each LPSfor i = 1 : hif  i ==1RDp= Pr(X≥Xi);elseTemp_R_1 = Pr(X≥Xi);If  i ==2Temp_R_2 = Pr(X≥ max(X1,Xi)); //max(X1,Xi) = (X1⊕Xi)elsefor j= 1 : i–1Xj = max(Xj,Xi); //max(Xj,Xi) = (Xj⊕Xi)endTemp_R_2 = RSDP(X1,X2,…,Xi-1);endendRDp = RDp + (Temp_R_1) − (Temp_R_2);


## 3.1. Problem Description

This paper describes how the probability that a specified amount of data can be sent from Taipei and Hsinchu to New York via TWAREN is measured. This is referred to as network reliability. Also, Figure1 is transformed into Figure 2 which is constructed by the light path segments and nodes.Figure 2
Revised network from Taipei and Hsinchu to New York using light path segments and nodes connection.


## 3.2. Some Definitions

As Figure2 shows, those cities or site devices defined as nodes are denoted by nk, where k=1,2,…,p with p being the number of nodes. For example, Taipei City is n1 and TP-1 is n2. We denote each LPSs as li,j where li,j∈LPi means the jth segment in LPi (j=1,2,…,ri with ri being the number of LPS in LPi). For example, in Figure 2, LP1 is a tunnel from Taipei (n1) to Chicago (n8), which is combined with three LPS l1,1,l1,2, and l1,3, and goes through two nodes n2 (TP-1) and n6 (San Francisco). Its connection sequence is n1↔l1,1↔n2↔l1,2↔n6↔l1,3↔n8. The capacity of each LP is 622 Mb, and each LP is combined by four 155 Mb channels. As each channel is regarded as one unit, there are 4 units for each LPs.The physical line (PL) is the actual optical cable where the LP is located and used for data transmission. For example, LPSl1,3,l4,4,l11,1 is combined in one PL from San Francisco to Chicago, as shown as PL P10 in Figure 3. The capacity of each PL is 2.5 G and is divided into four 622 Mb LP.Figure 3
Physical line connection.The capacity state of an LPS is the same as a PL either when connected or disconnected. Each LPS has two capacity states: 0 units (0 G) and 4 units (622 Mb with four 155 Mb LP), respectively. That is, once the PL fails, all the LPSs that are located in this PL also fail. Those LPSs located in the same PL have the same disconnection probability (or, conversely, the same connection probability). For example, LPSl1,3,l4,4,l11,1 located in one PL P10 have the same disconnection probability.


## 3.3. Model Formulation

The stochastic-flow network evaluation technology developed in [3] is a method that is not suitable to be applied to TWAREN in Figure 2. There are some differences in this problem, since each LPi is combined with LPS li,j, which cannot be divided through any nodes. To create an easier expression, we re-sort all LPSs as a1,a2,…,an, where n is the total number of LPS, instead of li,j. Let G=(A,N,M) be a stochastic flow network where A={ai∣1≤i≤n} is the set of LPS, N is the set of nodes, and M=(M1,M2,…,Mn) with Mi (an integer) being the maximum capacity of each LPS ai. Such a G is assumed to further satisfy the following assumptions.(1)
Each node is perfectly reliable.(2)
The capacity of each LPS is stochastic with a given probability distribution according to historical data.(3)
The capacities of different LPS are statistically independent.Let Taipei be the first source node denoted bys1, and let Hsinchu be the second source node denoted by s2. Then let S={s1,s2}. A minimal light path (MLP) is a series of LPSs from a source node to a sink node, which contains no cycle. In particular, any segment used by LPi cannot be divided during transmission in LPi. That is, each LPS belongs to only one LP. Suppose ml1,ml2,…,mlr are all MLPs from s1 to t and mlr+1,mlr+2,…,mlq are all MLPs from s2 to t.Then, the stochastic flow network can be described by the capacity vector X=(x1,x2,…,xn) and the flow vector F=(f1,f2,…,fq) where xi denotes the current capacity of ai, and fj denotes the current flow on mlj. The following constraint shows that the flow through ai cannot exceed the maximum capacity of ai:(3.1)∑j=1q{fj∣ai∈mlj}≤Mi.
Let the total demand to New York be p. Then demand set Dp={(d1,d2)∣(d1+d2)=p} where d1 and d2 are the demand from Taipei and Hsinchu to New York, respectively. To meet the demand pair (d1,d2), the flow vector F=(f1,f2,…,fq) has to satisfy(3.2)∑j=1rfj=d1,∑j=r+1qfj=d2.
For convenience, let F(d1,d2) = {F∣F satisfy constraints (3.1) and (3.2)}. For each F∈F(d1,d2), the corresponding capacity vector XF=(x1,x2,…,xn) is generated via(3.3)xi=∑j=1q{fj∣ai∈mlj},xi=1,2,…,n.
Let Ω(d1,d2)={XF∣F∈F(d1,d2)} be such capacity vectors, and let Ω(d1,d2),min={X∣X be ≤ with respect to in Ω(d1,d2)} (where Y≤X if and only if yi≤xi for each i=1,2,…,n and Y<X, if and only if Y≤X and yi<xi for at least one i). For convenience, each X∈Ω(d1,d2),min is named a (d1,d2)-MLP in this paper. Suppose all MLPs have been precomputed. All (d1,d2)-MLP can be derived by the following steps.Step 1.
Do the following steps for each(d1,d2)∈Dp.Step 2.
Find all feasible solutionsF=(f1,f2,…,fq) of the constraints (3.1) and (3.2).Step 3.
Transform eachF into XF=(x1,x2,…,xn) via (3.3) to get Ω(d1,d2).Step 4.
Remove the nonminimal ones inΩ(d1,d2) to obtain Ω(d1,d2),min, that is, (d1,d2)-MLP.Step 5.
Next(d1,d2).Step 6.
End.


## 3.4. Network Reliability Evaluation

Network reliabilityRDp is the probability that the system can transmit p units of data to the sink, that is, RDp=∑(d1,d2)∈DpPr{Y∈Ω(d1,d2)∣Y≥X for a (d1,d2)-MLPX}. If {X1,X2,…,Xh} is the set of minimal capacity vectors capable of satisfying any (d1,d2)∈Dp, then network reliability RDp is(3.4)RDp=Pr{⋃v=1hQv},
where Qv={X∣X≥Xv}, v=1,2,…,h. Several methods such as the RSDP algorithm (Algorithm 1) [9], the inclusion-exclusion method (IEM) [10, 25], the disjoint-event method (DEM) [35], and state-space decomposition (SSD) [11, 12] may be applied to compute RDp. The IEM [10, 25] principle is a simple way to calculate network reliability, which basically is similar to the theorem in traditional probability theory that is recursively plus (inclusion) and minus (exclusion) the intersection portion, but easily results in memory overload as there are lots of input data. SSDs [12] are based upon the decomposition method, in which the state space is decomposed into three sets of states: acceptable (A) sets, nonacceptable (N) sets, and unspecified (U) sets, which recursively decompose the U sets into smaller A, N, and U sets to get the whole system reliability in terms of the summation of the reliability of all A sets. Aven [12] proved that somehow SSD has much better performance than IEM [10, 25]. Zuo et al. [9] implemented a new technique RSDP; it calculates one record’s reliability first and then continuously and, respectively, handles another single record that is minus the intersection portion with previous records that those reliability already been calculated, which quite different than the IEM that recursively plus and minus the intersection portions for all records. It has been proved by Zuo et al. [9] that RSDP has better efficiency than SSD [12] and easier than IEM [10, 25]. Therefore, recently most network reliability evaluation articles apply the RSDP to assess the related issue. It calculates the probability of a union with r vectors in terms of the probabilities unions with (r-1) vectors or less by using a special maximum operator [9] “⊕”, which is defined as(3.5)X1,2=X1⊕X2≡(max⁡⁡(x1i,x2i)),fori=1,2,…,n.
For example, if X1 = (2, 2, 1, 1, 0) and X2 = (3, 0, 1, 0, 1), X1,2=X1⊕X2 = (max(2,3), max(2,0), max(1,1), max(1,0), max(0,1)) = (3, 2, 1, 1, 1). The RSDP algorithm is presented as follows.Algorithm 1:RSDP algorithm.
//Calculate the network reliability RDp for all Ω(d1,d2),minfunctionRDp = RSDP(X1,X2,…,Xh)//Input h vectors (X1,X2,…,Xh) and connection probability of each LPSfor i = 1 : hif  i ==1RDp= Pr(X≥Xi);elseTemp_R_1 = Pr(X≥Xi);If  i ==2Temp_R_2 = Pr(X≥ max(X1,Xi)); //max(X1,Xi) = (X1⊕Xi)elsefor j= 1 : i–1Xj = max(Xj,Xi); //max(Xj,Xi) = (Xj⊕Xi)endTemp_R_2 = RSDP(X1,X2,…,Xi-1);endendRDp = RDp + (Temp_R_1) − (Temp_R_2);


## 4. Case Study: TWAREN between Taiwan and the US through the Light Path

### 4.1. Level of Demand and MLP from Taipei and Hsinchu to New York

To calculate TWAREN’s network reliability from Taipei and Hsinchu to New York, there must be a reasonable demand level. For each arc’s capacity, each LP occupies a bandwidth 622 Mb, and each 622 Mb bandwidth has four 155 Mb channels. We regard each 155 Mb as one unit. Therefore, there are four units in each 622 Mb LP channel.Let the total demand bep=20 units, that is, 5 × 622 Mb = 3,110 Mb. For Ω(d1,d2),min  the demand set D20={(20,0),(16,4),(12,8),(8,12),(4,16),(0,20)}, we try to evaluate RD20=∑(d1,d2)∈D20Pr{Y∈Ω(d1,d2)∣Y≥Xfora(d1,d2)-MLP X}. In these cases, there are 10 MLPs from n1 (Taipei) to n9 (New York) as Table 1(a) and 10 MLPs from n13 (Hsinchu) to n9 (New York) as shown in Table 1(b).Table 1
(a) All MLPs from Taipei (n1) to New York (n9). (b) All MLPs from Hsinchu (n13) to New York (n9).
(a)MLP no.Light paths combinationNodes & LPS combination flowml1Taipei→LP1→Chicago→LP10→New Yorkn1→l1,1→n2→l1,2→n6→l1,3→n8→l10,1→n9ml2Taipei→LP1→Chicago→LP13→New Yorkn1→l1,1→n2→l1,2→n6→l1,3→n8→l13,1→n9ml3Taipei→ LP4→Chicago→LP10→New Yorkn1→l4,1→n2→l4,2→n5→l4,3→n6→l4,4→n8→l10,1→n9ml4Taipei→LP4→Chicago→LP13→New Yorkn1→l4,1→n2→l4,2→n5→l4,3→n6→l4,4→n8→l13,1→n9ml5Taipei→LP3→New Yorkn1→l3,1→n2→l3,2→n3→l3,3→n7→l3,4→n9ml6Taipei→LP2→Los Angeles→LP12→New Yorkn1→l2,1→n2→l2,2→n3→l2,3→n4→l2,4→n7→l12,1→n9ml7Taipei→LP2→Los Angeles→LP11→Chicago→LP10→New Yorkn1→l2,1→n2→l2,2→n3→l2,3→n4→l2,4→n7→l11,2→n6→l11,1→n8→l10,1→n9ml8Taipei→LP2→Los Angeles→LP11→Chicago→LP13→New Yorkn1→l2,1→n2→l2,2→n3→l2,3→n4→l2,4→n7→l11,2→n6→l11,1→n8→l13,1→n9ml9Taipei→LP1→Chicago→LP11→Los Angeles→LP12→New Yorkn1→l1,1→n2→l1,2→n6→l1,3→n8→l11,1→n6→l11,2→n7→l12,1→n9ml10Taipei→LP4→Chicago→LP11→Los Angeles→LP12→New Yorkn1→l4,1→n2→l4,2→n5→l4,3→n6→l4,4→n8→l11,1→n6→l11,2→n7→l12,1→n9(b)MLP no.Light paths combinationNodes & LPS combination flowml11Hsinchu→LP5→Chicago→LP10→New Yorkn10→l5,1→n3→l5,2→n2→l5,3→n5→l5,4→n6→l5,5→n8→l10,1→n9ml12Hsinchu→LP5→Chicago→LP13→New Yorkn10→l5,1→n3→l5,2→n2→l5,3→n5→l5,4→n6→l5,5→n8→l13,1→n9ml13Hsinchu→LP7→New Yorkn10→l7,1→n3→l7,2→n4→l7,3→n7→l7,4→n9ml14Hsinchu→LP6→Los Angeles→LP12→New Yorkn10→l6,1→n3→l6,2→n7→l12,1→n9ml15Hsinchu→LP6→Los Angeles→LP11→Chicago→LP10→New Yorkn10→l6,1→n3→l6,2→n7→l11,2→n6→l11,1→n8→l10,1→n9ml16Hsinchu→LP6→Los Angeles→LP11→Chicago→LP13→New Yorkn10→l6,1→n3→l6,2→n7→l11,2→n6→l11,1→n8→l13,1→n9ml17Hsinchu→LP8→Los Angeles→LP12→New Yorkn10→l8,1→n3→l8,2→n7→l12,1→n9ml18Hsinchu→LP8→Los Angeles→LP11→Chicago→LP10→New Yorkn10→l8,1→n3→l8,2→n7→l11,2→n6→l11,1→n8→l10,1→n9ml19Hsinchu→LP8→Los Angeles→LP11→Chicago→LP13→New Yorkn10→l8,1→n3→l8,2→n7→l11,2→n6→l11,1→n8→l13,1→n9ml20Hsinchu→LP5→Chicago→LP11→Los Angeles→LP12→New Yorkn10→l5,1→n3→l5,2→n2→l5,3→n5→l5,4→n6→l5,5→n8→l11,1→n6→l11,2→n7→l12,1→n9


### 4.2. Probability of All LPSs Breaking

To compute the connection probability of each PL, we use the disconnection data from 2008 through 2011. The longest duration of every break for each physical line during the 168 hours of every week is used to determine the disconnection probability of each line. For example, as the physical lineP10 from San Francisco to Chicago broke for 403 minutes on 2010/5/25, its connection probability is (168 × 60 − 403)/(168 × 60) = 0.90. Therefore, its disconnection probability is (1 − 0.9) = 0.1. All the LPSs l1,3,l4,4 and l11,1 located in this physical line P10 have the same disconnection probability of 0.1.Table2 shows all LPSs’ connection probability after screening all physical lines’ disconnection records and selecting the longest broken time for each. These breaks include disabled card devices, circuit failures, and breaks from March 11, 2011 Japanese earthquake and tsunami that caused the physical submarine line P8 to break. This line uses a submarine cable connection between TP-3 and Los Angeles. Artificial devices, short circuits, and natural disasters simultaneously influence TWAREN’s network reliability from Taipei and Hsinchu to New York. Since each failure of a node device has been included and recorded in the physical line’s disconnection record, each node is supposed to be perfect with a reliability of 1. For computational convenience, as described in Section 3.3, we converted LPS li,j by using ai and the probability of ai, as Table 3 shows.Table 2
Connection probability of all physical lines and LPSs.
PL no.LPS in this PLDisconnection starting timeDisconnection ending timeDisconnection durationConnection probability (t = a week = 4032 mins)Root causedP1l1,1; l2,1; l3,1; l4,12011/4/21 10:17:00 AM2011/4/21 11:56:00 AM99 minst-99/t=0.98Circuit brokenP2l2,2; l3,2; l5,2N/AN/AN/A1NoP3l2,3; l7,2N/AN/AN/A1NoP4l1,22010/9/28 10:08:00 AM2010/9/28 02:07:00 PM239 minst-239/t=0.94Card brokenP5l4,2; l5,32011/4/21 22:01 PM2011/4/22 04:29:00 AM388 minst-388/t=0.90Circuit brokenP6l4,3; l5,42009/5/29 05:16 AM2009/5/29 08:27:00 AM191 minst-191/t=0.95Circuit brokenP7l3,3; l6,2; l8,22009/9/16 04:40:00 PM2009/9/16 05:01:00 PM211 minst-211/t=0.99Circuit brokenP8l2,4; l7,32011/3/11 01:53:00 PM2011/3/12 01:37:00 AM704 minst-704/t=0.83Japans’ earthquakeP9l11,22011/2/17 01:19:00 AM2011/2/17 03:33:00 AM134 minst-134/t=0.97Card disableP10l1,3; l4,4; l11,1; l5,52010/5/25 04:28:00 AM2010/5/25 11:11:00 AM403 minst-403/t=0.90Circuit brokenP11l3,4; l12,1; l7,42009/3/21 08:58:00 PM2009/3/22 03:23:00 AM385 minst-385/t=0.90Card disableP12l10,1; l13,12011/2/8 01:17:00 AM2011/2/8 11:07:00 AM590 minst-590/t=0.85Card disableP13l5,1; l6,1; l7,1; l8,1N/AN/AN/A1NoTable 3
LPSli,j redenoted by ai and its connection probability the same as the physical line Pi it locates.
Arca1a2a3a4a5a6a7a8a9a10a11a12a13a14a15a16a17LPSl1,1l1,2l1,3l2,1l2,2l2,3l2,4l3,1l3,2l3,3l3,4l4,1l4,2l4,3l4,4l10,1l11,1Prob0.980.940.90.98110.830.9810.990.90.980.90.950.90.850.9Arca18a19a20a21a22a23a24a25a26a27a28a29a30a31a32a33LPSl11,2l12,1l13,1l5,1l5,2l5,3l5,4l5,5l6,1l6,2l7,1l7,2l7,3l7,4l8,1l8,2Prob0.970.90.85110.90.950.910.99110.830.910.99


### 4.3. Network Reliability Computation

When line breaks occur, the suppliers of these pass-through physical lines provide all serviceable lines as backup lines, therefore increasing the network reliability. In this study, we do not discuss the backup lines and concentrate only on the regular lines to determine those factors that affect their network reliability. Firstly, we focus on the demand setD20={(20,0),(16,4),(12,8),(8,12),(4,16),(0,20)}, given all MLPs in Tables 1(a) and 1(b) and by using the algorithm in Section 3.3 as follows to obtain Ω(d1,d2),min.Step 1.
Do the following steps for (4,16)∈D20 (since there is no solution for Ω(0,20),min in this example, we only demonstrate Ω(4,16),min here).Step 2.
Find all feasible solutionsF that satisfy constraints (4.1):
(4.1)f1+f2+f9≤M1=4,f1+f2+f9≤M2=4,⋮f17+f18+f19≤M32=4,f17+f18+f19≤M33=4,f1+f2+⋯+f10=d1=4,f11+f12+⋯+f20=d2=16.
In this step, eachfi has two values, say 0 and 4, standing for the two capacity states of failure or success. From this, we obtain 4 flow vectors as shown in Table 4(a) (column 1).Table 4
(a) Results of example forΩ(4,16),min in D20. (b) Results of example for Ω(8,12),min in D20. (c)  Results of example for Ω(12,8),min in D20. (d) Results of example for Ω(16,4),min in D20.
(a)FX(4,16)-MLP or not?RemarkF1=(0,0,0,0,4,0,0,0,0,0,0,4,4,0,4,0,4,0,0,0)X1=(0,0,0,0,0,0,0,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4)NoX1≧X2F2=(0,0,0,0,4,0,0,0,0,0,0,4,4,4,0,0,0,4,0,0)X2=(0,0,0,0,0,0,0,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4)NoX2≧X3F3=(0,0,0,0,4,0,0,0,0,0,4,0,4,0,0,4,4,0,0,0)X3=(0,0,0,0,0,0,0,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4)NoX3≧X4F4=(0,0,0,0,4,0,0,0,0,0,4,0,4,4,0,0,0,0,4,0)X4=(0,0,0,0,0,0,0,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4)Yes(b)FX(8,12)-MLP or not?RemarkF1=(0,0,0,0,4,0,0,4,0,0,4,0,4,0,0,0,4,0,0,0)X1=(0,0,0,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4)NoX1≧X3F2=(0,0,0,0,4,0,0,4,0,0,4,0,4,4,0,0,0,0,0,0)X2=(0,0,0,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0)NoX2≧X4F3=(0,0,0,0,4,0,4,0,0,0,0,4,4,0,0,0,4,0,0,0)X3=(0,0,0,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4)NoX3≧X5F4=(0,0,0,0,4,0,4,0,0,0,0,4,4,4,0,0,0,0,0,0)X4=(0,0,0,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0)NoX4≧X6F5=(0,0,0,0,4,4,0,0,0,0,0,4,4,0,0,0,0,4,0,0)X5=(0,0,0,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4)NoX5≧X7F6=(0,0,0,0,4,4,0,0,0,0,0,4,4,0,4,0,0,0,0,0)X6=(0,0,0,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0)NoX6≧X8F7=(0,0,0,0,4,4,0,0,0,0,4,0,4,0,0,0,0,0,4,0)X7=(0,0,0,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4)YesF8=(0,0,0,0,4,4,0,0,0,0,4,0,4,0,0,4,0,0,0,0)X8=(0,0,0,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0)YesF9=(0,0,0,4,4,0,0,0,0,0,0,0,4,0,4,0,4,0,0,0)X9=(0,0,0,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,4,4)NoX9≧X10F10=(0,0,0,4,4,0,0,0,0,0,0,0,4,4,0,0,0,4,0,0)X10=(0,0,0,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,4,4)NoX10≧X13F11=(0,0,0,4,4,0,0,0,0,0,4,0,4,0,0,0,4,0,0,0)X11=(0,0,0,0,0,0,0,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4)NoX11≧X15F12=(0,0,0,4,4,0,0,0,0,0,4,0,4,4,0,0,0,0,0,0)X12=(0,0,0,0,0,0,0,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0)NoX12≧X16F13=(0,0,4,0,4,0,0,0,0,0,0,0,4,0,0,4,4,0,0,0)X13=(0,0,0,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,4,4)NoX13≧X14F14=(0,0,4,0,4,0,0,0,0,0,0,0,4,4,0,0,0,0,4,0)X14=(0,0,0,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,4,4)YesF15=(0,0,4,0,4,0,0,0,0,0,0,4,4,0,0,0,4,0,0,0)X15=(0,0,0,0,0,0,0,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4)YesF16=(0,0,4,0,4,0,0,0,0,0,0,4,4,4,0,0,0,0,0,0)X16=(0,0,0,0,0,0,0,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0)YesF17=(0,4,0,0,4,0,0,0,0,0,0,0,4,0,4,0,4,0,0,0)X17=(4,4,4,0,0,0,0,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,4,4)NoX17≧X18F18=(0,4,0,0,4,0,0,0,0,0,0,0,4,4,0,0,0,4,0,0)X18=(4,4,4,0,0,0,0,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,4,4)NoX18≧X21F19=(0,4,0,0,4,0,0,0,0,0,4,0,4,0,0,0,4,0,0,0)X19=(4,4,4,0,0,0,0,4,4,4,4,0,0,0,0,4,0,0,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4)NoX19≧X23F20=(0,4,0,0,4,0,0,0,0,0,4,0,4,4,0,0,0,0,0,0)X20=(4,4,4,0,0,0,0,4,4,4,4,0,0,0,0,4,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0)NoX20≧X24F21=(4,0,0,0,4,0,0,0,0,0,0,0,4,0,0,4,4,0,0,0)X21=(4,4,4,0,0,0,0,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,4,4)NoX21≧X22F22=(4,0,0,0,4,0,0,0,0,0,0,0,4,4,0,0,0,0,4,0)X22=(4,4,4,0,0,0,0,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,4,4)YesF23=(4,0,0,0,4,0,0,0,0,0,0,4,4,0,0,0,4,0,0,0)X23=(4,4,4,0,0,0,0,4,4,4,4,0,0,0,0,4,0,0,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4)YesF24=(4,0,0,0,4,0,0,0,0,0,0,4,4,4,0,0,0,0,0,0)X24=(4,4,4,0,0,0,0,4,4,4,4,0,0,0,0,4,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0)Yes(c)FX(12,8)-MLP or not?RemarkF1=(0,0,0,4,4,0,0,0,4,0,4,0,4,0,0,0,0,0,0,0)X1=(4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,0,0)NoX1≧X7F2=(0,0,0,4,4,0,4,0,0,0,0,0,4,0,0,0,4,0,0,0)X2=(0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,0,0,4,4,4,4,4,4)NoX2≧X4F3=(0,0,0,4,4,0,4,0,0,0,0,0,4,4,0,0,0,0,0,0)X3=(0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0)NoX3≧X5F4=(0,0,0,4,4,4,0,0,0,0,0,0,4,0,0,0,0,4,0,0)X4=(0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,0,0,4,4,4,4,4,4)NoX4≧X8F5=(0,0,0,4,4,4,0,0,0,0,0,0,4,0,4,0,0,0,0,0)X5=(0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0)NoX5≧X9F6=(0,0,0,4,4,4,0,0,0,0,4,0,4,0,0,0,0,0,0,0)X6=(0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4,4,0,0,4,4,4,4,0,0)NoX6≧X12F7=(0,0,4,0,4,0,0,0,4,0,0,4,4,0,0,0,0,0,0,0)X7=(4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,0,0)NoX7≧X13F8=(0,0,4,0,4,0,0,4,0,0,0,0,4,0,0,0,4,0,0,0)X8=(0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,0,0,4,4,4,4,4,4)NoX8≧X10F9=(0,0,4,0,4,0,0,4,0,0,0,0,4,4,0,0,0,0,0,0)X9=(0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0)NoX9≧X11F10=(0,0,4,0,4,4,0,0,0,0,0,0,4,0,0,0,0,0,4,0)X10=(0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,0,0,4,4,4,4,4,4)YesF11=(0,0,4,0,4,4,0,0,0,0,0,0,4,0,0,4,0,0,0,0)X11=(0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0)YesF12=(0,0,4,0,4,4,0,0,0,0,0,4,4,0,0,0,0,0,0,0)X12=(0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4,4,0,0,4,4,4,4,0,0)YesF13=(0,4,0,0,4,0,0,0,0,4,4,0,4,0,0,0,0,0,0,0)X13=(4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,0,0)NoX13≧X19F14=(0,4,0,0,4,0,4,0,0,0,0,0,4,0,0,0,4,0,0,0)X14=(4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,0,0,4,4,4,4,4,4)NoX14≧X16F15=(0,4,0,0,4,0,4,0,0,0,0,0,4,4,0,0,0,0,0,0)X15=(4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0)NoX15≧X17F16=(0,4,0,0,4,4,0,0,0,0,0,0,4,0,0,0,0,4,0,0)X16=(4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,0,0,4,4,4,4,4,4)NoX16≧X23F17=(0,4,0,0,4,4,0,0,0,0,0,0,4,0,4,0,0,0,0,0)X17=(4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0)NoX17≧X24F18=(0,4,0,0,4,4,0,0,0,0,4,0,4,0,0,0,0,0,0,0)X18=(4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,4,0,0,4,4,4,4,4,4,4,0,0,4,4,4,4,0,0)NoX18≧X27F19=(0,4,4,0,4,0,0,0,0,0,0,0,4,0,0,0,0,0,0,4)X19=(4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,0,0)NoX19≧X22F20=(0,4,4,0,4,0,0,0,0,0,0,0,4,0,0,0,4,0,0,0)X20=(4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,0,0,4,4,0,0,0,0,0,0,0,4,4,4,4,4,4)NoX20≧X29F21=(0,4,4,0,4,0,0,0,0,0,0,0,4,4,0,0,0,0,0,0)X21=(4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,0,0,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0)NoX21≧X30F22=(4,0,0,0,4,0,0,0,0,4,0,4,4,0,0,0,0,0,0,0)X22=(4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,0,0)NoX22≧X28F23=(4,0,0,0,4,0,0,4,0,0,0,0,4,0,0,0,4,0,0,0)X23=(4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,0,0,4,4,4,4,4,4)NoX23≧X25F24=(4,0,0,0,4,0,0,4,0,0,0,0,4,4,0,0,0,0,0,0)X24=(4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0)NoX24≧X26F25=(4,0,0,0,4,4,0,0,0,0,0,0,4,0,0,0,0,0,4,0)X25=(4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,0,0,4,4,4,4,4,4)YesF26=(4,0,0,0,4,4,0,0,0,0,0,0,4,0,0,4,0,0,0,0)X26=(4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0)YesF27=(4,0,0,0,4,4,0,0,0,0,0,4,4,0,0,0,0,0,0,0)X27=(4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,4,0,0,4,4,4,4,4,4,4,0,0,4,4,4,4,0,0)YesF28=(4,0,0,4,4,0,0,0,0,0,0,0,4,0,0,0,0,0,0,4)X28=(4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,0,0)YesF29=(4,0,0,4,4,0,0,0,0,0,0,0,4,0,0,0,4,0,0,0)X29=(4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,0,0,4,4,0,0,0,0,0,0,0,4,4,4,4,4,4)YesF30=(4,0,0,4,4,0,0,0,0,0,0,0,4,4,0,0,0,0,0,0)X30=(4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,0,0,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0)Yes(d)FX(16,4)-MLP or not?RemarkF1=(0,1,1,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0)X1=(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,0,0,0,0,0,0,0,1,1,1,1,0,0)NoX1≧X2F2=(1,0,0,1,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0)X2=(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,0,0,0,0,0,0,0,1,1,1,1,0,0)YesStep 3.
Transform eachF into LPS X to get Ω4,16 by (4.2).
ForF1=(0,0,0,0,4,0,0,0,0,0,0,4,4,0,4,0,4,0,0,0), the capacity vector X1 is transformed by
(4.2)x1=f1+f2+f9=0+0+0=0,x2=f1+f2+f9=0+0+0=0,⋮x32=f17+f18+f19=4+0+0=4,x33=f17+f18+f19=4+0+0=4.
Thus,X1=(0,0,0,0,0,0,0,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4). Similarly, we obtain 4 capacity vectors as shown in Table 4(a) (column 2).Step 4.
The non-minimal ones inΩ(4,16) are removed to obtain Ω(4,16),min, that is, (4,16)-MLP as shown in Table 4(a) (column 3).When repeating the previous steps, we can also obtainΩ(8,12),min (resp., Ω(12,8),min and Ω(16,4),min) in Table 4(b) (resp. Tables 4(c) and 4(d)). In terms of RSDP [9], we calculate the network reliability RD20= ∑(d1,d2)∈D20Pr{Y∈Ω(d1,d2)∣Y≥X for a (d1,d2)-MLP X} = 0.4140. Similarly, RD16 = 0.8195, RD12= 0.9707, RD8 = 0.9976, and RD4= 0.9999 can be evaluated, respectively. The network reliability can be observed to decrease as the total demand increases, as shown in Figure 4.Figure 4
(Demand, network reliability) for demand set beingD20, D16, D12, D8, D4.In regard to QoS, this is only a concern when there are insufficient networks resources. When there are enough resources and demand is low, for instance, as above withD4, there are still plenty of resources to handle other transmission requests, so the network reliability is quite high. On the other hand, if demand is high, say above set D20, the network reliability will be low, since there are not enough resources to handle other data transmissions. To maintain the network reliability, it is important to avoid full transmission loads or increase line capacity. Depending on the results of our analysis, we may decide to allocate more economic resources to TWAREN to maximize future network utilities.


## 4.1. Level of Demand and MLP from Taipei and Hsinchu to New York

To calculate TWAREN’s network reliability from Taipei and Hsinchu to New York, there must be a reasonable demand level. For each arc’s capacity, each LP occupies a bandwidth 622 Mb, and each 622 Mb bandwidth has four 155 Mb channels. We regard each 155 Mb as one unit. Therefore, there are four units in each 622 Mb LP channel.Let the total demand bep=20 units, that is, 5 × 622 Mb = 3,110 Mb. For Ω(d1,d2),min  the demand set D20={(20,0),(16,4),(12,8),(8,12),(4,16),(0,20)}, we try to evaluate RD20=∑(d1,d2)∈D20Pr{Y∈Ω(d1,d2)∣Y≥Xfora(d1,d2)-MLP X}. In these cases, there are 10 MLPs from n1 (Taipei) to n9 (New York) as Table 1(a) and 10 MLPs from n13 (Hsinchu) to n9 (New York) as shown in Table 1(b).Table 1
(a) All MLPs from Taipei (n1) to New York (n9). (b) All MLPs from Hsinchu (n13) to New York (n9).
(a)MLP no.Light paths combinationNodes & LPS combination flowml1Taipei→LP1→Chicago→LP10→New Yorkn1→l1,1→n2→l1,2→n6→l1,3→n8→l10,1→n9ml2Taipei→LP1→Chicago→LP13→New Yorkn1→l1,1→n2→l1,2→n6→l1,3→n8→l13,1→n9ml3Taipei→ LP4→Chicago→LP10→New Yorkn1→l4,1→n2→l4,2→n5→l4,3→n6→l4,4→n8→l10,1→n9ml4Taipei→LP4→Chicago→LP13→New Yorkn1→l4,1→n2→l4,2→n5→l4,3→n6→l4,4→n8→l13,1→n9ml5Taipei→LP3→New Yorkn1→l3,1→n2→l3,2→n3→l3,3→n7→l3,4→n9ml6Taipei→LP2→Los Angeles→LP12→New Yorkn1→l2,1→n2→l2,2→n3→l2,3→n4→l2,4→n7→l12,1→n9ml7Taipei→LP2→Los Angeles→LP11→Chicago→LP10→New Yorkn1→l2,1→n2→l2,2→n3→l2,3→n4→l2,4→n7→l11,2→n6→l11,1→n8→l10,1→n9ml8Taipei→LP2→Los Angeles→LP11→Chicago→LP13→New Yorkn1→l2,1→n2→l2,2→n3→l2,3→n4→l2,4→n7→l11,2→n6→l11,1→n8→l13,1→n9ml9Taipei→LP1→Chicago→LP11→Los Angeles→LP12→New Yorkn1→l1,1→n2→l1,2→n6→l1,3→n8→l11,1→n6→l11,2→n7→l12,1→n9ml10Taipei→LP4→Chicago→LP11→Los Angeles→LP12→New Yorkn1→l4,1→n2→l4,2→n5→l4,3→n6→l4,4→n8→l11,1→n6→l11,2→n7→l12,1→n9(b)MLP no.Light paths combinationNodes & LPS combination flowml11Hsinchu→LP5→Chicago→LP10→New Yorkn10→l5,1→n3→l5,2→n2→l5,3→n5→l5,4→n6→l5,5→n8→l10,1→n9ml12Hsinchu→LP5→Chicago→LP13→New Yorkn10→l5,1→n3→l5,2→n2→l5,3→n5→l5,4→n6→l5,5→n8→l13,1→n9ml13Hsinchu→LP7→New Yorkn10→l7,1→n3→l7,2→n4→l7,3→n7→l7,4→n9ml14Hsinchu→LP6→Los Angeles→LP12→New Yorkn10→l6,1→n3→l6,2→n7→l12,1→n9ml15Hsinchu→LP6→Los Angeles→LP11→Chicago→LP10→New Yorkn10→l6,1→n3→l6,2→n7→l11,2→n6→l11,1→n8→l10,1→n9ml16Hsinchu→LP6→Los Angeles→LP11→Chicago→LP13→New Yorkn10→l6,1→n3→l6,2→n7→l11,2→n6→l11,1→n8→l13,1→n9ml17Hsinchu→LP8→Los Angeles→LP12→New Yorkn10→l8,1→n3→l8,2→n7→l12,1→n9ml18Hsinchu→LP8→Los Angeles→LP11→Chicago→LP10→New Yorkn10→l8,1→n3→l8,2→n7→l11,2→n6→l11,1→n8→l10,1→n9ml19Hsinchu→LP8→Los Angeles→LP11→Chicago→LP13→New Yorkn10→l8,1→n3→l8,2→n7→l11,2→n6→l11,1→n8→l13,1→n9ml20Hsinchu→LP5→Chicago→LP11→Los Angeles→LP12→New Yorkn10→l5,1→n3→l5,2→n2→l5,3→n5→l5,4→n6→l5,5→n8→l11,1→n6→l11,2→n7→l12,1→n9


## 4.2. Probability of All LPSs Breaking

To compute the connection probability of each PL, we use the disconnection data from 2008 through 2011. The longest duration of every break for each physical line during the 168 hours of every week is used to determine the disconnection probability of each line. For example, as the physical lineP10 from San Francisco to Chicago broke for 403 minutes on 2010/5/25, its connection probability is (168 × 60 − 403)/(168 × 60) = 0.90. Therefore, its disconnection probability is (1 − 0.9) = 0.1. All the LPSs l1,3,l4,4 and l11,1 located in this physical line P10 have the same disconnection probability of 0.1.Table2 shows all LPSs’ connection probability after screening all physical lines’ disconnection records and selecting the longest broken time for each. These breaks include disabled card devices, circuit failures, and breaks from March 11, 2011 Japanese earthquake and tsunami that caused the physical submarine line P8 to break. This line uses a submarine cable connection between TP-3 and Los Angeles. Artificial devices, short circuits, and natural disasters simultaneously influence TWAREN’s network reliability from Taipei and Hsinchu to New York. Since each failure of a node device has been included and recorded in the physical line’s disconnection record, each node is supposed to be perfect with a reliability of 1. For computational convenience, as described in Section 3.3, we converted LPS li,j by using ai and the probability of ai, as Table 3 shows.Table 2
Connection probability of all physical lines and LPSs.
PL no.LPS in this PLDisconnection starting timeDisconnection ending timeDisconnection durationConnection probability (t = a week = 4032 mins)Root causedP1l1,1; l2,1; l3,1; l4,12011/4/21 10:17:00 AM2011/4/21 11:56:00 AM99 minst-99/t=0.98Circuit brokenP2l2,2; l3,2; l5,2N/AN/AN/A1NoP3l2,3; l7,2N/AN/AN/A1NoP4l1,22010/9/28 10:08:00 AM2010/9/28 02:07:00 PM239 minst-239/t=0.94Card brokenP5l4,2; l5,32011/4/21 22:01 PM2011/4/22 04:29:00 AM388 minst-388/t=0.90Circuit brokenP6l4,3; l5,42009/5/29 05:16 AM2009/5/29 08:27:00 AM191 minst-191/t=0.95Circuit brokenP7l3,3; l6,2; l8,22009/9/16 04:40:00 PM2009/9/16 05:01:00 PM211 minst-211/t=0.99Circuit brokenP8l2,4; l7,32011/3/11 01:53:00 PM2011/3/12 01:37:00 AM704 minst-704/t=0.83Japans’ earthquakeP9l11,22011/2/17 01:19:00 AM2011/2/17 03:33:00 AM134 minst-134/t=0.97Card disableP10l1,3; l4,4; l11,1; l5,52010/5/25 04:28:00 AM2010/5/25 11:11:00 AM403 minst-403/t=0.90Circuit brokenP11l3,4; l12,1; l7,42009/3/21 08:58:00 PM2009/3/22 03:23:00 AM385 minst-385/t=0.90Card disableP12l10,1; l13,12011/2/8 01:17:00 AM2011/2/8 11:07:00 AM590 minst-590/t=0.85Card disableP13l5,1; l6,1; l7,1; l8,1N/AN/AN/A1NoTable 3
LPSli,j redenoted by ai and its connection probability the same as the physical line Pi it locates.
Arca1a2a3a4a5a6a7a8a9a10a11a12a13a14a15a16a17LPSl1,1l1,2l1,3l2,1l2,2l2,3l2,4l3,1l3,2l3,3l3,4l4,1l4,2l4,3l4,4l10,1l11,1Prob0.980.940.90.98110.830.9810.990.90.980.90.950.90.850.9Arca18a19a20a21a22a23a24a25a26a27a28a29a30a31a32a33LPSl11,2l12,1l13,1l5,1l5,2l5,3l5,4l5,5l6,1l6,2l7,1l7,2l7,3l7,4l8,1l8,2Prob0.970.90.85110.90.950.910.99110.830.910.99


## 4.3. Network Reliability Computation

When line breaks occur, the suppliers of these pass-through physical lines provide all serviceable lines as backup lines, therefore increasing the network reliability. In this study, we do not discuss the backup lines and concentrate only on the regular lines to determine those factors that affect their network reliability. Firstly, we focus on the demand setD20={(20,0),(16,4),(12,8),(8,12),(4,16),(0,20)}, given all MLPs in Tables 1(a) and 1(b) and by using the algorithm in Section 3.3 as follows to obtain Ω(d1,d2),min.Step 1.
Do the following steps for (4,16)∈D20 (since there is no solution for Ω(0,20),min in this example, we only demonstrate Ω(4,16),min here).Step 2.
Find all feasible solutionsF that satisfy constraints (4.1):
(4.1)f1+f2+f9≤M1=4,f1+f2+f9≤M2=4,⋮f17+f18+f19≤M32=4,f17+f18+f19≤M33=4,f1+f2+⋯+f10=d1=4,f11+f12+⋯+f20=d2=16.
In this step, eachfi has two values, say 0 and 4, standing for the two capacity states of failure or success. From this, we obtain 4 flow vectors as shown in Table 4(a) (column 1).Table 4
(a) Results of example forΩ(4,16),min in D20. (b) Results of example for Ω(8,12),min in D20. (c)  Results of example for Ω(12,8),min in D20. (d) Results of example for Ω(16,4),min in D20.
(a)FX(4,16)-MLP or not?RemarkF1=(0,0,0,0,4,0,0,0,0,0,0,4,4,0,4,0,4,0,0,0)X1=(0,0,0,0,0,0,0,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4)NoX1≧X2F2=(0,0,0,0,4,0,0,0,0,0,0,4,4,4,0,0,0,4,0,0)X2=(0,0,0,0,0,0,0,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4)NoX2≧X3F3=(0,0,0,0,4,0,0,0,0,0,4,0,4,0,0,4,4,0,0,0)X3=(0,0,0,0,0,0,0,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4)NoX3≧X4F4=(0,0,0,0,4,0,0,0,0,0,4,0,4,4,0,0,0,0,4,0)X4=(0,0,0,0,0,0,0,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4)Yes(b)FX(8,12)-MLP or not?RemarkF1=(0,0,0,0,4,0,0,4,0,0,4,0,4,0,0,0,4,0,0,0)X1=(0,0,0,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4)NoX1≧X3F2=(0,0,0,0,4,0,0,4,0,0,4,0,4,4,0,0,0,0,0,0)X2=(0,0,0,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0)NoX2≧X4F3=(0,0,0,0,4,0,4,0,0,0,0,4,4,0,0,0,4,0,0,0)X3=(0,0,0,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4)NoX3≧X5F4=(0,0,0,0,4,0,4,0,0,0,0,4,4,4,0,0,0,0,0,0)X4=(0,0,0,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0)NoX4≧X6F5=(0,0,0,0,4,4,0,0,0,0,0,4,4,0,0,0,0,4,0,0)X5=(0,0,0,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4)NoX5≧X7F6=(0,0,0,0,4,4,0,0,0,0,0,4,4,0,4,0,0,0,0,0)X6=(0,0,0,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0)NoX6≧X8F7=(0,0,0,0,4,4,0,0,0,0,4,0,4,0,0,0,0,0,4,0)X7=(0,0,0,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4)YesF8=(0,0,0,0,4,4,0,0,0,0,4,0,4,0,0,4,0,0,0,0)X8=(0,0,0,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0)YesF9=(0,0,0,4,4,0,0,0,0,0,0,0,4,0,4,0,4,0,0,0)X9=(0,0,0,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,4,4)NoX9≧X10F10=(0,0,0,4,4,0,0,0,0,0,0,0,4,4,0,0,0,4,0,0)X10=(0,0,0,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,4,4)NoX10≧X13F11=(0,0,0,4,4,0,0,0,0,0,4,0,4,0,0,0,4,0,0,0)X11=(0,0,0,0,0,0,0,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4)NoX11≧X15F12=(0,0,0,4,4,0,0,0,0,0,4,0,4,4,0,0,0,0,0,0)X12=(0,0,0,0,0,0,0,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0)NoX12≧X16F13=(0,0,4,0,4,0,0,0,0,0,0,0,4,0,0,4,4,0,0,0)X13=(0,0,0,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,4,4)NoX13≧X14F14=(0,0,4,0,4,0,0,0,0,0,0,0,4,4,0,0,0,0,4,0)X14=(0,0,0,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,4,4)YesF15=(0,0,4,0,4,0,0,0,0,0,0,4,4,0,0,0,4,0,0,0)X15=(0,0,0,0,0,0,0,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4)YesF16=(0,0,4,0,4,0,0,0,0,0,0,4,4,4,0,0,0,0,0,0)X16=(0,0,0,0,0,0,0,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0)YesF17=(0,4,0,0,4,0,0,0,0,0,0,0,4,0,4,0,4,0,0,0)X17=(4,4,4,0,0,0,0,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,4,4)NoX17≧X18F18=(0,4,0,0,4,0,0,0,0,0,0,0,4,4,0,0,0,4,0,0)X18=(4,4,4,0,0,0,0,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,4,4)NoX18≧X21F19=(0,4,0,0,4,0,0,0,0,0,4,0,4,0,0,0,4,0,0,0)X19=(4,4,4,0,0,0,0,4,4,4,4,0,0,0,0,4,0,0,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4)NoX19≧X23F20=(0,4,0,0,4,0,0,0,0,0,4,0,4,4,0,0,0,0,0,0)X20=(4,4,4,0,0,0,0,4,4,4,4,0,0,0,0,4,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0)NoX20≧X24F21=(4,0,0,0,4,0,0,0,0,0,0,0,4,0,0,4,4,0,0,0)X21=(4,4,4,0,0,0,0,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,4,4)NoX21≧X22F22=(4,0,0,0,4,0,0,0,0,0,0,0,4,4,0,0,0,0,4,0)X22=(4,4,4,0,0,0,0,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,4,4)YesF23=(4,0,0,0,4,0,0,0,0,0,0,4,4,0,0,0,4,0,0,0)X23=(4,4,4,0,0,0,0,4,4,4,4,0,0,0,0,4,0,0,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4)YesF24=(4,0,0,0,4,0,0,0,0,0,0,4,4,4,0,0,0,0,0,0)X24=(4,4,4,0,0,0,0,4,4,4,4,0,0,0,0,4,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0)Yes(c)FX(12,8)-MLP or not?RemarkF1=(0,0,0,4,4,0,0,0,4,0,4,0,4,0,0,0,0,0,0,0)X1=(4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,0,0)NoX1≧X7F2=(0,0,0,4,4,0,4,0,0,0,0,0,4,0,0,0,4,0,0,0)X2=(0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,0,0,4,4,4,4,4,4)NoX2≧X4F3=(0,0,0,4,4,0,4,0,0,0,0,0,4,4,0,0,0,0,0,0)X3=(0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0)NoX3≧X5F4=(0,0,0,4,4,4,0,0,0,0,0,0,4,0,0,0,0,4,0,0)X4=(0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,0,0,4,4,4,4,4,4)NoX4≧X8F5=(0,0,0,4,4,4,0,0,0,0,0,0,4,0,4,0,0,0,0,0)X5=(0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0)NoX5≧X9F6=(0,0,0,4,4,4,0,0,0,0,4,0,4,0,0,0,0,0,0,0)X6=(0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4,4,0,0,4,4,4,4,0,0)NoX6≧X12F7=(0,0,4,0,4,0,0,0,4,0,0,4,4,0,0,0,0,0,0,0)X7=(4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,0,0)NoX7≧X13F8=(0,0,4,0,4,0,0,4,0,0,0,0,4,0,0,0,4,0,0,0)X8=(0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,0,0,4,4,4,4,4,4)NoX8≧X10F9=(0,0,4,0,4,0,0,4,0,0,0,0,4,4,0,0,0,0,0,0)X9=(0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0)NoX9≧X11F10=(0,0,4,0,4,4,0,0,0,0,0,0,4,0,0,0,0,0,4,0)X10=(0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,0,0,4,4,4,4,4,4)YesF11=(0,0,4,0,4,4,0,0,0,0,0,0,4,0,0,4,0,0,0,0)X11=(0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0)YesF12=(0,0,4,0,4,4,0,0,0,0,0,4,4,0,0,0,0,0,0,0)X12=(0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,4,4,4,0,0,4,4,4,4,0,0)YesF13=(0,4,0,0,4,0,0,0,0,4,4,0,4,0,0,0,0,0,0,0)X13=(4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,0,0)NoX13≧X19F14=(0,4,0,0,4,0,4,0,0,0,0,0,4,0,0,0,4,0,0,0)X14=(4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,0,0,4,4,4,4,4,4)NoX14≧X16F15=(0,4,0,0,4,0,4,0,0,0,0,0,4,4,0,0,0,0,0,0)X15=(4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0)NoX15≧X17F16=(0,4,0,0,4,4,0,0,0,0,0,0,4,0,0,0,0,4,0,0)X16=(4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,0,0,4,4,4,4,4,4)NoX16≧X23F17=(0,4,0,0,4,4,0,0,0,0,0,0,4,0,4,0,0,0,0,0)X17=(4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0)NoX17≧X24F18=(0,4,0,0,4,4,0,0,0,0,4,0,4,0,0,0,0,0,0,0)X18=(4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,4,0,0,4,4,4,4,4,4,4,0,0,4,4,4,4,0,0)NoX18≧X27F19=(0,4,4,0,4,0,0,0,0,0,0,0,4,0,0,0,0,0,0,4)X19=(4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,0,0)NoX19≧X22F20=(0,4,4,0,4,0,0,0,0,0,0,0,4,0,0,0,4,0,0,0)X20=(4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,0,0,4,4,0,0,0,0,0,0,0,4,4,4,4,4,4)NoX20≧X29F21=(0,4,4,0,4,0,0,0,0,0,0,0,4,4,0,0,0,0,0,0)X21=(4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,0,0,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0)NoX21≧X30F22=(4,0,0,0,4,0,0,0,0,4,0,4,4,0,0,0,0,0,0,0)X22=(4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,0,0)NoX22≧X28F23=(4,0,0,0,4,0,0,4,0,0,0,0,4,0,0,0,4,0,0,0)X23=(4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,0,0,4,4,4,4,4,4)NoX23≧X25F24=(4,0,0,0,4,0,0,4,0,0,0,0,4,4,0,0,0,0,0,0)X24=(4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0)NoX24≧X26F25=(4,0,0,0,4,4,0,0,0,0,0,0,4,0,0,0,0,0,4,0)X25=(4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,0,0,4,4,4,4,4,4)YesF26=(4,0,0,0,4,4,0,0,0,0,0,0,4,0,0,4,0,0,0,0)X26=(4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,4,4,4,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0)YesF27=(4,0,0,0,4,4,0,0,0,0,0,4,4,0,0,0,0,0,0,0)X27=(4,4,4,4,4,4,4,4,4,4,4,0,0,0,0,4,0,0,4,4,4,4,4,4,4,0,0,4,4,4,4,0,0)YesF28=(4,0,0,4,4,0,0,0,0,0,0,0,4,0,0,0,0,0,0,4)X28=(4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0,4,4,4,4,0,0)YesF29=(4,0,0,4,4,0,0,0,0,0,0,0,4,0,0,0,4,0,0,0)X29=(4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,0,0,4,4,0,0,0,0,0,0,0,4,4,4,4,4,4)YesF30=(4,0,0,4,4,0,0,0,0,0,0,0,4,4,0,0,0,0,0,0)X30=(4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,0,0,4,4,0,0,0,0,0,4,4,4,4,4,4,0,0)Yes(d)FX(16,4)-MLP or not?RemarkF1=(0,1,1,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0)X1=(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,0,0,0,0,0,0,0,1,1,1,1,0,0)NoX1≧X2F2=(1,0,0,1,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0)X2=(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,0,0,0,0,0,0,0,1,1,1,1,0,0)YesStep 3.
Transform eachF into LPS X to get Ω4,16 by (4.2).
ForF1=(0,0,0,0,4,0,0,0,0,0,0,4,4,0,4,0,4,0,0,0), the capacity vector X1 is transformed by
(4.2)x1=f1+f2+f9=0+0+0=0,x2=f1+f2+f9=0+0+0=0,⋮x32=f17+f18+f19=4+0+0=4,x33=f17+f18+f19=4+0+0=4.
Thus,X1=(0,0,0,0,0,0,0,4,4,4,4,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4). Similarly, we obtain 4 capacity vectors as shown in Table 4(a) (column 2).Step 4.
The non-minimal ones inΩ(4,16) are removed to obtain Ω(4,16),min, that is, (4,16)-MLP as shown in Table 4(a) (column 3).When repeating the previous steps, we can also obtainΩ(8,12),min (resp., Ω(12,8),min and Ω(16,4),min) in Table 4(b) (resp. Tables 4(c) and 4(d)). In terms of RSDP [9], we calculate the network reliability RD20= ∑(d1,d2)∈D20Pr{Y∈Ω(d1,d2)∣Y≥X for a (d1,d2)-MLP X} = 0.4140. Similarly, RD16 = 0.8195, RD12= 0.9707, RD8 = 0.9976, and RD4= 0.9999 can be evaluated, respectively. The network reliability can be observed to decrease as the total demand increases, as shown in Figure 4.Figure 4
(Demand, network reliability) for demand set beingD20, D16, D12, D8, D4.In regard to QoS, this is only a concern when there are insufficient networks resources. When there are enough resources and demand is low, for instance, as above withD4, there are still plenty of resources to handle other transmission requests, so the network reliability is quite high. On the other hand, if demand is high, say above set D20, the network reliability will be low, since there are not enough resources to handle other data transmissions. To maintain the network reliability, it is important to avoid full transmission loads or increase line capacity. Depending on the results of our analysis, we may decide to allocate more economic resources to TWAREN to maximize future network utilities.


## 5. Summary and Conclusion

Instead of the classical TTNR, KTNR, and ATNR analysis of a binary-state flow network, this paper evaluates the network reliability of a stochastic-flow network with multiple sources. It also designs an MLP-based network reliability evaluation technique for the international LP portion of TWAREN’s academic and research network. This portion contains the domestic land surface line and the Asia Pacific submarine cables which connect to the global academic research network, including the Internet2 Network [27]. Since the LP cannot be divided through any of its nodes or LPSs during transmission, MLP is a new concept to evaluate the network reliability in an LP environment. MLP is used to discuss the flow assignment and to evaluate the network reliability. This research contributes by making real TWAREN data available to be analyzed in a stochastic-flow network model. By using the MLP analysis technique, we will know how to continuously adjust TWAREN’s infrastructure to achieve higher network reliability. In this study, we concentrate on the portion of the network that includes regular lines and does not include backup cables yet. This allows us to determine those factors that influence the dedicated regular lines’ network reliability. We also consider the effects of the earthquake that hit Japan on March 11, 2011. All factors are studied, including artificial, machine, and cable failures and natural disasters that simultaneously influence TWAREN’s network reliability from the two source nodes, Taipei and Hsinchu, to the single sink node, New York. In addition, the MLP network reliability technique used in the multiple sources case will enable us to increase the efficiency of TWAREN and help us to learn how to improve its network infrastructure and performance in the near future. Subsequently, further study may be undertaken on the network reliability of TWAREN’s multisource to multisink (terminal) issue.



---

*Source: 737562-2012-07-02.xml*