Skip to Main content Skip to Navigation
Conference papers

Bandwidth Constrained Multi-interface Networks

Gianlorenzo d'Angelo 1, 2 Gabriele Di Stefano 1 Alfredo Navarra 3
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-00644104
Contributor : Gianlorenzo d'Angelo <>
Submitted on : Wednesday, November 23, 2011 - 3:46:32 PM
Last modification on : Wednesday, October 14, 2020 - 4:23:51 AM
Long-term archiving on: : Friday, February 24, 2012 - 2:30:11 AM

File

MultiInterfacesFlowTheor.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Gianlorenzo d'Angelo, Gabriele Di Stefano, Alfredo Navarra. Bandwidth Constrained Multi-interface Networks. 37th Conference on Current Trends in Theory and Practice of Computer Science, Jan 2011, Nový Smokovec, Slovakia. pp.202-213, ⟨10.1007/978-3-642-18381-2_17⟩. ⟨hal-00644104⟩

Share

Metrics

Record views

530

Files downloads

358