Traffic Grooming: Combinatorial Results and Practical Resolutions.

Tibor Cinkler; David Coudert; Michele Flammini; Gianpiero Monaco; Luca Moscardelli; Xavier Muñoz; Ignasi Sau; Mordechai Shalom; Shmuel Zaks

inria-00530964, version 1

Traffic Grooming: Combinatorial Results and Practical Resolutions.

Tibor Cinkler^a^, 1, David Coudert () ², Michele Flammini ()^b^, 3, Gianpiero Monaco () ^2, 3, Luca Moscardelli ()^c^, 3, Xavier Muñoz ()^d^, 4, Ignasi Sau () ^2, 4, Mordechai Shalom ()^e^, 5, Shmuel Zaks ()^f^, 6

Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless, and Ad Hoc Networks. Springer (Ed.) (2010) 63-94

Abstract: In an optical network using the wavelength division multiplexing (WDM) technology, routing a request consists in assigning it a route in the physical network and a wavelength. If each request uses $1/g$ of the bandwidth of the wavelength, we will say that the grooming factor is $g$. That means that on a given edge of the network we can groom (group) at most $g$ requests on the same wavelength. With this constraint the objective can be either to minimize the number of wavelengths (related to the transmission cost) or minimize the number of Add Drop Multiplexers (shortly ADM) used in the network (related to the cost of the nodes). Here, we first survey the main theoretical results obtained for different grooming factors on various topologies: complexity, (in)approximability, optimal constructions, approximation algorithms, heuristics, etc. Then, we give an ILP formulation for multilayer traffic grooming and present some experimental results.

a – Budapest University of Technology
b – University of L'Aquila
c – University of Chieti-Pescara
d – Universitat Politècnica de Catalunya
e – Tel Hai Academic College
f – Technion
1: Department of Telecommunications and Media Informatics (BME-TMIT)
Budapest University of Technology and Economics
2: MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
3: Dipartimento di Informatica [Italy] (DI)
Università degli Studi dell'Aquila
4: Applied Mathematics IV Department
Universitat Politécnica de Catalunya
5: Tel Hai Academic College
Tel Hai Academic College
6: Department of Computer Science [Haifa]
University of Haifa

inria-00530964, version 1
http://hal.inria.fr/inria-00530964
oai:hal.inria.fr:inria-00530964
From: Gianpiero Monaco <>
Submitted on: Sunday, 31 October 2010 16:07:36
Updated on: Wednesday, 1 December 2010 11:52:35

See detailed view

Associated documents

DOI: 10.1007/978-3-642-02250-0

Export

Bibtex EndNote TEI RefWorks

%% inria-00530964, version 1
%% http://hal.inria.fr/inria-00530964
@incollection{cinkler:inria-00530964,
    hal_id = {inria-00530964},
    url = {http://hal.inria.fr/inria-00530964},
    title = {{Traffic Grooming: Combinatorial Results and Practical Resolutions.}},
    author = {Cinkler, Tibor and Coudert, David and Flammini, Michele and Monaco, Gianpiero and Moscardelli, Luca and Mu{\\~n}oz, Xavier and Sau, Ignasi and Shalom, Mordechai and Zaks, Shmuel},
    abstract = {{In an optical network using the wavelength division multiplexing (WDM) technology, routing a request consists in assigning it a route in the physical network and a wavelength. If each request uses $1/g$ of the bandwidth of the wavelength, we will say that the grooming factor is $g$. That means that on a given edge of the network we can groom (group) at most $g$ requests on the same wavelength. With this constraint the objective can be either to minimize the number of wavelengths (related to the transmission cost) or minimize the number of Add Drop Multiplexers (shortly ADM) used in the network (related to the cost of the nodes). Here, we first survey the main theoretical results obtained for different grooming factors on various topologies: complexity, (in)approximability, optimal constructions, approximation algorithms, heuristics, etc. Then, we give an ILP formulation for multilayer traffic grooming and present some experimental results.}},
    keywords = {WDM Networks, Grooming, ADM},
    language = {English},
    affiliation = {Department of Telecommunications and Media Informatics - BME-TMIT , MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S , Dipartimento di Informatica [Italy] - DI , Applied Mathematics IV Department , Tel Hai Academic College , Department of Computer Science [Haifa]},
    booktitle = {{Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless, and Ad Hoc Networks.}},
    publisher = {Springer},
    pages = {63-94},
    volume = {XXVII},
    editor = {Arie Koster and Xavier Mu{\\~n}oz },
    series = {EATCS Texts in Theoretical Computer Science },
    isbn = {978-3-642-02249-4 },
    doi = {10.1007/978-3-642-02250-0 },
    year = {2010},
    month = Jan,
}

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inbook"><head>Scientific Book chapters</head>
<biblStruct type="inbook" xml:id="inria-00530964"><analytic>
<author><persName><forename>Tibor</forename><surname>Cinkler</surname></persName>
<affiliation>
<orgName type="laboratory">BME-TMIT</orgName>
<orgName type="team">Department of Telecommunications and Media Informatics</orgName>
<country>HU</country>
<orgName type="institution">Budapest University of Technology and Economics</orgName>
</affiliation>
</author>
<author><persName><forename>David</forename><surname>Coudert</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis / Laboratoire I3S</orgName>
<orgName type="team">MASCOTTE</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Nice Sophia Antipolis [UNS]</orgName>
<orgName type="institution">CNRS : UMR7271</orgName>
</affiliation>
</author>
<author><persName><forename>Michele</forename><surname>Flammini</surname></persName>
<affiliation>
<orgName type="laboratory">DI</orgName>
<orgName type="team">Dipartimento di Informatica [Italy]</orgName>
<country>IT</country>
<orgName type="institution">Università degli Studi dell'Aquila</orgName>
</affiliation>
</author>
<author><persName><forename>Gianpiero</forename><surname>Monaco</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis / Laboratoire I3S</orgName>
<orgName type="team">MASCOTTE</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Nice Sophia Antipolis [UNS]</orgName>
<orgName type="institution">CNRS : UMR7271</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">DI</orgName>
<orgName type="team">Dipartimento di Informatica [Italy]</orgName>
<country>IT</country>
<orgName type="institution">Università degli Studi dell'Aquila</orgName>
</affiliation>
</author>
<author><persName><forename>Luca</forename><surname>Moscardelli</surname></persName>
<affiliation>
<orgName type="laboratory">DI</orgName>
<orgName type="team">Dipartimento di Informatica [Italy]</orgName>
<country>IT</country>
<orgName type="institution">Università degli Studi dell'Aquila</orgName>
</affiliation>
</author>
<author><persName><forename>Xavier</forename><surname>Muñoz</surname></persName>
<affiliation>
<orgName type="team">Applied Mathematics IV Department</orgName>
<country>ES</country>
<orgName type="institution">Universitat Politécnica de Catalunya</orgName>
</affiliation>
</author>
<author><persName><forename>Ignasi</forename><surname>Sau</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis / Laboratoire I3S</orgName>
<orgName type="team">MASCOTTE</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Nice Sophia Antipolis [UNS]</orgName>
<orgName type="institution">CNRS : UMR7271</orgName>
</affiliation>
<affiliation>
<orgName type="team">Applied Mathematics IV Department</orgName>
<country>ES</country>
<orgName type="institution">Universitat Politécnica de Catalunya</orgName>
</affiliation>
</author>
<author><persName><forename>Mordechai</forename><surname>Shalom</surname></persName>
<affiliation>
<orgName type="team">Tel Hai Academic College</orgName>
<country>IL</country>
<orgName type="institution">Tel Hai Academic College</orgName>
</affiliation>
</author>
<author><persName><forename>Shmuel</forename><surname>Zaks</surname></persName>
<affiliation>
<orgName type="team">Department of Computer Science [Haifa]</orgName>
<country>IL</country>
<orgName type="institution">University of Haifa</orgName>
</affiliation>
</author>
<title type="main" level="a">Traffic Grooming: Combinatorial Results and Practical Resolutions.</title></analytic><monogr><title level="m" type="main">Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless, and Ad Hoc Networks.</title><imprint><publisher>Springer</publisher><biblScope type="publicationDate">2010-01-01</biblScope><biblScope type="vol">XXVII</biblScope><biblScope type="pp">63-94</biblScope></imprint></monogr><idno type="doi">10.1007/978-3-642-02250-0</idno><idno type="HALid">http://hal.inria.fr/inria-00530964</idno></biblStruct>
</listBibl>
</listBibl>