Chapter Eleven. Route Computation and Path Selection

11.1 INTRODUCTION

11.2 SHORTEST PATH COMPUTATION

11.2.1 The Bellman-Ford Algorithm

11.2.1.1 Bellman-Ford Algorithm Example

11.2.2 Dijkstra's Algorithm

11.2.2.1 Dijkstra's Algorithm Example

11.2.3 A Comparison of Bellman-Ford and Dijkstra Algorithms

11.3 ROUTING WITH SIMPLE CONSTRAINTS

11.3.1 Link Protection Constraints Example

11.3.2 Bandwidth Constraints

11.4 PATH SELECTION FOR DIVERSITY

11.4.1 Link Diverse Routing Algorithms

11.4.1.1 Nonoptimal Disjoint Paths via Pruning

11.4.2 Shortest Link Diverse Paths Algorithm

11.4.2.1 Link Disjoint Path Pair Algorithm

11.5 NETWORK OPTIMIZATION

11.5.1 Batch Processing

11.5.2 Shortest Path: Mathematical Formulation

11.5.3 Multicommodity Flow: Mathematical Formulation

11.5.4 Formulating and Solving Multicommodity Optimizations

11.6 SUMMARY