Combinatorial structures for communication networks

Abstract

This thesis deals with a class of theoretical problems arising in applications in communication networks. The dissertation is mainly divided in two parts. In the first part, we attempt to solve a set of survivability network design problems. Network survivability refers to the guarantees that a communication network provides in the event that one or more failures occur. An attack or failure can significantly reduce the capability of the communication network to efficiently deliver basic services to users. In several cases, when a failure occurs, the network operators are interested in restoring traffic by re-routing it through different links. Since re-routing traffic can be rather expensive and may cause delays in transmissions, a key property is that of requiring that traffic which is not affected by the failure is not redirected in failure situations. We study the problem of determining whether a given network, where the traffic is commonly routed on the edges of a shortest path tree (e.g. Ethernet networks with the Spanning Tree Protocol), may satisfy the above mentioned property. We provide computational complexity results for directed and undirected net- works. In particular, for the directed case, we prove that such problem is in general NP-hard and that it remains NP-hard also in some special cases. More- over, we show how to assign weights to the links of the network in order to configure a routing topology with the above mentioned property. In the second part of the thesis, we deal with a problem regarding broadcast- ing in telecommunication networks. We investigate a new version of the well known Minimum Broadcast Time problem which has been deeply studied in the past, since broadcasting is a basic primitive in the communication networks area. Fundamental requirements for a broadcast process are that it completes in the quickest way and that, at the end of the procedure, all the peers in the net- work are informed. In this thesis we deal with an objective function that takes into account the quality of the service associated with the broadcast, namely the minimization of the average broadcast time of the peers. We show that the considered version of the broadcast problem is an NP-hard problem. Indeed, the problem becomes polynomially solvable, if the instance graph is a tree. We also provide a distributed approximation algorithm for our version of the broadcast problem, in which every network node does not know the network topology.