You are previewing Optimization of Computer Networks.
O'Reilly logo
Optimization of Computer Networks

Book Description

This book covers the design and optimization of computer networks applying a rigorous optimization methodology, applicable to any network technology.  It is organized into two parts. In Part 1 the reader will learn how to model network problems appearing in computer networks as optimization programs, and use optimization theory to give insights on them.  Four problem types are addressed systematically – traffic routing, capacity dimensioning, congestion control and topology design.

Part 2 targets the design of algorithms that solve network problems like the ones modeled in Part 1.  Two main approaches are addressed – gradient-like algorithms inspiring distributed network protocols that dynamically adapt to the network, or cross-layer schemes that coordinate the cooperation among protocols; and those focusing on the design of heuristic algorithms for long term static network design and planning problems.

Following a hands-on approach, the reader will have access to a large set of examples in real-life technologies like IP, wireless and optical networks.  Implementations of models and algorithms will be available in the open-source Net2Plan tool from which the user will be able to see how the lessons learned take real form in algorithms, and reuse or execute them to obtain numerical solutions. 

An accompanying link to the author’s own Net2plan software enables readers to produce numerical solutions to a multitude of real-life problems in computer networks (www.net2plan.com).  

Table of Contents

  1. Title Page
  2. Copyright
  3. Dedication
  4. About the Author
  5. Preface
    1. Reader Requisites and Intended Audience
  6. Acknowledgments
    1. Chapter 1: Introduction
      1. 1.1 What is a Communication Network?
      2. 1.2 Capturing the Random User Behavior
      3. 1.3 Queueing Theory and Optimization Theory
      4. 1.4 The Rationale and Organization of this Book
  7. Part One: Modeling
    1. Chapter 2: Definitions and Notation
      1. 2.1 Notation for Sets, Vectors and Matrices
      2. 2.2 Network Topology
      3. 2.3 Installed Capacities
      4. 2.4 Traffic Demands
      5. 2.5 Traffic Routing
      6. References
    2. Chapter 3: Performance Metrics in Networks
      1. 3.1 Introduction
      2. 3.2 Delay
      3. 3.3 Blocking Probability
      4. 3.4 Average Number of Hops
      5. 3.5 Network Congestion
      6. 3.6 Network Cost
      7. 3.7 Network Resilience Metrics
      8. 3.8 Network Utility and Fairness in Resource Allocation
      9. 3.9 Notes and Sources
      10. 3.10 Exercises
      11. References
    3. Chapter 4: Routing Problems
      1. 4.1 Introduction
      2. 4.2 Flow-Path Formulation
      3. 4.3 Flow-Link Formulation
      4. 4.4 Destination-Link Formulation
      5. 4.5 Convexity Properties of Performance Metrics
      6. 4.6 Problem Variants
      7. 4.7 Notes and Sources
      8. 4.8 Exercises
      9. References
    4. Chapter 5: Capacity Assignment Problems
      1. 5.1 Introduction
      2. 5.2 Long-Term Capacity Planning Problem Variants
      3. 5.3 Fast Capacity Allocation Problem Variants: Wireless Networks
      4. 5.4 MAC Design in Hard-Interference Scenarios
      5. 5.5 Transmission Power Optimization in Soft Interference Scenarios
      6. 5.6 Notes and Sources
      7. 5.7 Exercises
      8. References
    5. Chapter 6: Congestion Control Problems
      1. 6.1 Introduction
      2. 6.2 NUM Model
      3. 6.3 Case Study: TCP
      4. 6.4 Active Queue Management (AQM)
      5. 6.5 Notes and Sources
      6. 6.6 Exercises
      7. References
    6. Chapter 7: Topology Design Problems
      1. 7.1 Introduction
      2. 7.2 Node Location Problems
      3. 7.3 Full Topology Design Problems
      4. 7.4 Multilayer Network Design
      5. 7.5 Notes and Sources
      6. 7.6 Exercises
      7. References
  8. Part Two: Algorithms
    1. Chapter 8: Gradient Algorithms in Network Design
      1. 8.1 Introduction
      2. 8.2 Convergence Rates
      3. 8.3 Projected Gradient Methods
      4. 8.4 Asynchronous and Distributed Algorithm Implementations
      5. 8.5 Non-Smooth Functions
      6. 8.6 Stochastic Gradient Methods
      7. 8.7 Stopping Criteria
      8. 8.8 Algorithm Design Hints
      9. 8.9 Notes and Sources
      10. 8.10 Exercises
      11. References
    2. Chapter 9: Primal Gradient Algorithms
      1. 9.1 Introduction
      2. 9.2 Penalty Methods
      3. 9.3 Adaptive Bifurcated Routing
      4. 9.4 Congestion Control using Barrier Functions
      5. 9.5 Persistence Probability Adjustment in MAC Protocols
      6. 9.6 Transmission Power Assignment in Wireless Networks
      7. 9.7 Notes and Sources
      8. 9.8 Exercises
      9. References
    3. Chapter 10: Dual Gradient Algorithms
      1. 10.1 Introduction
      2. 10.2 Adaptive Routing in Data Networks
      3. 10.3 Backpressure (Center-Free) Routing
      4. 10.4 Congestion Control
      5. 10.5 Decentralized Optimization of CSMA Window Sizes
      6. 10.6 Notes and Sources
      7. 10.7 Exercises
      8. References
    4. Chapter 11: Decomposition Techniques
      1. 11.1 Introduction
      2. 11.2 Theoretical Fundamentals
      3. 11.3 Cross-Layer Congestion Control and QoS Capacity Allocation
      4. 11.4 Cross-Layer Congestion Control and Backpressure Routing
      5. 11.5 Cross-Layer Congestion Control and Power Allocation
      6. 11.6 Multidomain Routing
      7. 11.7 Dual Decomposition in Non-Convex Problems
      8. 11.8 Notes and Sources
      9. 11.9 Exercises
      10. References
    5. Chapter 12: Heuristic Algorithms
      1. 12.1 Introduction
      2. 12.2 Heuristic Design Keys
      3. 12.3 Local Search Algorithms
      4. 12.4 Simulated Annealing
      5. 12.5 Tabu Search
      6. 12.6 Greedy Algorithms
      7. 12.7 GRASP
      8. 12.8 Ant Colony Optimization
      9. 12.9 Evolutionary Algorithms
      10. 12.10 Case Study: Greenfield Plan with Recovery Schemes Comparison
      11. 12.11 Notes and Sources
      12. 12.12 Exercises
      13. References
  9. Appendix A: Convex Sets. Convex Functions
    1. A.1 Convex Sets
    2. A.2 Convex and Concave Functions
    3. A.3 Notes and Sources
    4. Reference
  10. Appendix B: Mathematical Optimization Basics
    1. B.1 Optimization Problems
    2. B.2 A Classification of Optimization Problems
    3. B.3 Duality
    4. B.4 Optimality Conditions
    5. B.5 Sensitivity Analysis
    6. B.6 Notes and Sources
    7. References
  11. Appendix C: Complexity Theory
    1. C.1 Introduction
    2. C.2 Deterministic Machines and Deterministic Algorithms
    3. C.3 Non-Deterministic Machines and Non-Deterministic Algorithms
    4. C.4 <img xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0" src="images/b03-math-0150.png" alt="b3-math-0150" style="vertical-align:middle;"></img> and and <img xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0" src="images/b03-math-0151.png" alt="b3-math-0151" style="vertical-align:middle;"></img> Complexity Classes Complexity Classes
    5. C.5 Polynomial Reductions
    6. C.6 <img xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ibooks="http://vocabulary.itunes.apple.com/rdf/ibooks/vocabulary-extensions-1.0" src="images/b03-math-0264.png" alt="b3-math-0264" style="vertical-align:middle;"></img>-Completeness-Completeness
    7. C.7 Optimization Problems and Approximation Schemes
    8. C.8 Complexity of Network Design Problems
    9. C.9 Notes and Sources
    10. References
  12. Appendix D: Net2Plan
    1. D.1 Net2Plan
    2. D.2 On the Role of Net2Plan in this Book
      1. Index
  13. End User License Agreement