Mathematical aspects of network routing optimization. (Q549117)

This book provides first an elementary introduction into algorithms for network routing. In the second part of the book, the discussion is concentrated on two types of networks, namely multicast networks and wireless ad hoc systems. In principle, the investigations of this book focus on two major types of problems, namely minimum cost routing and cache placement problems. For these problems, the major goal is to present efficient algorithms, either with or without a performance guarantee. The book has about 200 pages and consists of 12 chapters and three appendices. Chapter 1 gives an introduction to telecommunication networks. It deals with unicast routing problems which are usually solvable in polynomial time. This chapter deals with a flooding algorithm, distance-vector algorithms (the Bellman-Ford algorithm) and link-state algorithms (Dijkstra's algorithm). The second chapter describes some basic algorithms and models used in multicast routing. Chapter 3 considers Steiner tree problems, which are useful in representing solutions for multicast routing problems, and discusses the main algorithms using such problems as a model. It contains e.g. sections on Steiner trees on graphs, modeling multicast routing constraints, Steiner tree problems with delay constraints, and it gives an integer programming formulation for multicast routing. The fourth chapter deals with online versions of multicast routing. In particular, this chapter deals with speeding up routing tree computations and with the quality of service maintenance for online multicast routing. Chapter 5 discusses the most important distributed algorithms for multicast routing. Chapter 6 deals with the use of center-based trees for the determination of multicast routes. It investigates the multicast packing problem and the related multicast dimensioning problem. Since the majority of problems considered in this book are NP-hard, Chapter 7 deals with heuristic algorithms for multicast routing problems. This chapter discusses the use of genetic algorithms, tabu search, simulated annealing and the GRASP heuristic and also some experimental results. Chapter 8 considers the point-to-point connection problem including multiple sources. Such a problem arises e.g. in situations where multiple caches of the same piece of information are maintained. Some computational results are also presented. Chapter 9 discusses the streaming cache placement problem in which one wishes to determine the minimum number of multicast routers required to deliver a content to a number of destinations not violating the link capacities. It is shown that many variants of this problem are NP-hard. The tenth chapter presents several algorithms for solving the streaming cache placement problem. Here both a flow-based algorithm with a performance guarantee in specific cases as well as different heuristics are given, and some computational results are also discussed. Chapter 11 considers an extension from multicast routing to wireless networks. The last chapter discusses connections between routing on wireless networks and power management for mobile devices. For the power control problem in ad hoc networks, an integer programing model and a variable neighborhood search algorithm together with some computational results are presented. Three appendices deal with some basic concepts in communication networks. In particular, a basic introduction into computer networks (e.g. network topology, data packets and circuits, protocols, routing, algorithmic performance) and into the main algorithmic problems (network design, packet routing, complexity, heuristic methods and distributed algorithms) is given. The book is well-written in an easily understandable form. The main algorithms are described in a pseudo-code. Summarizing, the book can be recommended to graduate students, researchers and professionals interested in routing in computer networks and network algorithms.