Optimization of Computer Networks – Modeling and Algorithms – A Hands–On Approach

<p>About the Author xv</p>
<p>Preface xvii</p>
<p>Acknowledgments xxi</p>
<p>1 Introduction 1</p>
<p>1.1 What is a Communication Network? 1</p>
<p>1.2 Capturing the Random User Behavior 4</p>
<p>1.3 Queueing Theory and Optimization Theory 5</p>
<p>1.4 The Rationale and Organization of this Book 6</p>
<p>1.4.1 Part I: Modeling 6</p>
<p>1.4.2 Part II: Algorithms 7</p>
<p>1.4.3 Basic Optimization Requisites: Appendices I, II, and III 10</p>
<p>1.4.4 Net2Plan Tool: Appendix IV 11</p>
<p>Part I MODELING</p>
<p>2 Definitions and Notation 15</p>
<p>2.1 Notation for Sets, Vectors and Matrices 15</p>
<p>2.1.1 Norm Basics 15</p>
<p>2.1.2 Set Basics 16</p>
<p>2.2 Network Topology 17</p>
<p>2.3 Installed Capacities 19</p>
<p>2.4 Traffic Demands 19</p>
<p>2.4.1 Unicast, Anycast, and Multicast Demands 20</p>
<p>2.4.2 Elastic versus Inelastic Demands 21</p>
<p>2.5 Traffic Routing 21</p>
<p>References 22</p>
<p>3 Performance Metrics in Networks 23</p>
<p>3.1 Introduction 23</p>
<p>3.2 Delay 23</p>
<p>3.2.1 Link Delay 23</p>
<p>3.2.2 End–to–End Delay 27</p>
<p>3.2.3 Average Network Delay 27</p>
<p>3.2.4 Convexity Properties 27</p>
<p>3.3 Blocking Probability 28</p>
<p>3.3.1 Link Blocking Probability 28</p>
<p>3.3.2 Demand and Network Blocking Probability 30</p>
<p>3.3.3 Other Blocking Estimations 31</p>
<p>3.3.4 Convexity Properties 34</p>
<p>3.4 Average Number of Hops 34</p>
<p>3.5 Network Congestion 36</p>
<p>3.6 Network Cost 36</p>
<p>3.7 Network Resilience Metrics 37</p>
<p>3.7.1 Shared Risk Groups 40</p>
<p>3.7.2 Simplified Availability Calculations 41</p>
<p>3.7.3 General Model 41</p>
<p>3.8 Network Utility and Fairness in Resource Allocation 44</p>
<p>3.8.1 Fairness in Resource Allocation 44</p>
<p>3.8.2 Fairness and Utility Functions 45</p>
<p>3.8.3 Convexity Properties 47</p>
<p>3.9 Notes and Sources 47</p>
<p>3.10 Exercises 49</p>
<p>References 51</p>
<p>4 Routing Problems 53</p>
<p>4.1 Introduction 53</p>
<p>4.2 Flow–Path Formulation 54</p>
<p>4.2.1 Optimality Analysis 55</p>
<p>4.2.2 Candidate Path List Pre–Computation 58</p>
<p>4.2.3 Ranking of Paths Elaboration 58</p>
<p>4.2.4 Candidate Path List Augmentation (CPLA) 59</p>
<p>4.3 Flow–Link Formulation 61</p>
<p>4.3.1 Flow Conservation Constraints 62</p>
<p>4.3.2 Obtaining the Routing from xde Variables 63</p>
<p>4.3.3 Optimality Analysis 64</p>
<p>4.4 Destination–Link Formulation 65</p>
<p>4.4.1 Obtaining the Routing Tables from xte Variables 67</p>
<p>4.4.2 Some Properties of the Routing Table Representation 67</p>
<p>4.4.3 Comparing Flow–Based and Destination–Based Routing 71</p>
<p>4.5 Convexity Properties of Performance Metrics 71</p>
<p>4.6 Problem Variants 72</p>
<p>4.6.1 Anycast Routing 72</p>
<p>4.6.2 Multicast Routing 74</p>
<p>4.6.3 Non–Bifurcated Routing 75</p>
<p>4.6.4 Integral Routing 77</p>
<p>4.6.5 Destination–Based Shortest Path Routing 77</p>
<p>4.6.6 SRG–Disjoint 1+1 Dedicated Protection Routing 79</p>
<p>4.6.7 Shared Restoration Routing 80</p>
<p>4.6.8 Multi–Hour Routing 81</p>
<p>4.7 Notes and Sources 83</p>
<p>4.8 Exercises 83</p>
<p>References 86</p>
<p>5 Capacity Assignment Problems 88</p>
<p>5.1 Introduction 88</p>
<p>5.2 Long–Term Capacity Planning Problem Variants 89</p>
<p>5.2.1 Capacity Planning for Concave Costs 89</p>
<p>5.2.2 Capacity Planning with Modular Capacities 94</p>
<p>5.2.3 Multi–Period Capacity Planning 97</p>
<p>5.3 Fast Capacity Allocation Problem Variants: Wireless Networks 98</p>
<p>5.3.1 The Wireless Channel 99</p>
<p>5.3.2 Wireless Networks 100</p>
<p>5.3.3 Modeling Wireless Networks 101</p>
<p>5.4 MAC Design in Hard–Interference Scenarios 104</p>
<p>5.4.1 Optimization in Random Access Networks 105</p>
<p>5.4.2 Optimization in Carrier–Sense Networks 109</p>
<p>5.5 Transmission Power Optimization in Soft Interference Scenarios 113</p>
<p>5.6 Notes and Sources 116</p>
<p>5.7 Exercises 117</p>
<p>References 118</p>
<p>6 Congestion Control Problems 120</p>
<p>6.1 Introduction 120</p>
<p>6.2 NUM Model 121</p>
<p>6.2.1 Utility Functions for Elastic and Inelastic Traffic 121</p>
<p>6.2.2 Fair Congestion Control 122</p>
<p>6.2.3 Optimality Conditions 123</p>
<p>6.3 Case Study: TCP 124</p>
<p>6.3.1 Window–Based Flow Control 125</p>
<p>6.3.2 TCP Reno 126</p>
<p>6.3.3 TCP Vegas 131</p>
<p>6.4 Active Queue Management (AQM) 134</p>
<p>6.4.1 A Simplified Model of the TCP–AQM Interplay 135</p>
<p>6.5 Notes and Sources 136</p>
<p>6.6 Exercises 137</p>
<p>References 139</p>
<p>7 Topology Design Problems 141</p>
<p>7.1 Introduction 141</p>
<p>7.2 Node Location Problems 142</p>
<p>7.2.1 Problem Variants 143</p>
<p>7.2.2 Results 144</p>
<p>7.3 Full Topology Design Problems 146</p>
<p>7.3.1 Problem Variants 148</p>
<p>7.3.2 Results 150</p>
<p>7.4 Multilayer Network Design 152</p>
<p>7.5 Notes and Sources 154</p>
<p>7.6 Exercises 154</p>
<p>References 157</p>
<p>Part II ALGORITHMS</p>
<p>8 Gradient Algorithms in Network Design 161</p>
<p>8.1 Introduction 161</p>
<p>8.2 Convergence Rates 163</p>
<p>8.3 Projected Gradient Methods 164</p>
<p>8.3.1 Basic Gradient Projection Algorithm 165</p>
<p>8.3.2 Scaled Projected Gradient Method 165</p>
<p>8.3.3 Singular and Ill–Conditioned Problems 168</p>
<p>8.4 Asynchronous and Distributed Algorithm Implementations 169</p>
<p>8.5 Non–Smooth Functions 172</p>
<p>8.6 Stochastic Gradient Methods 174</p>
<p>8.7 Stopping Criteria 176</p>
<p>8.8 Algorithm Design Hints 177</p>
<p>8.8.1 Dimensioning the Step Size 177</p>
<p>8.8.2 Discrete Step Length 178</p>
<p>8.8.3 Heavy–Ball Methods 179</p>
<p>8.9 Notes and Sources 181</p>
<p>8.10 Exercises 181</p>
<p>References 182</p>
<p>9 Primal Gradient Algorithms 184</p>
<p>9.1 Introduction 184</p>
<p>9.2 Penalty Methods 185</p>
<p>9.2.1 Interior Penalty Methods 185</p>
<p>9.2.2 Exterior Penalty Methods 186</p>
<p>9.3 Adaptive Bifurcated Routing 188</p>
<p>9.3.1 Removing Equality Constraints 189</p>
<p>9.3.2 Optimality and Stability 190</p>
<p>9.3.3 Implementation Example 192</p>
<p>9.4 Congestion Control using Barrier Functions 197</p>
<p>9.4.1 Implementation Example 198</p>
<p>9.4.2 Exterior Penalty 200</p>
<p>9.5 Persistence Probability Adjustment in MAC Protocols 201</p>
<p>9.5.1 Implementation Example 203</p>
<p>9.6 Transmission Power Assignment in Wireless Networks 205</p>
<p>9.6.1 Implementation Example 207</p>
<p>9.7 Notes and Sources 210</p>
<p>9.8 Exercises 211</p>
<p>References 213</p>
<p>10 Dual Gradient Algorithms 214</p>
<p>10.1 Introduction 214</p>
<p>10.2 Adaptive Routing in Data Networks 217</p>
<p>10.2.1 Optimality and Stability 219</p>
<p>10.2.2 Implementation Example 219</p>
<p>10.3 Backpressure (Center–Free) Routing 221</p>
<p>10.3.1 Relation between , P, and Average Queue Sizes, Qnd 224</p>
<p>10.3.2 Implementation Example 225</p>
<p>10.4 Congestion Control 228</p>
<p>10.4.1 Optimality and Stability Conditions 229</p>
<p>10.4.2 Implementation Example 230</p>
<p>10.5 Decentralized Optimization of CSMA Window Sizes 231</p>
<p>10.5.1 Implementation Example 234</p>
<p>10.6 Notes and Sources 236</p>
<p>10.7 Exercises 236</p>
<p>References 238</p>
<p>11 Decomposition Techniques 240</p>
<p>11.1 Introduction 240</p>
<p>11.2 Theoretical Fundamentals 241</p>
<p>11.2.1 Primal Decomposition 241</p>
<p>11.2.2 Dual Decomposition 244</p>
<p>11.2.3 Other Decompositions 246</p>
<p>11.3 Cross–Layer Congestion Control and QoS Capacity Allocation 247</p>
<p>11.3.1 Implementation Example 249</p>
<p>11.4 Cross–Layer Congestion Control and Backpressure Routing 249</p>
<p>11.4.1 Implementation Example 252</p>
<p>11.5 Cross–Layer Congestion Control and Power Allocation 253</p>
<p>11.5.1 Implementation Example 254</p>
<p>11.6 Multidomain Routing 256</p>
<p>11.6.1 Implementation Example 258</p>
<p>11.7 Dual Decomposition in Non–Convex Problems 259</p>
<p>11.7.1 Implementation Example 261</p>
<p>11.8 Notes and Sources 261</p>
<p>11.9 Exercises 263</p>
<p>References 265</p>
<p>12 Heuristic Algorithms 266</p>
<p>12.1 Introduction 266</p>
<p>12.1.1 What Complexity Theory Tells us that We cannot Do 266</p>
<p>12.1.2 Our Options 267</p>
<p>12.1.3 Organization and Rationale of this Chapter 268</p>
<p>12.2 Heuristic Design Keys 270</p>
<p>12.2.1 Heuristic Types 270</p>
<p>12.2.2 Intensification versus Diversification 271</p>
<p>12.2.3 How to Assess the Solution Quality 271</p>
<p>12.2.4 Stop Conditions 272</p>
<p>12.2.5 Defining the Cost or Fitness Function 272</p>
<p>12.2.6 Coding the Solution 273</p>
<p>12.3 Local Search Algorithms 273</p>
<p>12.3.1 Design Hints 274</p>
<p>12.4 Simulated Annealing 276</p>
<p>12.4.1 Design hints 277</p>
<p>12.5 Tabu Search 278</p>
<p>12.5.1 Design Hints 280</p>
<p>12.6 Greedy Algorithms 281</p>
<p>12.7 GRASP 282</p>
<p>12.8 Ant Colony Optimization 283</p>
<p>12.8.1 Design Hints 286</p>
<p>12.9 Evolutionary Algorithms 288</p>
<p>12.9.1 Design Hints 289</p>
<p>12.10 Case Study: Greenfield Plan with Recovery Schemes Comparison 291</p>
<p>12.10.1 Case Study Description 291</p>
<p>12.10.2 Algorithm Description 293</p>
<p>12.10.3 Combining Heuristics and ILPs 295</p>
<p>12.10.4 Results 296</p>
<p>12.11 Notes and Sources 297</p>
<p>12.12 Exercises 297</p>
<p>References 299</p>
<p>A Convex Sets. Convex Functions 301</p>
<p>A.1 Convex Sets 301</p>
<p>A.2 Convex and Concave Functions 303</p>
<p>A.2.1 Convexity in Differentiable Functions 303</p>
<p>A.2.2 Strong Convexity/Concavity 306</p>
<p>A.2.3 Convexity in Non–Differentiable Functions 306</p>
<p>A.2.4 Determining the Curvature of a Function 307</p>
<p>A.2.5 Sub–level Sets 310</p>
<p>A.2.6 Epigraphs 311</p>
<p>A.3 Notes and Sources 311</p>
<p>Reference 312</p>
<p>B Mathematical Optimization Basics 313</p>
<p>B.1 Optimization Problems 313</p>
<p>B.2 A Classification of Optimization Problems 315</p>
<p>B.2.1 Linear Programming 315</p>
<p>B.2.2 Convex Programs 318</p>
<p>B.2.3 Nonlinear Programs 320</p>
<p>B.2.4 Integer Programs 321</p>
<p>B.3 Duality 324</p>
<p>B.3.1 Dual Function 324</p>
<p>B.4 Optimality Conditions 330</p>
<p>B.4.1 Optimality Conditions in Problems with Strong Duality 330</p>
<p>B.4.2 Graphical Interpretation of KKT Conditions 333</p>
<p>B.4.3 Optimality Conditions in Problems Without Strong Duality 336</p>
<p>B.5 Sensitivity Analysis 337</p>
<p>B.6 Notes and Sources 339</p>
<p>References 340</p>
<p>C Complexity Theory 341</p>
<p>C.1 Introduction 341</p>
<p>C.2 Deterministic Machines and Deterministic Algorithms 342</p>
<p>C.2.1 Complexity of a Deterministic Algorithm 342</p>
<p>C.2.2 Worst–Case Algorithm Complexity 343</p>
<p>C.2.3 Asymptotic Algorithm Complexity 343</p>
<p>C.2.4 Complexity is a Real Barrier 345</p>
<p>C.3 Non–Deterministic Machines and Non–Deterministic Algorithms 346</p>
<p>C.3.1 Complexity of a Non–Deterministic Algorithm 347</p>
<p>C.4 N and NP Complexity Classes 347</p>
<p>C.5 Polynomial Reductions 349</p>
<p>C.5.1 A Polynomial Time Reduction Example 350</p>
<p>C.6 NP–Completeness 351</p>
<p>C.6.1 An Example Proving NP–Completeness for a Problem 352</p>
<p>C.7 Optimization Problems and Approximation Schemes 352</p>
<p>C.7.1 The NP Class 353</p>
<p>C.7.2 Approximation Algorithms 354</p>
<p>C.7.3 PTAS Reductions 356</p>
<p>C.7.4 NP –Complete Problems 356</p>
<p>C.8 Complexity of Network Design Problems 357</p>
<p>C.9 Notes and Sources 357</p>
<p>References 358</p>
<p>D Net2Plan 359</p>
<p>D.1 Net2Plan 359</p>
<p>D.2 On the Role of Net2Plan in this Book 360</p>
<p>Index 363</p>