Optimal Solution of the Maximum All Request Path Grooming Problem - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2006

Optimal Solution of the Maximum All Request Path Grooming Problem

Résumé

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.
Fichier principal
Vignette du fichier
BCCP-AICT06.pdf (115.3 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00429167 , version 1 (01-11-2009)

Identifiants

Citer

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. ⟨10.1109/AICT-ICIW.2006.144⟩. ⟨inria-00429167⟩
108 Consultations
87 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More