Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 9 Mars 2004

Logique linéaire : une introduction

par Patrick Baillot (Université de Paris XIII)

L'explosion des nouveaux services multimédia (texte, image, son) sur les réseaux nécessite des débits tels qu'il ne suffit pas d'augmenter la "bande passante". Il est nécessaire d'allouer au mieux les ressources existantes en fonction de paramètres comme la fluctuation de trafic à différents instants, les contraintes de qualité de service, ...

Dans cet exposé on s'intéresse à la réservation dynamique de connexions dans un contexte d'administration de réseaux ATM (Asynchronous Transfert Mode). Lors d'une nouvelle demande, on cherche à lui attribuer une route avec garanties de ressources et de qualité de service (QdS). Pour diminuer le risque de rejet d'une demande, on autorise le REROUTAGE des connexions réservées, tout en maintenant leurs calendriers de réservation et leurs QdS. L'acceptation ou le rejet d'une demande doit se faire dans un temps borné de l'ordre de la minute (contexte dit anytime).

Pour résoudre ce problème, nous avons choisi une approche de type réparation, basée sur le reroutage d'un ensemble de connexions déjà établies dans le réseau.

Dans un premier temps, nous recherchons à attribuer un chemin à une demande.

En cas d'échec, on autorise le reroutage. Le reroutage à été modélisé sous forme d'un CSP Valués (VCSP), puis résolu par VNS/LDS+CP, une méthode hybride dédiée à la résolution en contextes anytime des vcsp.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr