Wiley.com
Print this page Share

Optimization of Computer Networks: Modeling and Algorithms: A Hands-On Approach

ISBN: 978-1-119-01335-8
420 pages
May 2016
Optimization of Computer Networks: Modeling and Algorithms: A Hands-On Approach (1119013356) cover image

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).  

See More

Table of Contents

About the Author xv

Preface xvii

Acknowledgments xxi

1 Introduction 1

1.1 What is a Communication Network? 1

1.2 Capturing the Random User Behavior 4

1.3 Queueing Theory and Optimization Theory 5

1.4 The Rationale and Organization of this Book 6

1.4.1 Part I: Modeling 6

1.4.2 Part II: Algorithms 7

1.4.3 Basic Optimization Requisites: Appendices I, II, and III 10

1.4.4 Net2Plan Tool: Appendix IV 11

Part I MODELING

2 Definitions and Notation 15

2.1 Notation for Sets, Vectors and Matrices 15

2.1.1 Norm Basics 15

2.1.2 Set Basics 16

2.2 Network Topology 17

2.3 Installed Capacities 19

2.4 Traffic Demands 19

2.4.1 Unicast, Anycast, and Multicast Demands 20

2.4.2 Elastic versus Inelastic Demands 21

2.5 Traffic Routing 21

References 22

3 Performance Metrics in Networks 23

3.1 Introduction 23

3.2 Delay 23

3.2.1 Link Delay 23

3.2.2 End-to-End Delay 27

3.2.3 Average Network Delay 27

3.2.4 Convexity Properties 27

3.3 Blocking Probability 28

3.3.1 Link Blocking Probability 28

3.3.2 Demand and Network Blocking Probability 30

3.3.3 Other Blocking Estimations 31

3.3.4 Convexity Properties 34

3.4 Average Number of Hops 34

3.5 Network Congestion 36

3.6 Network Cost 36

3.7 Network Resilience Metrics 37

3.7.1 Shared Risk Groups 40

3.7.2 Simplified Availability Calculations 41

3.7.3 General Model 41

3.8 Network Utility and Fairness in Resource Allocation 44

3.8.1 Fairness in Resource Allocation 44

3.8.2 Fairness and Utility Functions 45

3.8.3 Convexity Properties 47

3.9 Notes and Sources 47

3.10 Exercises 49

References 51

4 Routing Problems 53

4.1 Introduction 53

4.2 Flow-Path Formulation 54

4.2.1 Optimality Analysis 55

4.2.2 Candidate Path List Pre-Computation 58

4.2.3 Ranking of Paths Elaboration 58

4.2.4 Candidate Path List Augmentation (CPLA) 59

4.3 Flow-Link Formulation 61

4.3.1 Flow Conservation Constraints 62

4.3.2 Obtaining the Routing from xde Variables 63

4.3.3 Optimality Analysis 64

4.4 Destination-Link Formulation 65

4.4.1 Obtaining the Routing Tables from xte Variables 67

4.4.2 Some Properties of the Routing Table Representation 67

4.4.3 Comparing Flow-Based and Destination-Based Routing 71

4.5 Convexity Properties of Performance Metrics 71

4.6 Problem Variants 72

4.6.1 Anycast Routing 72

4.6.2 Multicast Routing 74

4.6.3 Non-Bifurcated Routing 75

4.6.4 Integral Routing 77

4.6.5 Destination-Based Shortest Path Routing 77

4.6.6 SRG-Disjoint 1+1 Dedicated Protection Routing 79

4.6.7 Shared Restoration Routing 80

4.6.8 Multi-Hour Routing 81

4.7 Notes and Sources 83

4.8 Exercises 83

References 86

5 Capacity Assignment Problems 88

5.1 Introduction 88

5.2 Long-Term Capacity Planning Problem Variants 89

5.2.1 Capacity Planning for Concave Costs 89

5.2.2 Capacity Planning with Modular Capacities 94

5.2.3 Multi-Period Capacity Planning 97

5.3 Fast Capacity Allocation Problem Variants: Wireless Networks 98

5.3.1 The Wireless Channel 99

5.3.2 Wireless Networks 100

5.3.3 Modeling Wireless Networks 101

5.4 MAC Design in Hard-Interference Scenarios 104

5.4.1 Optimization in Random Access Networks 105

5.4.2 Optimization in Carrier-Sense Networks 109

5.5 Transmission Power Optimization in Soft Interference Scenarios 113

5.6 Notes and Sources 116

5.7 Exercises 117

References 118

6 Congestion Control Problems 120

6.1 Introduction 120

6.2 NUM Model 121

6.2.1 Utility Functions for Elastic and Inelastic Traffic 121

6.2.2 Fair Congestion Control 122

6.2.3 Optimality Conditions 123

6.3 Case Study: TCP 124

6.3.1 Window-Based Flow Control 125

6.3.2 TCP Reno 126

6.3.3 TCP Vegas 131

6.4 Active Queue Management (AQM) 134

6.4.1 A Simplified Model of the TCP-AQM Interplay 135

6.5 Notes and Sources 136

6.6 Exercises 137

References 139

7 Topology Design Problems 141

7.1 Introduction 141

7.2 Node Location Problems 142

7.2.1 Problem Variants 143

7.2.2 Results 144

7.3 Full Topology Design Problems 146

7.3.1 Problem Variants 148

7.3.2 Results 150

7.4 Multilayer Network Design 152

7.5 Notes and Sources 154

7.6 Exercises 154

References 157

Part II ALGORITHMS

8 Gradient Algorithms in Network Design 161

8.1 Introduction 161

8.2 Convergence Rates 163

8.3 Projected Gradient Methods 164

8.3.1 Basic Gradient Projection Algorithm 165

8.3.2 Scaled Projected Gradient Method 165

8.3.3 Singular and Ill-Conditioned Problems 168

8.4 Asynchronous and Distributed Algorithm Implementations 169

8.5 Non-Smooth Functions 172

8.6 Stochastic Gradient Methods 174

8.7 Stopping Criteria 176

8.8 Algorithm Design Hints 177

8.8.1 Dimensioning the Step Size 177

8.8.2 Discrete Step Length 178

8.8.3 Heavy-Ball Methods 179

8.9 Notes and Sources 181

8.10 Exercises 181

References 182

9 Primal Gradient Algorithms 184

9.1 Introduction 184

9.2 Penalty Methods 185

9.2.1 Interior Penalty Methods 185

9.2.2 Exterior Penalty Methods 186

9.3 Adaptive Bifurcated Routing 188

9.3.1 Removing Equality Constraints 189

9.3.2 Optimality and Stability 190

9.3.3 Implementation Example 192

9.4 Congestion Control using Barrier Functions 197

9.4.1 Implementation Example 198

9.4.2 Exterior Penalty 200

9.5 Persistence Probability Adjustment in MAC Protocols 201

9.5.1 Implementation Example 203

9.6 Transmission Power Assignment in Wireless Networks 205

9.6.1 Implementation Example 207

9.7 Notes and Sources 210

9.8 Exercises 211

References 213

10 Dual Gradient Algorithms 214

10.1 Introduction 214

10.2 Adaptive Routing in Data Networks 217

10.2.1 Optimality and Stability 219

10.2.2 Implementation Example 219

10.3 Backpressure (Center-Free) Routing 221

10.3.1 Relation between 𝛾, ΔP, and Average Queue Sizes, Qnd 224

10.3.2 Implementation Example 225

10.4 Congestion Control 228

10.4.1 Optimality and Stability Conditions 229

10.4.2 Implementation Example 230

10.5 Decentralized Optimization of CSMA Window Sizes 231

10.5.1 Implementation Example 234

10.6 Notes and Sources 236

10.7 Exercises 236

References 238

11 Decomposition Techniques 240

11.1 Introduction 240

11.2 Theoretical Fundamentals 241

11.2.1 Primal Decomposition 241

11.2.2 Dual Decomposition 244

11.2.3 Other Decompositions 246

11.3 Cross-Layer Congestion Control and QoS Capacity Allocation 247

11.3.1 Implementation Example 249

11.4 Cross-Layer Congestion Control and Backpressure Routing 249

11.4.1 Implementation Example 252

11.5 Cross-Layer Congestion Control and Power Allocation 253

11.5.1 Implementation Example 254

11.6 Multidomain Routing 256

11.6.1 Implementation Example 258

11.7 Dual Decomposition in Non-Convex Problems 259

11.7.1 Implementation Example 261

11.8 Notes and Sources 261

11.9 Exercises 263

References 265

12 Heuristic Algorithms 266

12.1 Introduction 266

12.1.1 What Complexity Theory Tells us that We cannot Do 266

12.1.2 Our Options 267

12.1.3 Organization and Rationale of this Chapter 268

12.2 Heuristic Design Keys 270

12.2.1 Heuristic Types 270

12.2.2 Intensification versus Diversification 271

12.2.3 How to Assess the Solution Quality 271

12.2.4 Stop Conditions 272

12.2.5 Defining the Cost or Fitness Function 272

12.2.6 Coding the Solution 273

12.3 Local Search Algorithms 273

12.3.1 Design Hints 274

12.4 Simulated Annealing 276

12.4.1 Design hints 277

12.5 Tabu Search 278

12.5.1 Design Hints 280

12.6 Greedy Algorithms 281

12.7 GRASP 282

12.8 Ant Colony Optimization 283

12.8.1 Design Hints 286

12.9 Evolutionary Algorithms 288

12.9.1 Design Hints 289

12.10 Case Study: Greenfield Plan with Recovery Schemes Comparison 291

12.10.1 Case Study Description 291

12.10.2 Algorithm Description 293

12.10.3 Combining Heuristics and ILPs 295

12.10.4 Results 296

12.11 Notes and Sources 297

12.12 Exercises 297

References 299

A Convex Sets. Convex Functions 301

A.1 Convex Sets 301

A.2 Convex and Concave Functions 303

A.2.1 Convexity in Differentiable Functions 303

A.2.2 Strong Convexity/Concavity 306

A.2.3 Convexity in Non-Differentiable Functions 306

A.2.4 Determining the Curvature of a Function 307

A.2.5 Sub-level Sets 310

A.2.6 Epigraphs 311

A.3 Notes and Sources 311

Reference 312

B Mathematical Optimization Basics 313

B.1 Optimization Problems 313

B.2 A Classification of Optimization Problems 315

B.2.1 Linear Programming 315

B.2.2 Convex Programs 318

B.2.3 Nonlinear Programs 320

B.2.4 Integer Programs 321

B.3 Duality 324

B.3.1 Dual Function 324

B.4 Optimality Conditions 330

B.4.1 Optimality Conditions in Problems with Strong Duality 330

B.4.2 Graphical Interpretation of KKT Conditions 333

B.4.3 Optimality Conditions in Problems Without Strong Duality 336

B.5 Sensitivity Analysis 337

B.6 Notes and Sources 339

References 340

C Complexity Theory 341

C.1 Introduction 341

C.2 Deterministic Machines and Deterministic Algorithms 342

C.2.1 Complexity of a Deterministic Algorithm 342

C.2.2 Worst-Case Algorithm Complexity 343

C.2.3 Asymptotic Algorithm Complexity 343

C.2.4 Complexity is a Real Barrier 345

C.3 Non-Deterministic Machines and Non-Deterministic Algorithms 346

C.3.1 Complexity of a Non-Deterministic Algorithm 347

C.4 N and NP Complexity Classes 347

C.5 Polynomial Reductions 349

C.5.1 A Polynomial Time Reduction Example 350

C.6 NP-Completeness 351

C.6.1 An Example Proving NP-Completeness for a Problem 352

C.7 Optimization Problems and Approximation Schemes 352

C.7.1 The NPʘ Class 353

C.7.2 Approximation Algorithms 354

C.7.3 PTAS Reductions 356

C.7.4 NPʘ-Complete Problems 356

C.8 Complexity of Network Design Problems 357

C.9 Notes and Sources 357

References 358

D Net2Plan 359

D.1 Net2Plan 359

D.2 On the Role of Net2Plan in this Book 360

Index 363

See More
Students Resources
Wiley Student Companion Site
See More
See Less
Back to Top