Notions of Connectivity in Overlay Networks

Abstract : " How well connected is the network? " This is one of the most fundamental questions one would ask when facing the challenge of designing a communication network. Three major notions of connectivity have been considered in the literature, but in the context of traditional (single-layer) networks, they turn out to be equivalent. This paper introduces a model for studying the three notions of connectivity in multi-layer networks. Using this model, it is easy to demonstrate that in multi-layer networks the three notions may differ dramatically. Unfortunately, in contrast to the single-layer case, where the values of the three connectivity notions can be computed efficiently, it has been recently shown in the context of WDM networks (results that can be easily translated to our model) that the values of two of these notions of connectivity are hard to compute or even approximate in multi-layer networks. The current paper shed some positive light into the multi-layer connectivity topic: we show that the value of the third connectivity notion can be computed in polynomial time and develop an approximation for the construction of well connected overlay networks.
Type de document :
Communication dans un congrès
Structural Information and Communication Complexity - 19th International Colloquium, 2012, Jun 2012, Reykjavik, Iceland. 2015, 〈10.1007/978-3-642-31104-8_3〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01241098
Contributeur : Amos Korman <>
Soumis le : mercredi 6 janvier 2016 - 08:59:02
Dernière modification le : mardi 17 avril 2018 - 11:24:47
Document(s) archivé(s) le : jeudi 7 avril 2016 - 15:44:55

Fichiers

overlay-sub-sirocco-new.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pierre Fraigniaud, Amos Korman, Shay Kutten, David Peleg, Emek Yuval. Notions of Connectivity in Overlay Networks. Structural Information and Communication Complexity - 19th International Colloquium, 2012, Jun 2012, Reykjavik, Iceland. 2015, 〈10.1007/978-3-642-31104-8_3〉. 〈hal-01241098〉

Partager

Métriques

Consultations de la notice

250

Téléchargements de fichiers

58