On the Complexity of Compressing Two Dimensional Routing Tables with Order

Frédéric Havet 1 Frédéric Giroire 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

https://hal.inria.fr/hal-01686641
Contributeur : Frederic Havet <>
Soumis le : mercredi 17 janvier 2018 - 15:43:29
Dernière modification le : jeudi 15 février 2018 - 10:31:17

Fichier

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

Identifiants

Collections

Citation

Frédéric Havet, Frédéric Giroire, 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〉

Partager

Métriques

Consultations de la notice

170

Téléchargements de fichiers

30