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 , Laboratoire I3S - 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 |.
Document type :
Journal articles
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-01686641
Contributor : Frederic Havet <>
Submitted on : Wednesday, January 17, 2018 - 3:43:29 PM
Last modification on : Friday, November 30, 2018 - 5:02:04 PM
Long-term archiving on : Monday, May 7, 2018 - 2:29:04 PM

File

compacting.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

686

Files downloads

145