Foreword PrefacePART 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 3PART 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 8PART 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 13APPENDICES
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
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.
- Written by leading researchers with a combined 40 years of industrial and academic network design experience.
- Considers the development of design models for different technologies, including TCP/IP, IDN, MPLS, ATM, SONET/SDH, and WDM.
- Discusses recent topics such as shortest path routing and fair bandwidth assignment in IP/MPLS networks.
- Addresses proper multi-layer modeling across network layers using different technologies—for example, IP over ATM over SONET, IP over WDM, and IDN over SONET.
- Covers restoration-oriented design methods that allow recovery from failures of large-capacity transport links and transit nodes.
- Presents, at the end of each chapter, exercises useful to both students and practitioners.
Practitioners working in network architecture and design, engineering and operations at service providers, router companies, fiber companies, and telecom transmission equipment vendors.
- No. of pages:
- © Morgan Kaufmann 2004
- 1st July 2004
- Morgan Kaufmann
- eBook ISBN:
- Hardcover ISBN:
Pioro and Medhi’s book is very refreshing and gives a comprehensive view of network design. It unifies many important topics on network design that are not found in one place; for example, this book provides the first thorough treatment of multi-layer design. Practitioners will find the book useful due to its development of both models and algorithms that are more applicable to real-world problems. --Dr. Robert D. Doverspike: Bell Labs, Bellcore (now Telcordia), and AT&T Labs – Research, USA The authors successfully bridge the gap between networking technology and system modeling and optimization, providing a comprehensive and authoritative reference on communication and computer network design through mathematical optimization-oriented modeling. It is an essential book for graduate students and academia and industry researchers. --Professor Luigi Fratta, Politecnico di Milano, Italy This book provides an in-depth view of network design problems both from a theoretical and a practical perspective. It will become the reference work in the area of telecommunication network design for the years to come. --Professor André Girard, INRS-EMT, Canada "I heartily recommend this impressive work to all students interested in a career in networking as well as to many experienced planners faced with the current problems of network design and evolution, where they continually seek network design solutions, that optimize cost/benefits. Outside of the telecommunications sector per se the book should also be of great interest to members of the operations research community as it provides them with a current window on the technologies and problems arising in telecommunication and computer network design. This should provide fertile ground for applications of new theoretical developments and guide their research toward practical ends. To sum up, Pioro's and Medhi's book is a must read for a broad audience with basic mathematical skills who are interested in network design, a topic that continues to be of immense and growing importance in our everyday business activities and lives." - IEEE Communications Magazine "This book presents the basic principles and methods for developing optimization models for contemporary communication and computer network design. The book focuses on optimization problems and methods for traffic routing, flow, and resource capacity optimization...practioners, graduate students, and researchers will find the book useful for academic and industrial purposes." -Demetre Voukalis, in ZENTRALBLATT MATH
Michal Pióro heads the Department of Computer Networks and Switching at the Institute of Telecommunications at Warsaw University of Technology. He serves as professor there and also at the Department of Communication Systems at Lund University in Sweden.
Warsaw University of Technology (Poland) and Lund University (Sweden)
Deep Medhi is Curators' Distinguished Professor in the Computer Science Electrical Engineering Department at the University of Missouri--Kansas City (UMKC), USA. Prior to joining UMKC in 1989, he was a member of the technical staff in the traffic network routing and design department at the AT&T Bell Laboratories. He was an invited visiting professor at the Technical University of Denmark, a visiting research fellow at the Lund University, Sweden, a research visitor at Université Pierre et Marie Curie (UPMC), Paris, France, and a short-term visitor at Princeton University, Massachusetts Institute of Technology, and KTH Royal Institute of Technology, Sweden. He was also a Fulbright Senior Specialist. He was on the Brazilian Science Mobility Program with the University of Campinas, Brazil as his host institution. He serves as the editor-in-chief of Springer's Journal of Network & Systems Management, and is serving (or served) on the editorial board of IEEE Communications Surveys \& Tutorials, IEEE Transactions on Network and Service Management, IEEE/ACM Transactions on Networking, Computer Networks, Telecommunication Systems, and IEEE Communications Magazine. He has served on the technical program committees of numerous conferences including IEEE INFOCOM, IEEE ICNP, IEEE NOMS, IEEE IM, IEEE CloudNet, ITC, and DRCN, while serving as the Technical Program Co-Chair of DRCN 2009, IEEE NOMS 2010, IFIP Networking 2014, IEEE CloudNet 2016. He received his B.Sc.(Hons.) in Mathematics from Cotton College, Gauhati University, India, his M.Sc. in Mathematics from St.~Stephens College, University of Delhi, India, and both his M.S. and Ph.D. in Computer Sciences from the University of Wisconsin--Madison, USA. He % has published over one hundred and fifty peer-reviewed papers, and is co-author of Routing, Flow, and Capacity Design in Communication and Computer Networks, also published by Elsevier (2004).
University of Missouri, Kansas City, Missouri, USA