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 :
Communication dans un congrès
INOC (International Network Optimization Conference), May 2015, Varsovie, Poland. Elsevier, 52, pp.351-358, 2016, Electronic Notes In Discrete Mathematics. <http://www.inoc2015.pl/>


https://hal.inria.fr/hal-01162724
Contributeur : Joanna Moulierac <>
Soumis le : mardi 11 octobre 2016 - 12:28:18
Dernière modification le : jeudi 8 décembre 2016 - 19:40:07

Fichier

compacting-camera-ready-final....
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01162724, version 1

Collections

Relations

Citation

Frédéric Giroire, Frédéric Havet, Joanna Moulierac. Compressing two-dimensional routing tables with order. INOC (International Network Optimization Conference), May 2015, Varsovie, Poland. Elsevier, 52, pp.351-358, 2016, Electronic Notes In Discrete Mathematics. <http://www.inoc2015.pl/>. <hal-01162724>

Partager

Métriques

Consultations de
la notice

172

Téléchargements du document

18