Purchase textbook

Routing, Flow, and Capacity Design in Communication and Computer Networks,

Edition 1

Editors: By Michal Pioro and Deep Medhi

Publication Date: 01 Jul 2004

Educator resources

0 Reviews

Inaccessible, or known limited accessibility

Ways Of Reading

This e-publication is accessible to the full extent that the file format and types of content allow, on a specific reading device, by default, without necessarily including any additions such as textual descriptions of images or enhanced navigation.

Navigation

The contents of the PDF have been tagged to permit access by assistive technologies as per PDF-UA-1 standard.
Page breaks included from the original print source

Additional Accessibility Information

All (or substantially all) textual matter is arranged in a single logical reading order (including text that is visually presented as separate from the main text flow, e.g., in boxouts, captions, tables, footnotes, endnotes, citations, etc.). Non-textual content is also linked from within this logical reading order. (Purely decorative non-text content can be ignored).
The language of the text has been specified (e.g., via the HTML or XML lang attribute) to optimise text-to-speech (and other alternative renderings), both at the whole document level and, where appropriate, for individual words, phrases or passages in a different language.

Conformance

The publication was certified on 20250710
Accessibility addendum
For detailed accessibility information, see Elsevier’s website at https://www.elsevier.com/about/accessibility
For queries regarding accessibility information, contact [email protected]

Note

This product relies on 3rd party tooling which may impact the accessibility features visible in inspection copies. All accessibility features mentioned would be present in the purchased version of the title.

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.

Key Features

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.

About the author

By Michal Pioro, Warsaw University of Technology (Poland) and Lund University (Sweden) and Deep Medhi, University of Missouri, Kansas City, Missouri, USA

ForewordPrefacePART I - INTRODUCTORY NETWORK DESIGNChapter 1 - Overview1.1 A Network Analogy1.2 Communication and Computer Networks, and Network Providers1.3 Notion of Traffic and Traffic Demand1.4 A Simple Design Example1.5 Notion of Routing and Flows1.6 Architecture of Networks: Multi-Layer Networks1.7 Network Management Cycle1.8 Scope of the Book1.9 Naming and Numbering Convention1.10 SummaryChapter 2 - Network Design Problems—Notation and Illustrations2.1 A Network Flow Example in Link-Path Formulation 2.2 Node-Link Formulation 2.3 Notions and Notations2.4 Dimensioning Problems2.5 Shortest-Path Routing2.6 Fair Networks2.7 Topological Design2.8 Restoration Design2.9 *Multi-Layer Networks Modeling2.10 SummaryExercises for Chapter 2Chapter 3 - Technology-Related Modeling Examples3.1 IP Networks: Intra-Domain Traffic Engineering3.2 MPLS Networks: Tunneling Optimization3.3 ATM Networks: Virtual Path Design3.4 Digital Circuit-Switched Telephone Networks: Single–Busy Hour and Multi–Busy Hour Network Dimensioning3.5 SONET/SDH Transport Networks: Capacity and Protection Design3.6 SONET/SDH Rings: Ring Bandwidth Design3.7 WDM Networks: Restoration Design with Optical Cross-Connects3.8 IP Over SONET: Combined Two-Layer Design3.9 Summary and Further ReadingExercises for Chapter 3 PART II - DESIGN MODELING AND METHODS Chapter 4 - Network Design Problem Modeling4.1 Basic Uncapacitated and Capacitated Design Problems4.2 Routing Restrictions4.3 Non-Linear Link Dimensioning, Cost, and Delay Functions4.4 Budget Constraint4.5 Incremental NDPs4.6 Extensions of Problem Modeling4.7 Summary and Further ReadingExercises for Chapter 4Chapter 5 - General Optimization Methods for Network Design5.1 Linear Programming5.2 Mixed-Integer Programming5.3 Stochastic Heuristic Methods5.4 LP Decomposition Methods5.5 Gradient Minimization and Other Approaches for Convex Programming Problems5.6 Special Heuristics for Concave Programming Problems5.7 Solving Multi-Commodity Flow Problems5.8 Summary and Further ReadingExercises for Chapter 5Chapter 6 - Location and Topological Design6.1 Node Location Problem6.2 Joint Node Location and Link Connectivity Problem6.3 Topological Design6.4 Lower Bounds for Branch-and-Bound6.5 Summary and Further ReadingExercises for Chapter 6Chapter 7 - Networks With Shortest-Path Routing7.1 Shortest-Path Routing Allocation Problem7.2 MIP Formulation of the Shortest-Path Routing Allocation Problem and Dual Problems7.3 Heuristic Direct Methods for Determining the Link Metric System7.4 Two-Phase Solution Approach7.5 Impact Due to Stochastic Approaches7.6 Impact of Different Link Weight System7.7 Impact on Different Performance Measures7.8 Uncapacitated Shortest-Path Routing Problem 7.9 Optimization of the Link Metric System under Transient Failures7.10 *NP-Completeness of the Shortest-Path Routing Allocation Problem7.11 *Selfish Routing and its Relation to Optimal Routing7.12 Summary and Further ReadingExercises for Chapter 7Chapter 8 - Fair Networks8.1 Notions of Fairness8.2 Design Problems for Max-Min Fairness (MMF)8.3 Design Problems for Proportional Fairness (PF)8.4 Summary and Further ReadingExercises for Chapter 8PART III - ADVANCED MODELSChapter 9 - Restoration and Protection Design of Resilient Networks9.1 Failure States, Protection/Restoration Mechanisms, and Diversity9.2 Link Capacity Protection/Restoration9.3 Demand Flow Re-Establishment9.4 Extensions9.5 Protection Problems9.6 Applicability of the Protection/Restoration Design Models9.7 Summary and Further ReadingExercises for Chapter 9Chapter 10 - Application of Optimization Techniques for Protection and Restoration Design10.1 Path Generation10.2 Lagrangian Relaxation (LR) With Subgradient Maximization10.3 Benders’ Decomposition10.4 Modular Links10.5 Stochastic Heuristic Methods10.6 *Selected Application: Wavelength Assignment Problem in WDM Networks10.7 Summary and Further ReadingExercises for Chapter 10Chapter 11 - Multi-Hour and Multi–Time-Period Network Modeling and Design11.1 Multi-Hour Design11.2 Multi-Period Design11.3 Summary and Further ReadingExercises for Chapter 11Chapter 12 - Multi-Layer Networks: Modeling and Design12.1 Design of Multi-Layer Networks12.2 Modeling of Multi-Layer Networks for Restoration Design12.3 Multi-Layer Design With Multi-Hour Traffic12.4 Application of Decomposition Methods for Two-Layer Design12.5 Numerical Results12.6 Cost Comparison12.7 Grooming/Multiplex Bundling12.8 Summary and Further ReadingExercises for Chapter 12Chapter 13 - Restoration Design of Single- and Multi-Layer Fair Networks13.1 Restoration Design of Single-Layer PF Networks13.2 Decomposition Methods for the Single-Layer Restoration Problems13.3 Design of Resilient Two-Layer PF Networks13.4 Extensions13.5 Summary and Further ReadingExercises for Chapter 13APPENDICESAppendix A - Optimization Theory RefresherA.1 Basic NotionsA.2 Karush-Kuhn-Tucker (KKT) Optimality ConditionsA.3 Interpretation of the Lagrange Multipliers in the KKT ConditionsA.4 Numerical Methods for Finding Minima of Differentiable ProblemsA.5 DualityA.6 Duality for Convex ProgramsA.7 Duality for Convex Objective and Linear ConstraintsA.8 Subgradient Maximization of the Dual FunctionA.9 Subgradient Maximization of the Dual Function of Linear Programming ProblemsAppendix B - Introduction to Complexity Theory and NP-CompletenessB.1 IntroductionB.2 Complexity of a ProblemB.3 Deterministic and Non-Deterministic MachinesB.4 The Classes of Problems Known as P and NPB.5 Reducibility Relation between ProblemsB.6 The Class of NP-Complete ProblemsB.7 The Satisfiability Problem and Cook’s TheoremB.8 Network Flow ProblemsB.9 Final RemarksAppendix C - Shortest-Path AlgorithmsC.1 Introduction and Basic NotionsC.2 Basic Shortest-Path ProblemC.3 K-Shortest Paths and All Optimal PathsC.4 Shortest Sets of Disjoint PathsAppendix D - Using LP/MIP PackagesD.1 Solving Linear Programming Problems using Maple, Matlab, and CPLEXD.2 Solving (Mixed) Integer Programming Problems Using CPLEXD.3 Modeling Using AMPLD.4 Final RemarkList of AcronymsSolutions to Selected ExercisesBibliographyIndex

Book Reviews

"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

ISBN: 9780125571890

Page Count: 800

Retail Price :

Network Analysis, Architecture, and Design 2e by James McCabe (MK, 2003). Hardcover, 532 pp, $64.95/£42.99. 155860887. (Both editions have sold 11,000 copies to date.)Top-Down Network Design by P. Oppenheimer (Cisco Press, 1999). Hardcover, 592 pp, $55.00/£42.99 (1578700698).

Access to teacher/student resources is available to registered users with approved inspection copies or confirmed adoptions. To review this material, please request an inspection copy.

slides
- 04~Chapter_4.ppt
- 05~Chapter_5.ppt
solutions
- Solutions_to_Exercises.pdf

Practitioners working in network architecture and design, engineering and operations at service providers, router companies, fiber companies, and telecom transmission equipment vendors.