HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

# Optimal Solution of the Maximum All Request Path Grooming Problem

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - 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.
Keywords :
Document type :
Reports
Domain :

Cited literature [14 references]

https://hal.inria.fr/inria-00070381
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 8:19:21 PM
Last modification on : Friday, February 4, 2022 - 3:11:40 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:04:41 PM

### Identifiers

• HAL Id : inria-00070381, version 1

### Citation

Jean-Claude Bermond, Michel Cosnard, David Coudert, Stéphane Pérennes. Optimal Solution of the Maximum All Request Path Grooming Problem. [Research Report] RR-5627, INRIA. 2006, pp.12. ⟨inria-00070381⟩

Record views