IEEE TRANSACTIONS ON RELIABILITY, VOL. 46, NO. 4, 1997 DECEMBER 473
Exact & Approximate Improvement to the Throughput of a Stochastic Network
Yupo Chan Air Force Institute of Technology, Wright-Patterson AFB
Eugene Yim HQ US Air Force, Washington DC
Alfred Marsh Marine Maritime Academy, Castine
Key Words - Stochastic network, Average maximum flow, Cut set, Flow path, Network design.
Summary & Conclusions - This paper presents a model for throughput-improtement in stochastic networks. It syn- thesizes & extends the state-of-knowledge on determining the mean value, the lower bound (LB), and upper bound (UB) for the maximum-flow network-design problem. Through the use of an artificial-intalligence programming-language such as PROLOG, the LB was solved very efficiently the first time. The key lies in using 'depth-first search' to generate the flow paths, which are then directly fed into a linear programming (LP) or mixed-integer mathematical programming (MIP) package for solution. The largest network solved consists of 70 nodes and 116 arcs, surpassing ohher computational experience reported in the literature.
In all test cases, the solutions were validated from the pre- scriptive model against a descriptive model. This is particu- larly insightful for the 3 case-studies of defense communication networks, where estimates from simulation were used as a ref- erence for comparison against the mathematical-programming results. The simulaticn-derived response-surface models val- idate not only the LB & UB, but the network-improvement strategies. In a complementary fashion, simulation serves as the approximate solution to an exact problem, while the LP or MIP seek the exact solution to an approximate problem (at a tiny fraction of computation time). Theoretical findings are verified on 7 experiments, which represent the largest data-set analyzed (to the best o f our knowledge). This includes mea- sures of approximation-error and of network vulnerability & reliability - key components of mean throughput. Sensitiv- ity analysis, which is inherent in the LP or MIP formulations, also yields consistent rrwdts with controlled experiments using simulation models.
In all networks, the LB solution in this paper is a better approximation to the exact solution than the UB, which is consistent with theoretical findings. This finding is important in that the 7 acyclic networks represent a diversity of geome- try and of survival probabilities. Another advantage of using the LB model and the path-enumeration solution-strategy has to do with an approximation of network reliability & vulnera- bility in that these approximate measures of performance are readily available from the solutions. Built upon the idea of
most-probable states, reliability UB and vulnerability are re- lated to the paths actually used. The paths used are but a small fraction of the paths generated, and the number of gen- erated paths is again tiny compared to the 2" probability states (n = number of arcs & nodes). A minute fraction of the total number of failure states accounts for most of the state space - a fact that is further reinforced by the prevalence of a zero- throughput state in the flow distributions.
1. 1NTR.ODUCTION Nomenclature
acyclic network: a network without any cycles. bipartite network: a network that can be decomposed
into 2 sets of nodes, with an edge leading from a node in one set to another node in the second set.
combinatorial space: the enumeration of all possible com- binat ions.
degrees-of-freedom: number of data-points (minus the number of coefficients) used to fit a response-surface regression-equation. . max-flow: largest throughput in a network. . monofil network: a balanced, acyclic, junction-free net- work. . multicommodity network: a network that carries more than one type of flow.
network with side constraints: a network problem with a pure network portion and a portion that is a regular linear-program. . response surface: a statistical fit over the output of sim- ulation results, consisting of a sufficient number of repli- cations of the simulation. . stochastic network: a graph with nodes & arcs whose attributes are r.v. . t-value: statistical goodness-of-fit measure to show s- significance of a coefficient in a response-surface equation.
Acronyms' AI artificial intelligence
CPLEX LP & MIP software-suite exploiting
lThe singular & plural of an acronym are always spelled the same.
001 8-9529/97/$10.00 01997 IEEE
474 IEEE TRANSACTIONS ON RELIABILITY, VOL. 46, NO. 4, 1997 DECEMBER
network structure in the model linear programming [lower, upper] bound mixed integer programming non-deterministic polynomial AI language built upon list-processing
Z(Trz l e ) = 1, Z ( F a l s e ) = 0 Z(arc i lies on path j ) [az,,]: arc-path-incidence matrix arc-path-incidence matrix in state k predetermined amount of arc-capacity improvement for arc z r.h.s. vector of a network-flow linear-program of all zeros except for the source entry -Vk and the sink entry V k budget available for network improvement best & worst number of calculations expressed as the argument function of E unit cost of improving arc i amount of capacity by which arc i is improved ( d l , d 2 , . . . , d n ) : vector of d , capacity of arc i; a r.v. specific value of U, failure capacity or throughput of a stochastic network Z(arc i was improved) (g1,92,. . . , g z , . . . ): vector of gz 1 if arc i ends at node 1 , -1 if arc z starts a t node I , 0 otherwise; for state k [ h k : , , ~ ] : node-arc incidence matrix for state k Pr{arc i or node z is operational} survivability of arc z , j
Prinetwork is in state k} total number of paths from s to t (the paths need not be disjoint) flow path j number of paths actually used reliability index for a network [LB, UBI of R reliability of path j source state of path k state k of a network set of predecessor nodes to node i set of successor nodes to node i sink vulnerability index for a network capacity of arc i or node i ; an arc can be defined by a single ( 2 ) or a double (1 - m) parameter mean of U, (Ul, U2,. . . ,Uz, . . . ): vector of U,
mean max-flow LB of V(X) UB of V(X) max-flow in state k positive flow in arc i , in an arc-path formulation ( X I ,x2,. . . ,IC%,. . . ): vector of x, minimum value of x, flow on arc ( i , j ) , in a node-arc formulation flow on path j ( X I , X z , . . . , X q ) : vector of X,, the X, need not be disjoint cost of b, ( w l , w 2 , . . . , w,, . . . ): vector of w,
Other, standard notation is given in “Information for R,eaders & Authors” at the rear of each issue.
This paper comprehensively looks at improving the throughput of a stochastic network. Traditional network- analysis has largely concentrated on deterministic net- works. Where there are stochastic elements, simulation is often used to solve the problem, particularly in real applications. RRcently, the amount of research activity on stochastic networks has been increasing, which, in our judgment, opens a new vista for operations research. It is also a constructive way to bridge the existing schism between stochastic processes and mathematical program- ming.
We report some results where the throughput of a sto- chastic network from a single source to a single sink (of- ten referred to as single commodity flow) is estimated. We are mainly interested in a binomial distribution on the node- or arc-capacity r.v., which assumes the state is either up or down. Node/arc failures are considered to be mutually s-independent events. Exact & approximate solutions are given, even though state-of-the-art compu- tation usually allows only approximate solutions. We are interested not only in the descriptive model of flow predic- tion, but in the prescriptive model of optimization. Thus, the classical max-flow problem and network-improvement strategies are addressed simultaneously. Through an ex- tensive set of experiments, including 3 case-studies of de- fense communication-networks, we validate & clarify cer- tain theoretical conjectures. To the best of our knowledge, the 7 experiments are among the most comprehensive tests conducted. We include controlled experiments in which the errors in approximation are measured, and sensitivity analysis is used to make statements about the behavior of this class of stochastic networks.
2. MATHEMATICAL FORMULATION Assumptions
arcs that connect the source s to the sink t .
of component j , for all i & j, i # j .
0. The network is directed, and has n1 nodes and 722
1. The state of component i is s-independent of the state
2. A node or arc is either u p or down. 3. Without loss of generality, any node can be modeled
CHAN ET A L EXACT 8: APPROXIMATE IMPROVEMENT TO THE THROUGHPUT OF A STOCHASTIC NETWORK 475
as an arc; ie, a node N is split into a pair of nodes N I & N2 connected by an arc (N1,Nz) . Arc failures are expressed as among n1 + 122 =I n arcs rather than both node & arc
4
The network is at, state Sk (k = 1,. . . , 2n) with proba- bility 9, together with the corresponding F(.); the combi- natorial space has n stochastic arcs. The mean throughput of the stochastic network is:
failures, for clarity t~ ease.
2”
V(x) = F(x, Sk) Pk.
k = l
F ( x , s k ) = result of the max-flow problem for state k [lo]:
max{Vk : Hk 3 x = b, 0 5 x 5 U}. (2)
Ref [25] augmented (1) & (2) to maximize the mean throughput by improving arcs in a network. Let each arc be improved by d, units of capacity [26] at cost c, .d,; then the max-flow problem is:
F(x, d, s k ) = max{ Vk : Hk . x = b, 0 I x L: U + d}. (3)
Alternatively, let a pre-determined b, be added to an arc with a corresponding g,. An improvement a t arc i costs w, = c, . b,; then the max-flow problem is:
F ( x , g, S A ) = max{Vk : Hk . x = b, 0 5 z, 2 U, + b, * gz}.
(4)
If the improvement increases V as much as possible within B , the network-improvement (sometimes referred to as network-design) problem is:
1. For the continuous, type-1, improvement model:
maxF(x, d), subject to: c . d 5 B.
2. For the discrete, type-2, improvement model:
max F(x , g ) , subject to: c g L: 13.
( 5 )
Both ( 5 ) & (6) compute the mean value of V(x), re- ferred to hereafter m the exact solution - to be differ- entiated from the LB & UB of such a mean value. For the same network and budgetary constraints, model ( 5 ) undoubtedly yields a UB for model (6), since ( 5 ) is an LP-relaxation of the ( 6 ) MIP formulation. Our research is directed to solving models ( 5 ) & (6), both exactly and through bounding approximations.
3. TR.ANSF0R.M TO ARC-PATH FORMULATION With the exception of small “textbook” networks, the
exact formulation for mean max-flow is computationally imposing, even with current computers. By contrast, it is quite feasible to compute the LB & UB, particularly the UB. Numerous researchers, eg, [3, 6 , 16, 171, have worked on these topics. To formulate LB or UB, it is advisable to
change the max-flow problem in terms of an arc-path for- mulation, rather than the node-arc formulation in section 2. The arc-path incidence formulation of (2) is based on these definitions:
max{Vk : Ak . X 5 U,X 2 0); (7)
Assumption 4. The flow paths are pre-defined & fixed; thus there is
no re-routing of messages to maximize the throughput in
By re-interpreting the other variables such as sj for path j , and using assumption #4, then (1) is re-written as a result of deleting some states.
case a path fails. 4
4 4
VL(X) = F(X, 3 , ) . P, = X , * R,. (9) j = 1 ,=1
In (9), the throughput still represents the mean flow. Eq (9), because of assumption #4, represents an LB ap- proximation on the mean max-flow. Instead of 2” states, there are only q << 2” states [20]. There are several ways to define the set of q states. Computational results and the theoretical development in the appendix show that the def- inition adopted in this paper yields a reasonable LB. The type-1 and -2 network-design problems remain the same as before except that we compute the ‘mean max-flow in the absence of re-routing’, instead of the exact solution. The UB for the throughput is much easier to formulate. Assumptzon
5. (For the most optimistic scenario.) All arcs survive
Using assumption # 5 , the largest throughput is repre- sented in (10) by the special case of (9) in which R, = 1 for all j:
and are fully operational. 4
a a
VU(X) = C F ( X j ) = cxj . j=l j=l
The ‘path-flows bundled in an arc’ are subject to bottle- neck capacities a t specific arcs:
1. For type-1 improvement,
4
ai,j . X j 5 f(Ui) + di for all i E Qj; j = 1
2. For type-2 improvement, (11) becomes:
a
j = l
In ( l a ) , f ( U ; ) is a specific value of U;. For a binomial- distribution on U; and -
476
1. For a reasonably-tight LB-estimate of V(x):
f(Vz) = mFx{U,} = max{O,G,} = G,; z
2. For a reasonably-tight UB-estimate of V ( x ) :
f(Vz) = E{U,} = p , . ii, = U,.
IEEE TRANSACTIONS ON RELIABILITY, VOL. 46, NO. 4, 1997 DECEMBER
The appendix discusses the tightness of these bounds in detail.
4. NUMERICAL EXAMPLE Figure 3 (see section 5) shows the example network. The
arc-path formulation as shown in (7), (9), (13) for the 3 flow paths is: s -+ 1 -+ 3 -+ t , with flow XI, s -+ 1 -+ 4 -+ t , with flow X2, s -+ 2 -+ 4 -+ t , with flow X3.
The paths have: RI = 1 . 1 . 0.9 = 0.9, R2 = 1, R3 = 0.05.
4.1 Lower Bound
maxVL(X) = 0.9X1 + X2 + 0.05X3 subject to:
arc(s,l) XI +Xz 5 5 arc(s,2) X3 5 6 arc( 1,3) XI 5 2 arc(l,4) X2 5 4 arc(2,4) X3 I 5 arc(3,t) XI 5 4 arc(4,t) X2 + X3 I 7
x1,x2,x3 2 0 In the two inequalities governing flow on path 1, the XI
can be reduced to X1 5 2, the tighter of the two LB. The same is true for X3. Appendix A.1.2 treats this point in more detail; see also (107).
4.2 Upper Bound
maxVU(X) = XI + Xz + X.3
subject to
Using (7), ( lo), (14), we write:
arc(s,l) XI +Xz 5 5 arc(s,2) X3 L: 0.6 arc(l,3) XI 5 2 arc(l,4) X2 I 4 arc(2,4) X3 I 2.5 arc(3,t) X1 I 3.6 arc(4,t) X2 + X3 I 7
x l , X Z , x 3 2 0
The only difference between the LB & UB models is in the coefficients in the objective function and the r.h.s.
4.3 Lower Bound: LP Type-1 The LP Type-1 improvement-model, in (5) & (ll), in-
troduces the continuous-capacity-improvement variables into the constraints of the LB formulation:
arc(s,l) XI + X2 I 5 + ds,l arc(s,2) X3 I 6 + ds,2
arc(] ,4) X2 I 4 + d1,4 arc(2,4) X3 I 5 + d2,4 arc(3,t) X1 I 4 + d3,t arc(4,t) X2 + X3 I 7 + d4,t budget 50ds,1 + 60ds,2 + 20d1,3 + 40d1,~ + 50d2,4
arc(l,3) x1 5 2 f d1,3
+4O&,t + 70d4,t 5 1000 ds,l,ds,2,d1,3,d1,4,d2,4,d3,t,d4,t 2 0 x l , X 2 , x 3 2 0
4.4 Lower Bound: MIP Type-2
constraints, as in (12): The MIP Type-2 improvement-model includes the same
arc(s,l) x1 + xz I 5 + gs.1 X3 5 6 + gs,2 arc(s,2)
arc(l73) arc(l,4)
x1 5 2 + g1,3 XZ 5 4 f g1,4
arc(2,4) x3 I 5 + Q2,4 arc(3,t) x1 5 4 + g3,t arc(4,t) x2 + x3 I 7 + g4,t budget 25Ogs,1 + 3OOgs,z + 1OOg1,3 + 2oog1,4 + 25og2,4
+2OOg3,t + 35Og4,t I 1000 gs,i ,g~,2, g1,3,Q1,4,Q2,4,g3,t, g4,t = integer x l , X 2 , x 3 2 0
4.5 Upper Bound: LP & MIP Similar improvement-models can be written for the UB
formulation. These are well defined LP & MIP. However, several questions remain unanswered:
tightness of these LB & UB in estimating the mean max-
. computational feasibility of solving these huge mathe- matical programs, particularly the tasks of generating all the flow paths XI , X2,. . . . 4.6 Other Measures
While the models (1 ) - (14) have been concentrating on throughput as the figure-of-merit, a third question is: . can other equally important measures, reliability & vul- nerability of the network, be obtained from the model out-
flow;
put?
5. COMPUTATIONAL R,ESULTS2 In deterministic communication-networks, throughput
is a very meaningful measure of performance. While one can argue that the equivalent measure for stochastic net- works, mean ma-flow, is adequate, others argue that vul-
2The number of significant figures is not intended to imply any accuracy in the estimates contained in this paper, but to illustrate the arithmetic.
CHAN ET A L EXACT dt APPROXIMATE IMPROVEMENT TO THE THROUGHPUT OF A STOCHASTIC NETWORK 417
nerability & reliability are equally important figures-of- merit. Vulnerability & reliability are both related to, yet different from, mean max-flow. Vulnerability shows the criticality of certain network components in the network throughput (Achilles heels). R.eliability, on the other hand, is a statement on the overall connectivity and states of the entire network when flow capacities are set-asides. Mean max-flow encompasses both throughput and failure status. The main body of this paper concentrates on mean max- flow. Appendix A.;! discusses reliability & vulnerability. The appendix shows how reliability & vulnerability can readily be approximated by a path-enumeration model. Built upon the concept of most-probable-state, the Ru in (115) serves as a U13 to the exact network-reliability ob- tained by simulation.
Depending on the model formulation and the solution algorithm, the max-flow through a network can be calcu- lated by implicitly enumerating all paths or cut sets. Sim- ply put, the maximum capacity is the largest amount of flow that can be pushed through all the available paths, or the minimum cut-sei; capacity. In a stochastic network of the kind in this paper, enumeration of many paths or cuts is unavoidable in obtaining a reasonably tight bound; see (9) & (107). The key is an efficient algorithm to generate paths or cut sets. For example, [23] reported on inverting minimum paths to obtain minimal cut-sets. A sequential method is suggested to simplify the inversion, resulting in substantial reduct,ion in computation. R.ef [4] followed the [23] method in generating all the proper cut-sets for case studies A, B, C , and example network 4, which are discussed in section 6. The FORTRAN code in [4] con- sumed hours in a PC-AT class machine for the case-study networks. The resulting cut sets are then examined in each Monte-Carlo siinulation repetition to determine the max-flow. Including the example networks in figure 4, lo4 repetitions were run for each network.
Due to the arc-path formulation finally adopted in the current study (9)-(14), the remainder of this paper concen- trates on path generation, rather than cut-set generation. Mainly facilitated by an AI language such as PROLOG, the depth-first search [5] is well suited to finding paths in the network, resulting in important gain in computational efficiency. For example, the paths for the same case-study networks are now generated within minutes, rather than hours for cut-set generation. The implemented program FORMULA [27] comes complete with output interface to a mathematical-programming package such as LP/MIP 83(XA), wherein the output of the path-generation routine becomes the input to i;he optimization model as formulated in (5) & (6). The efficient path-enumeration-codes make the LB, (9), computa,tionally feasible. The numerical ex- amples in section 4, e!y, would not be feasible if it were not for the availability of all paths.
The results in this paper represent, to the best of our knowledge, the largest set of computation experience doc- umented in the literature. Tables 1 & 2 document 7 acyclic networks, 4 of which are small “textbook” networks (fig-
ures 1 - 4), while the remaining 3 are case studies of real communication networks (figures 5 - 7). Each case reports the LB, UB, and the exact solution to the flow problem. The exact solution was either obtained by enumeration for small networks, or estimated by Monte-Carlo simula- tion for large networks. We believe this is the first place where exact solutions are placed side-by-side with the LB & UB approximations. Notation f o r Figures
(x,y) (survivability, capacity) * infinity
Figure 1. l-Path Network with Auxiliary Arcs for Nodes
Figure 2. 2-Path Network #2 with Auxiliary Arcs for Nodes
(.3,5W)
Figure 3. Example Network #3 [17]
Figure 4. Example Network #4 [12]
For use in other research, this paper presents all the data
To substantiate the computational results in section 7 by that were used in the 7 test networks, for two reasons:
478 IEEE TRANSACTIONS ON RELIABILITY, VOL. 46, NO. 4, 1997 DECEMBER
Table 1: Computation Experience with Small Networks
Network Mean Upper Lower Improve-1 Improve-2 R T #1 14.00 35.00 14.00 35.00 35.00 - -
#2 206.00 380.00 206.00 227.00 226.00 - -
#3 5.06 5.60 5.05 15.02 13.30 - -
#4 “133.50 360.00 128.64 252.39 248.64 - -
Table 2: Computation Experience with Case Studies
Network Mean(S) Upper Lower Improve-1 Improve-2 R T #A 619 5760 167 238 238 0.7605 0.2395 #B 354 2040 344 844 637 0.3158 0.9172 #C 1169 4290 855 2276 2272 0.8967 0.1220
referencing complete physical networks in all detail. . To allow others in the field to use this database in their tests & studies, in view of the fact that exact solutions are hard to ~ b t a i n . ~ Notation for Tables 1 & 2 *
- mean value was obtained by simulation networks are too small for valid use of (115) & (116)
Improve-1 LP model Improve-2 MIP model
Mean(S) Mean (by simulation)
Tables 1 & 2 show that the exact throughput-solution is much closer to the LB than the UB. This is somewhat important in that the 7 networks represent a diversity of geometries & characteristics. But they are acyclic and more-or-less linear in geometry from source to sink, which generally limit the path choice, hence drawing the exact & LB solutions together. This is anticipated from theo- retical results as discussed in appendix A.1. To the ex- tent that the exact solution for each network differs from the LB in terms of re-routing flexibility, the networks are rank-ordered based on the closeness of the LB to the exact solution: networks 1, 2, 3, B, 4, C, A.
For the pure linear network #1, where there is exactly one path, it is obvious that path shift is impossible. Hence the LB is the exact solution (see the theoretical explana- tion for monofil networks in appendix A.l) . The same can be said about networks #2 and, to a large extent, #3. Network #2 is monofil and contains only 2 paths from source to sink. In network #3, there can be no more than 2 alternate paths out of total of 3, should the stochastic arcs (3,t), (s,2), or (2, 4) fail one at a time. Network #B has switching flexibility only at selected portions of the network: the top left portion. Even then, the options are not too numerous. Network #4 has more flexibility for re-routing, but not too much more, because there are only
3The Monte-Carlo simulation took hours (if not days) to estimate the mean-throughput in networks A, B, C.
3 possible paths. While the paths are enumerable in the front portion of network #C, there are quite a few choices a t the back portion. The path choices in network #A are quite numerous, considering there are switching possibil- ities all through the network from left to right - within the confines of a more-or-less linear geometry.
The end of section 2 shows that the throughput from the ‘Improve-1 column in tables 1 & 2’ serves as the UB for the ‘Improve-2 column’. Improve-l is the LP-relaxation model while Improve-2 is the MIP model. The improve- ment strategy depends greatly on each e, and on B. In all these mathematical-programming formulations, alternate optima are quite common. This in part substantiates the discussions in appendix A. l , which states that there are several max-flows realizing the value F ( x ) , hence V(x).
6. CASE STUDIES Networks #A, #B, #C represent 3 communication net-
works in the US DoD. Notation for Figures
x node survivability (x,y) arc (survivability, capacity) x, x’ dependent nodes
(x,y)(y,x’) dependent arcs (x,y)(x’,y’) dependent arcs - critical path [bold/heavy line]
6.1 Case 1 Figure 5 shows network #A, in which all paths from
source to sink go through node 14. The survival probabil- ity of this node affects the network performance apprecia- bly. From a capacity standpoint, the arcs leaving sources 1 - 4 most likely form the bottlenecks of the system, be- cause they have Aow capacities of 1200 each, compared with 4800 elsewhere.
Figure 6 shows network #B. Node 16 is the most critical node in this system, with its survival probability of 0.07. The arcs out from node 16 have a capacity of only 75, forming an obvious bottleneck. There are 3 direct paths, consisting of 1 arc each from source to sink. They have
CHAN ET A L EXACT ck APPROXIMATE IMPROVEMENT TO THE THROUGHPUT OF A STOCHASTIC NETWORK 479
Figure 5. Network #A
at least a 0.5 survival probability. Because of their high survival-probabilities and low capacities, these paths most likely form the bottlenecks as well.
Figure 7 shows network #C, in which all paths go through node 11. The distribution of survival probabil- ities and capacities indicate that the majority of arcs prior to node 11 probably cause congestion in the system.
As with the small networks (#1- #4), the networks #A, #B, #C are to be improved according to the LP & MIP models formulated in (5) & (6) and illustrated in section 4. Paths are generalied in accordance with the procedure outlined in section 5.
Network #A contains 63 paths from source to sink, of which only 8 paths (12.7%) are used to carry messages. Several of the bottleneck arcs are located prior to node 11. Improvement to the network goes to arc (1,14), which has a survival probability of 1 and an original capacity of 1200. As a result of network improvement, 2 additional paths are now used to carry messages. The same result is obtained in both type-1 and type-2 network-design as shown in ta- bles 1 & 2. Network performance depends critically upon the survivability of node 14. The network throughput in- creases linearly with increasing survival probability a t this node, reaching a capacity of 334 at p1,4 = 1.
6.2 Case 2
Network #B has 1d7 paths from source to sink, of which 22 paths (11.8%) were used. Most of the 22 paths have low reliabilitiea. Path 4-24, consisting of only one arc (4,24), has survival probability of 0.5. This becomes the most critical arc, and most investment goes to improve this arc. All the arcs starting at node 16 reach their max-flow ca- pacities and are therefore quite critical to the performance of the network as well.
For the type-1 model, network improvement is suggested for arc (4,24) as anticipated.
For the type-2 model, the improvement goes to arcs (1,8) & (4,24).
In spite of the apparent criticality of node 16, improving its survivability does little to improve performance, since there are alternate paths that can go around node 16.
6.3 Case 3
Network #C has 198 paths from source to sink, of which only 8 (4.0%) carry flow. The relatively large number of path choices contributes toward a recognizable 25% diver- gence between the LB and exact solution. All arcs prior to node 11 are critical in this network. Improvements are suggested for arcs (2 , l l ) & (11,23) for both type-1 & type- 2 investments. Increasing the survivability of node 11 has an important result on network performance, allowing the throughput to reach 1222 at p11 = 1.0.
7. TIGHTNESS & EFFICIENCY OF THE BOUNDS The experiments show that UB estimates are less accu-
rate predictors of mean-throughput than LB. While the linear shape of the network plays a role, other factors con- tribute toward this. As shown in (106) and the associated discussions in appendix A. l , the difference between the UB and the mean throughput is related to the precise number of random arc-capacities that are replaced by their mean value. To the extent that all random arc-capacities are replaced in the UB formulation, the accuracy of the UB estimate is related to the fraction of arc capacities that are random to begin with, see (106). Table 3 shows that the discrepancy between UB and mean throughput is related to the fraction of random arcs in the network. In gen- eral, the larger the fraction of random arcs, the bigger the
480 IEEE TRANSACTIONS ON RELIABILITY, VOL. 46, NO. 4, 1997 DECEMBER
Figure 6. Network #B
discrepancy between the UB and mean throughput. The correlation is not perfect, in accordance with (103), where the survivability distribution on a random arc comes into play. For the m random arcs out of n (1 5 m 5 n), (106) seems4 to hold.
Notation for Table 3 #A-Rndm number of random arcs
#A-Tot1 total number of arcs # A a a t i o (# A-Rndm) / (# A-Tot al)
There is a plausible explanation for why the UB is not as tight an estimator as the LB for mean throughput. The assumption of the UB estimate is that all arcs are fully operational, which effectively reverts the UB to a deter- ministic network, see (IO).
Appendix A.2 shows that a ‘tiny fraction of the total number of states’ accounts for most of the state space, and the q states ( q << an) that are examined in the LB - corresponding to the set of s-t paths - represent a promi- nent part of the state space. Out of these q paths, only a small fraction T* (T* << q ) are actually used. Even though the LB estimate ignores re-routing, the states considered are prominent enough to represent adequately the mean throughput - apparently much more accurately than the
4Because the experimental result is based on a limited sample, this is the most that can be said.
gross assumption of no arc failure in the UB formulation. Consider the efficiency of computing the bounds. While
robustness of the arc-path formulation was discussed, the UB can be estimated by the node-arc LP formulation of (2) & (14), or (109). Furthermore the model can be cast in a network-flow format: max Vu subject to:
With the availability of network-flow programs such as SAS & CPLEX, the VU can be computed by an extremely efficient polynomial algorithm. Similarly, the LB model of (2) & (13) can be re-formulated as a ‘network with side constraints’ [8]: max VL subject to:
-VL, fo r i = s
0 , otherwise;
(1 6)
CHAN ET A L EXACT iSr APPROXIMATE IMPROVEMENT TO THE THROUGHPUT OF A STOCHASTIC NETWORK , 481
Table 3: Relationship between #A-Rndm and 'Amount of Over-Estimate by UB Throughput'
Network Mean Upper Upper-Mean Upper/Mean #A-Rndm #A-Tot1 #A-R.atio
#3 5.06 5.60 0.54 1.11 3 7 0.43 #2 206 380 174 1.84 4 8 0.50 #1 14.00 35.0 21 2.50 2 4 0.50 #4 133.5 360 126.50 2.70 8 13 0.62 #C 1169 4290 3121 3.67 69 92 0.75 #B 354 2040 1686 5.76 44 62 0.71 #A 619 5760 5141 9.31 32 46 0.70
.3
Arc (surv.cap) 13-23 ( 3.4800) 13-24 (.6,4800) 13-25 (.7.2400)
13-27 (1.1200) 13-28 (1.1200)
11-26 ( 9,1200)
13-29 (.3.1200) .8 14-23 ( 6.4800)
14-24 (3,4800) 14-25 (6,2400)
x node survivability 14-26 ( 7,1200) 14-27 (.9.1200) 14-28 (1,1200) - critical path 14-29 ( I , 1200)
(x,y) (arc survivability, arc capacity)
.7
.8
1
.3
.7
.5
.8
1
.3
.7
.5
.8
1
.3
.7
.5
.5
Figure 7. Network #C
482 IEEE TRANSACTIONS ON RELIABILITY, VOL. 46, NO. 4, 1997 DECEMBER
k = l
Constraint (17) is a restatement of (11) for d, = 0. Con- straint (18) limits the Bow through the network to that of V,: because constraint (18) consists of the objective function (9), minus the total flow into t . By adding the last 2 side-constraints (17) & (18), it is possible to use a network-with-side-constraints algorithm, such as those in SAS or CPLEX, to estimate this LB. Minor modification of constraint (17) to (11) or (la), and the addition of the budget constraint,
readily converts the LB model to an investment model ( 5 ) or (6). The resulting investment model is solvable either by network-with-side-constraint or MIP algorithms.
Eq (16), unlike (15), is shown here for illustration only. It accentuates how today’s LP software can fully exploit any network structure embedded in an LP. The formula- tion by itself saves little effort since the only difference from the original arc-path formulation in ( 2 ) & (13) is the placement of the objective function (9) in the last con- straint. The formulation still needs path enumeration to be performed first. The number of side constraints is likely to be on the order of n2, or in relation to the number of arcs in the network. Irrespective of how fast an LP code can execute, the efficiency of path enumeration remains to be discussed.
The paths are to be generated by a depth-first search- procedure. The question then becomes: how efficient is such a procedure in solving a potentially NP-hard problem. According to [9], the running time of depth-first search is O(nl f n2), or it is related to the number of nodes & arcs. Unlike the worst-case complexity of O(.) notation, the e(.) notation provides both a LB & UB (a more precise statement) on an algorithm’s performance. The PROLOG AI data-structure further enhances the computational effi- ciency. This explains why the path-enumeration algorithm in FORMULA executed in minutes even in a PC-AT class microcomputer, rather than hours in a comparable FOR- TRAN code for cut-set enumeration.
Network-design problems are difficult a t best. Short of brute-force simulation approaches, finding bounds is the only feasible way to estimate the network performance [7]. This paper proposes a LB on throughput which appears to be efficient and, more importantly, tighter than most oth- ers in the literature. We used this LB in network design; it yields results consistent with Monte-Carlo simulation. Aside from LB on throughput, appendix A.2 has a UB for network reliability. These last two points are elaborated in section 6.
Observed Maximum Flow
10 20 30 40 50 60
Frequency Of Occurrence { % )
Figure 8. Throughput Distribution for Network #4 [la]
8. DISCUSSION
Refs [4, 121 provide a set of controlled experiments on the most important 4 of the 7 networks we have tested. This allows us to estimate the ‘exact throughput to net- works #4, #A, #B, #C’, and also full distributions on throughput for networks #4, #C. Figures 8 & 9 show such throughput distributions which are obtained by run- ning lo4 replications of Monte-Carlo simulation each. Al- though we cannot generalize, €he distributions appear to be bi-modal, with one mode on zero capacity and an- other a t some positive value. The important point is that they are far from being Gaussian distributions, and zero- throughput is a prominent phenomenon. For example, it accounts for 60% of the state-space in network #4 and 38% in network #C. This confirms findings elsewhere that a tiny fraction of the failure states account for most of the state space (see appendix A.2).
Notation for Figures 8 ~ 9
$ lower bound 62 exact throughput & upper bound
R.esponse-surface models were also fitted on top of the hours/days of simulation results on networks #4 & #C [4]. The results are shown for network #C, the larger and much more interesting of the two.
CHAN ET A L EXACT & APPROXIMATE IMPROVEMENT TO THE THROUGHPUT OF A STOCHASTIC NETWORK 483
Observed Maimum Flow
***********
***************#***** 2000
20 30 40 50 60 Frequency Of O C C U ~ ~ ~ C C (% 1
10
Figure 9. Throughput Distribution for Network #C [4]
Terms in (19) vs Their &Values (There are 31 degrees-of-freedom.)
2243p1,1 24 30 1299.6~1,~ 14 08
0.14461-11 11 71 0.38062-li 30,85 O.268iid-11 16.32
The ‘coefficient (of multiple determination’ = 0.988. These data suggest!; a 1% s-significance level, or better. The ii are in hundreds-of-units (eg, 31-2 = 20 =+- 2000).
The reliability response-surface is:
R = 0.6284 + 0.094,01,1 + 0.0094p1,2 + 0.0071611--39, (20)
with a similar s-significance level as in (19). The response-surlace analysis points toward the same
conclusions that we drew from mathematical programming (albeit at a drastically different computational require- ment). For example, any improvement in throughput is contingent upon the capacity of the arc from node 2 to node 11. The importance of node 11 on network reliabil- ity is confirmed. The R in (20) is consistent with that defined in (115), with: R = 70.93 + 70.9331, from (20); R = 89.67%, from ( I 15).
As anticipated from the discussion in appendix A.2, the latter (115) over-estimates the former (20). The same is observed for network #4, with: R = 15.19 3 15.19%, from (20); R = 33.52%, from (1 15).
Generally speaking, when R is high, the T is low, and vice-versa - as one would anticipate. This result is con- firmed in table 2, where R & T are displayed. For network #A, R + T = 100% - because the capacities for all flow
paths are 1200, as determined by the arcs emanating from nodes 1, 2, 3, 4. Eqs (115) & (116) show this result when ii, = 1200 for all path j ’ s - hence dropping out in (116), making R + T = 1. Network #B has a high vulnerability of 92%. A review of network #B, and its discussion in section 6, shows the criticality of node 16 and mcs (4,24), (6,25), (6,26), which is reflected through (116) - designed as an extension of (111).
ACKNOWLEDGMENT We are pleased to thank other members of the research
team who worked on the simulation models, which served as a datum for validation of our model. They include T.G. Bailey, K. Bauer, D. Knue, and G. Morgan (in alphabetical order). We also appreciate the research support from the US Department of Defense. Part of the travel to present this paper a t a national meeting of the Institute for Op- erations R.esearch and Management Science was funded by the Center for R,eliability & Maintainability at the Air Force Institute of Technology. The statements in this pa- per are the sole responsibilities of the individual authors. They do not necessarily represent the official views of the present or past affiliations of the authors.
APPENDIX A . l Notes on Throughput Bounds
For realistic-size networks, the most practical LB & UB are those reported in (9) & (10) for both regular flow- models and network-improvement models, They offer rea- sonable results commensurate with an acceptable level of accuracy. Even though the tightness of the LB & UB can only be experimentally measured in the real world, it is useful to provide the theoretical background govern- ing such tightness. The accuracy of these LB & UB are developed & discussed in this appendix. A.1.1 Further Comment on UB
Ref [24] gives a UB approximation of the mean max-flow when the number of random arcs is small. She estimated the error involved in setting the random capacities to their means as shown in (14). Such a result can be generalized to network-design problems, where U,, U%, 21, are re-defined as the expanded arc-capacities after improvement - rather than the original arc-capacities. Specifically, for m random arcs in a network of n arcs, replacing a random capacity Up by its mean up results in the inequality:
E(J‘(u1, . . . ,up , . ,un-m, VI, - - 9 Um)} L E{F(ui,. . . ,uP-i ,up+i , . . . , U i , . . . , u p , . . ,Um)}.
(101) Notation
F(U) max-flow corresponding to the optimal value of U for a given B; see (3) - (6). F(x,d), F ( x , g ) can be shortened to F(U)
It becomes difficult for m 2 2 to compute the error:
484 IEEE TRANSACTIONS ON RELIABILITY, VOL. 46, NO. 4, 1997 DECEMBER
It is more feasible to estimate E(F(U1, U2)) by A.1.2.1 Simpler LB The model, (7) - (9), involves path enumeration in a net-
work. In view of the computational complexity, [6] showed that by using a log-linear transformation of (8) in the ob- jective function, one can find a simpler LB to the measure VL(X) in (7) & (9), although this simpler LB is less tight:
E(F(u1, U2)) or E(F(h ,U2)) :
F ( ~ 1 , % 2 ) - E(F(Ul,U2)) = el . L1 - fl , = el - f1 + (el - 1) . L1, otherwise;
for u1 2 L1; (103) (104)
i Notatzon ( K f ln(R,)). X , : A . X 5 U,X 2 0 ; (108)
L1 F(G, U2) - F(0 , U21 el Pr(U1 I L 1 )
GL, Cdf(F(Ui,u*)) fl Jtl U* . dGL,(u*)
U can be extended here to include the capacity expansion, as suggested by (11) - (13).
Re-formulation in node-arc incidence form - using the relationship between path and arc survivability - yields:
The error as measured by (103) is no worse than,
F(u1, U21 - E{F(Ul, U2)>1
F(u i ,u2) L E(F(Ui1u2)} L E{F(U1,U2)}.
m a x { g c : .z, : H . x = b,O 6 x 5 ii (109) by virtue of (101). Eqs (101) - (104) show that:
(105)
The UB on the mean max-flow is obtained by setting a subset of the random arc-capacities to their mean values, as suggested in (14) & (101), and illustrated in the numer- ical examples in section 4. This extends our original UB based on the Jensen inequality.
The result in (105) can be generalized to any number of terms, say m, n:
F(U1rU2,*.* 2 E(F(U1, ~ 2 , . . . ,U,))
LE{F(Ul ,U2, . . . ,U,)>
L E { W l , u2,. * > U,)> (106)
...
Notation H node-arc incidence matrix K a free parameter: K 2 - ln(minj{Bj})
K ,
ln(pi), 0, otherwise.
for the artificial arc re-circulating flow from t to s
if arc i is stochastic
Except for the improvement portion of the formulation, the LB can be estimated either by a path-oriented method, see (108), or by a common network-flow algorithm, see (log), as discussed in section 7. The important point is that unlike the original formulation, path enumeration can be avoided. Should the node-arc incidence form be used, some very efficient network-flow codes are available to solve the model as mentioned in section 7.
Since the log function is monotonic, this simpler LB, see (108) or (log), preserves the ranking of the paths in terms of their reliability and other salient features of the original formulation. Having solved the LB in (log), one
LB as close to the original path-oriented model as possible, is obtained. A.1.2.2 Upper Bound
Unfortunately, the error so introduced can be calculated analytically only for highly simplified 2-arc networks with no more than one random arc-capacity. The error of a general bound can only be measured by comparing it with the (simulated) mean throughput. A.1.2 Further Comment on LB
to calculate the LB capacity on the flow Problem d&ned by (5) & (6) and further expanded by (9), (11) - (13). This LB value depends upon the capacity of each path, where the path capacity is defined as:
Another of approximating the mean throughput is can parametrically vary K to see if a solution yielding a
The UB can be estimated by the node-arc formulation
ie, path capacity is defined by the smallest arc-capacity in the path, as illustrated by the numerical examples in section 4. The set of constraints in (11) & (12) in the mathematical program automatically guarantees this. The real issue is the randomness of U,. In the max-flow problem defined in section 2 where the arc capacity is either up or down, the mean path-capacity is R, . ii, for each term of (9). The sum of the mean capacity of each path, as defined in (9), becomes the value of the LB, under (5) & (6).
of (109) as well when U is replaced by U and c: = 1 only for the artificial arc from t to s , with all other arc costs set to zero. With the availability of network-flow codes, it is an extremely efficient way of computing the UB as shown in (15). A.1.3 Exact Estimation of Throughput
Ref [14] pointed out that the LB [6] gives the exact value of the mean max-flow iff the network obtained by removing all residual capacities is monofil. Ref [13] also outlined the necessary & sufficient conditions for the Onaga UB (10) to provide the exact value of the mean max-flow.
CHAN ET A L EXACT di APPROXIMATE IMPROVEMENT TO THE THROUGHPUT OF A STOCHASTIC NETWORK 485
The conditions are more exacting for the UB, compared to the LB. This happens when the graph is bipartite in the following way. Let C be a cut-set for a network. The arcs with survival probabilities between the open inter- val 0 & 1 (except the minimum cut-set arcs) are removed from the network. [f the resulting deterministic network is partitioned into 2 parts, separated by the same mini- mum cut-set C, then the mean max-flow in the original network is Vu, exactly. In practice, there are many acyclic networks. But the likelihood of obtaining the same bi- partite graph between the original and reduced network as described is unlikely. Between the LB & UB, the LB is therefore anticipated to be a more accurate estimate of the mean max-flow.
A.2 Measuring Vulnerability & Reliability Notation
xi* minimum value of the flow through arc i in the max-flows the state after the damage
Ref [19] proposed 2 measures of vulnerability for the network, T , when the capacity a t an arc is reduced (in- cluding its elimination). The generalized measures show the degree of influence arc i has on the throughput. There are several max-flows realizing the value F ( x ) in (2), con- sidering the number of states possible. Let arc 1 (i = 1) be damaged during an irldversity. For a general survivability- distribution on arc 1,
xi* - x:* = F ( x ) - F’(x). (110)
If the influence of arc 1 is greater than that of arc 2, then:
2 1 ‘ Xi. x2* X‘
F ( x ) F’(x) - FI:x) F’(x)’ - - - > _- - 2’
A more overall measure of network-performance [I 11 was subsequently extended by [22]. Ref [ll] recognizes that a tiny fraction of the total number of failure states account for most of the state space. For example, the states that result in zero throughLput are a prominent part of the state- space - a fact verified in figures 8 & 9.
Notation A , A’
T
R(sk)
set of [functioning, failed] arcs number of most probable states, T << 2” network reliability a t state k
The reliability of a network can be approximated by the LB [all:
T
(113)
Algorithms were provided to generate the T most prob- able states; the R converges very rapidly between the LB & UB as a handful of probable states are generated [l, 151.
While the measures (113) & (114) are useful, a much simpler measure of vulnerability & reliability is obtainable from the arc-path formulation in this paper [18]. Thus out of q paths possible from s to t , T* paths (T* << q ) can be used in the LB computation. (These paths need not be disjoint.) A simple indicator of reliability of the network is:
which records the system redundancy for alternate path choices. Generally, the more paths used, the greater the redundancy (and hence the higher the reliability). In the spirit of ( l l l ) , which shows the fraction of flow-loss in an adversity, vulnerability can be defined as:
The larger the exposure, the more vulnerable. This sum- marizes the flow-path criticality-rating proposed by [19] and the failure-state concept suggested by [ll]. These measures break down in the limiting cases. For example, when all paths are used (T* = q ) , R = 0 no matter how reliable the network is.
To the extent that T* << q for most realistic networks, we anticipate the measures of (115) & (116) to over-estimate the mean network reliability & vulnerability; ie, they are likely to be a UB similar to (114). R & T are computed for the larger network and the results compared to the exact values estimated by simulation, which measures s-t connectivity directly [2]. While there are other measures of reliability & vulnerability, these working definitions can be readily computed inasmuch as path enumeration is an integral part of the modeling approach in our research, as illustrated in section 4 and explained in the computational algorithm in section 5 .
REFERENCES
[I] H.M. AboElFotoh, C.J. Colbourn, “Series-parallel bounds for the two-terminal reliability problem”, ORSA J. Com- puting, vol 1, 1989, pp 209-222.
[2] C. Alexopoulos, G.S. Fishman, “Sensitivity analysis in stochastic flow networks using the Monte-Carlo method, Networks, vol 23, 1993, pp 605-621.
[3] Y.P. Aneja, K.P.K. Nair, “Maximal expected flow in a network subject to arc failure”, Networks, vol 10, 1980, pp 45-57.
k=l
486 IEEE TRANSACTIONS ON RELIABILITY, VOL. 46, NO. 4, 1997 DECEMBER
[4] T.G. Bailey, “Response surface analysis of stochastic net- work performance”, Masters Thesis, 1988; Dep’t of Oper- ational Sciences, US AFIT, Wright-Patterson AFB.
[5] I. Brako, PROLOG Programmang for ArtaJicaal Intella- gence, 1987; Addison-Wesley.
[6] M. Carey, C. Hendrickson, “Bounds on expected perfor- mance of networks with links subject of failure”, Networks,
[7] C.J. Colbourn, L.D. Nel, “Using and abusing bounds for network reliability” , reprint from IEEE Communication SOC, IEEE Global Telecommunacataons ConA 1990 Dec.
[8] W.L. Gaught, “Improving reliability in a stochastic com- munication network”, Masters Thesas, 1990; Dep’t of Op- erational Sciences, US AFIT, Wright-Patterson AFB.
[9] T.H. Gormen, C.E. Leiserson, R.L. Rivest, Introductaon to Algorathms, 1990; MIT Press and McGraw-Hill.
[lo] W. Kishimoto, “A method for obtaining the maximum multiroute flows in a network”, Networks, vol 27, 1996, pp
[11] V.O.K. Li, J.A. Silvester, “Performance analysis of net- works with unreliable components”, IEEE Trans. Com- munacatzons, vol COM-32, 1984, pp 1105-1110.
[12] A. Marsh, G. Morgan, Private communication, 1988; US Dep’t of Defense.
[13] H. Nagamochi, T. Ibaraki, “Maximum flows in probabilis- tic networks”, Networks, vol 21, 1991, pp 645-666.
[14] H. Nagamochi, T. Ibaraki, “On Onaga’s upper bound on mean values of probabilistic maximum flows”, IEEE Trans. Relaabzlzty, vol 41, 1992 Jun, pp 225-229.
[15] L.D. Nel, C. J. Colbourn, “Combining Monte-Carlo esti- mates and bounds for network reliability”, Networks, vol 20, 1990, pp 277-298.
[16] K. Onaga, “Bounds on the average terminal capacity of probabilistic nets”, IEEE ’Trans. Informataon Theory,
[17] N.G.F. Sancho, “On the maximum expected flow in a net- work”, J . Operational Research Society, vol 39, 1988, pp
[18] B. Sanso, F. Soumis, “Communication and transportation network reliability using routing models”, IEEE Trans. Relaabzlzty, vol 40, 1991 Apr, pp 29-38.
[19] M. Sengoku, S. Shinoda, R. Yatsuboshi, “On a function for the vulnerability of a directed flow network”, Networks,
[20] D. Shier, E. Bibelnieks, J.P. Jarvis, R.J. Lakin, “Algo- rithms for approximating the performance of multimode systems”. IEEE Proc. INFOCOM, 1990, pp 741-748.
[21] D.R. Shier, Network Relaabzlzty and Algebrazc Structures, 1991; Oxford University Press.
[22] D.R. Shier, “A new algorithm for performance analysis of communication systems”, IEEE Trans. Communacataons,
[23] D.R. Shier, D.F. Whited, “Algorithms for generating min- imal cut sets by inversion”, IEEE Trans. Relaabzlzty, vol
V O ~ 14, 1984, pp 439-456.
279-291.
1968, pp 766-768.
48 1-485.
V O ~ 18, 1988, pp 73-83.
VOI 36, 1988, pp 516-519.
R-34, 1985 Oct, pp 314-318.
[24] J.E. Somers, “Maximum flow in networks with a small number of random arc capacities”, Networks, vol12, 1982,
[25] S.W. Wallace, “Investing in arcs in a network to maximize the expected max flow”, Networks, vol17, 1988, pp 87-103.
[26] R.D. Wollmer, “Investments in stochastic maximum flow networks”, Annals operations Research, vol 31, 1991, pp
[27] E. Yim, “Improving the survivability of a stochastic com- munication network”, Masters Thesis, 1988; Dep’t of Op- erational Sciences, US AFIT, Wright-Patterson AFB.
pp 241-253.
459-468.
AUTHORS Dr. Yupo Chan; Dep’t of Operational Sciences (ENS); AFIT; 2950 P St; Wright-Patterson AFB, Ohio 45433-7765 USA. Internet (e-mail): [emailprotected]
Yupo Chan is Professor of Operations Research. He has 25 years of post-doctoral experience in industry, universities, and government, including a Congressional Fellowship at the Office of Technology Assessment. He received his BS (1967) in Civil Engineering, MS (1969) in Transportation Systems, and PhD (1972) in Operations Research, all from the Massachusetts Institute of Technology.
Major Eugene Uim; Analyses Division (XPY); HQ US Air Force; 1070 Air Force Pentagon; Washington, DC 20330-1070 USA. Internet (e-mail): [emailprotected])
Eugene Yim received the BS (1984) in Electrical Engineer- ing from the University of Texas, Austin, the MS (1988) in Op- erations Research from the Air Force Institute of Technology, and PhD (1997) in Operations Research and Industrial Engi- neering from the University of Texas, Austin. He is a principal analyst at the HQ, US Air Force, where he performs research & analysis relating to space programs. His research interests are feature representation & matching.
Dr. Alfred B. Marsh 111; Maine Maritime Academy; Castine, Maine 04420 USA. Internet (e-mail): [emailprotected]
Alfred Marsh was, when he did this work, a technical direc- tor in the Operations Research staff at the US National Security Agency, modeling telecommunication systems. He is an Asso- ciate Professor of Mathematics and Computer Science at the Maine Maritime Academy - a College of Engineering, Science, and Management. He earned his BA (1968) in Mathematics, MSE (1969) in Operations Research, MS (1972) in Computer Science, MS (1982) in Electrical Engineering, and PhD (1979) in Mathematical Sciences - all from Johns Hopkins University.
Manuscript TR96-114 received 1996 August 14;
Responsible editor: C.J. Colbourn Publisher Item Identifier S 0018-9529(97)09384-6
revised 1997 May 12, 1997 October 5.
mailto:[emailprotected]
mailto:[emailprotected]
