Routing, Flow, and Capacity Design in Communication and Computer Networks
Regular price
12.250 KD
inc. VAT
Couldn't load pickup availability
Table of contents
- Cover
- Copyright Pageiv
- Contentsvii
- Forewordxix
- Prefacexxi
- PART I: INTRODUCTORY NETWORK DESIGN1
- Chapter 1. Overview3
- 1.1 A Network Analogy4
- 1.2 Communication and Computer Networks, and Network Providers9
- 1.3 Notion of Traffic and Traffic Demand11
- 1.4 A Simple Design Example22
- 1.5 Notion of Routing and Flows23
- 1.6 Architecture of Networks: Multi-Layer Networks25
- 1.7 Network Management Cycle27
- 1.8 Scope of The Book31
- 1.9 Naming and Numbering Convention35
- 1.10 Summary36
- Chapter 2. Network Design Problems„Notation and Illustrations37
- 2.1 A Network Flow Example in Link-Path Formulation38
- 2.2 Node-Link Formulation43
- 2.3 Notions and Notations45
- 2.4 Dimensioning Problems50
- 2.5 Shortest-Path Routing60
- 2.6 Fair Networks62
- 2.7 Topological Design65
- 2.8 Restoration Design66
- 2.9 Multi-Layer Networks Modeling68
- 2.10 Summary74
- Exercises For Chapter 276
- Chapter 3. Technology-Related Modeling Examples77
- 3.1 IP Networks: Intra-Domain Traffic Engineering78
- 3.2 MPLS Networks: Tunneling Optimization82
- 3.3 ATM Networks: Virtual Path Design84
- 3.4 Digital Circuit-Switched Telephone Networks: Single-Busy Hour and Multi-Busy Hour Network Dimens86
- 3.5 SONET/SDH Transport Networks: Capacity and Protection Design90
- 3.6 SONET/SDH Rings: Ring Bandwidth Design94
- 3.7 WDM Networks: Restoration Design with Optical Cross-Connects96
- 3.8 IP Over Sonet: Combined Two-Layer Design98
- 3.9 Summary and Further Reading101
- Exercises for Chapter 3102
- PART II: DESIGN MODELING AND METHODS103
- Chapter 4. Network Design Problem Modeling105
- 4.1 Basic Uncapacitated and Capacitated Design Problems106
- 4.2 Routing Restrictions115
- 4.3 Non-Linear Link Dimensioning, Cost, and Delay Functions124
- 4.4 Budget Constraint140
- 4.5 Incremental NDPS141
- 4.6 Extensions of Problem Modeling142
- 4.7 Summary and Further Reading145
- Exercises for Chapter 4148
- Chapter 5. General Optimization Methods for Network Design151
- 5.1 Linear Programming152
- 5.2 Mixed-Integer Programming162
- 5.3 Stochastic Heuristic Methods169
- 5.4 LP Decomposition Methods178
- 5.5 Gradient Minimization and Other Approaches for Convex Programming Problems194
- 5.6 Special Heuristics for Concave Programming Problems199
- 5.7 Solving Multi-Commodity Flow Problems203
- 5.8 Summary and Further Reading206
- Exercises for Chapter 5208
- Chapter 6. Location and Topological Design211
- 6.1 Node Location Problem212
- 6.2 Joint Node Location and Link Connectivity Problem217
- 6.3 Topological Design230
- 6.4 Lower Bounds for Branch-and-Bound243
- 6.5 Summary and Further Reading249
- Exercises for Chapter 6251
- Chapter 7. Networks With Shortest-Path Routing253
- 7.1 Shortest-Path Routing Allocation Problem256
- 7.2 MIP Formulation of the Shortest-Path Routing Allocation Problem and Dual Problems266
- 7.3 Heuristic Direct Methods for Determining the Link Metric System271
- 7.4 Two-Phase Solution Approach276
- 7.5 Impact Due to Stochastic Approaches283
- 7.6 Impact of Different Link Weight System285
- 7.7 Impact on Different Performance Measures289
- 7.8 Uncapacitated Shortest-Path Routing Problem291
- 7.9 Optimization of the Link Metric System Under Transient Failures292
- 7.10 NP-Completeness of the Shortest-Path Routing Allocation Problem295
- 7.11 Selfish Routing and its Relation to Optimal Routing298
- 7.12 Summary and Further Reading303
- Exercises for Chapter 7305
- Chapter 8. Fair Networks307
- 8.1 Notions of Fairness308
- 8.2 Design Problems for Max-Min Fairness (MMF)316
- 8.3 Design Problems for Proportional Fairness (PF)331
- 8.4 Summary and Further Reading346
- Exercises for Chapter 8348
- PART III: ADVANCED MODELS351
- Chapter 9. Restoration and Protection Design of Resilient Networks353
- 9.1 Failure States, Protection/Restoration Mechanisms, and Diversity354
- 9.2 Link Capacity Protection/Restoration361
- 9.3 Demand Flow Re-Establishment365
- 9.4 Extensions377
- 9.5 Protection Problems386
- 9.6 Applicability of the Protection/Restoration Design Models392
- 9.7 Summary and Further Reading398
- Exercises for Chapter 9400
- Chapter 10. Application of Optimization Techniques for Protection and Restoration Design403
- 10.1 Path Generation404
- 10.2 Lagrangian Relaxation (LR) with Subgradient Maximization415
- 10.3 Benders' Decomposition423
- 10.4 Modular Links435
- 10.5 Stochastic Heuristic Methods438
- 10.6 Selected Application: Wavelength Assignment Problem in WDM Networks446
- 10.7 Summary and Further Reading453
- Exercises for Chapter 10453
- Chapter 11. Multi-Hour and Multi–Time-Period Network Modeling and Design455
- 11.1 Multi-Hour Design456
- 11.2 Multi-Period Design474
- 11.3 Summary and Further Reading491
- Exercises for Chapter 11493
- Chapter 12. Multi-Layer Networks: Modeling and Design495
- 12.1 Design of Multi-Layer Networks497
- 12.2 Modeling of Multi-Layer Networks for Restoration Design515
- 12.3 Multi-Layer Design With Multi-Hour Traffic525
- 12.4 Application of Decomposition Methods for Two-Layer Design535
- 12.5 Numerical Results553
- 12.6 Cost Comparison559
- 12.7 Grooming/Multiplex Bundling565
- 12.8 Summary and Further Reading574
- Exercises for Chapter 12577
- Chapter 13. Restoration Design of Single- and Multi-Layer Fair Networks581
- 13.1 Restoration Design of Single-Layer PF Networks582
- 13.2 Decomposition Methods for the Single-Layer Restoration Problems597
- 13.3 Design of Resilient Two-Layer PF Networks600
- 13.4 Extensions609
- 13.5 Summary and Further Reading610
- Exercises for Chapter 13611
- Appendix A. Optimization Theory Refresher613
- A.1 Basic Notions613
- A.2 Karush-Kuhn-Tucker (KKT) Optimality Conditions614
- A.3 Interpretation of the Lagrange Multipliers in the KKT Conditions616
- A.4 Numerical Methods for Finding Minima of Differentiable Problems616
- A.5 Duality617
- A.6 Duality for Convex Programs618
- A.7 Duality for Convex Objective and Linear Constraints619
- A.8 Subgradient Maximization of the Dual Function620
- A.9 Subgradient Maximization of the Dual Function of Linear Programming Problems622
- Appendix B. Introduction to Complexity Theory and NP–Completeness625
- B.1 Introduction625
- B.2 Complexity of a Problem626
- B.3 Deterministic and Non-Deterministic Machines627
- B.4 The Classes of Problems Known as P and NP629
- B.5 Reducibility Relation between Problems630
- B.6 The Class of NP–Complete Problems631
- B.7 The Satisfiability Problem and Cook's Theorem631
- B.8 Network Flow Problems632
- B.9 Final Remarks637
- Appendix C. Shortest-Path Algorithms639
- C.1 Introduction and Basic Notions639
- C.2 Basic Shortest-Path Problem640
- C.3 K–shortest Paths and All Optimal Paths646
- C.4 Shortest Sets of Disjoint Paths648
- Appendix D. Using LP/MIP Packages653
- D.1 Solving Linear Programming Problems Using Maple, Matlab, and CPLEX653
- D.2 Solving (Mixed) Integer Programming Problems Using CPLEX656
- D.3 Modeling Using AMPL658
- D.4 Final Remark660
- List of Acronyms661
- Solutions to Selected Exercises663
- Bibliography679
- Index713
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.
Features
· 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.
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.
Features
· 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.