ROUTING, FLOW, AND CAPACITY DESIGN IN COMMUNICATION AND COMPUTER NETWORKS
To order this title, and for more information, click here
By Michal Pioro, Warsaw University of Technology (Poland) and Lund University (Sweden) Deepankar Medhi, University of Missouri, Kansas City, Missouri, USA
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.
Audience
Practitioners working in network architecture and design, engineering and operations at service providers, router companies, fiber companies, and telecom transmission equipment vendors.
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
Bibliographic & ordering Information Hardbound, 800 pages, publication date: JUL-2004
ISBN-13: 978-0-12-557189-0
ISBN-10: 0-12-557189-5
Imprint: MORGAN KAUFFMAN Price:Order form EUR 56.95 USD 63.95 GBP 37.99
Books and book related electronic products are priced in US dollars (USD), euro (EUR), and Great Britain Pounds (GBP). USD prices apply to the Americas and Asia Pacific. EUR prices apply in Europe and the Middle East. GBP prices apply to the UK and all other countries.
To order this title, and for more information, click 
