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 , 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.
Type de document :
[Research Report] RR-8658, INRIA Sophia Antipolis; INRIA. 2014
Contributeur : Frédéric Giroire <>
Soumis le : lundi 22 décembre 2014 - 14:08:47
Dernière modification le : samedi 17 septembre 2016 - 01:36:49
Document(s) archivé(s) le : lundi 23 mars 2015 - 19:21:16


Fichiers produits par l'(les) auteur(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>



Consultations de
la notice


Téléchargements du document