Groupage par tubes

Description

Dans cet article nous donnons des bornes sur le coût du groupage dans les réseaux où le trafic est un ensemble de requêtes transportées dans une hiérarchie de couches électroniques ou optiques (réseaux dorsaux SONET/SDH ou WDM). Nous nous limitons au cas du groupage entre deux couches avec un coefficient de groupage unique : on groupe au plus C requêtes ensemble dans un «tube» logique. Un tube est une connexion virtuelle entre deux noeuds du réseau. L'objectif ici est de minimiser le nombre de tubes utilisés, ce qui est une bonne mesure du coût actuel des réseaux où les équipements de (de)multiplexage mis aux bouts des tubes constituent la part importante du coût. Notons que le problème réel est plus complexe puisque certains choix de tubes logiques sont incompatibles avec la capacité physique du réseau. Nous considérons le cas d'un trafic simple (au plus une requête pour un couple de noeuds). Nous montrons que le problème est déjà NP-difficile avec C 2, et nous donnons une borne inférieure sur le nombre de tubes et caractérisons les cas où elle est atteinte. Dans le cas d'une matrice de trafic uniforme (All-to-All, une requête entre chaque couple de sommets), nous ramenons le problème à l'existence de décompositions des arcs du graphe complet orienté symétrique en graphes particuliers, ce qui est une variante du problème de packing de graphe. Ceci nous permet de résoudre les cas C 2 et C 3 et de donner une borne supérieure sur le nombre de tubes (au plus ´C • 1µ C fois la borne inférieure).

Abstract

International audience

Additional details