Communication & Transportation Network Reliability Using Routing Models

IEEE TRANSACTIONS ON RELIABILITY, VOL. 40, NO. 1 , 1991 APRIL Communication & Transportation Network Reliability Using Routing Models Brunilde Sanso Franwis Soumis Ecole Polytechnique de Montrkal, Montrkal Ecole Polytechnique de Montrkal, Montrkal Key Words - Routing, Flow network, Optimization, Com- munication network, Transportation network Reader Aids - Purpose: Advance state of the art Special math needed for explanations: Basic flow-network Special math needed to use results: Same Results useful to: Reliability analysts and researchers, formulations, Probability transportation analysts Abstract - A general framework is presented for calculating a reliability measure for several types of flow networks. This framework allows reliability analysis for complicated systems such as communication, electric power, and transportation networks. The analysis is based on the notion of routing and rerouting after a failure. Modeling approaches are discussed for each type of system surveyed. 1. INTRODUCTION This paper introduces a common procedure to evaluate reliability in diverse flow-networks. It focuses on new model- ing approaches to find commonality among various applications. Traditionally, two approaches have been taken to evaluate net- work reliability: Consider the network as a pure graph. Knowing node and arc reliabilities, evaluate some measure of connectivity as the reliability of the network. Many authors are studying this ap- proach [l-51; see also the works compiled in [6]. Consider the purpose of a flow network as carrying com- modities from origin to destination nodes to satisfy a demand. In general, such measures are related to the ability of the net- work to transmit a level of flow [7-121. Many of the connectivity measures for approach #1 have been proven, or are suspected, to give rise to NP-hard problems [4]. Moreover, connectivity in most real networks is usually high even after important failures. Therefore, taking the prob- ability of connectivity as a measure of reliability can lead to an overestimation of network performance. This approach does not consider the flow nature of the network; related parameters such as arc capacity and demand are completely left out. The clear advantage of approach #2 is that the flow nature of the network is specifically considered. However, both ap- 29 proaches ignore the fact that failures in real systems bring up the issues of routing. By using the bounding method of Li & Silvester [ 131 , we use more complicated models that incorporate routing and show that they can be used in reliability evaluation; ie, we propose a reliability measure that accounts not only for network prob- ability of failures or the capacity of the network, but also the ability of the system to adjust its flow after a failure. The specific areas that we survey are: communication, elec- tric power, vehicular transportation, and air transportation. For some of these areas, reliability techniques have been widely ap- plied to measures of network performance [14, 151. For others, such as transportation systems, traditional reliability approaches were difficult to model. Our method is useful and innovative for all areas treated. We first outline the general methodology to evaluate the performance of specific networks. For every system, we then discuss: a mathematical description of the system, measures of performance, a mathematical model of failures, routing models and (if available) routing algorithms. 2. GENERAL METHODOLOGY The procedure for finding a good measure of performance in any network flow problem is summarized. The reliability parameter for most areas is a measure of average performance and, therefore, bounds on the measure are to be found. However, for some systems, other kinds of statistics could be more interesting. The general methodology is then based on the evaluation of an average measure; specific changes are discussed within every system. Methodology : 1. Choose a performance measure Z such that E{Z} is the desired measure of reliability. 2. Consider the kinds of failure which can occur in a net- work; then partially enumerate the m most probable states of the network. 3. For each of the m states, find the routing and the value of Z for that specific scenario. 4. Use the Z values computed for every state to obtain bounds on E{Z}. 2.1 Choice of Measure The measure of performance must consider the flow nature of the network. Two groups of measures are immediately 0018-9529/91/0400-0029$01.00O1991 IEEE 30 outlined, those which evaluate reliability from: a) the point of view of the user, and b) the point of view of the manager. 1. Quality of service measures. (user view point) A suitable measure could be related to the number and im- portance of customers served (this could be applied in telecom- munication and electric systems). In transportation, a quality- of-service measure is always related to time, eg, mean time for a passenger to reach his destination or mean time of delay in event of failure. 2. Economic measures. (Manager view point) Failures can always be quantified in terms of money, Reliability can then be measured by loss of revenue in event of failure. 2.2 Partial Enumeration Define a system-state as the state of every component. If the components are either failed or operating, there are 2" possible states ( n E number of components in the system). If each device has s operating states, there are s" possible states. If each device i has si states, there are si possible states. For the sake of simplicity, we refer to 2-state devices; then if a component can have several suitable and unsuitable levels of operation we have two choices: Consider a failed state as the union of all unsuitable levels and, the operating state as the union of all suitable levels. Use an enumerating algorithm for multimode components Li & Silvester [13] have developed an algorithm to enumerate the m most probable states for systems with 2-state devices. However for systems whose arc availability is very high, no algorithm is needed since the 0-failure and 1-failure states cover most of the space-state probability. For some systems, such as vehicular transportation, the planner is not necessarily interested in the " m most probable states" but rather in the " m most important states"; they could be the states that create the most damage in the system. In this case, neither the algorithm nor the bounds in [13] are ap- propriate. We discuss in more detail this situation when describ- ing the vehicular-transportation system. [ la . 2.3 Routing: Global & User Optimization Notions A general network can be formalized by a graph. In a net- work, flow usually models some physical flow quantity such as people, electric power, fluid, or money. Nodes usually model points of origin, destination or trans-shipment of commodities. Arcs are direct paths between nodes. Most physical-network flow problems have to be model- ed as multicommodity networks, viz, networks where the flow is of a varied nature, usually associated with the OID pair. Notation (for a multi-commodity network) X; Cii capacity of arc ( i J ) d' demand for commodity c flow of commodity c flowing from node i to node j IEEE TRANSACTIONS ON RELIABILITY, VOL. 40, NO. 1 , 1991 APRIL F ( i ) r -' ( i ) arc set whose terminal extremity is node i N node set A arc set G(N,A) graph N, commodity set sC,tC O / D origin & destination node-pair In a single-commodity network it is necessary only to change the cardinality of the commodity set. When the routing procedure is a global optimization pro- cedure from the manager view point it can be modeled by the multi-commodity problem: arc set whose initial extremity is node i origin, destination node for commodity c such that - conservation of flow: d' if i=s' -d'if i=t', for all c E N , 0 otherwise, for all i E N capacity: X ; I c ~ , for all ( i , j ) E A ' E N c nonnegativity : X ; 2 0, for all ( i J ) E A , for all c E N,. (4) In (l), L(X;) is a linear function to be minimized; it can be simply a dummy function, a valid function evaluating costs or minimum paths in the network, or even the value of the reliability-measure for the state considered. The multi-commodity problem with capacity constraints is very difficult to solve. Traditionally, the capacity constraints have been replaced by a penalty function to be added to the ob- jective function. In several of the routing applications we review, the penalty function is not artificial, but a carefully studied nonlinear function that either corresponds to congestion delay or reflects the stochastic character of the demand while avoiding the capacity of the arcs to be surpassed. The problem can then be reformulated as: min{L(X;) + P ( X ; ) } such that - {conservation of flow} { nonnegativity } Notation Notation P ( X i ) penalty function. Existing algorithms can solve, in reasonable time, large net- work problems formulated as (5). The routing formulations shown up to now correspond to a global-optimization model of the network. This kind of model considers that the network is managed by a centralized deci- sion maker who routes the flows in such a way as to optimize the global performance of the network. Global optimization is then a good approach in networks where no customers or users are involved in the outcome of the routing such as in electric- power systems. When users can decide the route to take, a decentralized system and the notion of user optimization have to be considered. A user-optimization model can be a simple description of the equilibrium conditions of the system in order for the user to optimize a specific parameter. In general, a user-optimization model can be formulated as a set of nonlinear equations: {equilibrium conditions} {flow conservation} { nonnegativity } Some user-optimization models are derived from the Kuhn- Tucker conditions applied to a network problem. For those models the possibility of solution by solving the corresponding network-optimization problem exists [ 171. Otherwise, large user-optimization formulations can be solved by methods such as Newton-Raphson and Gauss-Seidel or specialized methods for variational inequalities [ 171. Global-optimization routing gives a better performance measure than user-optimization models. However, for some systems (such as vehicular transportation), only the users have control over the routing and, therefore, only user-optimization models should be considered. 2.4 Pe~ormance Evaluation When there are many system-states, it is not practical to evaluate an exact average of a performance-measure; thus bounds on such a measure have to be computed. The upper and lower bounds on such a measure of performance can be those proposed in [ 131 : SANSONISOUMIS: COMMUNICATION & TRANSPORTATION NETWORK RELIABILITY USING ROUTING MODELS 31 ~ ~~ ~~~ ~ ~ ~ Sk system-state k Z measure of performance Z ( SI) min { Z ( Sk)} :measure of performance for the no- k failure state Z ( S z n ) max { Z ( &)}:outcome for the total-failure state (all k components have failed The principal appeal of bounds is that they can be used with the re-routing option in mind. There are m routing prob- lems to be solved but, since they are very similar to one another, we need only to re-optimize the routing of state k - 1 to find We do not put great importance on the closeness of the bounds. Since they are based on the outcome of the routing, their reference point could vary widely depending on the routing policy. In general, for pessimistic reliability-measures we are interested in the upper bound. Sometimes, when the most damaging states are considered, our interest is not even in the bounds but rather in the contribution of those states to the value of performance. We now discuss the influence of routing in performance- evaluation. In general, re-routing the demand after a failure gives better performarice thah losing the demand when a com- ponent fails. However, some physical networks do not have the capacity to re-route flow. Carey & Hendrickson [ 1 11 show ex- cellent bounds on average performance-measures when no re- route is done. z(Sk). 3. RELIABILITY MEASURES FOR COMMUNICATION NETWORKS 3.1 The System Switching stations correspond to nodes and communica- tion links to arcs. Flow can be measured in a unit of traffic called the Erlang (or CCS in the American system). Messages going from an origin to a destination node are a commodity. This is a multi-commodity system having as many types of flow as O/D pairs of nodes. These networks can be further classified into two general types: circuit switching and packet switching. The basic dif- ference between them is the strategy to allocate a request of call. If all the necessary resources for the complete duration of the connection are reserved once a call is requested, we have circuit switching. For calls with low utilization, the allocated resources are used only a short time; and circuit switching is an inefficient way to route the calls. For these types of calls the suitable switching is packet switching. The information is divided into packets, and the resources to transmit a call are then only partially allocated from one switching station to the other for the time it takes a packet to travel between the sta- tions. In general, telephone calls use circuit-switching while packet-switching is used to transmit data (computer networks). 32 IEEE TRANSACTIONS ON RELIABILITY, VOL. 40, NO. 1 , 1991 APRIL Since the nature and the behavior of the flow depends on the type of switching, the modeling changes accordingly. Circuit-switched networks do not allow delay: calls are simply routed or lost. On the other hand the notion of overflow (lost calls) is not present as such in packet switching but transmis- sion delays are important in the routing. In this paper, we specifically model circuit-switched net- works. However, since most of the work in telecommunica- tion network-reliability was done for packet switching, we men- tion the pioneering work by Frank and his colleagues in this field [ 18-24]. One of the very first studies on circuit-switching was Lee [25]. Methods for finding the blocking probability of a network were elaborated. The blocking probability of a network is a reliability-measure where failures model the event that a call is blocked. This idea has been studied by several authors in the circuit-switching field, eg, Girard [26, chapter 41 and its numerous references. This approach focuses on the evaluation of system performance considering only the capacity of the equipment. Our approach considers the capacity of the equipment, the damage caused by the failures, as well as the ability of the system to adjust to failure. A good reliability-measure that considers all these features is the average lost-call traffic in the system. A methodology to evaluate this measure has been developed in [27, 281. 3.2 Failures Both nodes and arcs can fail; thus there are 2"" states to be enumerated. Notation n the number of arcs S number of nodes A partial enumeration procedure to find the m most probable states should not discriminate between the kinds of devices which produce a failed state. Therefore, switching stations and communication links can be treated as simple devices while find- ing the m most probable states. On the other hand, once placed in the routing subproblem, the failures of arcs and nodes have to be distinguished. When a node fails, some or all the arcs ad- jacent to it fail as well. We have then considered that if a state admits the failure of some nodes, the corresponding routing takes place in a subgraph where the failed arcs as well as the failed nodes and their adjacent arcs are removed. Another problem regarding failures arises in communica- tion networks. Usually the communication company works with a logic network in mind and failures are referred to that kind of network. Unfortunately, since most of the tipe, different logic paths share the same physical equipment, fdures in the logic net- work can be statistically dependent. The algorithm of partial enumeration considers that device failures are statistically indepen- dent. In order to overcome this difficulty, we can choose to work on the physical network where failures are statistically indepen- dent, and translate the necessary results into the logic ones. 3.3 Routing Ref [27, 281 present several global-optimization models. The basic idea was to use the nonlinear formulation of a multi- commodity problem given by (5). The penalty function P ( X $ ) chosen to avoid the capacity of the arcs to be surpassed and, at the same time, to reflect the stochastic character of the de- mand was the Erlang mean loss call-traffic function. The for- mulation was: such that - {conservation of flow} (nonnegativity } In (8), L ( X $ ) is a term to favor the shortest path and B corresponds to the Erlang loss formula, that is, the function that gives the probability of blocking in a link. Notation (Simplified) S capacity of the link (in number of circuits) a demand on the link (or offered traffic) in units of flow (Erlangs). Then - (9) The number of variables in (8) can be made smaller by con- sidering one commodity as all the flows having the same origin. We now show another type of routing model related to the notion of user optimization. Although global-optimization models work better than user- optimization models, actual present-day switching policies are closer to decentralized routing. In our decentralized model, every origin-destination pair has a choice of three routes. The demand attempts to pass through the first route; the overflow from the first route attempts the second route; the overflow from the second route attempts the third route; and the overflow from the third route is lost. Figure 1 shows this flow behavior. Figure 1. SANSON/SOUMIS: COMMUNICATION & TRANSPORTATION NETWORK RELIABILITY USING ROUTING MODELS ~ 33 Notation X, average traffic trying to pass through route q. h, average traffic flowing through route q. P, ( X,) average lost-call traffic of route q. D demand for an OID pair. X, = h, + P,(X,), for all q = 1 ,..., 4 (10) Eq (10) introduced a dummy route, #4, which receives the total traffic lost for the O/D pair. Therefore - Eq (1 1) corresponds to a set of equations that model the behavior for one O/D pair. When all O/D pairs are considered, (1 1) becomes a more complex equation system since several O/D routes can have arcs in common. Therefore, the excess flow in an OID route depends not only on the flow from this very route, but from all flows of the O / D routes that use the common arcs in the route. Then we can rewrite (1 1) as: where x is a function englobing the flow variables in the com- mon arcs. The equation system obtained by applying (12) for all O/D pairs can be solved by numerical methods such as Gauss-Seidel or Newton-Raphson. See [28] for an expression for Pi(Xi, x). 3.4 Reliability Evaluation Telecommunication components are extremely reliable. If only link failures are considered, and since link reliability is greater than 99 % , then 0-failure and 1-failure states cover most of the state-space probability. Then, for each of the states, a routing problem is solved. If the model uses global optimiza- tion, the function to be evaluated for every state is: (13) c ( i J ) For the decentralized model: Z(