Optimal Solution of the Maximum All Request Path Grooming Problem

Jean-Claude Bermond 1 Michel Cosnard 1 David Coudert 1, * Stéphane Pérennes 1
* Auteur correspondant
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We give an optimal solution to the Maximum All Request Path Grooming (MARPG) problem motivated by a traffic grooming application. The MARPG problem consists in finding the maximum number of connections which can be established in a path of size N, where each arc has a capacity or bandwidth C (grooming factor). We present a greedy algorithm to solve the problem and an explicit formula for the maximum number of requests that can be groomed. In particular, if C = s(s 1)/2 and N > s(s-1), an optimal solution is obtained by taking all the requests of smallest length, that is of length 1 to s. However this is not true in general since anomalies can exist. We give a complete analysis and the exact number of such anomalies.
Type de document :
Communication dans un congrès
Advanced International Conference on Telecommunications (AICT), Feb 2006, Le Gosier, Guadeloupe, France. IEEE, 2006, 〈10.1109/AICT-ICIW.2006.144〉
Liste complète des métadonnées
https://hal.inria.fr/inria-00429167
Contributeur : David Coudert <>
Soumis le : dimanche 1 novembre 2009 - 13:43:37
Dernière modification le : lundi 23 avril 2018 - 10:52:05
Document(s) archivé(s) le : jeudi 17 juin 2010 - 18:53:14

Fichier

BCCP-AICT06.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

UNICE | INRIA | I3S | TDS-MACS | UNIV-COTEDAZUR

Citation

Jean-Claude Bermond, Michel Cosnard, David Coudert, Stéphane Pérennes. Optimal Solution of the Maximum All Request Path Grooming Problem. Advanced International Conference on Telecommunications (AICT), Feb 2006, Le Gosier, Guadeloupe, France. IEEE, 2006, 〈10.1109/AICT-ICIW.2006.144〉. 〈inria-00429167〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

239

Téléchargements de fichiers

97

Contact


archive-ouverte@inria.fr