Flow problems 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 communicate by means of multiple wired or wireless interfaces. By switching among interfaces or by combining the available ones, each device might establish several connections. A connection may be established when the devices at its endpoints share at least one active interface. In this paper, we consider two fundamental optimization problems. In the first one (Maximum Flow in Multi-Interface Networks MFMI), we aim to establish the maximal bandwidth that can be guaranteed between two given nodes of the input network. In the second problem (Minimum-Cost Flow in Multi-Interface Networks MCFMI), 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 MFMI is polynomially solvable while MCFMI is NP-hard even for a bounded number of different interfaces and bounded degree networks. Moreover, we provide polynomial approximation algorithms for MCFMI and exact algorithms for relevant sub-problems. Finally, we experimentally analyze the proposed approximation algorithm, showing that in practical cases it guarantees a low approximation ratio.
Type de document :
Article dans une revue
IEEE Transactions on Computers, Institute of Electrical and Electronics Engineers, 2012
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

Contributeur : Gianlorenzo D'Angelo <>
Soumis le : jeudi 6 septembre 2012 - 19:21:18
Dernière modification le : lundi 5 novembre 2018 - 15:36:03
Document(s) archivé(s) le : vendredi 7 décembre 2012 - 03:43:53


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00728878, version 1



Gianlorenzo D'Angelo, Gabriele Di Stefano, Alfredo Navarra. Flow problems in multi-interface networks. IEEE Transactions on Computers, Institute of Electrical and Electronics Engineers, 2012. 〈hal-00728878〉



Consultations de la notice


Téléchargements de fichiers