In the first part of the thesis, we address the optimization of multimedia applications such as videoconferences or multi-player games in which user-dependent information has to be sent from the users to a core node to be chosen, and then global information has to be multicast back from the core node to all users. For a given communication network, this optimization seeks a core node under two potentially competing criteria, one being the sum of the distances to a set of user terminals, the other being the cost of connecting this core node and the terminals with a multicast (or Steiner) tree. We first consider the problem of minimizing a weighted sum of the two criteria and propose a heuristic which rapidly computes a solution guaranteed to be within a few percent of the optimum. Then we characterize the worst-case trade-offs between approximation ratios for the two criteria. To state our result informally, we show that there always exists a core location for which each criterion is close to its minimum value (if we were to disregard the other criterion). In the second part, we focus on the protection of multimedia streaming applications against packet losses. Because of real-time constraints, error recovery is often achieved by Forward Error Correction (FEC) techniques which consist of partitioning the packet stream into blocks of consecutive packets and adding redundant data packets to each block. If the number of packets lost within a block is at most the number of redundant packets added, the receiver is able to recover the original data packets. Otherwise some data is irrecoverably lost. In communication networks, FEC techniques are typically impaired by the fact that packet losses are not evenly distributed among blocks but rather occur in long bursts of consecutive losses. However it has been observed that splitting the transmission of a FEC block onto several paths typically decreases the probability of an irrecoverable loss. Whereas current approaches rely on an exact computation of the probability and are consequently restricted to very small network instances, we propose to approximate this probability by measuring the impact of the chosen routing on the peakedness of the received packet stream. The peakedness of a stream may be seen as a measure of how packets are spread over time within the stream. Numerical experiments are presented and show that our method yields good approximations of the probability of irrecoverable loss./La première partie de cette thèse concerne l'optimisation d'applications multimédias, telles que des vidéoconférences ou des jeux en groupes, pour lesquels l'information propre à chaque utilisateur doit être envoyée vers un noeud central à sélectionner. L'information globale est ensuite diffusée en retour de ce noeud central vers chacun des utilisateurs. Pour un réseau de communication donné, cette optimisation consiste à choisir le noeud central selon deux critères potentiellement concurrents, le premier étant la somme des distances vers les utilisateurs, le second étant le coût de connecter ce noeud central et les utilisateurs avec un arbre multicast (ou arbre de Steiner). Nous considérons tout d'abord le problème de la minimisation d'une somme pondérée des deux critères et proposons une heuristique qui calcule rapidement une solution garantie d'être éloignée de l'optimum d'au plus quelques pour cent. Ensuite nous caractérisons les pires cas du compromis existant entre les rapports d'approximation pour les deux critères. De façon informelle, notre résultat peut se formuler comme suit : nous montrons qu'il est toujours possible de sélectionner le noeud central de telle sorte que chaque critère soit proche de sa valeur minimum (obtenue sans considérer l'autre critère). Dans la seconde partie, nous nous concentrons sur la protection des applications de diffusion multimédia (streaming) contre les pertes de paquets. A cause de contraintes temps réel, la récupération des erreurs pour ces applications est typiquement réalisée par des techniques de corrections d'erreurs dites "en avant" (Forward Error Correction ou FEC) qui consistent à partitionner le flux de paquets en blocs de paquets consécutifs et à ajouter des paquets de données redondantes à chacun de ces blocs. Si le nombre de paquets perdus au sein d'un bloc est inférieur ou égal au nombre de paquets ajoutés, le récepteur est capable de récupérer les paquets de données originaux. Dans le cas contraire, des données sont perdues de façon irrécupérable. Dans les réseaux de communication, l'efficacité des techniques FEC est typiquement dégradée par le fait que les pertes de paquets ne sont pas distribuées uniformément parmi les blocs de paquets mais apparaissent plutôt groupées par en rafales de pertes consécutives. Cependant il a été récemment observé que répartir la transmission d'un bloc FEC sur plusieurs chemins permet généralement de diminuer la probabilité de perte irrécupérable. Alors que les approches existantes se basent sur un calcul exact de cette probabilité et se limitent donc à des réseaux de très petite taille, nous proposons d'en calculer une approximation en mesurant l'impact du routage choisi sur la "peakedness" du flux de paquets. La peakedness d'un flux peut être vue comme un mesure de la répartition temporelle des paquets au sein de ce flux. Des résultats numériques sont présentés et montrent que notre méthode permet de calculer une bonne approximation de la probabilité de perte irrécupérable..

La popularité de la grande variété de l'utilisation d'Internet entraîne une croissance significative du trafic de données dans les réseaux de télécommunications. L'efficacité de la transmission de données sera contestée en vertu du principe de la capacité actuelle du réseau et des mécanismes de contrôle de flux de données. En plus d'augmenter l'investissement financier pour étendre la capacité du réseau, améliorer les techniques existantes est plus rationnel et éconmique.Diverses recherches de pointe pour faire face aux besoins en évolution des réseaux ont vu le jour, et l'une d'elles est appelée codage de réseau. Comme une extension naturelle dans la théorie du codage, il permet le mélange de différents flux réseau sur les noeuds intermédiaires, ce qui modifie la façon d'éviter les collisions de flux de données. Il a été appliqué pour obtenir un meilleur débit, fiabilité, sécurité et robustesse dans différents environnements et applications réseau. Cette thèse porte sur l'utilisation du réseau de codage pour le multicast dans les réseaux maillés fixes et systèmes de stockage distribués. Nous avons d'abord des modèles de différentes stratégies de routage multicast dans un cadre d'optimisation, y compris de multicast à base d'arbres et de codage de réseau; nous résolvons les modèles avec des algorithmes efficaces et comparons l'avantage de codage, en termes de gain de débit de taille moyenne graphique généré aléatoirement. Basé sur l'analyse numérique obtenue à partir des expériences précédentes, nous proposons un cadre révisé de routage multicast, appelé codage de réseau stratégique, qui combine transmission muticast standard et fonctions de codage de réseau afin d'obtenir le maximum de bénéfice de codage réseau au moindre coût lorsque ces coûts dépendent à la fois sur le nombre de noeuds à exécuter un codage et le volume de trafic qui est codé. Enfin, nous étudions le problème révisé de transport qui est capable de calculer un système de routage statique entre les serveurs et les clients dans les systèmes de stockage distribués où nous appliquons le codage pour soutenir le stockage de contenu. Nous étendons l'application à un problème d'optimisation général, nommé problème de transport avec des contraintes de degré, qui peut être largement utilisé dans divers domaines industriels, y compris les télécommunications, mais n'a pas été étudié très souvent. Pour ce problème, nous obtenons quelques résultats théoriques préliminaires et nous proposons une approche de décomposition Lagrange raisonnable / The popularity of the great variety of Internet usage brings about a significant growth of the data traffic in telecommunication network. Data transmission efficiency will be challenged under the premise of current network capacity and data flow control mechanisms. In addition to increasing financial investment to expand the network capacity, improving the existing techniques are more rational and economical. Various cutting-edge researches to cope with future network requirement have emerged, and one of them is called network coding. As a natural extension in coding theory, it allows mixing different network flows on the intermediate nodes, which changes the way of avoiding collisions of data flows. It has been applied to achieve better throughput and reliability, security, and robustness in various network environments and applications. This dissertation focuses on the use of network coding for multicast in fixed mesh networks and distributed storage systems. We first model various multicast routing strategies within an optimization framework, including tree-based multicast and network coding; we solve the models with efficient algorithms, and compare the coding advantage, in terms of throughput gain in medium size randomly generated graphs. Based on the numerical analysis obtained from previous experiments, we propose a revised multicast routing framework, called strategic network coding, which combines standard multicast forwarding and network coding features in order to obtain the most benefit from network coding at lowest cost where such costs depend both on the number of nodes performing coding and the volume of traffic that is coded. Finally, we investigate a revised transportation problem which is capable of calculating a static routing scheme between servers and clients in distributed storage systems where we apply coding to support the storage of contents. We extend the application to a general optimization problem, named transportation problem with degree constraints, which can be widely used in different industrial fields, including telecommunication, but has not been studied very often. For this problem, we derive some preliminary theoretical results and propose a reasonable Lagrangian decomposition approach

Dans les réseaux de télécommunications, la demande croissante pour de nouveaux services, comme la diffusion de vidéos en continu ou les conférences en ligne, engendre un besoin pour des dispositifs de télécommunication où le même contenu est acheminé depuis un émetteur unique vers un groupe de récepteurs. Cette évolution ouvre la voie au développement de nouvelles techniques d'acheminement des données, comme le multicast qui laisse un nœud du réseau copier ses données d'entrée puis retransmettre ces copies, ou le codage réseau, qui est une technique permettant à un nœud d'effectuer des opérations de codage à partir de ses données d'entrée. Cette thèse traite de la mise en place de techniques de codage au sein d'un réseau multicast filaire. Nous formalisons certains problèmes qui apparaissent naturellement dans ce contexte grâce à la recherche opérationnelle et à des outils d'optimisation mathématique. Notre objectif est de développer des modèles et des algorithmes afin de calculer, au moins de manière approchée, certaines grandeurs qui ont vocation à être pertinentes dans le cadre de la comparaison de techniques d'acheminement de données dans un réseau de télécommunications. Nous évaluons ainsi, d'un point de vue à la fois théorique et expérimental, l'impact induit par l'introduction de techniques de codage au sein d'un réseau multicast. Nous nous concentrons en particulier sur des critères importants pour un opérateur de télécommunication, comme la maximisation du débit d'information entre une source et un ensemble de destinataires dans le réseau, la minimisation de la congestion sous contrainte de demande, ou la minimisation de la perte de débit ou du coût induit par l'acheminement des données dans un réseau soumis à des pannes. / In telecommunication networks, the increasing demand for new services, like video-streaming or teleconferencing, along with the now common situation where the same content is simultaneously requested by a huge number of users, stress the need for point to many data transmission protocols where one sender wishes to transmit the same data to a set of receivers. This evolution leads to the development of new routing techniques like multicast, where any node of the network can copy its received data and then send these copies, or network coding, which is a technique allowing any node to perform coding operations on its data. This thesis deals with the implementation of coding techniques in a wired multicast network. We formalize some problems naturally arising in this setting by using operations research and mathematical optimization tools. Our objective is to develop models and algorithms which could compute, at least approximately, some quantities whose purpose is to be relevant as far as forwarding data using either multicast and network coding in telecommunications networks is concerned. We hence evaluate, both in theory and numerically, the impact of introducing coding techniques in a multicast network. We specifically investigate relevant criteria, with respect to the field of telecommunications, like the maximum amount of information one can expect to convey from a source to a set of receivers through the network, the minimum congestion one can guarantee while satisfying a given demand, or the minimum loss in throughput or cost induced by a survivable routing in a network prone to failures.

Les formats RSS et Atom sont moins connus du grand public que le format HTML pour la publication d'informations sur le Web. Néanmoins les flux RSS sont présents sur tous les sites qui veulent publier des flux d'informations évolutives et dynamiques. Ainsi, les sites d'actualités publient des milliers de fils RSS/Atom, souvent organisés dans différentes thématiques (politique, économie, sports, société...). Chaque blog possède son propre flux RSS, et des sites de micro-blogage comme Twitter ou de réseaux sociaux comme Facebook publient les messages d'utilisateurs sous forme de flux RSS. Ces immenses quantités de sources de données continues sont accessibles à travers des agrégateurs de flux comme Google Reader, des lecteurs de messages comme Firefox, Thunderbird, mais également à travers des applications mash-up comme Yahoo! pipes, Netvibes ou Google News. Dans cette thèse, nous présentons ROSES -Really Open Simple and Efficient Syndication-, un modèle de données et un langage de requêtes continues pour des flux RSS/Atom. ROSES permet aux utilisateurs de créer des nouveaux flux personnalisés à partir des flux existants sur le web à travers un simple langage de requêtes déclaratif. ROSES est aussi un système capable de gérer et traiter des milliers de requêtes d'agrégation ROSES en parallèle et un défi principal traité dans cette thèse est le passage à l'échelle par rapport au nombre de requêtes. En particulier, on propose une nouvelle approche d'optimisation multi-requête fondée sur la factorisation des filtres similaires. Nous proposons deux algorithmes de factorisation: (i) STA, une adaptation d'un algorithme d'approximation pour calculer des arbres de Steiner minimaux [CCC+98], et (ii) VCA, un algorithme glouton qui améliore le coût CPU d'optimisation du précédant. Nous avons validé notre approche d'optimisation avec un important nombre de tests sur des données réelles.