HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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
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.
Document type :
Reports
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

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

Collections

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⟩

Share

Metrics

Record views

175

Files downloads

130