"Poussez si vous ne pouvez pas tirer - comment approcher un ordonnancement optimal"

Résumé :

Un des objectifs importants des réseaux de télécommunications actuels est de founir des services à la demande. La solution dite <<unicast>> (pull systems) qui dédie un canal de communication par requête est irréalisable même en tenant compte de la capacité toujours croissante des réseaux. Aussi, afin de satisfaire la demande croissante de ce type de services, la solution à terme consiste à effectuer une multi-diffusion (push systems) des services les plus demandés.

Deux applications phares qui bénéficieraient des systèmes de type push sont :

(i) les sytèmes de média à la demande dans lesquels les clients souhaitent voir un média populaire (film, journal télévisé)
(ii) air caching : dans ce cas les clients accèdent à une information très demandée (état du trafic routier, météo, cours de la bourse) diffusée périodiquement depuis un satellite.

Nous décrirons tout d'abord le problème dit de Window Scheduling qui peut s'appliquer à ces deux problèmes. Nous donnerons des algorithmes  de résolution approchée (dans les cas asymptotique et pratique). Enfin nous discuterons d'autres problèmes liés à ces deux applications, dont certains sont résolus et d'autres encore ouverts à ce jour.
 

Abstract:

An important goal of today communication networks is to provide media and information on demand. The unicast solution (pull systems) that dedicates a communication channel per request is implausible even with the ever growing available network bandwidth. Thus, multicasting popular media and information (push systems) to groups of clients seems to be the ultimate solution to the ever growing demand for media and information.

Two prominent applications that would benefit from push systems are:

(i) Media-on-Demand in which clients wish to view a popular media (e.g., a movie or a news clip)
(ii) Air-Caching in which clients retrieve popular information (e.g, traffic and weather reports, stock quotes) from a satellite that broadcasts such information periodically.

We first describe the Windows Scheduling Problem that could be applied to both applications. We show asymptotic and practical approximation solutions to this problem. Next, we discuss other problems related to both applications some with solution and some are still open.
 

Related papers:

Windows Scheduling Problems for Broadcast Systems (work by A. Bar-Noy and R. E. Ladner)