Compressing Two-dimensional Routing Tables with Order

A communication   in a network is a pair of nodes (s,t)(s,t). The node s is called the source source and t the destination. A routing   of a communication (s,t)(s,t) is a path in the network from s to t. A routing of a communication set is a union of routings of its communications.At each node, there is a set XX of communications whose routing path goes through this node. The node needs to find for each communication (s,t)(s,t) in XX, the port that the routing path of (s,t)(s,t) uses to leave it. An easy way of doing it is to store the list of all triples (s,t,k)(s,t,k), where (s,t)∈X(s,t)∈X and k   is the port used by the (s,t)(s,t)-path to leave the node.However, such a list might be very large. Motivated by routing in telecommunication network using Software Defined Network (SDN) technologies, we consider the problem of compacting this list using aggregation rules. Hence, in addition, we can use some additional triples, called *-triples. As an example, a t-destination triple  (⁎,t,p)(⁎,t,p), means that every communication with destination t leaves on port p.We carry out in this work a study of the problem complexity, providing results of NP-completeness, of Fixed-Parameter Tractability and approximation algorithms.