To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.
You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.
Reliability problems arise with incresing frequency as our moder systems of telecommunications, information transmission, transportation, and distribution become more and more complex. This workshop was designed to analyze the discret mathematical methods which are relevant to these problems, to identify the latest trends and important opern problems, and to survey potential practical applications, with an emphasis on computer and communication networks.
The workshop analyzed both questions of computation of reliability of existing systems and questions dealing with the design of highly reliable systems to begin with. (The two questions are closely related, since one needs to know how to compute reliability in order to design a reliable system.) The workshop also analyzed the closely related notion of survivability. Network survivability means the ability to restore "service" in the event of a catastrophic failure of a network component. We also discussed how to build redundancy into a network, how to define and measure redundancy, and how redundancy relates to reliability. The workshop dealt with both single stage and multistage, interconnected networks, which have been studied in connection with computer networks, and in particular with fault tolerance and otehr reliability issue sin mind. The workshop emphasized practical applications through invited speakers from a variety of companies that are dealing with practical network reliability problems.
In all, there were 89 attendees at the workshop, with the average daily attendance about 50. The attendees included theoretical mathematicians, computer scientists, and electrical engineers from academia and industry, as well as network parctitioners, engineers, and reliability planners from such companies as AT&T Bell Labs, Bellcore, Pacific Bell, GTE, Bolt, Beranek and Newman, MITRE, and IBM.
The workshop started with a session on network reliability. The speakers in that session were Charles Colbourn (Waterloo), Scott Provan (North Carolina), and Douglas Shier (William and Mary). These three speakers summarized the traditional problem of computing the reliability polynomial of a graph when there can be edge failures. Colbourn discussed the use of graph transformation to obtain bounds on the relibility. Provan discussed two types of approximation schemes for reliability, one using the property of shellability and the other using series-parallel and delta-wye transformations. Shier discussed algebraic methods for bounding reliability.
A second session on network reliability featured talks by Ricahrd McLean (Rutgers) and Andras Prekopa (Rutgers). McLean's talk brought to the reliability problem the point of view of the economist, and in particular the game theorist, and presented axioms which completely characterized the reliability polynomial. This point of view was quite novel and was received with great interest by the more traditional reliability theorists. Prekopa's talk also presented a nontraditional approach, making use of some recently developed lower and upper bounds for the probability of logical functions of events to obtain lower bounds for the reliability of a network.
The first day concluded with a session on applications which featured talkds by A.G. (Sandy) Fraser (AT&T Bell Labs) and Peter Kubat (GTE Laboratory). A third talk in this session, by Marianne Lepp (Bolt, Beranek and newman), was cancelled due to the speaker's illness. This first of three applied sessions at the workshop was intended to have practitioners present both important uses of theoretical reliability methods and new practical network reliability problems. Fraser's talk dealt with congestion and instability in data networks, and emphasized the new reliability problems posed by the large capacity of fiber optic connections. There was a great deal of interaction between the speaker and the audience, with many suggestions made for possible approaches to the problems posed, and with many suggestions made for possible approaches to the problems posed, and with many ideas for potential future reliaiblity research being discussed. After the session, it was agreed that the talk was such a success that it should be followed up by a more detailed presentation to a DIMACS group by a Bell Labs scientist. One of the positive aspects of Marianne Lepp's cancellation was that we were able to allow this part of the session to continue for one hour instead of the scheduled half hour. Kubat's talk emphasized a variety of approaches to the design of reliable and quality telecommunicaitons systems from the point of view of future costs and also resulted in a lively discussion.
The second day began with a session on reliability of multistage networks and fault tolerance. The session was introduced with a brief summary of the topic by Anujan Varma (IBM). The speakers in this session were D.K. Pradhan (Massachusetts), D.P. Agrawal (North Carolina State), and C.S. Raghavendra (Southern California). This session featured talks by electrical engineers/computer scientists, and was a very nice complement to both the mathematically oriented talks of the first day and the applied talks. One of the things which many of the participants pointed to as a highlight of the meeting was that we got together so many diverse researchers who do not usually attend the same meetings. Pradhan talked about a particluar multiprocessor network which is of great interest today, the de bruijn network. (A later speaker, Jean-Claude Bermond, also talked about the de Bruijn network.) Agrawal talked about redundant multistage interconnection networks (MIN's) and presented an algorithm for computing their reliability. Raghavendra also talked about MIN's and presented a variety of techniques for achieving fault-tolerance.
The next session dealt with network survivability, the problem of how to design a network which had prescribed survivability characteristics, given the desire to build such a network at minimum cost. The speakers in this session were Martin Grotschel (Augsburg) and Daniel Bienstock (Columbia). Grotschel's talk was a beautiful mix of theory and practice. It described how he and Clyde Monma had worked with Bellcore scientists (including Richard Cardwell, a network practitioner) to convince the regional Bell Telephone companies that survivability could be built into a network with small additional cost. It discussed how they interacted with the practitioners to define the precise mathematical problem, which tey then solved using polyedral methods. When one of the attendees questioned the seeming oversimplification in the network survivability model used by Grotschel, he was reassured by Cardwell that this was exactly the appropriate model to use. Bienstock's talk dealt with problems of searching a graph, seeking out an intruder by the use of guards. It covered a variety of important recent developments having to do with such graphical parameters as path-width and tree-width.
A second session on network survivability featured talks by William Cunningham (Carleton University, Ottawa) and Frank Boesch (Stevens). Cunningham discussed a variety of network attack problems, which are optimization problems in which one tries to minimize the difference between the effort required by an attacker to destroy the edges in a subset of a network and the resulting damage to the network. boesch gave a very nice summary of the node reliability problem, the reliability problem where nodes fail, rather than edges.
The second day ended with our second session on applications. This session again featured practitioners, in this case Gerald Ash (AT&T Bell Labs) and Richard Cardwell (Bellcore). A third talk, by Neal Crystal of Bellcore, had to be cancelled because the speaker was unable to attend. Ash described the 1987 AT&T switch from hierarchical routing of calls through its network to dynamic non hierarchical routing. He emphasized how much money AT&T had saved as a result and how much more reliable tings had become as a result. In answer to a question from the audience, he emphasized the important role that theoretical developments had played in the decision to make the switch to dynamic nonhierarchical routing, and in the design of the new system. He cited the important contribution of a foundational paper by Fan Chung, Ron Graham, and Frank Hwang, and the significance of the development of the linear programming algorithm of Karmarkar. Ash also discussed future routing methodologies and the technical problems involved in implementing them. Cardwell talked about alternative network topologies for building survivable fiber networks. He emphasized a ring topology which many of the participants found very interesting. There was considerable discussion about how to balance off the initial cost savings of such a network with the fact that once the network reaches capacity, it is very difficult and expensive to modify. Many interesting and important theoretical questions arose from this discussion.
The third day began with a session on redundancy and reliability of special networks. The four speakers were Joel Cohen (Rockefeller University), Nicholas Maxemchuk (AT&T Bell Labs), Philip Boland (University College, Dublin), and C.Y. Chyu (Berkeley). Cohen talked about calculating the reliability of a random graph or digraph, and also about calculating the redundancy as measured by the expected number of spanning tress. He explored the relationships between the two. Maxemchuk discussed a particular network topology, the Manhattan street network, and its reliability properties. Boland discussed reliability problems in which components of a system are arranged linearly and the system fails if and only if k consecutive components fail. He introduced positive dependence between adjacent components and argued that the system reliability is a decreasing function of this dependence for k large. Chyu talked about influence diagrams, structured digraphs which are used in applications to medical decisionmaking, realibility analysis, etc.
A second session on redundancy and reliability of special networks featured two speakers, Jean-Claude Bermond (CNRS, Valbonne) and Frank Hwang (AT&T Bell Labs). Bermond continued the discussion of special network topologies by discussing reliability properties of de Bruijn and Kautz graphs, and by introducing various generalizations of these graphs. He surveyed both recent results and open problems. Hwang discussed double loop networks, which are directed circulants, and which also have a potentially useful new network topology. He described a novel method for obtaining the most reliable double loop networks. He also gave a routing algorithm for such networks.
The final session of the workshop was the third session on applications. This featured a talk by Ying Cheng (AT&T Bell Labs). A second talk by Ralph Evans (private consultant), was cancelled due to the illness of the speaker. Cheng's talk dealt with ATM (asynchronous transfer mode) networks. He used algebraic and combinatorial methods to develop an error correction/error detection scheme in such networks.
The workshop was a success because it fostered so many new interactions between researchers and betweeen researchers and practitioners. It has also already had a very visible and dramatic impact. A number of participants from such companies as Pacific Bell were so excited by the potential value of the methods for designing highly survivable fiber optic networks which were discussed at the meeting, that they suggested that Bellcore arrange a follow-up meeting for Bellcore employees and employees of the Bell system operating companies. As a direct result of our DIMACS activity, such a workshop, entitled "Telecommunications Network Survivability Symposium," was organized for Bellcore and the Bellcore client companies. One of us, Clyde Monma, was a co-organizer. The response to the workshop was very enthusiastic: there were over 200 participants and the feedback from participants was that the workshop was timely and important.
The editors hope that the foundations laid by the workshop, its follow-up workshop, and this volume will lead to continuing developments in this exciting and importanat field.
Preface v
Program ix
List of Participants xv
Robust Desing of Dynamic Routing Networks
Gerald R. Ash 1
Graph Searching, Path-Width, Tree-Width and Related Problems
(A Survey)
Daniel Bienstock 33
On Residual Connectedness Network Reliability
F. Boesch, A. Satyanarayana, and C. Suffel 51
Survivable Fiber Network Design
R.H. Cardwell 61
Decomposable Probabilistic Influence Diagrams
C.C. Chyu 79
Bounding Network Parameters by Approximating Graphs
Charles J. Colbourn and Eugene I. Litvak 91
The Optimal Multiterminal Cut Problem
William H. Cunningham 105
Polyhedral Approaches to Network Survivability
M. Grotschel, C. Monma, and M. Stoer 121
A Survey on Double Loop Networks
F.K. Hwang 143
Quantitative Reliability Analysis of Redundant Multistage
Interconnection Networks
Nita M. Kini, Anup Kumar, and Dharma P. Agrawal 153
An Axiomatic Characterization of the Reliability Polynomial
Richard P. McLean and Douglas H. Blair 171
Fault-Tolerant VLSI Architectures Based on de Bruijn Graphs
(Galileo in the Mid Nineties)
Dhiraj K. Pradhan 183
The Use of Binomial Monments for Bounding Network Reliability
Andras Prekopa, Endre Boros, and Keh-Wei Lih 197
Boolean Decomposition Schemes and the Complexity of Reliability
Computations
J. Scott Provan 213
On Dynamic Full Access in Multistage Interconnection Networks
C.S. Raghavendra and M.A. Sridhar 229
Algebraic Methods for Bounding Network Reliability
Douglas R. Shier 245
Index of Volumes
DIMACS Homepage