# Survivable Networks: Algorithms for Diverse Routing

Springer Science & Business Media, 1999 - Computers - 200 pages
Survivable Networks: Algorithms for Diverse Routing provides algorithms for diverse routing to enhance the survivability of a network. It considers the common mesh-type network and describes in detail the construction of physically disjoint paths algorithms for diverse routing. The algorithms are developed in a systematic manner, starting with shortest path algorithms appropriate for disjoint paths construction. Key features of the algorithms are optimality and simplicity. Although the algorithms have been developed for survivability of communication networks, they are in a generic form, and thus applicable in other scientific and technical disciplines to problems that can be modeled as a network.
A notable highlight of this book is the consideration of real-life telecommunication networks in detail. Such networks are described not only by nodes and links, but also by the actual physical elements, called span nodes and spans. The sharing of spans (the actual physical links) by the network (logical) links complicates the network, requiring new algorithms. This book is the first one to provide algorithms for such networks.
Survivable Networks: Algorithms for Diverse Routing is a comprehensive work on physically disjoint paths algorithms. It is an invaluable resource and reference for practicing network designers and planners, researchers, professionals, instructors, students, and others working in computer networking, telecommunications, and related fields.

### What people are saying -Write a review

We haven't found any reviews in the usual places.

### Contents

 INTRODUCTION 1 12 DEFINITIONS AND NOTATIONS 14 13 TYPES OF GRAPHS CONSIDERED 18 SHORTEST PATH ALGORITHMS 21 22 THE DIJKSTRA ALGORITHM 22 23 THE MODIFIED DIJKSTRA ALGORITHM 29 24 THE BREADTHFIRSTSEARCH BFS SHORTEST PATH ALGORITHM 33 25 CONCLUDING REMARKS 35
 51 FIBER NETWORK DESCRIPTION 118 52 SHORTEST PAIR OF PHYSICALLY DISJOINT PATHS ALGORITHM 123 53 APPLICATION TO OTHER POSSIBLE CONFIGURATIONS 148 54 CONCLUDING REMARKS 155 MAXIMALLY DISJOINT PATHS ALGORITHMS FOR ARBITRARY NETWORK CONFIGURATIONS 157 61 GENERAL APPROACH 158 63 OPTIMAL ALGORITHM FOR MAXIMAL DISJOINTNESS 162 K 2 DISJOINT PATHS ALGORITHMS 175

 SHORTEST PAIR OF DISJOINT PATHS ALGORITHMS 39 32 THE SIMPLE TWOSTEPAPPROACH ALGORITHMS AND THEIR SHORTCOMINGS 40 33 EDGEDISJOINT SHORTEST PAIR ALGORITHM DEVELOPMENT 46 34 VERTEXDISJOINT SHORTEST PAIR ALGORITHM DEVELOPMENT 68 35 SUURBALLES DISJOINT PAIR ALGORITHMS 86 36 COMPARISON OF THE DEVELOPED ALGORITHMS AND THE SUURBALLES ALGORITHMS 92 MAXIMALLY DISJOINT PATHS AND PHYSICAL DIVERSITY VERSUS COST ALGORITHMS 93 41 IMPLEMENTATION OF EDGEDISJOINT PATHS ALGORITHMS 94 42 IMPLEMENTATION OF VERTEXDISJOINT PATHS ALGORITHMS 99 43 PHYSICAL DISJOINTNESS VERSUS COST 108 PHYSICALLY DISJOINT PATHS IN REALLIFE TELECOMMUNICATION FIBER NETWORKS 117
 72 K 2 VERTEXDISJOINT PATHS ALGORITHMS 179 73 IMPLEMENTATION OF K 2 DISJOINT PATHS ALGORITHMS 182 DISJOINT PATHS MULTIPLE SOURCES AND DESTINATIONS 183 82 TWO SOURCES SINGLE DESTINATION 184 83 TWO SOURCES TWO DESTINATIONS UNFIXED SOURCEDESTINATION PAIRS 185 84 TWO SOURCES TWO DESTINATIONS FIXED SOURCEDESTINATION PAIRS 186 FURTHER RESEARCH 189 REFERENCES 191 INDEX 195 Copyright

### About the author (1999)

Bhandari, AT&T Laboratories, Lincroft, NJ, USA.