Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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 : A communication in a network is a pair of nodes (s, t). The node s is called the source source and t the destination. A communication set is a set of distinct communications, i.e. two communications might have the same source or the same destination, but they cannot have both same source and same destination. A routing of a communication (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 X of communications whose routing path goes through this node. The node needs to be able to find for each communication (s,t) in X, the port that the routing path of (s,t) uses to leave it. An easy way of doing it is to store the list of all triples (s,t,k), where (s, t) ∈ X and k is the port used by the (s, t)-path to leave the node. Such triples are called communication triples. However, such a list might be very large. Motivated by routing in telecommunication network using Software Defined Network Technologies, we consider the problem of compacting this list using aggregation rules. Indeed, SDN routers use specific memory which is expensive and of small capacity. Hence, in addition, we can use some additional triples, called ∗-triples. As an example, a t-destination triple (∗, 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.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Frédéric Giroire Connect in order to contact the contributor
Submitted on : Monday, December 22, 2014 - 2:08:47 PM
Last modification on : Wednesday, October 26, 2022 - 8:14:46 AM
Long-term archiving on: : Monday, March 23, 2015 - 7:21:16 PM


Files produced by the author(s)


  • HAL Id : hal-01097910, version 1




Frédéric Giroire, Frédéric Havet, Joanna Moulierac. Compressing Two-dimensional Routing Tables with Order. [Research Report] RR-8658, INRIA Sophia Antipolis; INRIA. 2014. ⟨hal-01097910⟩



Record views


Files downloads