## Survivable Networks: Algorithms for Diverse RoutingSurvivable 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 |

191 | |

195 | |

### Common terms and phrases

ABCDZ Algorithm 3.2a Algorithm 5.1 arcs directed BFS algorithm Chapter connecting vertex cost denote destination vertex DISJOINT PATHS ALGORITHMS endpoint vertices erasure example express link Find the shortest fork configuration forward arcs given graph given pair graph G graph of Figure IEEE INF2 interlacing iteration junction node labeled vertex length equal modified Dijkstra algorithm modified graph negative arcs negative cycles nonnegative arcs optimal pair original graph original network pair of disjoint pair of edge-disjoint pair of paths pair of physically pair of vertex-disjoint pair of vertices parameter path from vertex path length paths in Network physically disjoint paths Refer to Figure result s x Sp second path shortest edge-disjoint pair shortest path algorithm shortest path found shortest path tree shortest triplet source vertex span node span overlap split SPVP algorithm Step subvertex subvertices telecommunication networks total length traffic undirected graph vertex Z vertex-disjoint paths Vertex-Splitting Method Y configuration zero

### References to this book

Next Generation Optical Network Design and Modelling: IFIP TC6 / WG6.10 ... Andrea Bianco,Fabio Neri No preview available - 2003 |

Next Generation Optical Network Design and Modelling Andrea Bianco,Fabio Neri No preview available - 2003 |