Maximum Flow and Minimum-Cost Flow in 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 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.
Type de document :
Communication dans un congrès
5th International Conference on Ubiquitous Information Management and Communication, Feb 2011, Seoul, South Korea. ACM, pp.19, 2011, ICUIMC '11 Proceedings of the 5th International Conference on Ubiquitous Information Management and Communication. <10.1145/1968613.1968637>
Liste complète des métadonnées

https://hal.inria.fr/hal-00644073
Contributeur : Gianlorenzo D'Angelo <>
Soumis le : mercredi 23 novembre 2011 - 15:11:29
Dernière modification le : mardi 22 mai 2012 - 16:19:00
Document(s) archivé(s) le : vendredi 24 février 2012 - 02:27:49

Fichier

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

Identifiants

Collections

Citation

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. ACM, pp.19, 2011, ICUIMC '11 Proceedings of the 5th International Conference on Ubiquitous Information Management and Communication. <10.1145/1968613.1968637>. <hal-00644073>

Partager

Métriques

Consultations de
la notice

196

Téléchargements du document

142