The Data Broadcast Problem with Preemption

The data-broadcast problem consists in finding an infinite schedule to broadcast a given set of messages so as to minimize the average response time to clients requesting messages, and the cost of the broadcast. This is an efficient means of disseminating data to clients, designed for environments, such as satellites, cable~TV, mobile phones, where there is a much larger capacity from the information source to the clients than in the reverse direction. Previous work concentrated on scheduling indivisible messages. Here, we studied a generalization of the model where the messages can be preempted. We show that this problem is NP-hard, even in the simple setting where the broadcast costs are zero, and give some practical 2-approximation algorithms for broadcasting messages. We also show that preemption can improve the quality of the broadcast by an arbitrary factor.La diffusion de données est une réponse apportée au problème de la surcharge des réseaux et serveurs d'information (de type info-trafic, info-bourse, info-sport), où le nombre de clients est très élevés et la plus part d'entre eux demande majoritairement le même petit nombre de messages; et plus généralement adaptées aux réseaux asymétriques où la bande passante des serveurs vers les clients est bien plus grande que des clients vers les serveurs (les réseaux satellites, téléphones mobiles/base,...). L'idée est de réserver des canaux (typiquement hertzien) pour la diffusion de ce petit nombre de messages qui seront diffusés indépendamment des requêtes effectives: un client intéressé par un de ces messages, se connecte sur ces canaux et attend que le message demandé soit diffusé. Le problème de la diffusion de données [Data broadcast problem] consiste à trouver un ordonnancement qui diffuse les messages, en minimisant l'attente moyenne des utilisateurs (défini par un profil-utilisateur: les probabilités de demande pour chaque message), et le coût de la diffusion des messages. Alors que les travaux précédents étudient l'ordonnancement de messages indivisibles, nous étudions ici une généralisation du modèle au cas où la diffusion des messages peut être interrompue. Nous démontrons que le problème est NP-dur, même quand les coûts de diffusion sont nuls, et proposons un algorithme qui génère un algorithme de coût inférieur au double de l'optimal. Nous montrons aussi que l'ajout de préemption permet d'améliorer d'un facteur arbitraire la qualité d'un ordonnancement de messages de temps de transmission non-uniforme