Bandwidth Constrained Multi-interface Networks

Abstract : In heterogeneous networks, devices can communicate by means of multiple wired or wireless interfaces. By switching among interfaces or by combining the available interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost, and provides a communication bandwidth. In this paper, we consider the problem of activating the cheapest set of interfaces among a network G = (V,E) in order to guarantee a minimum bandwidth B of communication between two specified nodes. Nodes V represent the devices, edges E represent the connections that can be established. In practical cases, a bounded number k of different interfaces among all the devices can be considered. Despite this assumption, the problem turns out to be NP-hard even for small values of k and Δ, where Δ is the maximum degree of the network. In particular, the problem is NP-hard for any fixed k ≥ 2 and Δ ≥ 3, while it is polynomially solvable when k = 1, or Δ ≤ 2 and k = O(1). Moreover, we show that the problem is not approximable within ηlogB or Ω(loglog|V|) for any fixed k ≥ 3, Δ ≥ 3, and for a certain constant η, unless P=NP. We then provide an approximation algorithm with ratio guarantee of b max , where b max is the maximum communication bandwidth allowed among all the available interfaces. Finally, we focus on particular cases by providing complexity results and polynomial algorithms for Δ ≤ 2.
Type de document :
Communication dans un congrès
Ivana Cerná and Tibor Gyimóthy and Juraj Hromkovic and Keith Jefferey and Rastislav Královic and Marko Vukolic and Stefan Wolf. 37th Conference on Current Trends in Theory and Practice of Computer Science, Jan 2011, Nový Smokovec, Slovakia. Springer, 6543, pp.202-213, 2011, Lecture Notes in Computer Science; SOFSEM 2011: Theory and Practice of Computer Science. <10.1007/978-3-642-18381-2_17>
Liste complète des métadonnées

https://hal.inria.fr/hal-00644104
Contributeur : Gianlorenzo D'Angelo <>
Soumis le : mercredi 23 novembre 2011 - 15:46:32
Dernière modification le : mardi 22 mai 2012 - 15:07:02
Document(s) archivé(s) le : vendredi 24 février 2012 - 02:30:11

Fichier

MultiInterfacesFlowTheor.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Gianlorenzo D'Angelo, Gabriele Di Stefano, Alfredo Navarra. Bandwidth Constrained Multi-interface Networks. Ivana Cerná and Tibor Gyimóthy and Juraj Hromkovic and Keith Jefferey and Rastislav Královic and Marko Vukolic and Stefan Wolf. 37th Conference on Current Trends in Theory and Practice of Computer Science, Jan 2011, Nový Smokovec, Slovakia. Springer, 6543, pp.202-213, 2011, Lecture Notes in Computer Science; SOFSEM 2011: Theory and Practice of Computer Science. <10.1007/978-3-642-18381-2_17>. <hal-00644104>

Partager

Métriques

Consultations de
la notice

243

Téléchargements du document

113