Cette thèse porte sur l'efficacité des algorithmes distribués de partage des ressources et des algorithmes de découvert de chemin en ligne. Dans la première partie de la thèse, nous analysons un jeu dans lequel les utilisateurs paient pour utiliser une ressource partagée. La ressource allouée à un utilisateur est directement proportionnel à son paiement. Chaque utilisateur veut minimiser son paiement en assurant une certaine qualité de service. Ce problème est modélisé comme un jeu non-coopératif de partage des ressources. A cause du manque des expressions analytiques de la discipline de file d'attente sous-jacente, nous pouvons résoudre le jeu que sous certaines hypothèses. Pour le cas général, nous développons une approximation basée sur un résultat fort trafic et nous validons la précision de l'approximation numériquement.Dans la deuxième partie, nous étudions l'efficacité des jeux de balance de charge, c'est à dire, nous comparons la perte de performance de routage non coopératif décentralisé avec un routage centralisé. Nous montrons que le PoA est une mesure très pessimiste car il est atteint que dans des cas pathologiques. Dans la plupart des scénarios, les implémentations distribués de balance de charge effectuent presque aussi bien que la mise en œuvre centralisée optimale.Dans la dernière partie de la thèse, nous analysons problème de découverte chemin optimal dans les graphes complets. En ce problème, les valeurs des arêtes sont inconnues, mais peuvent être interrogés. Pour une fonction donnée qui est appliquée à des chemins, l'objectif est de trouver un meilleur chemin de valeur à partir d'une source vers une destination donnée interrogation le plus petit nombre de bords. Nous vous proposons le rapport de requête en tant que mesure de l'efficacité des algorithmes qui permettent de résoudre ce problème. Nous prouvons une limite inférieure pour ne importe quel algorithme qui résout ce problème et nous avons proposé un algorithme avec un rapport de requête strictement inférieure à 2. / This thesis deals with the efficiency of distributed resource sharing algorithms and of online path discovery algorithms. In the first part of the thesis, we analyse a game in which users pay for using a shared resource. The allocated resource to a user is directly proportional to its payment. Each user wants to minimize its payment while ensuring a certain quality of service. This problem is modelled as a non-cooperative resource-sharing game. Due to lack of analytical expressions for the underlying queuing discipline, we are able to give the solution of the game only under some assumptions. For the general case, we develop an approximation based on a heavy-traffic result and we validate the accuracy of the approximation numerically. In the second part, we study the efficiency of load balancing games, i.e., we compare the loss in performance of noncooperative decentralized routing with a centralized routing. We show that the PoA is very pessimistic measure since it is achieved in only pathological cases. In most scenarios, distributed implementations of load-balancing perform nearly as well as the optimal centralized implementation. In the last part of the thesis, we analyse the optimal path discovery problem in complete graphs. In this problem, the values of the edges are unknown but can be queried. For a given function that is applied to paths, the goal is to find a best value path from a source to a given destination querying the least number of edges. We propose the query ratio as efficiency measure of algorithms that solve this problem. We prove a lower-bound for any algorithm that solves this problem and we proposed an algorithm with query ratio strictly less than 2.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Depuis quelques années, les centres d'appels enregistrent une forte croissance dans le monde. Les entreprises s'orientent de plus en plus vers ce choix qui leur offre une relation privilégiée avec leurs clients. Ainsi, ils disposent d'un moyen convivial et peu coûteux pour fidéliser leurs clients tout en essayant d'en acquérir de nouveaux. Ce travail fait suite à des problématiques réelles exprimées par l'entreprise Bouygues Telecom. Les données utilisées sont dans le même ordre de grandeur que ce qui se passe dans la réalité.<br />Dans la première partie de ce travail, nous étudions le phénomène de rappels. Nous commençons, d'abord, par montrer son importance dans le système. Par la suite, nous montrons que le fait d'ignorer ce phénomène engendre beaucoup d'erreurs lors du dimensionnement du centre d'appels et se traduit par des objectifs non satisfaits ou par un système surdimensionné sujet à des coûts supplémentaires. Cette analyse concerne le régime stationnaire. L'étude du système multi-période aboutit, elle, à la détermination de l'évolution de la demande réelle en fonction du temps et ce, à partir des arrivées observées.<br />Dans la deuxième partie, nous commençons par proposer des estimateurs du temps d'attente que les clients doivent passer dans la file avant d'être servis et ce, pour des clients répartis en plusieurs classes de priorité non-préemptive. En fonction de ces estimateurs, nous étudions plusieurs règles de routage. Nous comparons le système composé de plusieurs files d'attente, et nécessitant donc un routage, avec le système où les files d'attente sont fusionnées. Nous terminons cette partie par une analyse de deux disciplines de priorités probabilistes et nous les comparons avec la discipline de la priorité stricte. Comme dans le cas du routage, la comparaison s'effectue en fonction du nombre de conseillers nécessaires à la satisfaction de qualités de service objectif pour chaque classe de clients

Une architecture parallèle pour le traitement d'images, articulée autour d'un bus rapide, est étudiée en vue d'effectuer des rectifications géométriques d'images satellites de grande dimension. Une parallélisation de l'algorithme est proposée en tenant compte d'une optimisation possible du découpage de l'image

On étudie à la fois l'estimation de l'entropie de Shannon d'une probabilité à partir d'observations indépendantes ou markoviennes, et l'estimation du taux d'entropie d'un processus markovien de sauts d'espace d'état fini, à partir d'observations continues ou discrètes. Plusieurs problèmes connexes sont traités. Certains apparaissent en amont de l'estimation, comme l'étude de la géométrie de la divergence de Kullback-Leibler en lien avec la transformation escorte. D'autres apparaissent comme des applications des résultats d'estimation obtenus. On construit ainsi des tests sur le niveau d'entropie d'une probabilité, à partir d'un principe de grandes déviations pour la suite des estimateurs empiriques de l'entropie d'une suite de variables indépendantes. On étudie également diverses propriétés en lien avec l'estimation de l'entropie et du taux d'entropie de files d'attente modélisées par des processus markoviens de naissance et de mort.

Le développement du temps-réel est aujourd'hui une préoccupation majeure dans la conception des réseaux de télécommunication et des réseaux informatiques. Toute donnée doit alors avoir une "durée de vie" très limitée dans le système, puisque son traitement doit être instantané. Pour rendre compte de cette contrainte dans la représentation d'un nœud du réseau, on enrichit le modèle classique de la file d'attente d'un nouveau paramètre: le délai d'exécution des tâches. On parlera donc de file d'attente avec clients impatients: ils entrent dans le magasin avec une patience limitée et le quittent si leur délai expire avant d'avoir atteint un serveur. Nous étudions des cas où la discipline de service dépend du délai des clients ( EDF: on sert le plus pressé, LDF: le moins pressé...). Ceux-ci présentent une dynamique instable, ce qui en complique notoirement la description markovienne. Pour un système général sous toute discipline de service, un schéma de récurrence arrière aux instants de fins de service nous permet de prouver sous Palm l'Existence/Unicité du régime stationnaire, et de donner la condition de récurrence. Nous prouvons dans le même cadre par des techniques de couplage qu'EDF est la discipline optimale et que LDF est la pire pour la probabilité de perte à l'équilibre P et donnons une borne du gain d'EDF en terme de P. Nous calculons en outre des encadrements de P sous EDF dans certains cas. Nous proposons ensuite une description markovienne de la file d'attente avec clients impatients par le processus à valeur mesures ponctuelles simples où chaque masse de Dirac représente le délai résiduel d'un client en attente ou déjà perdu. Nous donnons la limite fluide d'une suite de renormalisations de ce processus en espace, temps et amplitude, ainsi qu'un théorème central limite fonctionnel établissant la convergence en loi de l'écart à la limite vers un processus de diffusion . La limite fluide, à trajectoires continues et déterministes, s'écrit explicitement comme l'unique solution d'une équation intégrale dans l'espace des processus à valeurs distributions tempérées. Les convergences s'obtiennent par passage aux fonctions tests du dual, et par des méthodes de compacité/unicité. Nous appliquons ces résultats à l'estimation asymptotique des processus de congestion et de perte sous EDF et FIFO, et au système délai pur.

Nos travaux de recherche sont dédiés µa la mise en oeuvre d'une maintenance<br />centralisée dans les systèmes manufacturiers. A partir de l'état de l'art sur le service<br />maintenance dans les différentes industries, notre problèmatique s'est portée sur la mise<br />en place d'un système de maintenance dans une entreprise possédant plusieurs unités<br />de production et dont la réparation des parties défaillantes des machines requiert des<br />ressources bien adaptées aux diverses machines complexes.<br />Dans le contexte d'une maintenance centralisée, une démarche de conception d'un atelier<br />de maintenance est proposée. A partir d'une étude fonctionnelle des machines de produc-<br />tion, la structure de l'atelier est établie et les ressources sont déterminées qualitativement.<br />Ensuite, nous proposons un dimensionnement de l'atelier de maintenance, passant par<br />l'évaluation des performances et en intégrant les coûts de maintenance. Enfin, pour que<br />l'atelier de maintenance soit efficace aussi bien sur le plan technique qu'économique de<br />l'entreprise, des stratégies de maintenance sont déterminées pour chaque machine.

Thèse de doctorat : Informatique : Nice : 2006. / Bibliogr. p. 147-154. Résumés en français et en anglais.

Les réseaux de communication jouant un rôle de plus en plus important dans nos activités quotidiennes, l'interruption des services qu'ils fournissent, ou même une degradation significative de leur qualité, deviennent de moins en moins acceptables. La sécurisation des réseaux et le contrôle de qualité de service sont ainsi devenus des enjeux majeurs qui nécessitent de réelles avancées méthodologiques dans plusieurs domaines. Nos contributions en ce sens peuvent se répartir en deux volets : d'une part celui de l'évaluation de performance et d'autre part celui de l'optimisation de réseaux. Nos travaux en évaluation de performance sont basés sur la théorie des files d'attente et sur la théorie des jeux. Ils visent le développement de modèles stochastiques analytiques ou de simulation permettant le passage à l'échelle pour l'évaluation, en régimes stationnaire et transitoire, des principales métriques de performance au niveau paquet (délai, taux de perte et gigue), mais aussi au niveau flot (nombre de sessions actives, temps de téléchargement, etc.). Ils concernent également l'analyse pire cas de la performance des stratégies de routage décentralisées. Les travaux en optimisation sont quant à eux essentiellement consacrés au développement de méthodes pour la conception de réseaux (d'accès ou de backbone) résilients, leur dimensionnement et l'optimisation de leur routage (avec OSPF ou MPLS). Les problèmes abordés étant généralement des problèmes combinatoires difficiles, avec souvent des fonctions objectifs non-linéaires, les approaches heuristiques sont privilégiées. D'autres travaux sont consacrés à l'ordonnancement de tâches strictement périodiques dans les systèmes embarqués avioniques.