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

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

by Michal Pioro, Deep Medhi
Released July 2004
Publisher(s): Morgan Kaufmann
ISBN: 9780080516431

Explore a preview version of Routing, Flow, and Capacity Design in Communication and Computer Networks right now.

O’Reilly members get unlimited access to live online training experiences, plus books, videos, and digital content from 200+ publishers.

Start your free trial

Book 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.
  • 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.

Table of contents

  1. Cover image
  2. Title page
  3. Table of Contents
  4. The Morgan Kaufmann Series in Networking
  5. Copyright
  6. Dedication
  7. FOREWORD
  8. PREFACE
  9. PART I: INTRODUCTORY NETWORK DESIGN
    1. INTRODUCTION TO INTRODUCTORY NETWORK DESIGN
    2. CHAPTER 1: Overview
      1. 1.1 A NETWORK ANALOGY
      2. 1.2 COMMUNICATION AND COMPUTER NETWORKS, AND NETWORK PROVIDERS
      3. 1.3 NOTION OF TRAFFIC AND TRAFFIC DEMAND
      4. 1.4 A SIMPLE DESIGN EXAMPLE
      5. 1.5 NOTION OF ROUTING AND FLOWS
      6. 1.6 ARCHITECTURE OF NETWORKS: MULTI-LAYER NETWORKS
      7. 1.7 NETWORK MANAGEMENT CYCLE
      8. 1.8 SCOPE OF THE BOOK
      9. 1.9 NAMING AND NUMBERING CONVENTION
      10. 1.10 SUMMARY
    3. CHAPTER 2: Network Design Problems—Notation and Illustrations
      1. 2.1 A NETWORK FLOW EXAMPLE IN LINK-PATH FORMULATION
      2. 2.2 NODE-LINK FORMULATION
      3. 2.3 NOTIONS AND NOTATIONS
      4. 2.4 DIMENSIONING PROBLEMS
      5. 2.5 SHORTEST-PATH ROUTING
      6. 2.6 FAIR NETWORKS
      7. 2.7 TOPOLOGICAL DESIGN
      8. 2.8 RESTORATION DESIGN
      9. 2.9 *MULTI-LAYER NETWORKS MODELING
      10. 2.10 SUMMARY
      11. EXERCISES FOR Chapter 2
    4. CHAPTER 3: Technology-Related Modeling Examples
      1. 3.1 IP NETWORKS: INTRA-DOMAIN TRAFFIC ENGINEERING
      2. 3.2 MPLS NETWORKS: TUNNELING OPTIMIZATION
      3. 3.3 ATM NETWORKS: VIRTUAL PATH DESIGN
      4. 3.4 DIGITAL CIRCUIT-SWITCHED TELEPHONE NETWORKS: SINGLE–BUSY HOUR AND MULTI–BUSY HOUR NETWORK DIMENSIONING
      5. 3.5 SONET/SDH TRANSPORT NETWORKS: CAPACITY AND PROTECTION DESIGN
      6. 3.6 SONET/SDH RINGS: RING BANDWIDTH DESIGN
      7. 3.7 WDM NETWORKS: RESTORATION DESIGN WITH OPTICAL CROSS-CONNECTS
      8. 3.8 IP OVER SONET: COMBINED TWO-LAYER DESIGN
      9. 3.9 SUMMARY AND FURTHER READING
      10. EXERCISES FOR Chapter 3
  10. PART II: DESIGN MODELING AND METHODS
    1. INTRODUCTION TO DESIGN MODELING AND METHODS
    2. CHAPTER 4: Network Design Problem Modeling
      1. 4.1 BASIC UNCAPACITATED AND CAPACITATED DESIGN PROBLEMS
      2. 4.2 ROUTING RESTRICTIONS
      3. 4.3 NON-LINEAR LINK DIMENSIONING, COST, AND DELAY FUNCTIONS
      4. 4.4 BUDGET CONSTRAINT
      5. 4.5 INCREMENTAL NDPs
      6. 4.6 EXTENSIONS OF PROBLEM MODELING
      7. 4.7 SUMMARY AND FURTHER READING
      8. EXERCISES FOR Chapter 4
    3. CHAPTER 5: General Optimization Methods for Network Design
      1. 5.1 LINEAR PROGRAMMING
      2. 5.2 MIXED-INTEGER PROGRAMMING
      3. 5.3 STOCHASTIC HEURISTIC METHODS
      4. 5.4 LP DECOMPOSITION METHODS
      5. 5.5 GRADIENT MINIMIZATION AND OTHER APPROACHES FOR CONVEX PROGRAMMING PROBLEMS
      6. 5.6 SPECIAL HEURISTICS FOR CONCAVE PROGRAMMING PROBLEMS
      7. 5.7 SOLVING MULTI-COMMODITY FLOW PROBLEMS
      8. 5.8 SUMMARY AND FURTHER READING
      9. EXERCISES FOR Chapter 5
    4. CHAPTER 6: Location and Topological Design
    5. CHAPTER 7: Networks With Shortest-Path Routing
      1. 7.1 SHORTEST-PATH ROUTING ALLOCATION PROBLEM
      2. 7.2 MIP FORMULATION OF THE SHORTEST-PATH ROUTING ALLOCATION PROBLEM AND DUAL PROBLEMS
      3. 7.3 HEURISTIC DIRECT METHODS FOR DETERMINING THE LINK METRIC SYSTEM
      4. 7.4 TWO-PHASE SOLUTION APPROACH
      5. 7.5 IMPACT DUE TO STOCHASTIC APPROACHES
      6. 7.6 IMPACT OF DIFFERENT LINK WEIGHT SYSTEM
      7. 7.7 IMPACT ON DIFFERENT PERFORMANCE MEASURES
      8. 7.8 UNCAPACITATED SHORTEST-PATH ROUTING PROBLEM
      9. 7.9 OPTIMIZATION OF THE LINK METRIC SYSTEM UNDER TRANSIENT FAILURES
      10. 7.10 *NP-COMPLETENESS OF THE SHORTEST-PATH ROUTING ALLOCATION PROBLEM
      11. 7.11 SELFISH ROUTING AND ITS RELATION TO OPTIMAL ROUTING
      12. 7.12 SUMMARY AND FURTHER READING
      13. EXERCISES FOR Chapter 7
    6. CHAPTER 8: Fair Networks
      1. 8.1 NOTIONS OF FAIRNESS
      2. 8.2 DESIGN PROBLEMS FOR MAX-MIN FAIRNESS (MMF)
      3. 8.4 SUMMARY AND FURTHER READING
      4. EXERCISES FOR Chapter 8
  11. PART III: ADVANCED MODELS
    1. INTRODUCTION TO ADVANCED MODELS
    2. CHAPTER 9: Restoration and Protection Design of Resilient Networks
      1. 9.1 FAILURE STATES, PROTECTION/RESTORATION MECHANISMS, AND DIVERSITY
      2. 9.2 LINK CAPACITY PROTECTION/RESTORATION
      3. 9.3 DEMAND FLOW RE-ESTABLISHMENT
      4. 9.4 EXTENSIONS
      5. 9.5 PROTECTION PROBLEMS
      6. 9.6 APPLICABILITY OF THE PROTECTION/RESTORATION DESIGN MODELS
      7. 9.7 SUMMARY AND FURTHER READING
      8. EXERCISES FOR Chapter 9
    3. CHAPTER 10: Application of Optimization Techniques for Protection and Restoration Design
      1. 10.1 PATH GENERATION
      2. 10.2 LAGRANGIAN RELAXATION (LR) WITH SUBGRADIENT MAXIMIZATION
      3. 10.3 BENDERS’ DECOMPOSITION
      4. 10.4 MODULAR LINKS
      5. 10.5 STOCHASTIC HEURISTIC METHODS
      6. 10.6 SELECTED APPLICATION: WAVELENGTH ASSIGNMENT PROBLEM IN WDM NETWORKS
      7. 10.7 SUMMARY AND FURTHER READING
      8. EXERCISES FOR Chapter 10
    4. CHAPTER 11: Multi-Hour and Multi–Time-Period Network Modeling and Design
      1. 11.1 MULTI-HOUR DESIGN
      2. 11.2 MULTI-PERIOD DESIGN
      3. 11.3 SUMMARY AND FURTHER READING
      4. EXERCISES FOR Chapter 11
    5. CHAPTER 12: Multi-Layer Networks: Modeling and Design
      1. 12.1 DESIGN OF MULTI-LAYER NETWORKS
      2. 12.2 MODELING OF MULTI-LAYER NETWORKS FOR RESTORATION DESIGN
      3. 12.3 MULTI-LAYER DESIGN WITH MULTI-HOUR TRAFFIC
      4. 12.4 APPLICATION OF DECOMPOSITION METHODS FOR TWO-LAYER DESIGN
      5. 12.5 NUMERICAL RESULTS
      6. 12.6 COST COMPARISON
      7. 12.7 GROOMING/MULTIPLEX BUNDLING
      8. 12.8 SUMMARY AND FURTHER READING
      9. EXERCISES FOR Chapter 12
    6. CHAPTER 13: Restoration Design of Single- and Multi-Layer Fair Networks
      1. 13.1 RESTORATION DESIGN OF SINGLE-LAYER PF NETWORKS
      2. 13.2 DECOMPOSITION METHODS FOR THE SINGLE-LAYER RESTORATION PROBLEMS
      3. 13.3 DESIGN OF RESILIENT TWO-LAYER PF NETWORKS
      4. 13.4 EXTENSIONS
      5. 13.5 SUMMARY AND FURTHER READING
      6. EXERCISES FOR Chapter 13
  12. APPENDICES
    1. APPENDIX A: Optimization Theory Refresher
    2. APPENDIX B: Introduction to Complexity Theory and NP-Completeness
    3. APPENDIX C: Shortest-Path Algorithms
    4. APPENDIX D: Using LP/MIP Packages
  13. LIST OF ACRONYMS
  14. SOLUTIONS TO SELECTED EXERCISES
  15. BIBLIOGRAPHY
  16. INDEX

Product information

  • Title: Routing, Flow, and Capacity Design in Communication and Computer Networks
  • Author(s): Michal Pioro, Deep Medhi
  • Release date: July 2004
  • Publisher(s): Morgan Kaufmann
  • ISBN: 9780080516431