Please use this identifier to cite or link to this item:
DC FieldValueLanguage
dc.contributor.advisorNicosia, Gaia-
dc.contributor.authorSperduto, Ezio-
dc.contributor.otherMalucelli, Federico-
dc.contributor.otherMirchandani, Pitu-
dc.description.abstractThis 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.it_IT
dc.publisherUniversità degli studi Roma Treit_IT
dc.titleCombinatorial structures for communication networksit_IT
dc.typeDoctoral Thesisit_IT
dc.subject.miurSettori Disciplinari MIUR::Scienze matematiche e informatiche::RICERCA OPERATIVAit_IT
dc.subject.anagraferoma3Scienze matematiche e informaticheit_IT
item.fulltextWith Fulltext-
Appears in Collections:X_Dipartimento di Informatica e automazione
T - Tesi di dottorato
Files in This Item:
File Description SizeFormat
Combinatorial_structures_for_communication_networks.pdf1.14 MBAdobe PDFView/Open
SFX Query Show simple item record Recommend this item

Page view(s)

checked on Sep 24, 2020


checked on Sep 24, 2020

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.