Ecole Nationale Supérieure des Télécommunications
Département Informatique et Réseaux

Projet POLKA






Description générale : English version

Les applications multimédia présentent des contraintes de qualité de service (QoS) temporelles. La prise en compte de ces contraintes est aujourd'hui faite par le concepteur d'applications qui doit les traduire en directives d'ordonnancement. Pour cela, une excellente connaissance de l'ordonnanceur du système d'exploitation sous-jacent est nécessaire.
Cette tâche est lourde et complexe. Elle présente de plus l'inconvénient de produire des applications qui ne sont pas portables, puisque l'ordonnancement change d'une configuration à une autre.
Le contexte de cette collaboration est le projet ARCADE du CNET. L'objectif de ce projet est de développer une méthodologie et un ensemble d'outils intégrés pour le développement d'applications réparties.
L'objectif de notre contribution est de proposer une approche dans laquelle les contraintes de QoS sont automatiquement traduites en directives d'ordonnancement. Les solutions envisagées mettent en jeu un ordonnanceur applicatif qui dialogue avec l'ordonnanceur du système d'exploitation. Un démonstrateur de l'approche a été développé (en langage JAVA).

General introduction :

When developing multi-media applications, software engineers have to make sure their system meets tight temporal Quality of Service (QoS) constraints.
Today, this daunting task rests entirely on the programmer's shoulders. He must have full knowledge of the underlying operating system scheduling support and plan the delicate timings of the application accordingly. This is not only tedious and error-prone, it is also highly non-portable as these scheduling services greatly differ from one operating system to the next.
This work is part of the ongoing ARCADE research project undertaken at the CNET (France Telecom research center). The goal of the ARCADE project is to come up with a paradigm for the development of distributed multi-media applications.
In this context, our research objective is to describe a multi-media development framework in which high-level QoS constraints are automatically translated into low-level scheduling directives for a user-level run-time monitor. This user level scheduler interacts with the underlying operating system to ensure proper accounting of the application timing constraints. A demontrator of the approach has been developped (in Java).

PUBLICATIONS

- Support of multimedia application by a CORBA and ATM based distributed system. Basma Driss. ENST Master's thesis. January 2000 (Postscript file).

Abstract :
The ASTRE group of the ENST has developed a specification technique and a middleware platfore named POLKA to support multimedia applications. It automatically schedules a distributed multimedia application in order to meet the application QoS constraints provided enough resources are available. POLKA extends a CORBA platform that runs over the TCP/IP/Ethernet stack of protocols. The objective of this work is to port POLKA to ATM in order to guarantee the availability of the required network resources during the application lifetime. The first step consists of implementing AAL5/ATM in the ORB using the Linux ATM API. The support of ATM is based on associating a transport protocol and a set of QoS parameters to a binding factory. POLKA focuses on the temporal constraints of the multimedia applications. It translates the user QoS constraints expressed in form of QoS equations into task deadlines and release times. It schedules the application tasks in order to meet the required QoS constraints. To specify the ATM network requirements, it is necessary to translate the QoS constraints at the application level into parameters well understood at the network level. A QoS mapping algorithm based on arithmetical rules is proposed. A network QoS manager is designed in order to provide QoS mapping and admission control. A QoS-based API allows the application to specify or change its QoS requirements. Some performance measurements are carried out on the extended POLKA platform in order to validate the mapping rules and show the gain by using ATM in POLKA.

- Spécification temporelle modulaire et support pour les applications multimédias réparties. Thèse de doctorat de l'Ecole Nationale Supérieure des Télécommunications. Paris. Décembre 1999. Frank Singhoff. ( Fichier postscript)

Résumé :
Par le passé, les applications informatiques manipulaient essentiellement des données textuelles ou graphiques non animées. Aujourd'hui, ces données, que l'on appelle parfois données ``discrètes'' sont mélangées à des données telles que le son ou les images animées. On parle alors d'applications multimédias (ou littéralement, applications mélangeant plusieurs médias différents). Dans ces nouveaux systèmes, les médias tels que le son ou l'image animé sont très souvent désignés sous le terme de flots de données ``continues''. En effet, contrairement aux données discrètes dont les éléments de données sont temporellement indépendants, les éléments de flots de données continues sont liés par des contraintes temporelles. On parle alors de contraintes de qualité de service temporelles (ex:délai entre l'affichage de deux images successives, synchronisation voix-lèvres, synchronisation de l'affichage d'objets animés, etc). Ainsi, un flot de données audio est constitué d'une suite d'échantillons qui doivent être délivrés au périphérique audio régulièrement. Il existe donc une contrainte temporelle entre un échantillon donné, son prédécesseur et son successeur. Si ce type de contrainte n'est pas respecté durant la présentation du flot audio, il risque de ne pas être suffisamment audible et ainsi de perdre une part importante de son utilité. Cette thèse traite du support des applications multimédias réparties qui mettent en oeuvre des flots de données continues tels que l'audio et la vidéo. Nous nous intéressons tout particulièrement à leur support dans des environnements banalisés non spécifiquement concus pour de telles applications (ex:micro-ordinateur PC muni d'un système d'exploitation Windows ou Linux). Par ailleurs, cette thèse cible plus particulièrement les applications multimédias dont le comportement temporel est partiellement prédictible ou encore celles dont les besoins en ressources sont difficiles à estimer. Dans un premier temps, nous proposons l'utilisation d'un modèle orienté flots de données dans lequel nous spécifions les flots de données multimédias ainsi que les éléments importants du système. Ce modèle permet la spécification des contraintes temporelles associées aux flots de données et indirectement de modéliser des contraintes de débits. Les contraintes visées sont des contraintes déterministes. Par la suite, nous décrivons des algorithmes qui exploitent ce modèle. Ces algorithmes offrent principalement des services pour ordonnancer les taches du système conformément aux contraintes temporelles spécifiées gràce au modèle. Ils offrent l'opportunité de réaliser automatiquement la traduction des contraintes de QoS en directives d'ordonnancement. Le modèle ainsi que les algorithmes sont validées par une plate-forme (la plate-forme POLKA) et plusieurs applications multimédias. Nous montrons les impacts de ces propositions sur la gestion des ressources ainsi que les capacités de notre plate-forme à s'adapter à un changement des contraintes temporelles. Enfin, nous terminons par une ouverture sur l'intégration des contraintes probabilistes.

- Modélisation et support d'applications multimédias réparties. Revue Calculateurs parallèles, Réseaux et Systèmes répartis. Septembre 1999. 11(2):161-191. Isabelle Demeure, Laurent Leboucher, Nicolas Rivierre, Frank Singhoff.

Résumé :
Article étendu de l'article publié dans la conférence CFSE'1.

- Modèle et plate-forme pour le support d'applications multimédias réparties. Conférence Francaise sur les systèmes d'exploitation (CFSE'1), pages 97-108, Rennes, 8-11 Juin 1999. Isabelle Demeure, Laurent Leboucher, Nicolas Rivierre, Frank Singhoff. ( Fichier postscript, Fichier html)

Résumé :
Cet article décrit une technique de spécification d'applications multimédias réparties et une plate-forme d'exécution pour ces applications. Les contraintes temporelles de l'application sont spécifiées indépendamment de l'application et du graphe de flots de données qui décrit le système multimédia. La plate-forme d'exécution est basée sur CORBA. Elle ordonnance automatiquement les applications de manière à respecter les contraintes temporelles spécifiées, dans la limite des ressources disponibles. Les concepts introduits sont illustrés par un exemple. Une évaluation de performances est fournie.

- Spécification et ordonnancement dynamique d'applications multimédias : l'environnement POLKA. Real time systems (RTS'98), pages 101-115, Paris la Défense Janvier 1998. Isabelle Demeure, Frank Singhoff. ( Fichier postscript, Fichier html)

Résumé :
Cet article traite de la spécification et du support des applications multimédias, et plus particulièrement de celles dont les besoins en ressources sont difficiles à estimer et dont le comportement n'est pas entièrement prédictible. Nous définissons un modèle qui permet de spécifier une application multimédia en termes d'objets, de flux multimédias et de contraintes temporelles sur ces flux. Un algorithme d'ordonnancement qui prend dynamiquement en compte ces contraintes temporelles est décrit informellement. Une mise en oeuvre de cet algorithme dans un environnement CORBA et un exemple d'application sont ensuite détaillés.

- Environnement d'éxécution pour les applications réparties sous contraintes temporelles : une solution CORBA-RTP. 10 eme Rencontres Francophones du Parallélisme (RENPAR'10). Strasbourg 9,12 Juin 1998. pages 53-57. Demeure isabelle, Singhoff frank. ( Fichier postscript, Fichier html)

Résumé :
Dans cet article, nous présentons une architecture orientée objet basée sur CORBA, qui permet l'exécution d'applications réparties possédant des contraintes temporelles. Elle exploite une technique qui, à partir d'une spécification de qualité de service, déduit automatiquement les échéances des taches de l'application. Les protocoles RTP et RTCP sont utilisés pour la génération et le partage des informations d'ordonnancement.


- Automatic Scheduling of a Dynamic Multimedia Applications with Polka : a Case Study Fourth IEEE Real-Time Technology and Applications Symposium (RTAS'98), WIP, Denver, Colorado, USA June 3-5, 1998, pages 15-19, Demeure Isabelle, Horn Francois, Singhoff frank. ( Postscript file, html file)

Abstract :
POLKA is a system to dynamically and automatically schedule application that have temporal QoS constraints. This paper briefly describes the POLKA system and scheduling approach; it then introduces a multimedia application that is used as a case study to show the effectiveness of the approach. The performance measurements presented in the paper were performed on a CORBA based prototype of POLKA.

- Ordonnancement automatique d'applications présentant des contraintes de QoS temporelles. Thèse de Doctorat de l'Ecole Nationale Supérieure des Télécommunications. Septembre 1996. J. Farhat-Gissler.

Résumé :
Dans cette thèse, nous nous intéressons au support des applications présentant des contraintes temporelles de qualité de service (QoS). La prise en compte de ces contraintes est aujourd'hui faite manuellement par le concepteur d'applications qui doit les traduire en directives d'ordonnancement. Nous proposons une approche dans laquelle les contraintes de QoS temporelles sont automatiquement traduites en directives d'ordonnancement. Dans cette approche, nous suggérons au concepteur d'applications de programmer son application en spécifiant des contraintes temporelles (sous forme d'équations de QoS simples) entre des événements importants de son application. Ces contraintes temporelles sont alors traduites en directives d'ordonnancement. Les fils de contrôle (user-threads) de l'application sont découpés en brins auxquels sont associés les contraintes temporelles. Cette décomposition en brins guide l'ordonnancement des fils de contrôle applicatifs associés. Le système support met en oeuvre un mécanisme d'ordonnancement coopératif basé sur un dialogue entre l'ordonnanceur du système d'exploitation et l'ordonnanceur applicatif. Les deux ordonnanceurs appliquent une politique d'ordonnancement EDF (Earliest Deadline First). Ils ordonnancent au mieux (best-effort) en tenant compte des contraintes imposées. Dû à cet environnement de meilleur effort, qui ne procure aucune garantie, les applications doivent être capable de s'adapter aux variations de la charge dans le système. Pour cette raison, l'ordonnanceur applicatif met en oeuvre une politique de gestion des variations de la charge, basée sur les spécifications du développeur d'applications. Un protocole de partage des ressources est également proposé pour permettre aux différents fils de contrôle applicatifs de partager des ressources sans risque d'interblocage (deadlocks). Des mesures du coût additionnel engendré par l'ordonnancement automatique sont effectuées grâce à un démonstrateur que nous avons développé. Les mesures sont encourageantes. Elles sont, cependant, très dépendantes de la structure du graphe de dépendances généré à partir des portions de code de l'application.


- A Scheduling Framework for the Automatic Support of Temporal QoS Constraints" in proceedings of the Fourth International Workshop on Quality of Service Paris, 6 - 8 March, 1996, I. DEMEURE, J. FARHAT-GISSLER, F. GASPERONI. (Postscript file)

Abstract :
This work focuses on the support of applications that must meet temporal QoS constraints. We propose an approach to automatically derive scheduling information from temporal QoS equations expressed at a high level. The application threads are partitioned into finer grain (or elementary) threads to which QoS constraints are applied. The elementary thread decomposition is used to guide the scheduling of the associated user threads. The scheduling framework involves best effort cooperative scheduling based on the Earliest Deadline First (EDF) policy.


- Automatic Scheduling of Applications with Temporal QoS Constraints: A Case Study, in proceedings of Euromicro'96, Prague, September 1996. J. FARHAT-GISSLER, I. DEMEURE.


- Ordonnancement local automatique d'applications sous contraintes de QoS temporelles" dans JDIR'96, Paris, Septembre 1996. J. FARHAT-GISSLER, I. DEMEURE (Fichier postscript)

Résumé :
Dans cet article nous nous intéressons au support des applications présentant des contraintes de QoS temporelles. Nous proposons une approche dans laquelle les contraintes de QoS temporelles sont automatiquement traduites en directives d'ordonnancement. Les fils de controle de l'application sont déecoupées en brins auxquels on associe des éechéances dérivées des contraintes temporelles spécifiées. Le système support met en oeuvre un méecanisme d'ordonnancement coopératif basé sur un dialogue entre l'ordonnanceur du système d'exploitation et l'ordonnanceur applicatif. Les deux ordonnanceurs appliquent une politique d'ordonnancement EDF. Ils ordonnancent au mieux en tenant compte des contraintes imposées.


- Automatic QoS Support for Distributed Multimedia Applications", in proceedings of ERSADS 95, pp. 158--163, Alpes d'Huez, France, Avril 95. J. FARHAT, I. DEMEURE, F. GASPERONI.



Page maintenue par Isabelle Demeure (Isabelle.Demeure@inf.enst.fr)
Dernière mise à jour le 22/6/00