HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Maximum Flow and Minimum-Cost Flow in 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 two fundamental optimization problems. In the first one, we aim to activate a set of interfaces in the network G = (V, E) in order to guarantee the maximal bandwidth between two given nodes. Nodes V represent the devices, edges E represent the connections that can be established according to the availability of the interfaces in the devices. In the second problem, we look for activating the cheapest set of interfaces among a network in order to guarantee a minimum bandwidth B of communication between two specified nodes. We show that the first problem is polynomially solvable while the second one is NP-Hard. However, we experimentally analyzed an algorithm for the second problem, showing that in practical cases it guarantees a low approximation ratio which allows us to use it in real-world networks.
Document type :
Conference papers
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

Contributor : Gianlorenzo d'Angelo Connect in order to contact the contributor
Submitted on : Wednesday, November 23, 2011 - 3:11:29 PM
Last modification on : Friday, February 4, 2022 - 3:19:52 AM
Long-term archiving on: : Friday, February 24, 2012 - 2:27:49 AM


Files produced by the author(s)




Gianlorenzo d'Angelo, Gabriele Di Stefano, Alfredo Navarra. Maximum Flow and Minimum-Cost Flow in Multi-Interface Networks. 5th International Conference on Ubiquitous Information Management and Communication, Feb 2011, Seoul, South Korea. pp.19, ⟨10.1145/1968613.1968637⟩. ⟨hal-00644073⟩



Record views


Files downloads