Multicast routing with bandwidth requirement in the case of incomplete information as a Steiner tree problem

Patrice Leguesdron; János Levendovszky; Miklós Molnár; Csaba Végsö

inria-00072245, version 1

Multicast routing with bandwidth requirement in the case of incomplete information as a Steiner tree problem

Patrice Leguesdron ¹, János Levendovszky ², Miklós Molnár ()^a^, 3, Csaba Végsö ²

N° RR-4343 (2001)

Résumé : This paper is concerned with developing novel algorithms for multicast routing in packet switched communication networks. First, multicast routing with bandwidth requirement in the case of incomplete information is reduced to a deterministic Steiner tree problem. Then taboo search algorithms are used to provide high quality, sub-optimal solutions for multicast routing in polynomial time.

a – Institut National des Sciences Appliquées de Rennes
1 : Institut de Recherche Mathématique de Rennes (IRMAR)
CNRS : UMR6625 – Université de Rennes 1 – École normale supérieure de Cachan - ENS Cachan – Institut National des Sciences Appliquées (INSA) : - RENNES – Université de Rennes II - Haute Bretagne
2 : Budapest University of Technology and Economics (BME)
Budapest University of Technology and Economics
3 : ARMOR (INRIA - IRISA)
CNRS : UMR6074 – INRIA – Institut National des Sciences Appliquées (INSA) - Rennes – Ecole Nationale Supérieure des Télécommunications de Bretagne – Université de Rennes 1

inria-00072245, version 1
http://hal.inria.fr/inria-00072245
oai:hal.inria.fr:inria-00072245
Contributeur : Rapport De Recherche Inria <>
Soumis le : Mardi 23 Mai 2006, 20:12:47
Dernière modification le : Mardi 23 Mars 2010, 11:19:42

Voir la fiche détaillée

Documents associés

PS :

PDF :

Exporter

Bibtex EndNote TEI RefWorks

<?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="report"><head>Rapports</head>
<biblStruct type="report" xml:id="inria-00072245"><monogr>
<author><persName><forename>Patrice</forename><surname>Leguesdron</surname></persName>
<affiliation>
<orgName type="laboratory">IRMAR</orgName>
<orgName type="team">Institut de Recherche Mathématique de Rennes</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR6625</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
<orgName type="institution">École normale supérieure de Cachan - ENS Cachan</orgName>
<orgName type="institution">Institut National des Sciences Appliquées (INSA) : - RENNES</orgName>
<orgName type="institution">Université de Rennes II - Haute Bretagne</orgName>
</affiliation>
</author>
<author><persName><forename>János</forename><surname>Levendovszky</surname></persName>
<affiliation>
<orgName type="laboratory">BME</orgName>
<orgName type="team">Budapest University of Technology and Economics</orgName>
<country>HU</country>
<orgName type="institution">Budapest University of Technology and Economics</orgName>
</affiliation>
</author>
<author><persName><forename>Miklós</forename><surname>Molnár</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA - IRISA</orgName>
<orgName type="team">ARMOR</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR6074</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Institut National des Sciences Appliquées (INSA) - Rennes</orgName>
<orgName type="institution">Ecole Nationale Supérieure des Télécommunications de Bretagne</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
</affiliation>
</author>
<author><persName><forename>Csaba</forename><surname>Végsö</surname></persName>
<affiliation>
<orgName type="laboratory">BME</orgName>
<orgName type="team">Budapest University of Technology and Economics</orgName>
<country>HU</country>
<orgName type="institution">Budapest University of Technology and Economics</orgName>
</affiliation>
</author>
<title type="main" level="m">Multicast routing with bandwidth requirement in the case of incomplete information as a Steiner tree problem</title><title type="main" level="m">Multicast routing with bandwidth requirement in the case of incomplete information as a Steiner tree problem</title><imprint><biblScope type="publicationDate">2001-00-00</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00072245</idno><idno type="HALFile">http://hal.inria.fr/inria-00072245/PDF/RR-4343.pdf</idno></biblStruct>
</listBibl>
</listBibl>