Schabanel
Le Jeudi 18 Mai 2000 à 14h30
au LRI, salle 101
ENS Lyon et LRI
Un petit tour en dissémination de données
Résumé/Abstract :
La dissémination de données est une réponse
apportée à la surcharge des réseaux et serveurs
d'information. Le fait est que la plupart des clients demande la plupart
du temps les mêmes informations. Aussi, afin d'éviter de saturer
à la fois le serveur et le réseau avec la diffusion des pages
les plus populaires, l'approche de la dissémination propose de
réserver un certain nombre de canaux d'émission à la
diffusion systématique des informations les plus populaires. Ces canaux
(typiquement Hertzien, TV par câble,...) sont accessibles en
simultané par tous les clients. Le problème est alors
d'ordonnancer la diffusion des différentes pages d'information. Un
client, intéressé par l'une de ces pages, n'émet pas de
requête mais se connecte sur ces canaux réservés et attend
que l'information qui l'intéresse soit diffusée. Il s'agit donc
de trouver un ordonnancement qui minimise l'attente moyenne des clients.
Ce problème est un problème de minimisation quadratique, NP-dur
en général, qui modélise également d'autres
problèmes d'ordonnancement tels la planification de maintenances de
machines ou le réapprovisionnement de stocks. Dans cet exposé
général, nous verrons quelles sont les méthodes qui ont
été proposées, et plus particulièrement les
avancées récentes (entre autres : un schéma
d'approximation et l'étude du cas des messages de longueurs
non-uniformes).