On the Complexity of Compressing Two Dimensional Routing Tables with Order

Frédéric Giroire 1 Frédéric Havet 1 Joanna Moulierac 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Motivated by routing in telecommunication network using Software Defined Network (SDN) technologies, we consider the following problem of finding short routing lists using aggregation rules. We are given a set of communications X , which are distinct pairs (s, t) ⊆ S × T , (typically S is the set of sources and T the set of destinations), and a port function π : X → P where P is the set of ports. A routing list R is an ordered list of triples which are of the form (s, t, p), If r(s, t) = π(s, t), then we say that (s, t) is properly routed by R and if all communications of X are properly routed, we say that R emulates (X , π). The aim is to find a shortest routing list emulating (X , π). In this paper, we carry out a study of the complexity of the two dual decision problems associated to it. Given a set of communication X , a port function π and an integer k, the A preliminary short version of this work has appeared in [7]. 2 Frédéric Giroire et al. first one called Routing List (resp. the second one, called List Reduction) consists in deciding whether there is a routing list emulating (X , π) of size at most k (resp. |X | − k). We prove that both problems are NP-complete. We then give a 3-approximation for List Reduction, which can be generalized to higher dimensions. We also give a 4-approximation for Routing List in the fundamental case when there are only two ports (i.e. |P | = 2), X = S × T and |S| = |T |.
Type de document :
Article dans une revue
Algorithmica, Springer Verlag, 2018, 80 (1), pp.209 - 233. 〈10.1007/s00453-016-0243-7〉
Liste complète des métadonnées

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

Contributeur : Frederic Havet <>
Soumis le : mercredi 17 janvier 2018 - 15:43:29
Dernière modification le : lundi 21 mai 2018 - 21:03:13
Document(s) archivé(s) le : lundi 7 mai 2018 - 14:29:04


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




Frédéric Giroire, Frédéric Havet, Joanna Moulierac. On the Complexity of Compressing Two Dimensional Routing Tables with Order. Algorithmica, Springer Verlag, 2018, 80 (1), pp.209 - 233. 〈10.1007/s00453-016-0243-7〉. 〈hal-01686641〉



Consultations de la notice


Téléchargements de fichiers