On the Complexity of Compressing Two Dimensional Routing Tables with Order - Archive ouverte HAL Access content directly
Journal Articles Algorithmica Year : 2018

On the Complexity of Compressing Two Dimensional Routing Tables with Order

(1) , (1) , (1)
1

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 |.
Fichier principal
Vignette du fichier
compacting.pdf (333.03 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

Cite

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⟩
315 View
133 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More