On the Complexity of Compressing Two Dimensional Routing Tables with Order - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Article Dans Une Revue Algorithmica Année : 2018

On the Complexity of Compressing Two Dimensional Routing Tables with Order

Résumé

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 |.
Fichier principal
Vignette du fichier
compacting.pdf (333.03 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01686641 , version 1 (17-01-2018)

Identifiants

Citer

Frédéric Giroire, Frédéric Havet, Joanna Moulierac. On the Complexity of Compressing Two Dimensional Routing Tables with Order. Algorithmica, 2018, 80 (1), pp.209 - 233. ⟨10.1007/s00453-016-0243-7⟩. ⟨hal-01686641⟩
323 Consultations
164 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More