Les performances des algorithmes d'ordonnancement ont un impact direct sur les performances du système complet. Les algorithmes d'ordonnancement temps réel possèdent des bornes théoriques d'ordonnançabilité optimales mais cette optimalité est souvent atteinte au prix d'un nombre élevé d'événements d'ordonnancement à considérer (préemptions et migrations de tâches) et d'une complexité algorithmique importante. Notre opinion est qu'en exploitant plus efficacement les paramètres des tâches il est possible de rendre ces algorithmes plus efficaces et à coût maitrisé, et ce dans le but d'améliorer la Qualité de Service (QoS) des applications. Nous proposons dans un premier temps des algorithmes d'ordonnancement monoprocesseur qui augmentent la qualité de service d'applications hybrides c'est-à-dire qu'en situation de surcharge, les tâches à contraintes souples ont leur exécution maximisée et les échéances des tâches à contraintes strictes sont garanties. Le coût d'ordonnancement de ces algorithmes est aussi réduit (nombre de préemptions) par une meilleure exploitation des paramètres implicites et explicites des tâches. Cette réduction est bénéfique non seulement pour les performances du système mais elle agit aussi positivement sur la consommation d'énergie. Aussi nous proposons une technique associée à celle de DVFS (dynamic voltage and frequency scaling) afin de minimiser le nombre de changements de points de fonctionnement du fait qu'un changement de fréquence implique un temps d'inactivité du processeur et une consommation d'énergie. Les algorithmes d'ordonnancement multiprocesseur basés sur le modèle d'ordonnancement fluide (notion d'équité) atteignent des bornes d'ordonnançabilité optimales. Cependant cette équité n'est garantie qu'au prix d'hypothèses irréalistes en pratique du fait des nombres très élevés de préemptions et de migrations de tâches qu'ils induisent. Dans cette thèse un algorithme est proposé (ASEDZL) qui n'est pas basé sur le modèle d'ordonnancement fluide. Il permet non seulement de réduire les préemptions et les migrations de tâches mais aussi de relâcher les hypothèses imposées par ce modèle d'ordonnancement. Enfin, nous proposons d'utiliser ASEDZL dans une approche d'ordonnancement hiérarchique ce qui permet d'obtenir de meilleurs résultats que les techniques classiques.

Résumé : La thèse développe une contribution à la spécification, la modélisation et l'évaluation de mécanismes destinés à la fourniture de qualité de service dans les réseaux sans fil locaux et métropolitains. La première partie du travail concerne une modélisation en chaîne de Markov du protocole d'accès EDCA de IEEE 802.11e qui, par rapport aux modèles présents dans la littérature, ajoute des mécanismes du standard qui n'avaient pas été introduits (prise en compte explicite de la collision virtuelle) et corrige des erreurs de conception (prise en compte des périodes AIFS de la procédure de Backoff). Ce modèle a été rendu synthétique pour en faciliter l'usage (réductions réalisées à l'aide des règles de Beizer). Ce modèle a ensuite été utilisé pour définir un algorithme de contrôle d'admission hybride, intégrant dans son processus de décision un modèle analytique et des mesures de l'état du réseau. L'algorithme de contrôle d'admission ainsi développé a été en premier lieu validé puis comparé à d'autres algorithmes de contrôle d'admission par simulation sous ns-2. Notons aussi que nous avons proposé, une modification du comportement de EDCA face à une collision virtuelle assurant une meilleure équité aux catégories d'accès. Cette modification a été évaluée à l'aide du modèle. Une deuxième partie du travail consiste en la proposition pour WiMAX d'une architecture de gestion de bande passante pouvant fournir des garanties de qualité de service. Cette architecture se compose de trois parties interagissantes : 1- une gestion de la bande passante sous WiMAX assimilée à une classe de serveurs dite classe des serveurs latence-débit, 2- un mécanisme de requête-réponse de bande passante agrégée simplifiant la gestion de bande passante et la rendant plus flexible, 3- un protocole de contrôle d'admission associé à l'architecture et qui en garantit le bon fonctionnement. L'architecture ainsi conçue s'inscrit dans une prospective de réseaux hétérogènes sans fil (réseaux métropolitain WiMAX connectant entre eux et à Internet des réseaux locaux WiFi). C'est dans cette optique que s'inscrira la suite de notre travail. Elle consistera en la combinaison des mécanismes que nous proposons afin de fournir une solution complète de qualité de service pour des réseaux hétérogènes sans fil.

Les réseaux IEEE 802.11 sont, entre autres, très souvent utilisés pour se connecter à l'Internet car ils proposent une solution bon marché, facile à déployer et qui supporte la mobilité. Dans cette thèse nous considérons quatre différents aspects de la qualité de service (QoS) dans ces réseaux :<br />- Différentiation de service : Le protocole IEEE 802.11 actuel n'a aucun support de la QoS. Ainsi, tous les terminaux partagent équitablement le débit disponible. Nous proposons des mécanismes de différentiation de services au niveau MAC. Nous développons et simulons plusieurs mécanismes de différentiation pour IEEE 802.11.<br />- Environnements bruités : IEEE 802.11 utilise des fenêtres de contention pour résoudre l'accès multiple des terminaux au canal. Un terminal double la taille de sa fenêtre de contention à chaque perte de paquet.<br />Cette stratégie diminue les collisions au canal, mais augmente le surcoût des paquets, diminuant ainsi le débit. Cependant, les pertes peuvent également être dues à du bruit sur le canal. L'augmentation de la fenêtre de contention peut alors être très néfaste en termes de performance. Il convient d'augmenter la fenêtre de contention uniquement si la perte à été produite par une collision. Nous proposons une stratégie d'adaptation de la fenêtre de contention qui varie selon l'estimation de la cause de perte des paquets. <br />- Environnements congestionnés : Après chaque bonne transmission de paquet, IEEE 802.11 remet la taille de la fenêtre de contention à zéro. Cependant, dans un environnement congestionné la charge sur le canal varie lentement, et un terminal risque d'avoir le même taux de collisions et de retransmissions. Nous proposons un mécanisme basé sur une réduction de la taille de la fenêtre de contention plus lente, pouvant mieux éviter les collisions et les retransmissions. Ceci présente un gain considérable en terme de débits et de consommation d'énergie.<br />- Réseaux ad-hoc: Dans un réseau ad-hoc les paquets sont routés suivant des chemins multi-saut. Ainsi le routage est coopératif entre les différents nœuds, et le débit utile moyen disponible à chaque nœud dépend du nombre total des nœuds, des interférences et des collisions. Nous proposons un mécanisme de contrôle de débits aux sources, basé sur l'estimation des débits et des délais, pouvant optimiser les débits utiles ainsi que la consommation d'énergie.

La thèse se situe dans le domaine de la conception des architectures capables de garantir la QoS dans des réseaux multi-domaines et multi-technologies. Elle porte plus particulièrement sur les problèmes liés à l'acquisition de topologie pour alimenter les fonctions de contrôle d'admission d'appel. En effet, il faut que l'entité responsable de la fonction de CAC (Call Admission Control) détienne une cartographie réelle et synchrone du domaine qu'elle gère. Si dans certains cas d'utilisation, la topologie peut être renseignée et gérée manuellement, il est impossible d'accomplir une telle tâche sur de grandes topologies. Différentes solutions existent. Bien que ces techniques soient efficaces dans certains cas d'utilisation, elles sont en fait soit incomplètes soit inadaptées à nos besoins. Pour répondre à cette problématique nous avons d'abord implémenté notre propre modèle d'acquisition intégrée des données topologiques des couches 2 et 3. Il s'agit du protocole STAMP (Simple Topology Annoucement and Management Protocol), un protocole de signalisation permettant la diffusion des informations de topologie et de qualité de service dans un réseau quelque soit sa taille. Pour généraliser et optimiser notre modèle, nous avons ensuite développé et proposé des nouvelles méthodes d'agrégation des topologies réseau, en particulier appliquées aux topologies précédemment obtenues, afin de réduire, en conservant les paramètres de QoS, la volumétrie de la base de données et améliorer les performances de la CAC.

La problématique de la qualité de service dans les réseaux locaux sans fils IEEE 802.11 demeure l'un des défis délicats à surmonter par la communauté scientifique. L'étude et l'évaluation des approches apportés pour le support de QoS dans ce type de réseaux que ce soit par des simulations, des modèles analytiques ou des mesures réelles montre que ces approches sont toujours insuffisantes pour apporter des vraies garanties de qualité de services aux utilisateurs sans fils. Suite à des travaux effectués au CRAN qui ont porté sur l'équilibrage des charges dans les réseaux Ethernet industriels nous avons opté pour une méthode d'équilibrage de charges dans le contexte des réseaux hotspots 802.11. L'objectif de cette approche étant d'équilibrer les charges des points d'accès pour satisfaire aux besoins en termes de qualité de service de l'ensemble des applications sans fils. Ces besoins sont exprimés en termes de disponibilité, de délais, de bande passante...Nous avons alors définis un algorithme d'équilibrage de charges pouvant établir dynamiquement des associations optimales entre les utilisateurs présents dans un hotspot et les points d'accès en service. Un protocole d'échanges entre les stations sans fils et les points d'accès et entre ces derniers et le serveur d'équilibrage de charges a été établi. Le fonctionnement de ce protocole a été vérifié et simulé en utilisant les outils SDL et MSC. Pour l'évaluation de la performance de l'approche d'équilibrage par rapport à la méthode d'accès de base du protocole, un ensemble de simulations ont été effectués. Ces simulations effectuées sur OPNET montrent que cette approche permet d'améliorer un ensemble de paramètres de qualité de service perçue par les utilisateurs d'un réseau Hotspot.

Depuis quelques années, les évolutions technologiques conjointes de l'informatique et des télécommunications ont conduit à une mutation de la perspective des communications et des réseaux. Une des conséquences de ces progrès est la convergence vers une infrastructure unique de transfert de données. Porté par son développement continu, l'Internet (IP) se révèle comme la solution pour l'interconnexion des différentes technologies hétérogènes, petite ou grande distance, fixe ou mobiles, l'infrastructure globale pour toute communication. L'Internet est devenu le support de nombreux nouveaux types d'applications dynamiques, multimédias, temps réels, distribuées, potentiellement multi utilisateurs, mobiles, comme la voix sur IP (VoIP), la vidéo à la demande (VoD), la visioconférence, les jeux interactifs, la simulation distribuée etc. De ce contexte résulte la problématique générale de nos travaux qui est de définir et de mettre en Suvre des nouveaux mécanismes, protocoles et architectures pour répondre aux besoins des applications émergentes. Nos contributions s'inscrivent dans ce thème de la maîtrise de la garantie de la Qualité de Service (QoS) de bout en bout dans un environnement Internet hétérogène à plusieurs niveaux : multi domaine, multi technologie et multi service. Nous adressons le besoin des nouvelles architectures en signalisation inter domaine couplée au provisionnement et au contrôle d'admission pour répondre aux besoins du trafic et des services actuels. Dans ce cadre, nous avons participé à la conception, l'implémentation, le déploiement et la validation de l'architecture du projet européen IST EuQoS (" End-to-end Quality of Service support over heterogeneous networks ").

Ce manuscrit présente une méthode de contrôle de qualité de service à grain fin d'applications multimédia. Celle-ci permet le contrôle d'applications dont les actions sont paramétrées par des niveaux de qualité et dont les durées d'exécution ne sont pas connues. Le contrôle consiste en la construction d'un ordonnancement et le choix des niveaux de qualité respectant des propriétés de sûreté et d'optimalité. C'est-à-dire que l'on cherche à maximiser l'utilisation du budget de temps sans pour autant le dépasser tout en ayant un choix de qualité régulier. Le contrôleur utilise une politique de gestion de qualité permettant de choisir pour chaque action l'ordonnancement et le niveau de qualité respectant les contraintes de qualité de service. Nous étendons et améliorons les résultats précédents dans deux directions. La première propose une approche symbolique de la politique de gestion de qualité. Celle-ci utilise un diagramme de vitesses qui est une représentation graphique du comportement de l'application contrôlée. À partir de cette représentation, nous avons proposé une technique de contrôle permettant de relâcher le nombre d'appels au contrôleur tout en respectant les propriétés de sûreté et d'optimalité. Nous avons ensuite proposé une approche stochastique du problème basée sur des fonctions de distribution de probabilités pour les durées d'exécution des actions. Notre méthode donne la possibilité à l'utilisateur de fixer la criticité des contraintes temps-réel. Elle permet aussi de calculer à priori le taux attendu de dépassement des échéances. Ces résultats théoriques ont été appuyés par des expériences réalisées sur un encodeur vidéo s'exécutant sur machine nue.

Les travaux présentés dans cette thèse ont pour but d'améliorer la couche transport de l'architecture réseau de l'OSI. La couche transport est de nos jour dominée par l'utilisation de TCP et son contrôle de congestion. Récemment de nouveaux mécanismes de contrôle de congestion ont été proposés. Parmi eux TCP Friendly Rate Control (TFRC) semble être le plus abouti. Cependant, tout comme TCP, ce mécanisme ne prend pas en compte ni les évolutions du réseau ni les nouveaux besoins des applications. La première contribution de cette thèse consiste en une spécialisation de TFRC afin d'obtenir un protocole de transport avisé de la Qualité de Service (QdS) spécialement défini pour des réseaux à QdS offrant une garantie de bande passante. Ce protocole combine un mécanisme de contrôle de congestion orienté QdS qui prend en compte la réservation de bande passante au niveau réseau, avec un service de fiabilité totale afin de proposer un service similaire à TCP. Le résultat de cette composition constitue le premier protocole de transport adapté à des réseau à garantie de bande passante. En même temps que cette expansion de service au niveau réseau, de nouvelles technologies ont été proposées et déployées au niveau physique. Ces nouvelles technologies sont caractérisées par leur affranchissement de support filaire et la mobilité des systèmes terminaux. De plus, elles sont généralement déployées sur des entités où la puissance de calcul et la disponibilité mémoire sont inférieures à celles des ordinateurs personnels. La deuxième contribution de cette thèse est la proposition d'une adaptation de TFRC à ces entités via la proposition d'une version allégée du récepteur. Cette version a été implémentée, évaluée quantitativement et ses nombreux avantages et contributions ont été démontrés par rapport à TFRC. Enfin, nous proposons une optimisation des implémentations actuelles de TFRC. Cette optimisation propose tout d'abord un nouvel algorithme pour l'initialisation du récepteur basé s ur l'utilisation de l'algorithme de Newton. Nous proposons aussi l'introduction d'un outil nous permettant d'étudier plus en détails la manière dont est calculé le taux de perte du côté récepteur.

Les travaux présentés dans cette thèse concernent la qualité de service dans les réseaux à commutation de paquets de grande dimension et plus spécifiquement la garantie de débit pour les flots TCP. L'architecture à différenciation de services, définie par l'IETF, dite DiffServ s'articule autour de trois services : le service garanti, le service assuré et le service par défaut dit "au mieux". Le service assuré a été élaboré pour servir les flots à caractère élastique comme les flots TCP. Cependant, des problèmes subsistent en ce qui concerne cette garantie de débit pour ce type de flots dans ce service. Ces dernières années, un effort important a été fait pour améliorer les mécanismes d'ordonnancement, de classification et de rejet au sein des routeurs afin qu'ils répondent au mieux à la spécification du service assuré. Malheureusement, leurs choix de conception et la complexité de leur mise en oeuvre est très souvent un frein à leur déploiement dans un Internet réel. Dans cette thèse, nous proposons une solution originale de conditionnement des flots TCP permettant de garantir un débit à la fois pour des flots individuels et des groupes de flots. Cette solution fonctionne quelquesoit le facteur d'echelle.

Les progrès technologiques confirmés au cours de cette décennie favorisent une importante révolution dans la façon de concevoir les systèmes informatiques. Des réseaux offrant des débits de milliards de bits par seconde permettront d'inter-connecter des ordinateurs personnels, moyens ultra-performants exécutant de nouvelles applications pouvant traiter, émettre ou recevoir des dizaines de megabits de données par seconde. Les systèmes automatisés sont des exemples de systèmes informatiques qui connaitront l'influence des progrés technologiques. L'audio, la vidéo, l'imagerie aux rayons X ou infrarouge, sont de nouveaux types d'information présentés sous forme de média continus pouvant être intégrés, à la faveur des progrès technologiques, aux systèmes automatisés. Nous proposons des extensions multimédia à MMS, la norme OSI de communication des systèmes automatisés, comme moyen d'intégration de ces nouveaux types d'information. MMS est basée sur le passage de messages et un protocole client-serveur mal adaptés aux flots soutenus de média continus. Après une présentation des particularités des systèmes multimédia traitant et véhiculant l'information sous forme de média discrets et continus, nous mettons en évidence des aspects de MMS qui la rendent inapte au traitement et au transfert de flots de média continus. Nous proposons ensuite un modèle d'extension du modèle objet et des services de MMS permettant de satisfaire les contraintes des média continus. Nous étudions enfin un prototype d'implémentation des nouveaux objets et services définis sur une plate-forme expérimentale. Ladite plate-forme se compose de stations de travail UNIX et Windows NT connectées par des infracstructures ATM. Elle servira à la mesure de performances des différents choix d'implémentation du modèle d'extension de MMS.