Notions of Connectivity in Overlay Networks
International audience " 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 tradit...
Main Authors: | , , , , |
---|---|
Other Authors: | , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2012
|
Subjects: | |
Online Access: | https://hal.inria.fr/hal-01241098 https://hal.inria.fr/hal-01241098/document https://hal.inria.fr/hal-01241098/file/overlay-sub-sirocco-new.pdf https://doi.org/10.1007/978-3-642-31104-8_3 |
id |
ftunivnantes:oai:HAL:hal-01241098v1 |
---|---|
record_format |
openpolar |
spelling |
ftunivnantes:oai:HAL:hal-01241098v1 2023-05-15T16:50:19+02:00 Notions of Connectivity in Overlay Networks Fraigniaud, Pierre Korman, Amos Kutten, Shay Peleg, David Yuval, Emek Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA) Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS) Networks, Graphs and Algorithms (GANG) Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria) Technion - Israel Institute of Technology Haifa Weizmann Institute of Science Rehovot, Israël Reykjavik, Iceland 2012-06-30 https://hal.inria.fr/hal-01241098 https://hal.inria.fr/hal-01241098/document https://hal.inria.fr/hal-01241098/file/overlay-sub-sirocco-new.pdf https://doi.org/10.1007/978-3-642-31104-8_3 en eng HAL CCSD info:eu-repo/semantics/altIdentifier/arxiv/1601.01104 info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-642-31104-8_3 hal-01241098 https://hal.inria.fr/hal-01241098 https://hal.inria.fr/hal-01241098/document https://hal.inria.fr/hal-01241098/file/overlay-sub-sirocco-new.pdf ARXIV: 1601.01104 doi:10.1007/978-3-642-31104-8_3 info:eu-repo/semantics/OpenAccess Structural Information and Communication Complexity - 19th International Colloquium, {SIROCCO} 2012 https://hal.inria.fr/hal-01241098 Structural Information and Communication Complexity - 19th International Colloquium, 2012, Jun 2012, Reykjavik, Iceland. ⟨10.1007/978-3-642-31104-8_3⟩ [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] info:eu-repo/semantics/conferenceObject Conference papers 2012 ftunivnantes https://doi.org/10.1007/978-3-642-31104-8_3 2022-10-12T00:02:22Z International audience " 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. Conference Object Iceland Université de Nantes: HAL-UNIV-NANTES 25 35 |
institution |
Open Polar |
collection |
Université de Nantes: HAL-UNIV-NANTES |
op_collection_id |
ftunivnantes |
language |
English |
topic |
[INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] |
spellingShingle |
[INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] Fraigniaud, Pierre Korman, Amos Kutten, Shay Peleg, David Yuval, Emek Notions of Connectivity in Overlay Networks |
topic_facet |
[INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] |
description |
International audience " 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. |
author2 |
Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA) Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS) Networks, Graphs and Algorithms (GANG) Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria) Technion - Israel Institute of Technology Haifa Weizmann Institute of Science Rehovot, Israël |
format |
Conference Object |
author |
Fraigniaud, Pierre Korman, Amos Kutten, Shay Peleg, David Yuval, Emek |
author_facet |
Fraigniaud, Pierre Korman, Amos Kutten, Shay Peleg, David Yuval, Emek |
author_sort |
Fraigniaud, Pierre |
title |
Notions of Connectivity in Overlay Networks |
title_short |
Notions of Connectivity in Overlay Networks |
title_full |
Notions of Connectivity in Overlay Networks |
title_fullStr |
Notions of Connectivity in Overlay Networks |
title_full_unstemmed |
Notions of Connectivity in Overlay Networks |
title_sort |
notions of connectivity in overlay networks |
publisher |
HAL CCSD |
publishDate |
2012 |
url |
https://hal.inria.fr/hal-01241098 https://hal.inria.fr/hal-01241098/document https://hal.inria.fr/hal-01241098/file/overlay-sub-sirocco-new.pdf https://doi.org/10.1007/978-3-642-31104-8_3 |
op_coverage |
Reykjavik, Iceland |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
Structural Information and Communication Complexity - 19th International Colloquium, {SIROCCO} 2012 https://hal.inria.fr/hal-01241098 Structural Information and Communication Complexity - 19th International Colloquium, 2012, Jun 2012, Reykjavik, Iceland. ⟨10.1007/978-3-642-31104-8_3⟩ |
op_relation |
info:eu-repo/semantics/altIdentifier/arxiv/1601.01104 info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-642-31104-8_3 hal-01241098 https://hal.inria.fr/hal-01241098 https://hal.inria.fr/hal-01241098/document https://hal.inria.fr/hal-01241098/file/overlay-sub-sirocco-new.pdf ARXIV: 1601.01104 doi:10.1007/978-3-642-31104-8_3 |
op_rights |
info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.1007/978-3-642-31104-8_3 |
container_start_page |
25 |
op_container_end_page |
35 |
_version_ |
1766040478688477184 |