Design of Modern Communication Networks focuses on methods and algorithms related to the design of communication networks, using optimization, graph theory, probability theory and simulation techniques. The book discusses the nature and complexity of the network design process, then introduces theoretical concepts, problems and solutions. It demonstrates the design of network topology and traditional loss networks, followed by uncontrolled packet networks, flow-controlled networks, and multiservice networks. Access network design is reviewed, and the book concludes by considering the design of survivable (reliable) networks and various reliability concepts.
Key Features
A toolbox of algorithms: The book provides practical advice on implementing algorithms, including the programming aspects of combinatorial algorithms.
Extensive solved problems and illustrations: Wherever possible, different solution methods are applied to the same examples to compare performance and verify precision and applicability.
Technology-independent: Solutions are applicable to a wide range of network design problems without relying on particular technologies.

Design of communication network is a complex task, as many of the problems involved are inherently difficult to solve. This leads to the necessity of using a collection of cleverly designed algorithms and methods rather than a single approach. The book is written on at least two levels. Firstly, specific problems related to network design form the main structure of the book. On a second level, various types of algorithms are used, discussed and modified in the course of the text. The structure gives views: one problem based, one method based.
The main intention is that the text will serve as a handbook in engineering with a focus on algorithms and their illustration by examples. On the other hand, rather than being an encyclopedia of algorithms and methods, the text should be possible to read as a discourse in techniques of network design. Even if mainly intended as a handbook, it may also be useful in academia as side literature in telecommunication education programs.
In practice, network design has been more of a handicraft than a science. This is no doubt due to the fact that almost all problems related to network design are NP-hard, or in some other class of problems which are difficult to solve. However, these problems can often be solved approximately. When presenting approximation schemes in this book, the author has taken into account both the precision of the result and the complexity of the algorithm. A simpler, intuitive algorithm has sometimes been favored over more complex algorithms, sometimes even if the precision is lower.
In this text, we will use a mixture of analytical analysis, heuristics, approximations, randomization and common sense to solve difficult problems related to network design. Thus, we may not be able to answer the question "What is the optimal solution to this problem?", but we may be able to answer the question "What is the probability that there is a better solution to this problem?", and if the probability is low enough, we should be close to the answer of the first question. Also, if a proposed network is available to us we can assert its superiority or inferiority to solutions obtained using the methods presented in this book.
It is the hope of the author that the reader will experience the same fascinating journey it has been writing this book. Indeed, at the heart of network design lies the combination of methods, mixed with a fair dose of common sense and experience, needed to solve often very intricate problems. It is an exquisite example of applied mathematics: finding methods that might work!
Most proofs of mathematical theorems have been omitted in the text, as the focus is on application level rather than a theoretical level. These proofs can be found in the cited references. The intention is instead to provide "empirical proofs" of the methods by solving problems using different methods and thereby arriving at the same or similar results. A number of such comparative examples are provided. Proofs have been included in some cases when they provide details that are instructive for constructing an algorithm.
With network design we mean the initial planning or long-term modifications of networks on a rather large scale. The text does not discuss control or routing mechanisms which instantaneously have to react on failure or overload situations. Such aspect may be referred to as operational rather than design related.
The aim of the text is to be as technology independent as possible. That is the reason why there are very little description of actual network technologies such as STM, ATM, IP, and so on, their protocols and functionality. There is a lot of literature available on these topics, and the algorithms presented in this book should be possible to translate into technology specific terms rather easily.
As mathematical prerequisites, the reader is probably familiar with some combinatorics, optimization, fundamental probability theory, queueing theory and analysis.
The author would like to thank V.B. Iversen and F.P. Kelly for their comments and encouragement. He is also grateful to the many researchers and scientists that have made their interesting papers freely available on the Internet.
Christofer Larsson,
Bratislava.

Preface xv

CHAPTER 1 Introduction 1

1.1 The Purpose of this Book 2

1.2 The Design Process 2

1.3 A First Example 5

1.4 Algorithms for Hard Problems 7

      1.4.1 Complexity Classes 9

      1.4.2 Showing Problem Hardness 10

1.5 Models and Algorithms 12

      1.5.1 Classification of Algorithms 14

      1.5.2 Randomization 16

      1.5.3 MonteCarlo Techniques 17

1.6 Organization of this Book 18

1.7 Summary 19

CHAPTER 2 Networks and Flows 21

2.1 Preliminaries 22

      2.1.1 Basic Flow Concepts 22

      2.1.2 Graph Flow Problems 27

2.2 Network Representations 28

2.3 Graph Connectivity 30

      2.3.1 Depth-First Search 31

      2.3.2 Breadth-First Search 31

2.4 Shortest Paths 32

      2.4.1 Shortest Path as a Linear Program 32

      2.4.2 Dijkstra's Algorithm 36

      2.4.3 The Bellman-Ford Algorithm 39

      2.4.4 The Floyd-War shall Algorithm 41

2.5 Maximum Flows 43

      2.5.1 Maximum Flow as a Linear Program 44

      2.5.2 The Ford-Fulkerson Labeling Algorithm 46

      2.5.3 Approximate Maximum Flow 49

2.6 Summary 55

CHAPTER 3 Advanced Flow Theory 57

3.1 Multi-Terminal Flows 57

      3.1.1 The Gomory-Hu Algorithm 59

3.2 Minimum-Cost Flows 63

      3.2.1 Problem Formulation 64

      3.2.2 The Out-of-Kilter Algorithm 66

      3.2.3 Variants and Modifications 72

3.3 Multi-Commodity Flows 73

      3.3.1 Problem Formulation 74

      3.3.2 An Approximation Algorithm 75

3.4 Summary 82

CHAPTER 4 Topological Design 85

4.1 Capacitated Network Design 85

      4.1.1 Cost Functions 86

      4.1.2 Routing 87

4.2 Important Properties of Graphs 88

      4.2.1 Sparseness of Graphs 88

      4.2.2 Example Topologies 91

4.3 Ring Topologies 92

      4.3.1 The Nearest Neighbor Algorithm 93

      4.3.2 Incremental Insertion 93

      4.3.3 k-Optimal Methods 93

4.4 Spanning Trees and Spanners 94

      4.4.1 Properties of Spanners 94

      4.4.2 A Greedy Algorithm for Spanner Construction 95

4.5 Gomory-Hu Design 99

      4.5.1 Constant Edge Costs 100

      4.5.2 Extension to General Networks 102

4.6 Randomized Topological Design 105

      4.6.1 Expander Graphs 106

      4.6.2 MonteCarlo Optimization 107

4.7 Genetic Algorithms 110

4.8 Resource Allocation 114

      4.8.1 The Knapsack Problem 114

      4.8.2 Dynamic Programming 115

      4.8.3 Branch-and-Bound 117

4.9 Summary 117

CHAPTER 5 Stochastic Processes and Queues 119

5.1 Traffic and Blocking 119

      5.1.1 Point Processes 121

      5.1.2 The Poisson Process 123

      5.1.3 Characterization of Traffic 125

5.2 Modeling with Queues 126

      5.2.1 Characteristics of Queueing Processes 127

      5.2.2 Measuring System Performance 129

      5.2.3 Some General Results 129

      5.2.4 Simple Markovian Queues 131

5.3 Markov Chain Analysis 135

      5.3.1 Discrete-Time Markov Chains 136

      5.3.2 Numerical Solution of Markov Chains 141

      5.3.3 Randomization 142

      5.3.4 Truncation of State Space 145

      5.3.5 Two Stations in Tandem 146

5.4 The Erlang B-Formula and Generalizations 149

      5.4.1 Integer Number of Circuits 150

      5.4.2 Non-Integer Number of Circuits 150

      5.4.3 Approximations 151

      5.4.4 The Erlang C-Formula 152

      5.4.5 Derivatives 153

      5.4.6 Inverse 154

5.5 Overflow Theory 155

      5.5.1 The Hayward Approximation 158

      5.5.2 The Wilkinson-Bretschneider Method 160

5.6 Summary 161

CHAPTER 6 Loss Networks 163

6.1 Calculating Blocking in a Network 164

6.2 Resource Allocation 168

      6.2.1 Moe's Principle 168

      6.2.2 An Optimization Procedure 171

6.3 Routing and Admission Control 172

      6.3.1 Routing 173

6.4 Network Programming 176

      6.4.1 Network Bounds 176

      6.4.2 Symmetric Networks 179

      6.4.3 The Cube Network 182

      6.4.4 General Networks 186

6.5 Simulation of Loss Networks 188

      6.5.1 Discrete Event Simulation 188

      6.5.2 The Erlang Link 190

6.6 Efficiency and Stability of Loss Networks 191

      6.6.1 Network Model 191

      6.6.2 Instability 193

      6.6.3 Trunk Reservation and Multiple Alternatives 194

6.7 Summary 197

CHAPTER 7 Simple Packet Networks 199

7.1 General Properties of Packet Networks 200

      7.1.1 Routing 202

7.2 Queueing Networks 204

      7.2.1 Open Jackson Networks 204

      7.2.2 The Routing Matrix 208

      7.2.3 End-to-End Delay 210

7.3 Resource Allocation 212

      7.3.1 Linear Costs 213

      7.3.2 Concave Costs 216

      7.3.3 Discrete Costs 219

      7.3.4 Moe's Principle 219

7.4 Flow Optimization 220

      7.4.1 The Flow Deviation Method 221

7.5 Simultaneous Resource and Flow Optimization 227

7.6 Finite Buffers 228

7.7 Local Search 232

      7.7.1 The Branch Exchange Method 233

      7.7.2 The Cut-Saturation Method 233

7.8 Simulation of General Packet Networks 234

      7.8.1 The Single Link 235

      7.8.2 Queueing Networks 236

7.9 Summary 236

CHAPTER 8 Flow-Controlled Packet Networks 237

8.1 Flow Control and Congestion Control 238

      8.1.1 Virtual Channels 238

      8.1.2 Transmission Control Protocol (TCP) 239

8.2 Closed Queueing Networks 241

      8.2.1 The Product-Form Solution 242

      8.2.2 Solving the Traffic Equation 243

8.3 Convolution 246

8.4 Mean Value Analysis 250

      8.4.1 Approximate Mean Value Analysis 254

8.5 Closed Network Approximations 255

      8.5.1 The Equal Throughput Method 256

      8.5.2 The Fixed-Population Mean Method 256

      8.5.3 Virtual Channels 259

8.6 Decomposition 260

      8.6.1 Norton's Theorem 260

      8.6.2 Linear Interpolation 262

      8.6.3 Conditional Mean Value Analysis 263

8.7 TCP Controlled Networks 264

      8.7.1 Performance Metrics 266

      8.7.2 The TCP Model 267

      8.7.3 Fixed-Point Equations 268

      8.7.4 The Effect of TCP 270

8.8 Summary 271

CHAPTER 9 Effective Bandwidth 273

9.1 Broadband Services 273

9.2 Queues in Multi-Service Networks 276

      9.2.1 The M/G/1 Queue 277

      9.2.2 Finite Queues 277

      9.2.3 The M/D/l queue 278

      9.2.4 Approximations for General Queues 281

9.3 Large Deviations 282

      9.3.1 The Scaled Cumulant Generation Funtion 285

      9.3.2 The Chernoff Formula 288

      9.3.3 Normal Approximation 290

      9.3.4 Improved Approximation 292

      9.3.5 Varadhan's Lemma 293

9.4 Effective Bandwidth 295

      9.4.1 The Workload Process 295

      9.4.2 Buffer Allocation 302

      9.4.3 Calculating Effective Bandwidths 303

9.5 Modeling Services 307

      9.5.1 The Basic On-Off Model 307

      9.5.2 Telephony 309

      9.5.3 The Markovian Additive Process 310

      9.5.4 Streaming Video 312

      9.5.5 Data Services 315

      9.5.6 Simulation of Markov Additive Processes 317

9.6 Estimation Techniques 317

      9.6.1 Constant Time-Window Estimator 318

      9.6.2 Variable Time-Window Estimator 320

9.7 Finite Buffers 323

9.8 Summary 327

CHAPTER 10 Multi-Service Systems 329

10.1 The Acceptance Region 329

10.2 The Binomial-Poisson-Pascal Models 331

      10.2.1 The Binomial Distribution 332

      10.2.2 Engset Distribution 336

      10.2.3 The Negative Binomial Distribution 338

      10.2.4 The Truncated Negative Binomial Distribution 339

10.3 Loss Systems with Multiple Services 340

      10.3.1 Systems in Product form 341

      10.3.2 Multi-Rate Systems 345

      10.3.3 Convolution 349

      10.3.4 State-Space Recursion 353

      10.3.5 A Generalized Algorithm 354

      10.3.6 Monte Carlo Simulation 357

10.4 Admission Control 358

10.5 Processor Load Sharing 363

      10.5.1 The Single-Server Queue with Processor Sharing 364

      10.5.2 Extensions to the Model 369

      10.5.3 A Recursive Algorithm 371

10.6 Summary 376

CHAPTER 11 Multi-Service Network Analysis 377

11.1 Fixed-Point Network Analysis 377

      11.1.1 Admission Control and Adaptive Routing 379

      11.1.2 The Fixed-Point Model 380

11.2 Generalized Queueing Networks 382

      11.2.1 Convolution Algorithm 384

      11.2.2 Mean Value Analysis 385

11.3 Flow Analysis by Effective Bandwidth 387

      11.3.1 Effective and Decoupling Bandwidths 388

      11.3.2 Design Methodology for Multi-Service Networks 394

11.4 Summary 398

CHAPTER 12 Survivable Networks 399

12.1 Connectivity and Cuts 399

12.2 Spanning Trees 401

      12.2.1 The Deletion-Contraction Principle 402

      12.2.2 Kirchhoff's Matrix-Tree Theorem 403

      12.2.3 Graph Strength 405

12.3 A Primal-Dual Algorithm 409

12.4 Local Search 414

      12.4.1 Testing Feasibility 414

      12.4.2 Generating an Initial Solution 416

      12.4.3 The Search Neighborhood 416

      12.4.4 Algorithm Summary 418

12.5 The Reliability Polynomial 421

      12.5.1 The Deletion-Contraction Principle 423

      12.5.2 Bounds and Approximations 423

      12.5.3 A Randomized Algorithm 423

12.6 Optimal Topologies and Circulants 425

12.7 Summary 429

Bibliography 431

Index 437

Christofer Larsson is a consultant in network design and traffic engineering, having worked for Ericsson for a decade. He holds an MSc in Engineering Physics from the Royal Institute of Technology, Stockholm, Sweden.

中科院文献情报中心