Routing, Flow, and Capacity Design in Communication and Computer Networks (Hardcover)

Description:

In network design, the gap between theory and practice is woefully broad. This book narrows it, comprehensively and critically examining current network design models and methods. You will learn where mathematical modeling and algorithmic optimization have been under-utilized. At the opposite extreme, you will learn where they tend to fail to contribute to the twin goals of network efficiency and cost-savings. Most of all, you will learn precisely how to tailor theoretical models to make them as useful as possible in practice.

Throughout, the authors focus on the traffic demands encountered in the real world of network design. Their generic approach, however, allows problem formulations and solutions to be applied across the board to virtually any type of backbone communication or computer network. For beginners, this book is an excellent introduction. For seasoned professionals, it provides immediate solutions and a strong foundation for further advances in the use of mathematical modeling for network design.

Table of Contents:

Foreword
Preface

PART I - INTRODUCTORY NETWORK DESIGN

Chapter 1 - Overview
1.1 A Network Analogy
1.2 Communication and Computer Networks, and Network Providers
1.3 Notion of Traffic and Traffic Demand
1.4 A Simple Design Example
1.5 Notion of Routing and Flows
1.6 Architecture of Networks: Multi-Layer Networks
1.7 Network Management Cycle
1.8 Scope of the Book
1.9 Naming and Numbering Convention
1.10 Summary

Chapter 2 - Network Design Problems—Notation and Illustrations
2.1 A Network Flow Example in Link-Path Formulation
2.2 Node-Link Formulation
2.3 Notions and Notations
2.4 Dimensioning Problems
2.5 Shortest-Path Routing
2.6 Fair Networks
2.7 Topological Design
2.8 Restoration Design
2.9

• Multi-Layer Networks Modeling
  2.10 Summary
  Exercises for Chapter 2
  
  Chapter 3 - Technology-Related Modeling Examples
  3.1 IP Networks: Intra-Domain Traffic Engineering
  3.2 MPLS Networks: Tunneling Optimization
  3.3 ATM Networks: Virtual Path Design
  3.4 Digital Circuit-Switched Telephone Networks: Single–Busy Hour and Multi–Busy Hour Network Dimensioning
  3.5 SONET/SDH Transport Networks: Capacity and Protection Design
  3.6 SONET/SDH Rings: Ring Bandwidth Design
  3.7 WDM Networks: Restoration Design with Optical Cross-Connects
  3.8 IP Over SONET: Combined Two-Layer Design
  3.9 Summary and Further Reading
  Exercises for Chapter 3
  
  PART II - DESIGN MODELING AND METHODS
  
  Chapter 4 - Network Design Problem Modeling
  4.1 Basic Uncapacitated and Capacitated Design Problems
  4.2 Routing Restrictions
  4.3 Non-Linear Link Dimensioning, Cost, and Delay Functions
  4.4 Budget Constraint
  4.5 Incremental NDPs
  4.6 Extensions of Problem Modeling
  4.7 Summary and Further Reading
  Exercises for Chapter 4
  
  Chapter 5 - General Optimization Methods for Network Design
  5.1 Linear Programming
  5.2 Mixed-Integer Programming
  5.3 Stochastic Heuristic Methods
  5.4 LP Decomposition Methods
  5.5 Gradient Minimization and Other Approaches for Convex Programming Problems
  5.6 Special Heuristics for Concave Programming Problems
  5.7 Solving Multi-Commodity Flow Problems
  5.8 Summary and Further Reading
  Exercises for Chapter 5
  
  Chapter 6 - Location and Topological Design
  6.1 Node Location Problem
  6.2 Joint Node Location and Link Connectivity Problem
  6.3 Topological Design
  6.4 Lower Bounds for Branch-and-Bound
  6.5 Summary and Further Reading
  Exercises for Chapter 6
  
  Chapter 7 - Networks With Shortest-Path Routing
  7.1 Shortest-Path Routing Allocation Problem
  7.2 MIP Formulation of the Shortest-Path Routing Allocation Problem and Dual Problems
  7.3 Heuristic Direct Methods for Determining the Link Metric System
  7.4 Two-Phase Solution Approach
  7.5 Impact Due to Stochastic Approaches
  7.6 Impact of Different Link Weight System
  7.7 Impact on Different Performance Measures
  7.8 Uncapacitated Shortest-Path Routing Problem
  7.9 Optimization of the Link Metric System under Transient Failures
  7.10
• NP-Completeness of the Shortest-Path Routing Allocation Problem
  7.11
• Selfish Routing and its Relation to Optimal Routing
  7.12 Summary and Further Reading
  Exercises for Chapter 7
  
  Chapter 8 - Fair Networks
  8.1 Notions of Fairness
  8.2 Design Problems for Max-Min Fairness (MMF)
  8.3 Design Problems for Proportional Fairness (PF)
  8.4 Summary and Further Reading
  Exercises for Chapter 8
  
  PART III - ADVANCED MODELS
  
  Chapter 9 - Restoration and Protection Design of Resilient Networks
  9.1 Failure States, Protection/Restoration Mechanisms, and Diversity
  9.2 Link Capacity Protection/Restoration
  9.3 Demand Flow Re-Establishment
  9.4 Extensions
  9.5 Protection Problems
  9.6 Applicability of the Protection/Restoration Design Models
  9.7 Summary and Further Reading
  Exercises for Chapter 9
  
  Chapter 10 - Application of Optimization Techniques for Protection and Restoration Design
  10.1 Path Generation
  10.2 Lagrangian Relaxation (LR) With Subgradient Maximization
  10.3 Benders’ Decomposition
  10.4 Modular Links
  10.5 Stochastic Heuristic Methods
  10.6

Selected Application: Wavelength Assignment Problem in WDM Networks
10.7 Summary and Further Reading
Exercises for Chapter 10

Chapter 11 - Multi-Hour and Multi–Time-Period Network Modeling and Design
11.1 Multi-Hour Design
11.2 Multi-Period Design
11.3 Summary and Further Reading
Exercises for Chapter 11

Chapter 12 - Multi-Layer Networks: Modeling and Design
12.1 Design of Multi-Layer Networks
12.2 Modeling of Multi-Layer Networks for Restoration Design
12.3 Multi-Layer Design With Multi-Hour Traffic
12.4 Application of Decomposition Methods for Two-Layer Design
12.5 Numerical Results
12.6 Cost Comparison
12.7 Grooming/Multiplex Bundling
12.8 Summary and Further Reading
Exercises for Chapter 12

Chapter 13 - Restoration Design of Single- and Multi-Layer Fair Networks
13.1 Restoration Design of Single-Layer PF Networks
13.2 Decomposition Methods for the Single-Layer Restoration Problems
13.3 Design of Resilient Two-Layer PF Networks
13.4 Extensions
13.5 Summary and Further Reading
Exercises for Chapter 13

APPENDICES

Appendix A - Optimization Theory Refresher
A.1 Basic Notions
A.2 Karush-Kuhn-Tucker (KKT) Optimality Conditions
A.3 Interpretation of the Lagrange Multipliers in the KKT Conditions
A.4 Numerical Methods for Finding Minima of Differentiable Problems
A.5 Duality
A.6 Duality for Convex Programs
A.7 Duality for Convex Objective and Linear Constraints
A.8 Subgradient Maximization of the Dual Function
A.9 Subgradient Maximization of the Dual Function of Linear Programming Problems

Appendix B - Introduction to Complexity Theory and NP-Completeness
B.1 Introduction
B.2 Complexity of a Problem
B.3 Deterministic and Non-Deterministic Machines
B.4 The Classes of Problems Known as P and NP
B.5 Reducibility Relation between Problems
B.6 The Class of NP-Complete Problems
B.7 The Satisfiability Problem and Cook’s Theorem
B.8 Network Flow Problems
B.9 Final Remarks

Appendix C - Shortest-Path Algorithms
C.1 Introduction and Basic Notions
C.2 Basic Shortest-Path Problem
C.3 K-Shortest Paths and All Optimal Paths
C.4 Shortest Sets of Disjoint Paths

Appendix D - Using LP/MIP Packages
D.1 Solving Linear Programming Problems using Maple, Matlab, and CPLEX
D.2 Solving (Mixed) Integer Programming Problems Using CPLEX
D.3 Modeling Using AMPL
D.4 Final Remark

List of Acronyms
Solutions to Selected Exercises
Bibliography
Index