Introduction

Abstract

The telecommunication industry has seen a tremendous development in recent decades, and modern networks are based on high-speed cellular technologies, ATM, and IP technologies, with capabilities of providing transport of sophisticated services combining voice, video, and data. It can be shown that even for much simpler networks, most design problems are NP-complete. Therefore, finding an optimal solution for realistic size network in reasonable time is next to impossible. There are, however, cleverly designed approximation algorithms, randomized approaches, and heuristics, that can be combined to find a good solution, even if not provably optimal. We use a combination of approaches to solve design problems. In particular, the same problem instance is solved using different methods, enabling a comparison of the solutions as well as the methods.

Keywords

Network design

Optimization

NP-complete

Algorithms

Approximations

Heuristics

Randomization

The telecommunication industry has seen a tremendous development in recent decades, with the advent of technologies such as cellular technologies, ATM, and in the IP domain, from DiffServ and MPLS to New Generation Networks (also known as All-IP), with increasing capabilities of providing ever more sophisticated services. Changed legislation has opened up markets for new carriers competing with the incumbent ones. The result is that we have networks of different sizes, implemented with different technologies. The efficient design of communication networks is therefore of great importance, whether it is design of new networks or optimization of existing architectures. A good network design ensures that the network has the necessary capabilities of providing services of a certain quality and that it is resilient to faults, at as low cost as possible.

With network design in this text, we mean the collective procedure of planning network architecture (or topology), assigning flows to links in the network, assigning resources (capacity) to network elements, and verifying performance criteria.

The problem is that these are in general very difficult tasks to perform even for small networks, and the difficulty is increasing rapidly with the network size. As a matter of fact, most tasks can’t be solved in reasonable time. We will therefore often have to resort to different approaches, such as approximations, randomized algorithms, and simulation. Even if none of these approaches give an exact answer, we can by combining the results from different approximate solutions gain insight into how close to an optimal solution we may be. It is similar to observing a far-away object from different angles in order to determine its actual position.

The reader is assumed to be familiar with the mathematics (in particular, probability theory, basic queueing theory, optimization, and linear algebra) equivalent to the mathematics courses in a Bachelor’s degree in computer science or electrical engineering. Most algorithms are suitable for software implementation using some programming language. Higher-level languages such as Matlab (or Octave), or S (or R) are often useful for smaller problems or to test algorithms. Readers familiar with object-oriented programming in general and C++ in particular may find the graph representation and other structures in Shaffer (1997) of use.

1.1 The purpose of this book

The term network design has different connotations. In this text, the term is used for the collective process of constructing a network topology, assigning flows and capacities to network elements, and evaluating related performance metrics. With few exceptions, the objective is that of minimizing the resulting network cost.

Often, due to the lack of a unifying approach and the difficulty of solving these problems, heuristic methods are used in practice. Some heuristics lead to suboptimal network designs (an example is given in Section 1.3).

The purpose of this book is manifold. It is intended to present a framework of methods and algorithms for realistic network design, with focus on practical applications. Many mathematical proofs are omitted in the text, but references are given where these proofs can be found. Examples, illustrations, and pseudocode provide an intuitive picture of how algorithms can be used in practice and indicate how they can be programmed on a computer. It presents a universal ‘toolbox’ for the network designer that can be used in solving a broad range of network design tasks.

The presentation is, as far as possible, technology independent. It should therefore be general enough to be applicable to different technologies and various implementations.

The foundation of the theory of telecommunication engineering is collection of topics from mainly statistics, probability theory, and optimization theory and has therefore the nature of a cross-scientific monograph. The author has applied two main principles in his selection of topics: the methods should as far as possible be independent of the underlying technology, and presented topics should have a practical relevance to communication network engineering, with numerous examples to illustrate their practical use.

It is also the hope of the author that the different approaches used will give the reader an intuitive understanding of solving difficult problems related to network design and the behavior of complex networks.

1.2 The design process

A network is a certain infrastructure, consisting of nodes and interconnecting links, intended for transportation of some commodities in a way as to meet a distributed demand-supply pattern between the nodes. This network has a topology (or architecture), which describes how the nodes are connected by links. The supply and demand pattern, together with topological restrictions, induce commodity flows in the network which in the case of communication network is known as traffic.

The question discussed in this text is how to design an optimal network. The first question that arises is what is meant by ‘optimal.’ Usually, a network should be designed so that it meets various technical constraints, supports a certain amount of flow (or traffic) subject to various performance criteria such as Grade of Service or Quality of Service and a certain degree of resilience for failure situations and, fulfilling these conditions, has the lowest costs of all possible such candidate network designs meeting these criteria.

Some technical constraints on the network are often relatively easy to formulate in exact terms. Examples of such constraints are how many connections a switch or multiplexor can accommodate, or how many nodes a traffic stream can be allowed to traverse. These constraints are considered ‘hard limits’ in the sense that if not fulfilled, the network cannot operate properly. It will be assumed that such constraints always can be met for a network candidate of interest in the design process.

Estimating and modeling traffic and formulating Grade of Service (GoS) or Quality of Service (QoS) criteria are difficult problems in their own right. Not only do different types of traffic require different Grade of Service or Quality of Service criteria, but these are generally of a subjective nature. The fundamental question is how the users perceive the service rendered, and what level of quality can be generally accepted by the users. Therefore, these metrics are closely linked to the cost structure of the service.

A somewhat different design criterion is network resilience. The goal is to have the operation of the network disrupted as little as possible, should, for example, a transmission link fail.

Both the service quality for a given traffic volume and the degree of network resilience are proportional to various costs. The costs can also be of various kinds: capital or operational, such as equipment and installation costs, maintenance costs, or rental or lease fees. Therefore, the cost models, which in this text are modeling the cost of transmission over long-distance links, are of vital importance.

To complicate matters further, various traffic engineering or traffic control policies may be applied to the network, which may have a large impact on its operation, both with respect to efficiency and stability. Traffic engineering such as routing schemes, traffic shaping, or scheduling aim at improving the network operation (and thus service quality and/or stability) by dynamically changing the traffic flow according to the state of the network. Such actions have to be accounted for in the design as well.

In other words, the optimization problem can then be stated as find the feasible network that fulfills the service quality and resilience requirements for a certain amount of traffic, that has the lowest cost.

Mathematically, this can be stated as an optimization problem, such as: Given an amount of offered traffic and a target performance, what is the minimum QoS resources needed?

In mathematical terms, this is an optimization problem, where the level of service quality and network resilience are the side condition, and the quantity of network resources is to be minimized, subject to the cost function. Some examples of cost functions are shown in Figure 1.1.

Figure 1.1 A simplified optimization problem for a link. Revenue is generated by carried traffic, cost is incurred by the link capacity, and the profit is the difference. The profit has its maximum for .

The optimization...