Skip to Main content Skip to Navigation
Journal articles

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 metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Wednesday, January 17, 2018 - 3:43:29 PM
Last modification on : Tuesday, December 7, 2021 - 4:10:49 PM
Long-term archiving on: : Monday, May 7, 2018 - 2:29:04 PM


Files produced by the author(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⟩



Record views


Files downloads