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 28 Novembre 2000

Algorithmique des reseaux

par Fabrice Guillemin (France-Telecom R et D, Lannion)

L'émergence depuis le debut des années 1980 des réseaux de télécommunications haut débit fondés sur le mode paquet (réseaux ATM et IP) a donné naissance au développement de nouveaux outils d'évaluation de performances afin d'appréhender l'efficacité de tel ou tel mécanisme d'écoulement de trafic, notamment en rapport avec le problème du multiplexage statistique. Alors que la théorie naturelle sous-jacente à ces outils est celle des processus stochastiques et du calcul des probabilités (essentiellement en relation avec la théorie des files d'attente), la reformulation de certains problèmes en termes d'analyse combinatoire permettent non seulement de simplifier le cadre de calcul mais également d'aboutir à des résultats nouveaux. Pour illustrer ce propos, on considère, sous certaines hypothèses simplificatrices (processus d'arrivée poissonnien de rafales de données distribuées exponentiellement), le multiplexage statistique en boucle ouverte de connexions de données sur un lien ATM. Le système est caractérisé par un certain nombre de paramètres de performance tels que la durée de congestion et le volume d'information perdue pendant une congestion. Le système peut \^etre analysé en utilisant son caractère markovien, mais en mettant en évidence une relation entre les processus de naissance et mort et la théorie des chemins latticiels, il est possible d'utiliser tous les résultats combinatoires relatifs aux chemins latticiels afin d'obtenir les transformées de Laplace des paramètres de performance en termes de fractions continues. Pour conclure, d'autres problèmes où interviennent des aspects combinatoires sont présentés, en particulier en ce qui concerne la formule d'Erlang multidébit pour laquelle un mode opératoire de calcul (en fait une relation de récurrence) est obtenu de manière immédiate à partir d'un lemme combinatoire de Spitzer.

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