On the Complexity of Compressing Two Dimensional Routing Tables with Order

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 \(\mathcal {X}\), which are distinct pairs \((s,t)\subseteq S\times T\), (typically S is the set of sources and T the set of destinations), and a port function \(\pi :\mathcal {X} \rightarrow P\) where P is the set of ports. A routing list \(\mathcal {R}\) is an ordered list of triples which are of the form (s, t, p), \((*,t,p)\), \((s,*,p)\) or \((*,*,p)\) with \(s\in S\), \(t\in T\) and \(p\in P\). It routes the communication (s, t) to the port \(r(s,t) =p\) which appears on the first triple in the list \(\mathcal {R}\) that is of the form (s, t, p), \((*,t,p)\), \((s,*,p)\) or \((*,*,p)\). If \(r(s,t)=\pi (s,t)\), then we say that (s, t) is properly routed by \(\mathcal {R}\) and if all communications of \(\mathcal {X}\) are properly routed, we say that \(\mathcal {R}\) emulates \((\mathcal {X}, \pi )\). The aim is to find a shortest routing list emulating \((\mathcal {X}, \pi )\). 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 \(\mathcal {X}\), a port function \(\pi \) and an integer k, the first one called Routing List (resp. the second one, called List Reduction) consists in deciding whether there is a routing list emulating \((\mathcal {X}, \pi )\) of size at most k (resp. \(|\mathcal {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\)), \(\mathcal {X}=S\times T\) and \(|S|=|T|\).