Keywords: PlanetLab, LastMile, diffusion, partage de bande passante, système de prédiction réseau, streaming, pare-feu, routage efficace en énergie, requêtes découpables PlanetLab, LastMile, broadcast, bandwidth sharing, network prediction, streaming, firewalls, power aware routing, splittable requests Discipline: Computer Science iv

La popularité croissante des applications Internet très gourmandes en bande passante (P2P, streaming,...) nous pousse à considérer le problème suivant : Comment construire des systèmes de communications collectives efficaces sur une plateforme à grande échelle ? Le développement de schéma de communications collectives dans le cadre d'un réseau distribué à grande échelle est une tâche difficile, qui a été largement étudiée et dont de multiples solutions ont été proposées. Toutefois, une nouvelle approche globale et systématique est nécessaire, une approche qui combine des modèles de réseaux et la conception algorithmique.

Dans ce mémoire nous proposons l'utilisation de modèles capables de capturer le comportement d'un réseau réel et suffisamment simples pour que leurs propriétés mathématiques puissent être étudiées et pour qu'il soit possible de créer des algorithmes optimaux.

Premièrement, nous considérons le problème d'évaluation de la bande passante disponible pour une connexion point-à-point donnée. Nous étudions la fac ¸on d'obtenir des jeux de données de bande passante, utilisant plateforme PlanetLab. Nous présentons aussi nos propres jeux de données, jeux obtenus avec bedibe, un logiciel que nous avons développé. Ces données sont nécessaires pour évaluer les performances des différents algorithmes de réseau. Bien qu'on trouve de nombreux jeux de données de latence, les jeux de données de bande passante sont très rares.

Nous présentons ensuite un modèle, appelé LastMile, qui estime la bande passante. En profitant des jeux de données décrits précédemment, nous montrons que cet algorithme est capable de prédire la bande passante entre deux noeuds donnés avec une précision comparable au meilleur algorithme connu de prédiction (DMF). De plus le modèle LastMile s'étend naturellement aux prédictions dans le scénario de congestion (plusieurs connexions partageant un même lien). Nous sommes effectivement en mesure de démontrer, à l'aide des ensembles de données PlanetLab, que la prédiction LastMile est préférable dans des tels scénarios.

Dans le troisième chapitre, nous proposons des nouveaux algorithmes pour résoudre le problème de diffusion. Nous supposons que le réseau est modélisé par le modèle LastMile. Nous montrons que, sous cette hypothèse, nous sommes en mesure de fournir des algorithmes avec des ratios d'approximation élevés. De plus nous étendons le modèle LastMile, de manière à y intégrer des artéfacts de connectivité, dans notre cas ce sont des firewalls qui empêchent certains noeuds de communiquer directement entre eux. Dans ce dernier cas, nous sommes également en mesure de fournir des algorithmes d'approximation avec des garanties de performances prouvables.

Les chapitres 1 à 3 forment les trois étapes accomplies de notre programme qui visent trois buts. Premièrement, développer à partir de zéro un modèle de réseau de communication. Deuxièmement, prouver expérimentalement sa performance. Troisièmement, montrer qu'il peut être utilisé pour i développer des algorithmes qui résolvent les problèmes de communications collectives.

Dans le 4e chapitre, nous montrons comment on peut concevoir des systèmes de communication efficaces, selon différents modèles de coûts, en utilisant des techniques combinatoires, tout en utilisant des hypothèses simplificatrices sur la structure du réseau et les requêtes. Ce travail est complémentaire au chapitre précédent puisque auparavant, nous avons adopté l'hypothèse que les connections étaient autonomes (i.e. nous n'avons aucun contrôle sur le routage des connexions simples). Dans le chapitre 4, nous montrons comment résoudre le problème du routage économe en énergie, étant donnée une topologie fixée.

Résumé étendu

Internet à haut débit est omniprésent dans notre vie quotidienne. Des connexions de plusieurs gigaoctet par seconde sont fréquentes, et des nouvelles applications gourmandes en bande passante sont apparues. Parmi ces services, on trouve les réseaux peer-to-peer, le streaming de vidéo, le stockage dans des clouds. Chacun de ces services, est utilisé par un grand nombre d'utilisateurs et manipule de grand volumes de données, laissent leurs créateurs avec un ensemble de défis à relever. Voici quelques exemples de questions à réoudre : comment modéliser le comportement du réseau ? Comment prédire le comportement du réseau ? Comment concevoir des réseaux de recouvrement efficaces ?

Même si le progrès technologique permet d'apporter des nouvelles solutions pour les utilisateurs, le facteur crucial dans leur développement réside dans le progrès algorithmique. C'était le développement d'architectures décentralisées, qui ont fait les solutions comme Gnutella [START_REF] Ertel | Unstructured p2p networks by example: Gnutella 0[END_REF] ou BitTorrent [START_REF] Pouwelse | The bittorrent p2p file-sharing system: Measurements and analysis[END_REF] un grand succès. La transition a eu lieu grâce à une meilleure utilisation des ressources, comme la bande passante, le temps CPU et la mémoire des machines connectées au réseau.

Ces solutions reposent sur la transmission de grandes quantités de données entre les noeuds du réseau. Le Broadcast est un scénario qui apparait souvent, où un noeud veut envoyer un (volumineux) message à tous les autres noeuds du réseau, ou plus généralement le multicast, où seul un sous-ensemble noeuds souhaite recevoir le bloc de données. Par exemple, dans un réseau peer-topeer, où les données sont initialement présentes sur un seul noeud (la source) et puis distribuées à chaque noeud ces données. Dans un tel cadre de coopération, les noeuds qui ont obtenu des blocs de données peuvent commencer à les redistribuer eux-mêmes, accélérant ainsi le processus de diffusion.

Nous trouvons un autre exemple avec les sites de streaming vidéo. Les sites de streaming vidéo sont basés sur une architecture hautement centralisé, où le fournisseur doit investir dans une infrastructure énorme (comme c'est le cas de YouTube, en s'appuyant sur l'infrastructure de Google), et doit s'appuyer sur les solutions comme les serveurs géographiquement dispersés (afin de réduire la charge du centre de données). Il n'y a pas beaucoup d'espace pour la coopération entre les clients dans un tel service. Le nombre d'utilisateurs simultanés est massif, mais ils sont répartis sur un grand nombre de vidéos. Une situation tout à fait différente est présente pour les services de vidéo en streaming fonctionnant comme la télévision, (dédié aux événements en direct : sport, musique, jeux), puisqu'un très grand nombre de téléspectateurs peut coopérer de manière peerto-peer. Cependant, même dans ce scénario, différentes solutions sont nécessaires. Ce n'est pas comme dans le cas de la diffusion classique. Dans le cas de video-streaming l'ordre de réception des données possède un rôle crucial. Les données sont produites et consommées en direct. Des solutions théoriques ont été proposés : CoolStreaming [START_REF] Zhang | CoolStreaming/DONet: A data-driven overlay network for peer-to-peer live media streaming[END_REF], PPLive [START_REF] Vu | Mapping the PPLive network: Studying the impacts of media streaming on P2P overlays[END_REF] ou SplitStream [START_REF] Castro | SplitStream: high-bandwidth multicast in cooperative environments[END_REF].

Comme nous l'avons vu, le développement des systèmes/méthodes efficaces est un problème complexe et repose sur plusieurs niveaux. Il est d'une grande importance de proposer des solutions en prenant en considération la bande passante disponible sur la plateforme sous-jacente. Beaucoup de travail a été fait pour développer ces solutions à un niveau algorithmique, qui consiste à présenter un modèle abstrait du réseau, puis à formaliser un problème et enfin à proposer une solution algorithmique pour la dernière. Internet lui-même est trop complexe pour permettre une approche "directe", d'où la nécessite d'introduire une couche d'abstraction.

Par conséquent, si nous représentons le réseau avec un modèle simple, par exemple, si nous faisons l'hypothèse que la structure sous-jacente du réseau n'intervient pas, nous permettons aux noeuds de communiquer librement et nous supposons qu'aucune interaction entre les différentes connexions ne prendra place, nous ne serons pas capable de capturer le comportement complexe et sophistiqué du réseau (par exemple l'apparition de contentions). Cependant, nous ne pouvons pas nous attendre à des résultats raisonnables des algorithmes reposant sur des modèles qui ne prennent pas en compte la contention. D'un autre côté, en s'appuyant sur des modèles trop complexes, par exemple les réseaux représentés par un graphe pondéré, on risque de se retrouver incapable de développer des algorithmes d'optimisation raisonnables pour l'allocation des ressources sur ces réseaux (car déjà de nombreux problèmes de base sont trop difficiles à résoudre). Nous rencontrons également le problème d'être incapable d'instancier les paramètres du modèle, c'est-à-dire incapable de trouver une bonne représentation dans l'espace des paramètres d'un modèle donné pour un réseau donné. Les modèles trop précis sont également incapables de s'adapter aux différentes variations de réseaux que nous pourrions rencontrer, donc ils peuvent se révéler inutiles. En outre, les difficultés que nous rencontrons avec les opérations de base (telles que les mesures de point à point étant très variable au fil du temps) font que des modèles sophistiqués sont inutiles en pratique.

Le juste milieu que nous trouvons ici (nous devons sacrifier soit la force du modèle, soit la capacité de concevoir un algorithme efficace en utilisant le modèle) nous amène à un examen attentif des propriétés du réseau, que nous aimerions garder dans notre modèle et de développer des modèles en fonction de nos besoins. Dans le reste de cette thèse, nous aimerions (à partir des idées simples et en augmentant progressivement la complexité tout en montant l'échelle d'abstraction) construire méthodiquement des modèles et des algorithmes agissants à la base de ces modèles. Le sujet n'a pas été épuisé dans ce travail, mais nous avons tracé un cadre général qui pourrait être réutilisé dans les travaux futurs.

Motivation

La motivation principale de ce travail est le développementde schémas de communications collectives dans le cadre des réseaux distribués à grande échelle. Nous mettons la bande passante au centre de nos considérations. Les systèmes de diffusion provenant de la littérature ne sont pas satisfaisants dans notre contexte. Soit ils supposent une connaissance détaillée de la topologie détaillée du réseau (par exemple des solutions de Broadcast dans des réseaux maillés), soit les solutions conc ¸ues sont compliquées, comme dans SplitStream [START_REF] Castro | SplitStream: high-bandwidth multicast in cooperative environments[END_REF].

Dans cette étude nous visons à trouver l'équilibre entre les deux approches décrites ci-dessus (à savoir des modèles simples rendant des solutions algorithmiques possibles, ou des modèles complexes et exact), et de proposer une approche nouvelle et globale. Nous allons commencer par l'approche très basique : la communication entre seulement deux noeuds sur Internet. Une telle communication simple peut déjà montrer un comportement complexe, que nous verrons en analysant le déroulement de l'envoi d'un message. Nous allons essayer de modéliser le réseau et de proposer un modèle qui représente fidèlement le réseau, même en cas de plusieurs communications simultanées.

Nous voulons abandonner l'idée d'une parfaite connaissance de la topologie du réseau . C'est pourquoi la prochaine étape est d'essayer de proposer des algorithmes afin d'instancier et d'évaluer les paramètres réels du modèle dans un vrai réseau. Nous sommes en mesure de le faire par l'usage de systèmes de prédictions (Network Prediction Systems), qui sont des systèmes conc ¸us pour prévoir diverses mesures de performance du réseau. Ces systèmes attribuent généralement un nombre de paramètres pour les noeuds, et font une évaluation des paramètres du réseau (latence, bande passante) en fonction des paramètres des extrémités de la liaison. Les systèmes que nous trouvons dans la littérature dépendent soit sur le plongement du réseau dans un espace métrique, soit utilisent des approches plus synthétiques, comme la factorisation des matrices [START_REF] Liao | Dmfsgd: A decentralized matrix factorization algorithm for network distance prediction[END_REF] ou le plongement sur un arbre (tree embedding) [START_REF] Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF]. Nous plaidons pour l'utilisation de LastMile, où chaque noeud possède des paramètres associés ayant une interprétation dans la réalité (capacités des liaisons reliant les noeuds périphériques au centre d'Internet). Cette interprétation permet une simple instanciation des paramètres et rend naturel le développement des algorithmes base sur notre modèle.

Notre dernière étape sera de développer des algorithmes avec des bonnes garanties de performance (facteur d'approximation). Le but de ces algorithmes est de créer des systèmes de communications collectives. Notre objectif est de montrer qu'il n'est pas nécessaire de connaître la topologie complète du réseau, et que la possibilité d'instancier quelques paramètres suffit pour concevoir des systèmes de communication efficaces. Nous construisons ces algorithmes en supposant que rien de plus que la connaissance des liens extrêmes qui caractérisent les capacités du noeud à transférer des données dans le réseau. Grâce à notre approche, nous sommes en mesure de réduire le problème de la construction des réseaux logique à des problèmes combinatoires très simples et de le résoudre en conséquence. Le cadre que nous construisons est assez large, et à titre d'exemple, nous montrons comment intégrer la notion de connectivy artefact, sous la forme de firewall (nous classons les noeuds comme "open" ou "guared", et nous supposons que deux noeuds guared ne peuvent pas se communiquer directement).

Une fois le réseau logique construit (ensemble de connexions entre les noeuds) et les débits qui devraient être alloués à toutes les connexion sont déterminés, la solution peut être décomposée en un ensemble d'arbres de diffusion pondérés. Cette décomposition précise quelles données doivent être envoyées sur quelle connexion. Afin d'éviter cette étape de décomposition, qui est difficile à utiliser en pratique, nous nous appuyons sur un algorithme randomisé de Broadcast, proposé par Massoulié dans [START_REF] Massoulie | Randomized decentralized broadcasting algorithms[END_REF]. Cet algorithme est entièrement décentralisé et est capable de résoudre des cas avec des légères variations des ressources, grâce à son caractère aléatoire et dynamique. Cet algorithme nécessite la connaissance de la topologie du réseau et des bandes passantes sur les arêtes et pas de contention sur les noeuds, ce qui est complètement irréaliste dans une plateforme à grande échelle. Cependant, le réseau logique que nous construisons possède exactement ces propriétés, par construction. Le réseau logique que nous construisons peut donc être utilisé comme une entrée directe dans l'algorithme de Massoulié.

L'originalité de cette thèse est d'étudier le problème d'un point de vue global, en partant des mesures pour arriver aux modèlex et aux algorithmes basés sur ces modèles. Toutes les étapes décrites ci-dessus peuvent être combinées en une plus grande image qui permet à notre solution d'avoir des applications pratiques :

• La méthodologie d'évaluation de la bande passante point-à-point,

• Le modèle de réseau, validé par ensemble de données expérimentales,

• L'instanciation des paramètres du modèle à partir des mesures,

• L'algorithme pour une construction d'un réseau logique efficace en termes d'énergie, ayant les paramètres du modèle de Broadcast en tant qu'entrée,

• L'algorithme de Massoulié pour une détermination randomisée du paquets routage réelle.

Comme un travail complémentaire, seulement partiellement lié au reste de la thèse, nous fournissons également une étude où nous analysons la fac ¸on de concevoir un système de routage efficace en termes d'énergie dans une classe spéciale de graphes. Ce travail est motivé par la nécessité de concevoir un nouveau type de solutions lorsqu'il s'agit de routage et des problèmes de flot dans les réseaux. Les solutions classiques analysent généralement des situations où les arêtes d'un réseau sont limitées de manière brutale. Nous avons des solutions de conception où à chaque lien est associée une fonction de coût convexe, et la forme de la fonction impose que les solutions à faible coût soient bien équilibrés et aucun arête ne recevra de bande passante élevée. Notre motivation provient du besoin d'assurer un routage des messages efficace dans un system-on-chips, où la fonction de coût représente la consommation d'énergie par rapport à un transfert de données sur l'arête.

Introduction

Recent years have made a high speed Internet ubiquitous. Connections of speed gigabytes per second are common, and new bandwidth-intensive applications have arisen. Examples of such services are peer-to-peer networks, video-streaming, cloud storage. Such services, massive in amount of users and data usage, put their creators with a set of challenges to overcome. Examples of such challenges are: how to model network behavior? How to predict network behavior? How to design efficient overlay networks?

Even though the technological progress makes possible to bring new solutions to users, the crucial factor in developing them lies in an algorithmic progress. It was the development of decentralized architectures that made the solutions like Gnutella [START_REF] Ertel | Unstructured p2p networks by example: Gnutella 0[END_REF] or BitTorrent [START_REF] Pouwelse | The bittorrent p2p file-sharing system: Measurements and analysis[END_REF] highly successful and made file-sharing a massive phenomenon. The transition occurred in better usage of given resources, i.e. bandwidth, CPU time and disk space of collective of machines connected to the network.

Such solutions rely on transmitting large chunks of data between nodes of the network. Broadcast is a common scenario, where one node wants to send a chunk of data to all other nodes in the network, or more general multicast, where there exists helper nodes but they do not need to receive the whole message. We can imagine, for example, a peer-to-peer network, where the data that is initially seeded by a single node (source) is finally distributed across every node wanting to obtain it. In such a cooperative setting, nodes that got some chunks of data can start redistributing them on their own, thus speeding the whole process.

Another example is provided by video-streaming sites. Popular video sites are based on highly centralized architecture, where the provider has to invest in a huge infrastructure (as it is the case of Youtube, relying on Google's infrastructure), and rely on the solutions like geographically distributed caching servers (to reduce the load of the data-center). There is not much space for cooperation between the clients in such a service: while the number of simultaneous users is massive, they are spread over huge number of different videos. Different situation is present for video-streaming services functioning tv-like, (dedicated for live events: sport, music, gaming), as even the massive number of viewers can cooperate in a peer-to-peer fashion. However even in this scenario different solutions are necessary, as in classical broadcast we do not care about the order of incoming data, as long as we finally get all of it, and in video-streaming, the data is produced and consumed live, and has short life-span. Theoretical solutions have been proposed: CoolStreaming [START_REF] Zhang | CoolStreaming/DONet: A data-driven overlay network for peer-to-peer live media streaming[END_REF], PPLive [START_REF] Vu | Mapping the PPLive network: Studying the impacts of media streaming on P2P overlays[END_REF] or SplitStream [START_REF] Castro | SplitStream: high-bandwidth multicast in cooperative environments[END_REF].

As we saw, designing efficient schemes is a complex and a multi-level problem. It is of high importance to make such solutions bandwidth-aware, that is taking into consideration available bandwidth of the underlying platform when constructing solution. Plenty of work has been done to develop such solutions on an algorithmic level, that is to present an abstract model of network, formalize a problem, and propose an algorithmic solution to it. Abstracting through a model is necessary, as the Internet itself is too complex to allow any "direct" approach.

Therefore, if we represent the network with a simple model, e.g. if we do not assume anything about the underlying structure, and allow nodes to communicate freely, and assume no interactions between various connections, it fails to capture complex and sophisticated behavior of the network (e.g. contention). However, we cannot expect any reasonable results from the algorithms relying on models that do not take contention into account.

On the other side, if relying on too complicated models, for example networks represented as a weighted graph, we are left unable to develop any reasonable optimization algorithms for resource allocation on those networks (as many basic problems became too hard to solve). We also encounter a problem of being unable to instantiate the parameters of the model, by which we mean being able to find a good representation in a parameter space of a given model for the given actual network. Too precise models are also unable to adapt to different variations of networks we could encounter, which may prove them useless. Also, the difficulties that we encounter with basic operations (such as point-to-point measurements being highly variable and changing over time) make sophisticated models useless.

The trade-off we are dealing here (we have to sacrifice either strength of the model, or ability to design efficient algorithm using the model) leads us to a careful examination of what network properties we would like to have in our model and develop models according to our needs. In the rest of this thesis we would like to (starting with simplest ideas and gradually increasing complexity while we move upward in abstraction layers) methodically construct models and algorithms working on them. The topic is not exhausted in this work, but a general framework that could be emulated in future work is provided.

Motivation for a study

The main motivation for this work is the design of collective communications in the context of large sale distributed networks. We put emphasis on being bandwidth-aware in our design. Stateof-the-art content distribution systems are unsatisfactory. They either assume knowledge of the detailed topology of the network, e.g. broadcast solutions for meshes, or the designed solutions are complicated, as in SplitStream [START_REF] Castro | SplitStream: high-bandwidth multicast in cooperative environments[END_REF].

We aim in this study at finding the balance between the two approaches described above (namely simple models making algorithmic solutions possible, and complex and exact models), and to propose a new and comprehensive approach. We will start with the very basic, atomic approach of understanding the communication between just two nodes on the Internet. Such a simple communication can already show complex behavior, which we will see by analyzing bandwidthtime plots of communications. We will try to model the network and to propose a model that accurately captures the bandwidth-related capabilities of the network, e.g. contention, bottleneck links and bandwidth sharing.

We want to abandon the idea of perfect knowledge of the network topology. That is why our next step is to try to propose algorithms in order to instantiate and evaluate the actual parameters of the model in a real network. We are able to do it by usage of Network Prediction Systems, which are systems built to predict various performance metrics of the network. Such systems usually assign a few parameters to the nodes, and evaluate network parameters (latency, bandwidth) as a function of parameters of the endpoints of the link. State-of-the-art systems either depend on embedding the network into a metric space, or use more synthetic approaches like matrix factorization [START_REF] Liao | Dmfsgd: A decentralized matrix factorization algorithm for network distance prediction[END_REF] or tree embedding [START_REF] Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF]. We advocate for the usage of LastMile, where each node has associated parameters having real-life interpretation (capacities of links connecting peripheral nodes to the core Internet). Such interpretation allows for simple instantiation of the parameters, as well as for natural usage in the design of algorithms operating on the model. Our last step will be to design algorithms building collective communication schemes with good approximation guarantees. Our aim is to show that it is not necessary to know the full topology of the network, and that the ability to instantiate few parameters provides enough knowledge to design efficient communication schemes. We build those algorithms assuming nothing more than the knowledge of the end-links characterizing the capabilities of the node to transfer data in the network. In our approach we are able to reduce the problem of building overlay networks into a very simple combinatorial problem and solve it accordingly. The framework we build there is broad enough, and as an example we show how to incorporate the notion of connectivity artifact, in the form of firewalls (we classify the nodes into "open" and "behind firewall", and we assume that two nodes behind firewalls cannot communicate directly).

Once the network is built (which nodes communicate together) and the bandwidths that should be allocated to each edge create an overlay are determined, the solution can be decomposed into a set of weighted broadcast trees. This decomposition specifies which data should be sent on which edge at a given time step. In order to avoid this decomposition step, which is difficult to use in practice, we rely on the randomized broadcasting algorithm proposed by Massoulié in [START_REF] Massoulie | Randomized decentralized broadcasting algorithms[END_REF]. This algorithm is fully decentralized and is even able to deal with small variations of resource performance due to its randomized and dynamic nature. This algorit hm requires the knowledge of the topology of the network with bandwidths on edges and no contentions on the nodes, that is in general not realistic. On the other hand, the overlay network that we build has exactly, by construction, these properties. The overlay network that we build in this chapter can therefore be used as direct input to Massoulié's algorithm.

The originality of this thesis is to consider the problem on the complete chain, from measurements to model and algorithms. All of the steps described above can be combined into a "bigger picture" which allows our solution to be applicable in practice:

• methodology of point-to-point bandwidth measurements,

• network model, validated through experimental dataset,

• instantiation of model parameters from measurements,

• algorithm for construction of efficient broadcast overlay network having model parameters as an input,

• Massoulié's algorithm for randomized determining actual packet routing.

As a complementary work, only partially related to rest of the thesis, we also provide a study where we analyze how to design an efficient, power-aware routing scheme in a special class of graphs. This work is motivated by a necessity to design a new kind of solutions when dealing with routing and flow-related network problems. Classical solutions usually analyze situations where links on a network are capped in a hard way. We design solutions where with every link there is associated a convex cost function, and the shape of the function enforces that low-cost solutions will be well-balanced ones and no edge will receive high bandwidth. Our motivation comes from need of efficient routing of messages in system-on-chips, where cost function represents the power usage in relation to data transfer over edge.

Structure of the thesis

This thesis is structured as follow:

In Chapter 1, we discuss the measurements of network parameters, e.g. latency and available bandwidth. We discuss techniques for measuring available-bandwidth. We also describe PlanetLab platform, a large-scale, worldwide distributed platform for performing networkrelated experiments. We discuss how to obtain reliable datasets of bandwidth measurements using a PlanetLab platform. The S 3 project from HP aimed at monitoring the PlanetLab platform, provides us an example of such datasets. We also provide our own datasets, and we discuss them together with the distributed software used to obtain them. While those datasets are not a part of our model per se, such datasets prove necessary when evaluating performance of various network algorithms. We also discuss differences between bandwidth-related and latency-related datasets, and the problems we encountered when trying to obtain the former ones. In this chapter we also describe our experiments concerning bandwidth sharing measurements. We provide a detailed discussion of the setting, methodology, software and platform concerning those datasets. We believe such datasets are important to validate models when it comes to predicting congestion.

In Chapter 2, we introduce the idea of Network Prediction Systems. These systems are an algorithmic approach to the problem of predicting the values of various network metrics (for instance latency or available bandwidth between nodes). They are typically used in a situation when only partial measurements are available, to be able to infer value for every point-to-point communication. Each algorithm is discussed together with its pro and cons, and for each system we also discuss the network model that it is based upon.

We start by discussing earlier approaches, based on embeddings into metric space. Such embedding rely on assigning to each node in network an appropriate point in the parameter space, and network metric we are estimating is read as the distance between points in the metric space. We present various systems based on such an approach, like GNP (embedding into Euclidean high dimension space) or Vivaldi (embedding into Euclidean space + height).

Another approach is basis of the Sequoia system, which tries to embed network into the virtual tree, trying to mimic the hierarchical structure of the network.

We also describe approaches based on a matrix factorization. This is a synthetic approach based on a treating the full set of measurements as an unknown, partially filled matrix of values, that we try to represent as a low rank matrix (a matrix product P × Q where P and

Q are respectively n × d and Q is d × n matrices, for some d ≪ n).
Our experimental comparison on datasets we obtained shows that this approach yields best estimation from known prediction systems. This is despite the fact that there is no underlying network model supporting this form of a calculation and effectiveness of the algorithm is only due to the matrix approximation as a low rank being very efficient.

Then, we advocate for a network model that tries to accurately capture the capabilities of the network, named LastMile model. This model assumes that essentially the congestions happen at the edges connecting machine to the wide Internet. It has a natural consequence in bandwidth prediction algorithm based on this. Using datasets described earlier, we prove that this algorithm is able to predict with an accuracy comparable to best known network prediction algorithm (Distributed Matrix Factorization) available bandwidth between two given nodes. While we were unable to improve upon DMF algorithm on the field of pointto-point prediction, we show that our algorithm naturally extends to the network predictions under the congestion scenario. We are actually able to show that LastMile predicts better in such scenarios, using PlanetLab datasets.

We also show the use of another strength of LastMile approach, i.e. the easiness of extending the model. We show how the model can be generalized to incorporate the notion of wellconnected core Internet. The division into small, well-connected core and large, sparse, treelike peripheral Internet is supported by various empirical evidences (for example measures of treewidth and hyperbolicity of the Internet). We show that LastMile is elastic enough to incorporate such notions into its model, and that this extension leads to similarly simple algorithms.

We end the chapter with description of a bedibe tool, that we developed as a response to a growing need to prototype and evaluate different algorithms over various datasets. We used this tool to obtain datasets, as well as analyzing performance of the algorithms with respect to this datasets.

Chapter 3 describes the next step of our work, of developing specific optimization algorithms for networking problems. We consider the classical problem of broadcasting a large message at an optimal rate in a large scale distributed network under the LastMile communication model. In this context, we are interested in both building an overlay network and providing an explicit algorithm for scheduling the communications. From an optimization point of view, we aim both at maximizing the throughput (i.e. the rate at which nodes receive the message) and minimizing the degree of the participating nodes (i.e. the number of TCP connections they must handle simultaneously). We propose new algorithms solving this massive scale broadcast problems. We show that under that type of assumption, we are able to provide algorithms with provable, strong approximation ratios.

Taking advantage of the simplicity and elasticity of the model, we can even extend it, so that it captures the idea of connectivity artifacts, in our case firewalls preventing some nodes to communicate directly between each other. In the extended case we are also able to provide approximation algorithms with provable performance.

In Chapter 4, we show how under different network cost models, using some simplifying assumptions on the structure of the network and of the queries, we can design very efficient communication schemes using simple combinatorial techniques. We investigate designing routing of the communication algorithms, using some simplifying assumptions on the environment (the graph where the communication takes place is a grid graph) and cost model (we investigate the power-aware model). This work is complementary to the previous chapter in the sense that previously when designing communication schemes, we assumed atomicity of connections, i.e. that we have no control over routing of simple connections. In this chapter we show that the knowledge of topology of the network or well-specified cost model allows us to solve efficiently the problem of routing the network requests. It shows the importance of being able to efficiently instantiate the parameters and the structure of the model, as such detailed instantiation gives us very strong tools to design efficient communication schemes.

Chapter 1

Measuring the Network

In large scale Internet platforms (e.g. peer-to-peer, streaming networks, clouds), measuring the available bandwidth between nodes of the platform is difficult and costly. In many Internet applications, network-awareness is an important part of achieving good performance or lowering resource usage. In the case of delivering video on demand [START_REF] Suh | Pushto-peer video-on-demand system: Design and evaluation[END_REF], or performing peer-assisted streaming [START_REF] Liu | Performance bounds for peerassisted live streaming[END_REF] for example, estimations of available bandwidth allow the construction of an efficient overlay topology. Efficient algorithms for broadcasting or for organizing master/slave communications have been proposed [START_REF] Beaumont | Heterogeneous resource allocation under degree constraints[END_REF][START_REF] Beaumont | Broadcasting on large scale heterogeneous platforms with connectivity artifacts under the bounded multi-port model[END_REF]. Examples of such overlays will be the topic of Chapter 3.

Those algorithms rely on an accurate representation of the performance of the network. In all these applications, large amounts of data need to be exchanged between nodes, and hence the available bandwidth is the important metric for application performance. However, the naive approach, that is measuring available bandwidth between nodes which are geographically distributed over the Internet usually incurs a high cost, both in terms of measuring time and induced network load. It is thus not desirable to perform periodic explicit end-to-end path measurements. Another downside of this direct approach is that the number of possible scenarios we have to consider grows quickly with the size of the network. Taking into account isolated point-to-point communication, the number grows quadratically with the number of nodes (which already is impractical for large networks), that is a full matrix of values indexed by starting and ending points of communications. If we consider congestion scenarios (where one node can communicate with a set of nodes), the number can be even exponential. This forces us to provide other solutions than measuring in advance network performance in every possible communication scenario, and directly measuring every value of the communication matrix can be too much. Furthermore, we should consider that network environment is a highly dynamic one, which implies that such explicit path measurements provide a representation of the platform that is never up-to-date. We should be able to reevaluate our measures, and take into consideration the high volatility of the measures.

As we will see in section 1.5.1, having the measures over the same edge varying twofold or even larger is not that uncommon. We will discuss the methodology of bandwidth measurement in Section 1.2.

To remedy problems highlighted above, we should consider the following solution. Firstly, for each node, just keep track of partial data only, trying to capture the behavior of the node in the network with only few essential measurements. We should be able to perform those measures for example when new nodes are introduced to the network (in a peer-to-peer networks), or periodically, to keep track of changes of network topology. Second, we should be able to extrapolate this small data to predict the behavior of connections in more complicated situations. We will discuss problem of predicting the network in Chapter 2. Having access to those predictions about the performance of the platform, and especially about the available bandwidth, allows us to design efficient algorithms that optimize resource usage for different types of collective communications. In fact, whenever designing broadcasting algorithms or organizing master/slave computations, it seems essential to obtain this type of information from the underlying network.

We will discuss point-to-point predictions with introduction of Network Coordinate Systems, and more generally, Network Prediction Systems in Chapter 2. We will cover them deeper further in the thesis, but the way both topics interact is worth noting. On the one hand, it is essential to have reliable datasets when designing, prototyping and testing various Network Prediction Systems. On the other hand, using reliable prediction algorithm, we can measure network only partially, for some landmark edges, and recover the rest of the data using predictions.

Available bandwidth datasets are quite rare in the literature. The S 3 project [START_REF] Yalagandula | S3: a scalable sensing service for monitoring large networked systems[END_REF], which measured available bandwidth with the Spruce tool [START_REF] Strauss | A measurement study of available bandwidth estimation tools[END_REF] between PlanetLab nodes, is now discontinued, and we are not aware of other similar projects which are still active. Several tools exist for measuring available bandwidth (i.e. the minimum remaining capacity on all links on the path) [START_REF] Prasad | Bandwidth estimation: metrics, measurement techniques, and tools[END_REF], while keeping the load incurred to the network low. Furthermore, available bandwidth is not identical to the available TCP throughput, which is the metric that actually influences the performance of applications. State-of-the art methods for measuring available TCP throughput (such as Iperf [START_REF] Gates | Iperf[END_REF]) are much more intrusive, and generally rely on mimicking the behavior of TCP, by sending as much data as possible, and measuring how much data is actually received in a given amount of time, once steady-state has been reached.

In this chapter, we describe our effort to obtain complete and reliable datasets of two different types. First, we present datasets measuring point-to-point bandwidth over larger collection of nodes, then we follow with datasets measuring bandwidth sharing over smaller sets of nodes. Both datasets were collected on PlanetLab platform. We discuss the methodology we used for performing both experiments, what we aimed for and what we obtained. We also provide broad discussion of obstacles we encountered while obtaining datasets, originating from either networking environment characteristic, or being specific to PlanetLab. Finally, in this chapter we also provide statistical analysis of the datasets, followed with reasoning about possible models for the behavior of underlying network.

Context

In this section, we discuss our measurements in a wider context. We discuss platforms and software used for obtaining datasets. In contrary to latency datasets, bandwidth datasets are rare. Nevertheless we discuss already existing bandwidth dataset, i.e. S 3 [START_REF] Yalagandula | S3: a scalable sensing service for monitoring large networked systems[END_REF]. Please note that we use a collective term bandwidth for both TCP throughput and available bandwidth.

PlanetLab

The measures have been performed on the PlanetLab platform1 [START_REF] Chun | Planetlab: an overlay testbed for broad-coverage services[END_REF]. PlanetLab is a large-scale, worldwide distributed platform which provides an access to nodes on more than 500 sites across the world, with more than 1000 nodes. PlanetLab was created in order to support the design and evaluation of various Internet related applications, such as peer-to-peer file sharing or content distribution networks. PlanetLab is designed with a heavy emphasis on virtualization. The center of PlanetLab architecture is a slice, a horizontal cut of global PlanetLab resources. Each service runs in a slice of PlanetLab. Each slice is allocated a certain amount of resources (processing, memory, network resources) across a set of individual nodes, and can be viewed as a network of virtual machines, with resource bound to each virtual machine. Nodes of PlanetLab are geographically distributed, connected by a diverse collection of links, including edge sites, co-location and routing centers, and low-profile machines. It has also become a de facto standard for conducting large scale Internet experiments, and is thus well suited for our purpose. Furthermore, its accessibility makes it relatively easy to conduct the required measurements.

However, there are still several downsides associated to the choice of PlanetLab for performing measurements. The nodes are not the best representation of the Internet, with majority of the nodes connected to the Global Research and Education Network (GREN). While there were various efforts to improve the diversity, most of the nodes are still connected through the GREN (with only 26 nodes connected through the commercial Internet). The heavy load that the nodes of PlanetLab experience is another source of problems.

SPLAY

The measurements were performed using the SPLAY middleware2 [START_REF] Leonini | Splay: distributed systems evaluation made simple[END_REF]. SPLAY was created with aim of simplifying the prototyping and development of large scale distributed applications and overlay networks. It provides a set of libraries and interfaces for writing applications. SPLAY also provides web and command-line interfaces for job management on platform, node selection tools, or for control of the behavior of testbed itself. We used SPLAY service on PlanetLab running on its own PlanetLab slice. Using SPLAY helped us to write really lightweight and error-less networking code, and concentrate on the logic of experiments and measures themselves. It is also a great tool for automatic deployment of code on tens or hundreds of PlanetLab nodes.

S 3

The S 3 project from HP [START_REF] Yalagandula | S3: a scalable sensing service for monitoring large networked systems[END_REF] was aimed at monitoring the large scale distributed platform Planet-Lab, and in particular at providing available bandwidth measurements between pairs of nodes of this platform, obtained with the Spruce tool [START_REF] Strauss | A measurement study of available bandwidth estimation tools[END_REF]. These datasets have been used by the community to validate bandwidth estimation tools [START_REF] Key | Non-metric coordinates for predicting network proximity[END_REF]. However, this project is now discontinued, and we are not aware of other similar projects which are still active. We decided not to use Spruce by ourselves, because it requires some extra knowledge on the measured link, that is capacities of individual links on the edge. We use S 3 datasets as a reference point for checking validity of our point-to-point measures.

Measurement methodology

In this chapter we focus on application-level measurements, in order to observe the platform as it would be accessible to the application. Hence, we measure available TCP throughput, which is the steady-state reachable throughput that can be achieved with a TCP connection.

Available bandwidth

It is a nontrivial problem to define the "available bandwidth" for a fixed Internet path P. It is common to define it as the maximum rate of transmission that could be achieved without reducing rate of the rest of the traffic in P [START_REF] Jain | End-to-end available bandwidth: Measurement methodology, dynamics, and relation with tcp throughput[END_REF]. However, in our experimental setting, we have no control on other traffic that goes over the same path. But we can safely assume that the network we are operating on (PlanetLab) is coupled with the Congestion Control mechanisms appropriate for systems under heavy usage [START_REF] Peterson | Using planetlab for network research: Myths, realities, and best practices[END_REF]. So we assume, that the bandwidth we achieve when we "flood" the path with our transfer, is in fact the maximum achievable one that does not prevent other communications from taking place.

Intrusive vs. non-intrusive measures

Efficiently measuring the available bandwidth on a path has been addressed in several works (see for example [START_REF] Jain | End-to-end available bandwidth: Measurement methodology, dynamics, and relation with tcp throughput[END_REF]). A simple and natural method consists in sending as much data as possible, and measuring how much data we are able to send in a given time. The major downside of this method is that it incurs a very heavy load on the network for the whole duration of the experiment, that needs to be long enough to ensure that steady-state has been reached. By necessity, several less intrusive methods for measuring available bandwidth have been developed, like pathload, IGI or pathchirp [START_REF] Prasad | Bandwidth estimation: metrics, measurement techniques, and tools[END_REF]. Pathload tool relies on a Self-Loading Periodic Streams (SLoPS) methodology. The methodology involves sending periodic packet streams of fixed size, and then monitoring variations in the one way delays of the probing packets. If the stream rate is larger than the path's available bandwidth, the stream will cause a short term overload in the queue of the tight link. On the other hand, if the stream rate is lower than the available bandwidth, the probing packets will go through the path without causing an increase in the delays. The sender can thus try and estimate the highest possible sending rate that will not increase the packet delays. IGI and pathchirp rely on Trains of Packet Pairs (TOPP) methodology, which is a modification of SLoPS, based on statistical analysis of behavior of pairs of packets. TOPP sends many packets pairs at gradually increasing rates from the source to the sink. If the offered rate of the packets (L/∆ S , where L is size of packet, ∆ S is the dispersion rate, that is the time between first and second packet) exceeds end-to-end available bandwidth, the second probing packet will be queued behind the first probing one, and measured rate will smaller than offered rate. On the other hand, if offered rate does not exceed available bandwidth, the measured rate will be the same. To summarize, those tools rely on sending a few packets along the path, and analyze the effects of intermediate nodes and cross traffic on these probe packets. Although they do not require privilege access, these tools require a fine grain access to the network. However, using them on PlanetLab is not easy and is not reliable [START_REF] Lee | Measuring bandwidth between planetlab nodes[END_REF], at least not more reliable than brute force approach, since the main source of failures of measurement between nodes is the inability to establish connection, without distinction for non-intrusive and intrusive measures. Even though these methods are much more efficient in terms of resource usage, we decided to rely on simple, yet intrusive, measures. This decision is motivated by two points. Firstly, since the goal of our study is to analyze several methods for predicting bandwidth from a limited number of measurements, it is important to introduce as few measurement errors as possible in the data. Furthermore, we could not find bandwidth datasets obtained with a direct method, since the S 3 dataset was obtained with Spruce. Secondly, and most importantly, our study of congestion with several connections requires direct intrusive measures.

Protocol limitations

The biggest obstacle to overcome is the slow start of a TCP connection [START_REF] Jacobson | Congestion avoidance and control[END_REF]. TCP protocol contains Congestion Control mechanisms. As a result, during the initial phase of the connection the transmission rate increases exponentially with time, by doubling the congestion window with each received acknowledgment. So, when measuring bandwidth, we must make sure not to take into account the initialization period of connection, as it will make measures underestimated. On the left side of the Figure 1 we provide a plot of both total number of bytes send and received as a function of time, during a single transmission session between two nodes, one sending and another one receiving. It provides an example of behavior described above, where we can clearly see that all sending nodes achieve full available transmission speed a few seconds after the connection we established, as constant slope means constant throughput. After a while, the sending speed gets adjusted, also as a result of a Slow Start mechanism. The delay between sending and receiving the data can be attributed to the TCP buffers. Situation becomes more unpredictable, when there are multiple simultaneous connections. We observed that the bandwidth share allocated to a unique connection, during a single transmission session is fluctuating heavily over time. Since the starting behavior is chaotic, we arrange the measures of the connection speed for sufficiently long enough to make averages overcome local fluctuations. However, even with the long snapshots, the behavior varies strongly, even when trying to reproduce the same scenario. Plot on the right of 1 provides an example of sharing a connection between two transmissions. The steps we see on the plot are another effect of TCP Congestion Control. Figure 2 shows an example of such a behavior, where multiple outgoing connections compete over share in more or less constant stream of outgoing data in one sending node to three receiving ones. We observe that while the sender quickly saturates its outgoing link and transmission is performed at constant speed, the share that is assigned to each receiver varies in time. We see that one connection (only after 12s since start) saturates and effectively kills both other competing connections (their speed drops to zero).

Another obstacle to overcome comes from the fact that TCP is not stateless. When performing series of measures, closing and reopening the connection can be not enough to reset the connection. To avoid encountering traces of old connections in the network when repeating the same connection, we made sure to wait a sufficient amount of time between measurements on the same edge (5min wait was implemented).

PlanetLab limitations

Our choice to perform the experiments on PlanetLab influenced heavily how they were performed. The PlanetLab platform itself, because of the fact that it is shared among a large number of users, comes with a number of restrictions.

In order to avoid flooding, PlanetLab has a policy fixing for each node a daily data transfer limit. Together with our measurement methodology which requires to send data for 20 seconds to perform one measurement, this means that it takes several days to gather an exhaustive and broad enough dataset, even for a small number of nodes. Hence, the number of nodes must be kept at reasonable size if we want our datasets to span relatively short periods of time.

PlanetLab nodes are under heavy usage, both in terms of CPU and bandwidth. Because of heavy CPU usage, and special process scheduler, time measures are unreliable (under 10ms error), which makes latency measures over network unpractical, and makes it very difficult to use stateof-the art available bandwidth estimation tools, that rely on precise timings of packet arrival times (see [START_REF] Prasad | Bandwidth estimation: metrics, measurement techniques, and tools[END_REF][START_REF] Jain | End-to-end available bandwidth: Measurement methodology, dynamics, and relation with tcp throughput[END_REF]). Our bandwidth measures however do not suffer from this problem, since we measure time at a much coarser scale. Heavy bandwidth usage from other PlanetLab users yields a very high variability of the measures, even when performing one measure just after another. Example of how variable individual measurements over single edge can be seen on the Plot 5.

The PlanetLab platform is not a "typical" Internet platform, in the sense that it consists of servers hosted by universities or research institutions, often connected through high-speed and high-bandwidth academic networks. They are also usually close to the main Internet routes. It is important to keep in mind that this platform is thus not representative of a typical peer-to-peer situation. However, its size and its geographically distributed nature make it interesting to observe and to analyze. Furthermore, when we will introduce LastMile model in Chapter 2, we will see that this situation is a "worst-case" for that model, since typical peer-to-peer platforms with DSL connected nodes are more likely to follow the LastMile model than PlanetLab (due to their slower "last-mile" links more likely being a bottleneck of transmission, which is a central assumption for this model).

Experiment design

We performed two types of experiments: individual end-to-end throughput measurements, as well as contention experiments for measuring the performance achieved when multiple communications take place at the same time. To keep them as simple as possible, we concentrated on the particular situation with one sender and two receivers. On the considered platform, such a situation is enough to generate contention, and thus allows us to capture congestion and sharing mechanisms. The situation with two senders and one receiver would be interesting to observe as well, but we left it open as a possible extension to our work in the future. The original scenario already cost us much in terms of effort and time, and provided us with enough data to analyze extensively. It is also important to point that, due to asymmetry of Internet download vs. upload, the one-to-two scenario is much more likely to generate congestion than the two-to-one scenario.

In order to make sure that we observe steady-state, and thus avoid the slow-start mechanisms of TCP, the setting for measuring individual connection was as following: data is sent from the sending node to the receiving node on a TCP socket for 20 seconds . The first 15 seconds are not measured, and only used to "warm-up" the connection. The receiver measures how much data is received for the last 5 seconds, and uses this value to compute an average throughput over these 5 seconds. We present an example of such a measurement on Figure 3. Notice, that the sending node sends data only for 20 seconds, and even if receiving nodes still receive the data after 20 seconds have passed, it doesn't count towards measured values. The length of measure was chosen as a compromise between usage of resources (daily cap on used bandwidth per node of PlanetLab) and precision of measurement. Contention experiments used a similar setting, with both receivers measuring how much data they receive on the last 5 seconds. This is a major difference from S 3 datasets, that were obtained using the Spruce tool [START_REF] Strauss | A measurement study of available bandwidth estimation tools[END_REF].

With the dynamic nature of the PlanetLab platform, both kinds of measurements suffer from high variability. In order to overcome this variability, we perform at least 10 repetitions of the measurement for each configuration (the same sender-receiver pair for end-to-end measures, and the same sender-receivers triplet for contention measures). The variability of measures is analyzed in Section 1.5.

Datasets

The measurements performed are grouped into two datasets. The first dataset contains our end-toend bandwidth measures. It was obtained by randomly selecting 50 nodes of PlanetLab, among which we performed measures over the course of one month, with the objective of having 10 measures for each sender/receiver pair. Due to PlanetLab limitations and in order to avoid exceeding daily limits for a node transfer, each node could be involved only in a few measurements daily. With a daily limits around 8GB of download, and one measurement taking even up to 200MB, or sometimes larger if the nodes involved happen to be in a network close proximity. The total transfer limitations of PlanetLab created a situation, where even with all nodes available all the time and with no connection problems, obtaining the full matrix would have taken months. Such a large timespan contradicts the idea of obtaining snapshot of network parameters at one precise moment. Even worse, because of unavailability and connection problems, we abandoned the starting target of the experiment, that is to obtain a complete matrix over a larger set of nodes. A subset of 15 most reliable nodes was selected (based on already obtained partial data), among which it was possible to obtain a complete set of measurements. This data was collected between December 20th, 2012 and January 16th, 2013.

The second dataset contains our congestion measurements. It consists of 87 measures of bandwidth shared between triplets of nodes (one sender and two receivers), where each measure over each triplet was performed 10 times in about 10 minutes of time. Triplets were selected at random among the set of 15 nodes which had been selected for the complete end-to-end measurements as described above. This data was collected between January 4th, 2013 and February 4th, 2013.

Examples of results of this type of measurements are on plots on Figure 4, where we plot measured source-to-first node bandwidth vs. measured source-to-second node bandwidth in a bandwidth sharing experiment. On both those plots the results seem to cluster on a X +Y = const line, however we see strong variability of a distribution of individual values.

Both of these datasets are available as part of a larger project named bedibe, and can be downloaded at the following address: https://gforge.inria.fr/frs/download.php/32092/data. zip. We will discuss bedibe more thoroughly in a Chapter 2.

Data analysis

In this section, we perform statistical analysis of datasets mentioned above. We provide basic statistical analysis of point-to-point datasets, followed with analysis of bandwidth sharing datasets. We perform them to increase our confidence that we are in fact measuring network parameters, even when faced with noise and highly volatile environment on a large scale.

Point-to-point measurements

In order to evaluate the variability of our measurements, we focus on the subset of 15 nodes, for which we have performed a larger number of measurements. Between all pairs of nodes, a

0.0 0.5 1.0 1.5 G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G 1e+05 1e+06 1e+07
Mean available bandwidth Relative Standard error total of 10 individual bandwidth measurements were performed. This allows to compute mean and standard deviation for each given source/destination pair, and we express how variable the results of a measurement between two given nodes can be by computing the relative standard deviation (the standard deviation divided by the mean). On Figure 5, we plot relative standard deviation as a function of mean bandwidth, and distribution of relative standard deviation among all source/destination pairs. We can see that only a fraction of measures are stable. However, in significant number of cases the variability is high, with relative standard error around or above 0.5. This means that on average, we can be certain of the measure only up to a factor of 2. This variability is not a surprise, given that the PlanetLab platform is shared among many users, and this shows that providing estimates for the bandwidth is certainly challenging.

Bandwidth sharing measurements

In the bandwidth sharing experiments, we measure the throughput received by both receivers. Here also, we want to observe the variability of these measurements. For each configuration (i.e. for each choice of one sending and two receiving nodes), the measurement was performed 10 times during 1 hour, and reports the throughput received by each receiving node (b 1 and b 2 ), as well as the sum of these throughputs b tot = b 1 + b 2 . Similarly to the previous paragraph, for each configuration we compute the relative standard error for b 1 , b 2 and b tot , as an indication of how variable these measures are. The results are shown on Figure 6, where we plot distribution of the relative standard error of the throughput received by the first node, by the second node, and of the total throughput received by both of them. We can see on the plot, that the total throughput is much more stable than the individual throughput received by a given node. This high variability for individual values is the reason why, in Chapter 2, we will not attempt to predict how the sharing is done between the two receivers, but instead focus on predicting the total throughput.

Conclusion

We have been able to get a consistent, reliable data in a reasonable time, using PlanetLab. Our initial aim to obtain data on how the bandwidth is shared between individual connections in a contention scenario proved to be too ambitious. As we saw on the results, even if the total throughput of a sending node is stable, the individual share of bandwidth is unpredictable when we repeatedly perform the same node connection configuration. However, higher stability of total sending throughput is a strong indicator of saturation of the sending node and applicability of the LastMile model in this scenario. Our point-to-point measurements provide better results, however scale of influence of various parameters is noticeable. Level of errors we obtain on this measurement is also a reason, that when we will be performing network predictions, we should not distinguish between perfect prediction, and prediction with a relative error of 50%, as that is usual error ratio the measurements come with. Further work in this area is needed, as there is not enough bandwidth datasets publicly available to the research community. On the measurement side, it would be very useful to obtain larger datasets for available TCP throughput. But to achieve this, it seems necessary to use other platforms, since we believe we have achieved the limits of what is possible within PlanetLab. While it might be possible to use existing tools for obtaining point-to-point measurements, and thus obtain larger datasets, no tools for measuring bandwidth sharing is known to us. As there exists S 3 pointto-point dataset obtained on PlanetLab, using Spruce, we saw no point in duplicating that work. For congestion measurements, it would be interesting to perform measures of congestion/bandwidth sharing in more general settings. In this chapter, we concentrated on scenarios with one sender and two receivers. Scenarios with two (or more) senders and one receiver would allow to explore congestion on links to receiving nodes, instead of sending nodes. Our work allowed to observe congestion with no more than 3 nodes involved. Considering larger scenarios, e.g. one sender and many receivers or many senders and one receiver, would also be interesting, in order to confirm the results obtained in this chapter in more general settings.

Chapter 2

Evaluation of Bandwidth Network Prediction Algorithms

Introduction

In many Internet applications, network awareness is an important part of achieving good performance or lowering resource usage. In the case of delivering video on demand [START_REF] Suh | Pushto-peer video-on-demand system: Design and evaluation[END_REF], or performing peer-assisted streaming [START_REF] Liu | Performance bounds for peerassisted live streaming[END_REF] for example, estimations of available bandwidth allow the construction of an efficient overlay topology (e.g. SplitStream [START_REF] Castro | SplitStream: high-bandwidth multicast in cooperative environments[END_REF]). In this chapter, we cover the topic of estimating available bandwidth between the nodes located in the network. We present systems (centralized algorithms and their decentralized versions), that can be deployed onto the platform and allow us to ask for estimated available bandwidth between any two given nodes. Such a system should take into account the dynamic nature of the network, nodes entering or leaving.

In many applications (such as content delivery or video streaming), large amounts of data need to be exchanged between nodes, making available bandwidth the important metric for application performance. However, as we saw in Chapter 1, it is often not desirable to perform explicit endto-end path measurements because of the high cost of such measurements. Single measurements are both time and resource consuming, and exhibit large discrepancy. Moreover the number of possible scenarios that should be covered by measures grows quickly with the size of the platform, typically as N 2 , where N is the number of nodes in the platform. The solution provided should take care of a dynamic nature of the platform, e.g. nodes added or leaving. Also, the dynamic of the network itself is another challenge that a naive approach has trouble dealing with, as the edges can change its throughput in time or new edges can appear thus changing topology of the networks.

In the light of problems stated above, and in order to perform resource optimization in large scale platforms, it is thus necessary to summarize the network performance in the platform, in a way that providing such a summary can be done with a reasonable amount of measurements. In a topic of the latency-awareness, this idea has led to the design of Network Coordinate Systems (NCS), which embed the nodes of the platform in a metric space. Appropriate metric spaces and efficient algorithms have been proposed for estimating latency over the Internet (Vivaldi [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF] is a good example). The idea of designating some nodes as a landmark nodes lead to the Global Network Positioning (GNP) system, which embeds subset of nodes into a (high) dimension Euclidean space [START_REF] Ng | Global network positioning: a new approach to network distance prediction[END_REF]. High dimension required for successful Euclidean embedding gave rise to the hyperbolic spaces embeddings [START_REF] Shavitt | Hyperbolic embedding of internet graph for distance estimation and overlay construction[END_REF]. Such systems should capture the large-core and long-tendrils structure of the Internet. A study measuring hyperbolicity, and treewidth of the Internet [START_REF] Montgolfier | Treewidth and hyperbolicity of the internet[END_REF], resulting in a finding a large, well connected, inseparable core of the Internet (large treewidth), and high hyperbolicity (so the peripheral Internet tends to be separated from each other). Main problem with metric space embeddings are the triangle-inequality-violations: a situation where a direct distance measured between two nodes A and B is larger than sum of two distances between a third node C and both of nodes A and B. Works measuring the range and effect of the phenomenon have been done, and solution by weakening the distance function into a inframetric has been proposed [START_REF] Fraigniaud | The inframetric model for the internet[END_REF]. Another worth noting solution is Sequoia [START_REF] Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF], which tries a different approach of embedding network into tree structure. The tree Sequoia embeds is built from virtual nodes, that does not necessarily reflect physical network infrastructure, and only leaves of the tree reflect actual network nodes.

As we will see in Section 2.2, the metric space embedding is an approach that translates poorly into the bandwidth estimation, and a new approach is required. In order to predict bandwidth, our main focus in this chapter is on the LastMile model [START_REF] Beaumont | Using the last-mile model as a distributed scheme for available bandwidth prediction[END_REF] and on Decentralized Matrix Factorization (DMF) [START_REF] Liao | Network distance prediction based on decentralized matrix factorization[END_REF]. Both are good candidates for available bandwidth prediction algorithms, mainly because they are able to give asymmetric estimation, which is impossible for all NCS based on a metric space embedding. In Section 2.2 we will discuss several other prediction algorithms (Vivaldi, Sequoia, Iterated LastMile).

In Section 2.3, we analyze the estimation precision of both DMF and LastMile algorithms, based on measurements datasets obtained on PlanetLab from S-cube [START_REF] Yalagandula | S3: a scalable sensing service for monitoring large networked systems[END_REF]. We show that matrix factorization techniques are quite efficient at predicting point-to-point available bandwidth. Last-Mile provides slightly less accurate estimation, but we also provide a variant of the algorithm which improves the predictions quality and provides ones comparable to DMF ones. Both DMF and LastMile outperform previously existing algorithms.

Then, in Section 2.4, we go beyond estimation of point-to-point performance and address the problem of congestion. The challenge is: is it possible to predict the performance obtained when several communications take place at the same time? When several large communications take place at the same time, they are expected to interfere with each other. Being able to predict and model these interferences is crucial for optimizing the resource usage of an application. On the one hand, algorithms like DMF or Sequoia do not seem to easily deal with such scenarios. On the other hand, the LastMile model actually specifies that communications can happen in parallel, as long as both the outgoing and the incoming bandwidth limits of each node are fulfilled. In this chapter, we evaluate performance of bandwidth prediction algorithms on a data described in details in Chapter 1, that is bandwidth sharing data, a dedicated measurements performed on PlanetLab specifically to study this question. Using this data, we show that LastMile allows to perform this prediction with a reasonable accuracy.

The Chapter 3 will cover the topic of algorithms constructing an efficient overlay networks for such a platform, under the assumption that LastMile model applies.

Network Prediction Algorithms

In this section, we present different models for network predictions. Several models have been developed for latency estimations (Vivaldi, GNP, DMF). We also present models for general network distance estimation (Sequoia). In such a situation, one tries to estimate the general network distance function d, that can be defined either in terms of latency

d(C i ,C j ) = latency(C i ,C j ) or in terms of bandwidth d(C i ,C j ) = 1 BW (C i ,C j ) or d(C i ,C j ) = maxbw -BW (C i ,C j ).
With this transformation in mind, we can even try to apply latency estimation into the bandwidth estimation (for example we will do such with DMF). The only model designed purely for bandwidth is the LastMile model.

Network Coordinate Systems have received a lot of attention recently, especially in the context of latency estimation. Original systems, like GNP [START_REF] Ng | Predicting internet network distance with coordinates-based approaches[END_REF], relied on landmarks to make the predictions -landmarks are special nodes whose positions are computed first, and all nodes of the system compute their position with respect to these landmark nodes. Afterwards, more distributed systems, like Vivaldi [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF], have been designed, in which all nodes have the same role, leading to more precise and robust estimations. The term Network Coordinate System comes from the fact that all those systems embed the nodes in a metric space, hence assigning coordinates to all nodes, and use the distance in this space as an approximation of latency.

A notable exception to this is the Matrix Factorization [START_REF] Liao | Network distance prediction based on decentralized matrix factorization[END_REF] technique, in which the rationale is to approximate the distance matrix by a low rank matrix by assigning a column and a row vectors to all the nodes of the system. Matrix Factorization has been originally designed for latency estimation [START_REF] Mao | Modeling distances in large scale by matrix factorization[END_REF], and later extended to estimate network performance classes [START_REF] Liao | Decentralized prediction of end-to-end network performance classes[END_REF]. However, in this chapter we are interested in estimating available bandwidth, and it seems natural to observe how well Matrix Factorization performs in this context.

Another exception to this is Sequoia, in which the algorithm tries to embed the nodes of the network into one or several (virtual) trees. Sequoia has been the first attempt to provide bandwidth estimation, but in fact it provides general network distance estimations. Plenty of work [START_REF] Montgolfier | Treewidth and hyperbolicity of the internet[END_REF] has been done in the area of treeness, as well as the connectivity of the Internet, measuring various metrics of the Internet.

Hyperbolic space has been proposed as a replacement for the Euclidean space embeddings. The rationale behind this is that when trying to embed Internet into the Euclidean space, one has either to choose high dimension of the space, or suffer from the problem of having not enough space on the periphery to represent ending nodes of the network as having high distance between themselves.

Shape of the Internet

In this section we will present various results of experiments performed to define the "shape" of the Internet. Those results, while not applicable in a small scale solutions (platforms deployed locally), are important when designing solutions working not in an arbitrary network, but in a geographically distributed hosts deployed over the Internet, e.g. peer-to-peer networks or live streaming.

An experimental evaluation measuring the treewidth of the Internet has been done [START_REF] Montgolfier | Treewidth and hyperbolicity of the internet[END_REF]. An evaluation was performed on the experimental datasets, obtained as follow. For a router level, a set of Internet hosts (IP addresses) was chosen. For those hosts a connectivity graph was obtained, containing as vertices both hosts and intermediate nodes. Paths were discovered using traceroute utility tool. For Autonomous System (AS) level, the IP interconnections between two IP addresses can be used to infer an AS interconnection between two ASes who advertise IP prefixes (such links are observed at the BGP routing level or at IP level).

A tree decomposition of G = (V, E) consists of a tree T and a subset V t ⊂ V associated with each node t of T (called a "bag"), that satisfies following properties

• every node of G belongs to at least one bag of T ,

• for every edge e ∈ E, there is a bag V t containing both ends of e,

• the collection of bags containing a given node of G induces a connected subtree of T .

The width of the tree decomposition (T, {V t }) is defined to be one less than the maximum size of a bag. The Treewidth of the G is the minimum width of a tree decomposition of G. Intuitively, a treewidth of a graph answers the question of how far away the structure of the graph is from the tree one. Calculating of exact value is NP-complete, however heuristic approach can be applied to get bounds on the value. Treewidth can be seen as a measure of the global connectivity of the graph. Tree has treewidth of 1, while n vertices grid graph has a treewidth of √ n. Treewidth of connectivity graphs described as above show follows the growth of treewidth(G) ≈ √ n, which means that a rather large number of vertices need to be removed from the graph to disconnect it. That is a strong evidence for existing of a well connected core of the Internet, composed of a small set of very well connected set of hosts.

Another evaluation of the Internet graph (with distances defined as a number of hops), was performed as follow. Hyperbolicity of a graph G, denoted as δ (G) is defined as follow: first, for arbitrary quadruple of nodes x, y, z,t, we define:

δ (x, y, z,t) = d 1 -d 2 2 ,
where

d 1 ≥ d 2 ≥ d 3 are sorted in a nondecreasing order values of d(x, y) + d(z,t), d(x, z) + d(y,t), d(x,t) + d(y, z).
Then, we simply define δ (G) = max x,y,z,t δ (x, y, z,t). Hyperbolicity measures how far graph is from the tree. Even stronger finding is that, if one takes not max, but the average over all quadruples of pairs, that the average hyperbolicity is relatively small. The conclusion of the measures is that the distances (in hop counts) between any four hosts in the Internet is on average behaving like they were vertices of a tree, with almost all quadruples having δ (x, y, z,t) either 0 or 1.

Symmetry violations

One of the major steps in improvement over bandwidth predictions was moving from symmetrical algorithms to asymmetrical ones. It is no longer a valid assumption, that BW(C i ,C j ) ≈ BW(C j ,C i ), while it was a valid assumption for latencies. On Figure 7, we present a CDF plot of an asymmetry ratio (a relative error between two symmetrical measured bandwidth) taken for all possible pairs:

max BW (C i ,C j ) BW (C j ,C i ) , BW (C j ,C i ) BW (C i ,C j ) .
So, we in fact plot what fraction of pairs have the error equal-or-less than a given value. As we can see, errors can be of a rather large magnitude. For example, in S 3 dataset, 40% of values measured differ by a factor 4 or larger from their symmetrical counterparts, and almost 20% have a factor 9 or larger. This means, that the best we can hope for when estimating using symmetrical algorithm, is that for 40% values measured we will have an error of a factor 2 or larger, and that for 20% values measured we will have an error of a factor 3.

Global Network Positioning

Global Network Positioning (GNP) was the first proposed network prediction system. It models the Internet as an Euclidean space, where any end host is assigned coordinates [START_REF] Ng | Global network positioning: a new approach to network distance prediction[END_REF]. Small number of distributed hosts called landmarks measure inter-landmark distances. The system then computes the coordinates of each landmark in the Euclidean embedding, by minimizing the discrepancy between measured distances and computed distances. Each host in the platform knows the landmark nodes, and their coordinates. When localizing itself in the network (for example, node enters the network), node has to measure its actual distance to each landmark. Node then computes its own coordinates that minimize the overall discrepancy between measured distances to the landmarks and computed distances. Actual performance of the algorithm depends on policy of choosing landmarks. Experimental evaluation shows that it achieves reasonable predictions on latencies. But the dimension of the Euclidean space has to be set to at least values of d = 7.

Vivaldi

Vivaldi was presented first in [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF], and is a latency prediction algorithm. It is meant to be simple and lightweight algorithm for assigning a synthetic coordinates to the hosts. Basic idea that the algorithm was developed around is embedding the hosts into an Euclidean metric space, to mimic the geographic-related behavior of a large scale Internet.

Vivaldi works by searching for coordinates x 1 , . . . , x n minimizing the value of an error function:

E = ∑ i, j L i, j -x i -x j 2
for a given L as an input matrix. Minimization is performed by mass-spring simulation. Based on Hooke's law, for each pair of nodes i, j, the force generated by j on i by the displacement of the spring connecting them is:

- → F i, j = L i, j -x i -x j × u(x i -x j ).
Note that u ( -→ v ) is the unit vector in the direction of -→ v . The algorithm simulates the "movement" of the nodes in the parameter space, by calculating total force at each step of iteration -→

F i = ∑ j - → F i, j
and by simulating the small progression of time

x ′ i = x i + δt • - → F i .
Algorithm is adapted to work with a partial input matrix, and it handles in an easy way updates of information. It can be also easily adapted into a decentralized environment, where each node computes its own coordinates, and performs its own set of measures. This way the algorithm can also handle the changing environment and other nodes joining/leaving the network.

The general algorithm presented here can be adapted to a various metric spaces. It works best, when the metric space is an Euclidean one paired with directionless height assigned to each node, that is included to capture latency overhead on the access links of single-homed hosts.

Sequoia

In general, algorithms specialized in latency predictions have poor performance when applied to bandwidth estimations. Sequoia was the first attempt to develop bandwidth estimation algorithms [START_REF] Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF], but it can be used for latencies also. It uses the notion of distance between two nodes of the network, being it either the latency measure, inverse bandwidth measure, or constant minus bandwidth measure. Note, that the distance is not necessarily a metric distance, as it can violate triangle inequality, having

d(C i ,C j ) > d(C i ,C k ) + d(C j ,C k )
In fact, various analysis of latency datasets show that between 10% and 40% of triplets violate the triangle inequality [START_REF] Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF]. We also have seen previously that bandwidth distance also violates symmetry, having

d(C i ,C j ) = d(C j ,C i ).
Sequoia relies on embedding network latency and bandwidth onto trees, using the notion of prediction trees, where end hosts at the leaf level connected via a network of virtual inner nodes model latency or bandwidth. This work differs from system trying to reconstruct internal topology of the Internet, in the sense that it operates using virtual nodes, that doesn't necessarily reflect existing gateways and routers. Sequoia virtual trees could be used to construct a hierarchically organized distributed system if required.

For each virtual tree, Sequoia designates one node as a lever, that acts as a reference for the tree. It means that for every other node in this tree, the distance in the tree between this node and lever is the same as real-life measured metric (bandwidth or latency, depending which one we are estimating).

In each virtual tree Sequoia chooses another node, named anchor. Having lever R, anchor A, while adding node C i , algorithm will try to preserve exact distances d(R, A), d(R,C i ) andd(A,C i ).It achieves it by connecting C i to the tree through new virtual node S on a path connecting R and A, such that it preserves all three distances. The node S should be selected that

d(s, R) = 1 2 (d(A, R) + d(C i , R) -d(A,C i )) .
The virtual construction proposed above has one disadvantage, that is the trees constructed there are of very poor structure (path with attached single edges). That is why Sequoia itself uses another abstraction, called anchor trees. It represents exactly the same set of predictions as corresponding prediction tree, but is a well balanced structure. It does not use virtual nodes, and network nodes can be intermediate nodes in the tree. On those type of trees, every operation (joining/leaving of a node, new measurement) can be performed with a time efficient computation.

A different architecture version of the algorithm have been proposed [START_REF] Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF], ranging from fully centralized one, through partially centralized (one machine builds prediction trees, machines can perform queries by itself), to fully decentralized one.

An advantage of Sequoia is that it mimics the treeness of the Internet in its prediction trees. Another strong point is that it does not assume much about the distance on the network, and works fine even on datasets with a lot of triangle-inequality-violations. The applicability of the algorithm to any form of network distance is an advantage, as the system is very generic, but it is also a source of disadvantage, as Sequoia does not use any specific properties of bandwidth measurements and bandwidth related metrics. This proves important when we compare the performance of Sequoia to other, more bandwidth-specific algorithms.

Decentralized Matrix Factorization

Matrix Factorization (MF) has recently been proposed as a novel approach for distance estimation in the Internet [START_REF] Mao | Modeling distances in large scale by matrix factorization[END_REF]. This approach strongly differs from other models, as it does not attempt to make any assumption on the underlying network. Rather, the objective is to approximate the bandwidth matrix (i.e. the n by n matrix M such that M i, j is the measured available bandwidth between C i and C j ) by a low rank matrix. In MF, we thus search for matrices P and Q (of dimension n × d and d × n respectively, where d is a fixed parameter) such that the product P × Q is "close to" the measured matrix M . If the closeness property is defined by the quadratic error

err(P, Q) = ∑ i, j (M i, j -(P × Q) i, j ) 2 ,
then optimal P and Q can be computed from M by SVD (Singular Value Decomposition), or by iterative optimization if some values are missing.

A fully distributed algorithm has also been proposed [START_REF] Liao | Network distance prediction based on decentralized matrix factorization[END_REF], [START_REF] Liao | Dmfsgd: A decentralized matrix factorization algorithm for network distance prediction[END_REF], named DMF, in which each node is in charge of its own values in matrices P and Q, and iteratively, nodes optimize their values based on the current values of their neighbors. The algorithm uses method named Stochastic Gradient Descent (SGD), founded on the stochastic optimization theory. The decentralized setting features neither requirement for explicit construction of matrices nor special landmark nodes and central servers. The network nodes exchange messages with each other, and matrix factorization is collaboratively and iteratively achieved at all nodes.

It has been shown experimentally that this algorithm converges [START_REF] Liao | Dmfsgd: A decentralized matrix factorization algorithm for network distance prediction[END_REF], and gives actually better latency estimates that Vivaldi algorithm; this algorithm has also been used to perform classification of paths in either "good" or "bad" performance [START_REF] Liao | Decentralized prediction of end-to-end network performance classes[END_REF]. As far as we know, there is no experimental evaluation validation of DMF for bandwidth estimation.

LastMile

The LastMile model [START_REF] Beaumont | Using the last-mile model as a distributed scheme for available bandwidth prediction[END_REF] was derived with aim at simplicity and easiness of derivation of algorithms operating on it. The LastMile model is based on the assumption that contention only happens at the periphery of the network (on the "last-mile" link that connects each participating node to the core network). This assumption is realistic in many scenarios (like for example when the system consists of home computers connected to the network by DSL connections), hence this model has been used in several studies to design or analyze communication algorithms for video-on-demand [START_REF] Bonald | Epidemic live streaming: optimal performance trade-offs[END_REF], peer-assisted streaming [START_REF] Liu | Performance bounds for peerassisted live streaming[END_REF] or master-slave tasking [START_REF] Beaumont | Allocation of clients to multiple servers on large scale heterogeneous platforms[END_REF].

The LastMile model assigns to each node C i an outgoing bandwidth b out i and an incoming bandwidth b in i , and then the available bandwidth between two nodes BW (C i ,C j ) can be estimated by LM(C i ,C j ), which by definition is equal to

LM(C i ,C j ) = min(b out i , b in j ).
Below, we present experimental evidences for the correctness of the LastMile model. If we take a fixed node C i (that has associated value of b out i ), and look at all the predicted bandwidth values "to" all the possible nodes C j (with associated values of b in j ), the value treated as a function of b in j , is either equal to b in j (for values of b in j smaller than b out i ), or is equal to a (constant) value b out i (for values of b in j greater than b out i ). On the Figure 8 we show evidence supporting that behavior described above takes place. We plot there, for a selected node, all the values of outgoing measured bandwidth, sorted. On the left plot, we see that smallest 50 values resemble even distribution of values. We also see that 50th Plots taken from [START_REF] Beaumont | Using the last-mile model as a distributed scheme for available bandwidth prediction[END_REF].

smallest value is very close to the 300th one, and only few values marginally exceed that value. We interpret it as the outgoing bandwidth of that node is limited by a value, and it determines the speed of connection for all connections except 50 smallest ones, where the other node limitations determine the speed.

The plot on the right of Figure 8 shows a different behavior, with few values greatly exceeding the speed limit we could otherwise infer. We can explain this fluctuation by a few nodes being in a very close network proximity, for example the same campus network, or other WAN.

Basic LastMile

LastMile bandwidth estimation algorithm is a simple approach to calculating the corresponding values of b out , b in . It relies on the fact, that in the scenario where measured values BW (C i ,C j ) are perfectly predicted by LM(C i ,C j ) calculated as above, we would have

b out i = max j LM(C i ,C j ), b in j = max i LM(C i ,C j ).
This finding gives us a first initial assignment of

b out i = max j BW (C i ,C j ), b in j = max i BW (C i ,C j ).
However, such a setting is potentially dangerous, as only one bogus measurement is enough to obtain wrong prediction for a node. Furthermore, the last-mile assumption is not always satisfied in practice, as it may happen that some nodes share a bottleneck link. This observation motivates the removal of a few extremal values before computing b out and b in values. The solution proposed is to define b out i an (1-α) percentile for some small α constant, of all measured values BW (C i ,C j ). This solution is a generalization of previous approach, with α = 0 reducing it to taking max.

Iterated LastMile

In order to improve on basic LastMile algorithm, a following approach, similar to Vivaldi approach, is proposed. We will iteratively change the values of b out and b in , to minimize the value of:

E = ∑ i, j BW (C i ,C j ) -LM(C i ,C j ) 2 .
Particularly, substituting b out i as x, above takes the form:

E(x) = const + ∑ j min(x, b in j ) -BW (C i ,C j ) 2
for which calculating value of x minimizing above function can be done in O(n) time.

By iterating above steps, we eventually end with a set of new values b out and b in , which give us optimal values of LM(C i ,C j ) in the sense of square-sum-difference from BW (C i ,C j ).

Evaluation of point-to-point Prediction Algorithms

In this section, we present an evaluation of the precision of LastMile (both in its plain and iterated versions, as described in 2.2.7) and DMF, obtained using a software named bedibe (which itself will be described in a Section 2.5).

Comparison methodology

There are many ways to measure the efficiency of a bandwidth prediction system. On the one hand, we should be able to compare the predictions to the actual data, and on the other hand, be able to simulate fact that algorithms are only given partial data. Our methodology involves taking a (possibly) full matrix of measurements M, and taking a partial measurement M ′ . Algorithm returns prediction matrix P(M ′ ). We can then calculate some metric d(M, P(M ′ )). For example, we could use:

d(A, B) = ∑ 1≤i, j≤n (A i, j -B i, j ) 2
However, one downside of a single value metric is that it does not give us insight on detailed performance of an algorithm. To remedy this problem, we use different evaluation technique. To evaluate the precision of estimation algorithms, we use the standard relative error metric, which is defined as e = max( p v , v p ), where p is the predicted value and v is the actual measured value. This relative error is computed for every corresponding pair of matrix elements, and we are interested in the distribution of all relative error values on all pairs.

DMF and LastMile

In our comparisons there are two datasets used: the first one is a snapshot of the PlanetLab platform of April 2th, 2010 taken from the (now discontinued) S-cube project [START_REF] Yalagandula | S3: a scalable sensing service for monitoring large networked systems[END_REF], which contains available bandwidth measurements between 426 hosts, with many missing measurements, and we extracted a set of 308 hosts for which the complete measurement matrix was available. The second one is obtained with bedibe measurement methodology (described in Section 1.4), and contains achievable TCP throughput between 50 hosts of PlanetLab. In this dataset, about 17% of measurements are unavailable. In order to account for the fact that performing all end-to-end measurements is not reasonable in a practical setting, a subset of 20% of values are randomly chosen and given to the estimation algorithms. Note however that algorithms provide estimations for all values, and that the relative errors are computed on the whole matrix (for comparison, we also provide plots how algorithms perform given full matrix as an input). These results are shown on Figure 9, where we plot the Cumulative Distribution Function of relative error for each estimation algorithm. For example, a point at coordinates (1.5, 0.8) for DMF on the S-cube dataset means that for this dataset, 80% of all source/destination pairs are predicted with an error below 1.5. Hence, plots closer to the upper left corner of the graph represent better estimations.

The analysis of Figure 9 shows several facts. On the S-cube dataset, DMF (with d = 10) clearly outperforms other algorithms, and provides reasonably good predictions, even when partial information only is available. Matrix Factorization technique is actually a very strong approach, as it packs the necessary information (measurement matrix) in the least available space. We expect DMF to consistently outperform other methods.

We can also see, as in [START_REF] Beaumont | Using the last-mile model as a distributed scheme for available bandwidth prediction[END_REF], that the iterated improvement of LastMile helps to obtain better predictions, but the improvement is not that significant.

On the bedibe dataset, DMF is only able to provide reasonable predictions if given the full matrix, and its performance drops by a large factor when given only partial data. The precision of LastMile suffers a much smaller drop and outperforms DMF on partial data. We suspect it is the result of sensitivity to the parameter selection of DMF, as bedibe dataset is small in size in comparison to S 3 one.

The bedibe dataset is harder to estimate than the S-cube dataset: the 80th percentile relative error is less than 1.5 for all algorithms on the S-cube dataset, but is around 2 for the bedibe dataset. It is worth remembering that S 3 dataset measured available bandwidth, but bedibe one measured throughput. Also, S 3 one was obtained using external tools, while bedibe one using the bruteforce approach. We believe it leads to less self-correlation, more noise and less smoothness of the bedibe dataset, making it overall harder to estimate. Size of the dataset also makes difference, as larger datasets should be more self-consistent.

Evaluation of one-to-many Prediction Algorithms

In this section, we study the possibility to predict the total achievable throughput when a sending node sends data to several receiving nodes. Being able to predict how the bandwidth is shared between several connections, or how the network behaves in the case of congestions is important, as single isolated connections are an artificial assumption. Congestion can happen in various different scenarios:

• at the first edge of connection, i.e. one node sending to several nodes at once,

• in the middle of connection (the general case),

• at the last edge of connection, i.e. one node receiving from several nodes at once.

In light of all the experimental evidences supporting LastMile, it seems reasonable to consider only first and last case, as those cases are most likely to cause congestion. Also, experimental evaluation of congestion happening in the middle seems out of our reach.

As we have seen in the Sections 2.2.2 and 2.2.1, Internet seems to be dominated by asymmetrical links connecting peripheral nodes to the core Internet, with download dominating over upload capacity. This way it seems reasonable to experimentally evaluate the case where the congestion is going to happen on the sender side, as two receivers are more likely to saturate one sender than in the opposing scenario. By similar argument we restrict ourselves to the case of two receiving nodes, because this is already enough to achieve congestion and thus obtain meaningful results.

For this study, we use both bedibe datasets described previously, in Section 1.5.2. The datasets were collected on the PlanetLab platform, by selecting at random three nodes, one as a sender, two as a receivers, and measuring the achieved bandwidth to both of the receiving nodes when establishing connection simultaneously and trying to push as much as possible data. For all the nodes used in this experiment, we also have full matrix of point-to-point bandwidth measurements, so we are able to look at what LastMile algortihms or DMF can deduce from the matrix and compare it to actually achieved measurements.

We will try to predict the value T T i, j,k , being the amount of data node i is able to transmit to nodes j and k simultaneously. The reasoning behind this is that, as seen in the Section 1.5.2, total throughput achieved by the sender has smaller variability than the individual values per each receiver.

For this prediction, we tried several possibilities:

• LastMile: we compute LastMile values (incoming and outgoing parameters) for all nodes, and we use the LastMile assumption to predict the available bandwidth: it is either limited by the sending capacity of the sender, or by the sum of the receiving capacities of the receivers:

P LM i, j,k = min(b out i , b in j + b in k ).
• Avg, Sum, Max: we use end-to-end individual measurements between the sender and each of the receivers, and use the average, total, or maximum value as a prediction:

P avg i, j,k = BW (C i ,C j ) + BW (C i ,C k ) 2 P sum i, j,k = BW (C i ,C j ) + BW (C i ,C k ) P max i, j,k = max(BW (C i ,C j ), BW (C i ,C k ))
• AvgDMF, SumDMF, MaxDMF: we compute the DMF predictions for the available bandwidth between the sender and each of the receivers, and similarly use the average, total, or maximum value as a prediction.

P avgDMF i, j,k = DMF(C i ,C j ) + DMF(C i ,C k ) 2 P sumDMF i, j,k = DMF(C i ,C j ) + DMF(C i ,C k ) P maxDMF i, j,k = max(DMF(C i ,C j ), DMF(C i ,C k ))
For this analysis, we have set the dimension value of DMF to d = 5.

We then compute the relative error of each prediction, with the same definition as in Section 2.2:

e X i, j,k = max( T T i, j,k P X i, j,k , P X i, j,k T T i, j,k ).
To evaluate all prediction techniques, we thus analyze the distribution of the error ratios for all the measured triplets in our experiments. The results are shown on Figure 10, and mean and median values are reported in Table 1.

The results show that Sum and SumDMF provide very bad estimations. This comes from the fact that in PlanetLab nodes, the congestion often takes place at the sending node, even with only For the same reasons, MaxDMF also has a rather good median error ratio, not as good as Max because of the imprecisions incurred by DMF. However, in some cases Max and MaxDMF provide estimates which are off by a larger factor, whereas LastMile predictions are more stable, as can be seen by the lower mean error ratio.

It is important to note that in a practical setting, Max estimates can only be obtained by actually performing both individual end-to-end measures, whereas by design LastMile and MaxDMF can be computed for all possible triplets by using only a smaller number of measurements. Furthermore, from an algorithmic point of view, these results encourage the use of the LastMile model for the design of bandwidth allocation algorithms, even in settings where the "LastMile" assumption is not completely valid.

Bedibe

We aim at keeping our results accessible and reproducible. That is why we decided to make the datasets used in this work publicly available (https://gforge.inria.fr/frs/download.php/ 32092/data.zip). We also decided to make available the software package used for generating the results available.

bedibe is a tool for benchmarking bandwidth and latency estimations. We created it with a purpose of the development, testing, benchmarking and visualization of bandwidth estimation algorithms. It is written in Python, a very popular scripting language. It can be downloaded at http://bedibe.gforge.inria.fr/. Below in this section we provide motivation for creation of this tool, followed with technical details.

Our basic motivation for the creation of bedibe was to create an environment, where we could evaluate the performance of different network prediction algorithms in an automated way. When working on possible improvements to algorithms like LastMile, we found ourselves without either a unified collection of datasets, or implementations of algorithms that would work on datasets we had access to. Thus, the first step was to standardize the format of datasets (and convert existing other ones), and provide implementation of state-of-the art prediction algorithms. From then, we followed with providing ways to visualize results of prediction algorithm.

Data is read from CSV files (Comma Separated Values), with source and target hostnames, and measured values. For example we provide S 3 datasets (see Section 1.1.3) and our SPLAY datasets (see Section 1.4) in this format. Because network measures admit large variations, datasets often contain multiple values per pair of nodes. Because of this, we provide a set of functions for easily picking representative value or set of values (in case of fuzzy computation) from several of them.

We provide implementations of the state-of-the art estimation algorithms: DMF, LastMile, Sequoia, Vivaldi (described in Section 2.2). LastMile is provided in both its basic and iterated versions. We also provide our implementation of two-level LastMile. To further simplify implementation of the algorithms, we also provide a library of decorators (function transformation, idea borrowed from a functional programming paradigm) that for example, allow us to transform functions that operate on matrices into ones working in our environment of CSV style data. Other decorators allow easy control over what type of preprocessing an algorithm supports.

Estimations done by algorithms can be stored into CSV files, or used in several comparison tools. Our module for comparing allows easy comparison of the error ratio between different measures or estimations, or calculation of various standard metrics (stress, 80th percentile error. . . ). Visualization tools allow to create images out of the computed matrices (assigning different colors to high/low bandwidth, or accurate/inaccurate estimation). Additionally, a plotting module can be used to produce (using gnuplot) different types of plots, for example a CDF of the dataset, or a CDF of relative error of the estimates. Various parameters of the plots can also be customized from inside the code.

In summary, we created a tool that greatly simplifies the implementation of an algorithm, and with a few extra lines of code it allows the algorithm to be tested on datasets we provide, tweaked, analyzed or compared to other algorithms. Finally, the tool can be used to output plots useful for performance visualization. The plots provided in this thesis were generated using this tool. Below we provide an example of a python code used to generate plots in a scientific paper. The code shows how in a few lines, a program can read the dataset, prepare the partial dataset (by choosing subset of measurements), run a set of prediction algorithms on partial dataset and then generate the CDF plots of comparison between original dataset and prediction results.

Future works: improving LastMile

In this chapter we advocate for usage of the LastMile model when dealing with algorithmic problems related to bandwidth. One of the strengths of the LastMile model lies in its simplicity. This, and the fact that we are not predicting generic network distances, just bandwidth, gives us a lot of room for improving and tweaking the model and algorithms.

Our aim is to have a model that can give reliable predictions. But we also would like the model to reflect somehow real structure of the network. Our belief is that by using a network model that is close to the real life structure of the network, we could obtain better predictions. As we saw, opposite implication is not true: DMF gives very synthetic and abstract representation of the network, but does not give us any "knowledge" on the structure of the network. For every node of the network i, the model encodes its parameters as a vector v i . DMF states that prediction is the scalar product of the vectors,

DMF(C i ,C j ) = v i • v j .
It is hard to imagine a model of network that would lead us to such a prediction scheme, both for latencies and bandwidth.

Apart from DMF and LastMile, every other model we presented in this thesis is using somehow the ideas of metric, distance and embedding. This way of constructing predictions is a result of those models being created mainly with aim of predicting latencies. The intuition comes from the treating the latency as a measure of a distance signal has to travel in the network. This leads to the way we combine edges into the paths in those types of models:

dist(p) = dist(e 1 ) + . . . + dist(e k )
for a path p composed of edges e 1 , . . . , e k and where dist() represents the latency incurred by this path or edge.

If we translate previous equation by the usual way the generic network distance prediction algorithms translate latency to bandwidth, that is by taking inverse, we get:

1 BW(p) = 1 BW(e 1 ) + . . . + 1 BW(e k )
.

LastMile is based on a simpler principle, which we believe to be closer to the actual network:

BW(p) = min (BW(e 1 ), . . . , BW(e k )) .

Two-level LastMile

We discussed in Section 2.2.1 what structure the Internet exhibits when measuring various parameters, i.e. strongly interconnected core of the network, and larger peripheral network having more of a tree-like structure. LastMile model captures the second behavior (see Figure 11), but fails to take into account the structure of the core itself. Also, LastMile model fails to take into account the possibility of nodes sharing a bottleneck link (for example belonging to the same academic network).

In light of problems listed above, we would like to propose the following improvement upon the LastMile model, a two-level LastMile. The way the model works is to group existing nodes C 1 , . . . ,C n into k distinct sets G 1 , G 2 , . . . , G k . Let us name the function assigning node to the corresponding sets containing it a GID (a Group ID):

GID(C i ) = G j iff C i ∈ G j .
Our model can be represented as a graph of (see Figure 12): • virtual nodes G 1 , . . . , G k represent the core of the Internet, and they form a full clique graph with edges

(G i , G j ) for 1 ≤ i, j ≤ k,
• nodes C 1 , . . . ,C n represent the peripheral Internet, and they are connected to the core by the edges

(C i , GID(i)) for 1 ≤ i ≤ n.
Since each edge is weighted (in fact, it represents two directed weighted edges), our model reduces to a set of values b in

1 , b out 1 , . . . , b in n , b out n and a full k × k matrix F[i, j] for 1 ≤ i, j ≤ k.
The prediction of bandwidth between nodes i and j is

LM(C i ,C j ) = min(b out i , F[GID(C i ), GID(C j )], b in j ).
It is worth noticing that if we set k = 1, our model collapses back into LastMile model. On the opposite, if we choose k = n, we can then encode any n × n matrix into the G matrix. We suspect that setting k ≈ √ n is a fine choice, making the number of parameters of both parts of model equal.

Notice that if we have been given in advance the values of cluster, finding a best match for a given set of measurements is solvable by an algorithm analogous to the one used in Iterative LastMile Algorithm (Section 2.2.7). However, we could not find a "good" method to perform the clusterization step. On the one hand, assigning nodes to clusters at random resulted in very poor performance. On the other hand, performing any non-random clusterization requires ability to decide if nodes are close (so they should be in the same cluster) or distant (so they should be in different clusters), which brings us back to the problem of predicting network distance. Probably a new approach is required if we want to develop this idea further.

Conclusion

In this chapter, we analyzed the possibility to provide estimations for available bandwidth in large scale platforms. Estimation techniques and models exist for the latency metric, but their extension to available bandwidth is not always possible. We focused on the LastMile model, widely used as a communication model in algorithmic works, and on Decentralized Matrix Factorization (DMF), originally designed for latency estimation. We show that DMF is able to provide very good estimations for available bandwidth as well, but that its precision drops when fewer measurements are available.

DMF provides better bandwidth predictions than any other algorithm. That should not be surprising, as DMF is in some sense optimal as an algorithm to encode matrix in a compressed form of a low rank matrix. However, this performance comes at a cost, that DMF has no intuitive model underlying. It does not rely at all on the fact that the estimated values are bandwidth, and exactly the same algorithm is used for latencies. The LastMile model, on the opposite, was developed with bandwidth in mind. It assumes a certain model of the underlying network. That will prove advantageous in Chapter 3, in which we develop an overlay network construction algorithm for broadcast on large-scale platforms.

Furthermore, we analyzed contention in the presence of multiple simultaneous communications. We used data obtained from the PlanetLab platform, and we observed that the total throughput can be predicted by the LastMile model with a precision almost comparable to estimations based on the complete set of measurements. That is another strong point of LastMile based algorithms, as the model of the network it is based upon takes into account naturally the multiple simultaneous communications, and that is not the case for other algorithms.

We already saw, in Chapter 1, how to perform measures over network parameters (bandwidth, latency). In this chapter we covered the topic of efficiency of measures, e.g. that we do not need to measure every single edge in case of point-to-point measures. We were able to perform predictions over the network when we assumed a certain model of a physical behavior of the network. By assuming LastMile model, we were able to predict both point-to-point communications, and to a certain degree also congestions. A natural step would be to try and apply this model in a more general setting. However, as we move up in the layers of networking, we lose control over certain details of communication (e.g. routing). When designing large scale communication scheme over large networks (e.g. Internet), we are unable to control routes used by point-to-point communications. This situation shows a clear advantage that LastMile model have in such setting over other models, that is no matter what routing would be chosen for fixed point-to-point communications, links connecting node to a network are always used by this communication. Another advantage of the LastMile model is that it does not contain any assumption about the inner structure of network.

Chapter 3

Broadcasting over LastMile 3.1 Introduction

Context and Motivation

Data dissemination in distributed platforms has been the subject of a vast literature. The problem comes into two flavors, depending on the context. On the one hand, if the topology of the platform is known (in the case of computer networks or parallel machines for example), the goal is to organize data transfers so as to maximize the throughput (or minimize the makespan for a given message size). On the other hand, in the context of a large scale Internet level platforms, the goal is to find the topology (i.e. the overlay network) that maximizes the throughput.

The one-to-all broadcast, or single-node broadcast, is the most primary collective communication pattern: initially, only the source processor holds the data that needs to be broadcast; at the end, there is a copy of the original data residing at each processor. Parallel algorithms often require to send identical data to all other processors, in order to disseminate global information (typically, input data such as the problem size or application parameters). Numerous broadcast algorithms have been designed for parallel machines such as meshes, hypercubes, and variants (see among others [START_REF] Johnsson | Optimum broadcasting and personalized communication in hypercubes[END_REF][START_REF] Watts | A pipelined broadcast for multidimensional meshes[END_REF][START_REF] Tseng | Efficient broadcasting in wormhole-routed multicomputers: a network-partitioning approach[END_REF][START_REF] Massoulie | Randomized decentralized broadcasting algorithms[END_REF]).

The same framework applies for broadcasting a live stream of data, such as a movie or a TV show. In the context of content distribution systems, it is at the core of live streaming distribution systems such as CoolStreaming [START_REF] Zhang | CoolStreaming/DONet: A data-driven overlay network for peer-to-peer live media streaming[END_REF], PPLive [START_REF] Vu | Mapping the PPLive network: Studying the impacts of media streaming on P2P overlays[END_REF] or SplitStream [START_REF] Castro | SplitStream: high-bandwidth multicast in cooperative environments[END_REF]. In this case also, we are interested in the distribution of a large message to all the nodes of a large scale platform, made of a large number of computers, geographically distributed, and interconnected by the Internet. In the context of this work, it is thus not possible to obtain the actual topology of the core of the network, and we are rather interested in application-level solutions. Thus, the goal is to build an overlay network that makes the best possible use of the communication capabilities of all participating nodes, so as to maximize the overall streaming rate (once steady-state has been reached).

In the context of large scale Internet platforms, it is common to assume that the communication between two nodes is only limited by the available outgoing bandwidth of the sender and by the incoming bandwidth of the receiver. This assumption is also very suited to the case where nodes are connected to the Internet with low bandwidth links, like DSL for example. In that case, the bandwidth limitation is either physical (from the link capacity) or logically enforced at the user's request. In large scale platforms, it is also desirable to limit the number of connections that must be handled simultaneously at each node. Both of these assumptions are common in the context of data dissemination in large scale platforms. However, they fail to correctly model the behavior of the nodes located behind a NAT or a firewall. As we will see, adding this constraint on node connectivity capabilities strongly modifies both the algorithms and the theoretical results.

In previous chapters we justified LastMile as a network model. Because it deals with a problem of congestion, and discards any knowledge on inner structure of the network, LastMile model seems well suited for dealing with the problem of broadcasting over a network. In this setting, we will deal with an optimization problem, where each node has fixed limit on both incoming and outgoing bandwidth. We are interested in designing a communication scheme where we maximize the size of a message that one node is able to broadcast to all other nodes, in a steady streaming fashion (we discard in our analysis the notion of time, assuming that transmissions are defined by a rate of data transfer), while keeping limits imposed on bandwidth used by nodes. In our communication scheme, we try to use all available resources to a network, not only the upload of the source, by making other nodes exchange parts of original message in a peer-to-peer fashion. Secondary way to measure efficiency of the solution is to keep track of the number of nodes a given node has to communicate with, that is the degree of a node. We will both try to develop solutions with unconstrained degree, and with small degrees.

In this chapter, we use the notion of "acyclic" solution, meaning that the solution treated as a graph can be sorted topologically. By "cyclic" solution, we mean any solution, not just necessarily non-acyclic. The main novelty of our approach is the classification of the set of participating nodes into two parts: open nodes that stay in the open-Internet and "guarded" nodes that lie behind firewalls or NATs. Two guarded nodes cannot communicate directly, but rather need to use an open node as a gateway for transmitting a message. In the presence of guarded nodes our main contributions are a closed form formula for the optimal cyclic throughput and the proof that the optimal solution may require arbitrarily large degrees. In the acyclic case, we propose an algorithm that reaches the optimal throughput with almost optimal degree used. Then, we prove a worst case ratio between the optimal acyclic and cyclic throughput and show through simulations that this ratio is on average very close to 1, what makes acyclic solutions efficient both in terms of throughput maximization and degree minimization.

This broadcast problem was introduced in [START_REF] Beaumont | Broadcasting on large scale heterogeneous platforms under the bounded multi-port model[END_REF], however in a slightly different version, with nodes having both bandwidth and strict degree constraints, and open nodes only. The solutions provided are based upon resource augmentation, through relaxation of the degree constraint while still enforcing strict bandwidth constraint. Results from sections 3.3.1, 3.3.2 and Theorem 3.5.2 , where we prove that it is possible to reach the optimal throughput, at the price of a quasi-optimal (up to a small additive increase) degree of the participating nodes, are based upon [START_REF] Beaumont | Broadcasting on large scale heterogeneous platforms under the bounded multi-port model[END_REF], but reworked to a new setting without strict (independent from bandwidth) degree constraints.

In summary, our goal is first to design an overlay network and to determine the bandwidths associated to the edges of the overlay, such that both degree and capacity constraints are satisfied, such that nodes behind a NAT or a firewall use third party nodes to communicate and such that the overall throughput that can be reached using this overlay network is close to the optimal one. One of the major contributions of this chapter is to study, under a realistic communication model and for a classic communication scheme, the impact on the complexity and on the performance of the algorithms of having nodes lying behind NATs and firewalls.

Outline

Below we summarize the results presented in this chapter, in the context of previous results. We either provide new results, or adapt results from [START_REF] Beaumont | Broadcasting on large scale heterogeneous platforms under the bounded multi-port model[END_REF] into a modified model of degree constraints. 2. In the presence of open nodes only, the optimal acyclic throughput can be achieved at the price of a small linear increase of 1 in the degree of the nodes (see Section 3.3.2, where we recall results from [START_REF] Beaumont | Broadcasting on large scale heterogeneous platforms under the bounded multi-port model[END_REF]).

3. In the presence of open and guarded nodes, the optimal acyclic throughput can be achieved at the price of a small linear increase of 3 in the degree of the nodes (see Section 3.4, this is a new result).

4. In the presence of open nodes only, the optimal cyclic throughput can be achieved at the price of a small linear increase of 2 in the degree of the nodes (in Section 3.5, we briefly recall the result from [START_REF] Beaumont | Broadcasting on large scale heterogeneous platforms under the bounded multi-port model[END_REF]).

5. In the presence of open and guarded nodes, the optimal cyclic throughput can be achieved only with an unbounded increase in the degree of the nodes (see Section 3.5, this is a new result).

6. For any instance, the optimal acyclic throughput is at least 5/7 of the optimal cyclic throughput (see Section 3.6, this is a new result).

7. On average (see Section 3.6), for a wide variety of realistic scenarios, the throughput of the low degree acyclic solutions proposed by our algorithms are very close to the optimal cyclic throughput (at most 5% decrease).

Therefore, except in the cyclic case with open and guarded nodes, and despite the strong NP-Completeness result, it is possible to build low degree solutions that achieve optimal throughput at the price of a small increase in the degree bound. Moreover, if the complexity of proofs dramatically increases from the acyclic open case to the cyclic open case and to the acyclic guarded case, all proposed algorithms are very efficient in time complexity and can therefore be used in practice.

The situation strongly differs in the cyclic guarded case: since arbitrarily large degrees are required in order to achieve the optimal throughput, so that we cannot rely on small degree increases to obtain optimal performance. Nevertheless, we prove in Section 3.6 that the algorithm that returns low degree solutions in the acyclic guarded case is a 5 7 -approximation algorithm for the cyclic guarded case.

Models and Related Works

Platform Modeling

The bounded multiport model has already been advocated by Hong et al. [START_REF] Hong | Distributed adaptive task allocation in heterogeneous computing environments to maximize throughput[END_REF] for independent tasks distribution on heterogeneous platforms. In this model, node C i can communicate with any number of nodes C j simultaneously, each using a bandwidth c i, j , provided that its outgoing bandwidth is not exceeded, i.e., ∑ j c i, j ≤ b out i . Similarly, node C i can receive messages from any number of nodes C j simultaneously, each using a bandwidth c j,i , provided that its incoming bandwidth is not exceeded, i.e., ∑ j c j,i ≤ b in i . This corresponds well to modern network infrastructure, where each communication is associated to a TCP connection.

This model strongly differs from the traditional one-port model used in scheduling literature, where connections are made in exclusive mode: each node can communicate with a single node at any time step. But in the context of large scale platforms, in which the networking heterogeneity ratio may be high, it is unreasonable to assume that a 10GB/s server may be kept busy for 10 seconds while communicating a 10MB data file to a 1MB/s DSL node. Therefore, in our context, we will assume that all communications are directly handled at TCP level. Nevertheless, in order to keep the flavor of the one-port model, we will minimize the number of connections that need to be handled simultaneously at a given node. This constraint is particularly important in a context where QoS mechanisms are used to fix or bound the bandwidth associated to each communication (each TCP connection in practice). It is worth noting that at the operating system level, several QoS mechanisms enable a prescribed sharing of bandwidth [START_REF] Downey | Tcp self-clocking and bandwidth sharing[END_REF][START_REF] Abendroth | A versatile model for tcp bandwidth sharing in networks with heterogeneous users[END_REF][START_REF] Zhu | Enhancing tcp for networks with guaranteed bandwidth services[END_REF]. In particular, it is possible to handle simultaneously several connections and to fix the bandwidth allocated to each connection. In our context, it has been proved in [START_REF] Beaumont | On the importance of bandwidth control mechanisms for scheduling on large scale heterogeneous platforms[END_REF] that these mechanisms are necessary since the bandwidth allocated to the connection between C i and C j may be lower than both b out i and b in j . Therefore, the variant of the LastMile model we propose encompasses the benefits of both the bounded multi-port model and the one-port model. It enables several communications to take place simultaneously, which is compulsory in the context of large scale distributed platforms. Practical implementation is achieved by using TCP QoS mechanisms and by bounding the number of connections.

However, this model fails to correctly model the behavior of the nodes located behind a NAT or a firewall. This issue is crucial in the context of Peer-to-Peer applications running over the Internet. For instance, in distributed applications such as Skype [START_REF] Baset | An analysis of the skype peer-to-peer internet telephony protocol[END_REF][START_REF] Guha | An experimental study of the skype peer-to-peer VoIP system[END_REF] or Bittorent [START_REF] Jimenez | Connectivity properties of mainline bittorrent DHT nodes[END_REF], NATs play a crucial role, since in certain situations where "hole punching" techniques [START_REF] Srisuresh | State of peer-to-peer (P2P) communication across network address translators (NATs)[END_REF] fail, it can be impossible for a pair of nodes to communicate directly. In this case, the technique consists in using a third party node that acts as a relay for the packets. At a higher level, we can classify the nodes between open and guarded nodes, where open-open, open-guarded (and guarded-open) connections are possible, but not guarded-guarded. As we will see, adding this constraint on node connectivity capabilities strongly modifies the algorithms and the theoretical results.

Related works

Broadcast and streaming optimization have already been the subject of several studies in the literature. However, none of them has considered the constraint added by the presence of firewalls in the system. The work closest to our approach is by Liu et al [START_REF] Liu | Performance bounds for peerassisted live streaming[END_REF] in which they provide bounds for the streaming rate, the upload rate of the source needed to ensure a given stream rate, and the depth of the distribution trees produced. Degree constraints are also considered in their work, but with specific limitations. In particular, the degree of the source is not limited, and the degree constraint on nodes is considered separately for each tree of the solution, which means that the actual degree of each node is not limited.

More applied studies have been published, which focus on designing distributed algorithms to build the streaming overlay. For example, CoolStreaming [START_REF] Zhang | CoolStreaming/DONet: A data-driven overlay network for peer-to-peer live media streaming[END_REF] builds upon a gossip-based overlay to propose a distributed streaming algorithm. This algorithm inherently includes degree limitations, and provides a guarantee on the diameter of the overlay, but no guarantee about the streaming rate is available. On the other hand, SplitStream [START_REF] Castro | SplitStream: high-bandwidth multicast in cooperative environments[END_REF] is based on a distributed hash table and builds an overlay made of k different distribution trees, with a probabilistic guarantee on the streaming rate. Furthermore, SplitStream allows multicast (some nodes may only receive the data from a subset of the k trees -but they do not choose which part) and also includes a degree limitation, which is typically k times larger than the degree of our solutions.

Positioning

In this chapter, we assume that the network can be represented using the LastMile model. We already presented ways to obtain this representation in previous chapters.

Our contribution consist in computing, using this instantiated model, the overlay network (which nodes communicate together) and the bandwidths that should be allocated to each edge of the overlay in order to maximize the overall throughput of the collective communication scheme, given the bandwidth, the degree and the connectivity constraints of the network. The resulting weighted graph can be decomposed into a set of weighted broadcast trees [START_REF] Schrijver | Combinatorial optimization: polyhedra and efficiency[END_REF]vol B,Chapter 53]. This decomposition specifies which data should be sent on which edge at a given time step.

In order to avoid this decomposition step, which is difficult to use in practice, we rely on the randomized broadcasting algorithm proposed by Massoulié in [START_REF] Massoulie | Randomized decentralized broadcasting algorithms[END_REF]. This algorithm is fully decentralized and is even able to deal with small variations of resource performance due to its randomized and dynamic nature. This algorithm requires knowledge of the topology of the network with bandwidths on edges and no contentions on the nodes, which is in general not realistic. On the other hand, the overlay network that we build has exactly, by construction, these properties, provided that bandwidth sharing mechanisms are used for the communications in order to limit the bandwidth of a communication to the weight of the edge, such as proposed in [START_REF] Downey | Tcp self-clocking and bandwidth sharing[END_REF][START_REF] Abendroth | A versatile model for tcp bandwidth sharing in networks with heterogeneous users[END_REF][START_REF] Zhu | Enhancing tcp for networks with guaranteed bandwidth services[END_REF]. The overlay network that we build can therefore be used as direct input of Massoulié's algorithm.

Therefore, on the one hand by relying on measurements to instantiate the parameters of the LastMile model and on the other hand on Massoulié's algorithm to actually perform the broadcast operation, our algorithmic contribution provides a practical solution to the streaming problem whose approximations (due to the model, to the use of approximation algorithms for NP-Complete problems and to the decentralized and randomized implementation of the broadcast) can be rigorously analyzed and controlled. In this work, we focus on the approximation algorithms perspective.

Model and notations

We consider a situation in which a source node, denoted as C 0 , wants to broadcast a message. The recipients are partitioned into two sets: on the one hand some nodes belong to the open-Internet, and can communicate with each other freely (we call them open nodes); on the other hand some nodes can communicate only with nodes of the open-Internet, because they are behind a firewall or behind a NAT router (we call them guarded nodes). The source itself is supposed to be an open node.

An instance of our problem is specified by the number n and m of open and guarded nodes, and by the outgoing bandwidth b i of each node C i for i ∈ 0, n + m . The source node is C 0 , nodes C i for i ∈ O = 1, n are open nodes, and nodes C i for i ∈ G = n + 1, n + m are guarded nodes.

The output of the problem is a broadcast scheme, defined by values {c i, j |(i, j) ∈ 0, n + m 2 }, where c i, j indicates the rate at which node C i sends data to node C j , subject to the following constraints:

• ∀i ∈ 0, n + m , ∑ j c i, j ≤ b i (bandwidth constraint) • ∀(i, j) ∈ G 2 , c i, j = 0 (firewall constraint). 50 C 0 C 3 C 2 C 4 C 5 2 3 4 4 4 2 1 b 0 = 6 b 3 = 4 b 1 = 5 b 2 = 5 b 4 = 1 b 5 = 1 C 1
Figure 14: An acyclic broadcast scheme of throughput 4 on the instance of Figure 13. The order associated with this acyclic broadcast scheme is σ = 031245.

We implicitly assume that the input bandwidth of each participating node is large enough. The throughput of a broadcast scheme is given by T = min i∈ 1,n+m {max f low(C 0 → C i )}, where the flows are computed on the weighted graph described by the c i, j s. Furthermore, given a broadcast scheme, we can define the outdegree of a node C i as the number of nodes to which C i actually sends some data, i.e. o i = |{ j, c i, j > 0}|. Notations are illustrated in Figure 13.

As stated above, we want to provide broadcast schemes with small degree. To define what small degree may mean, let us note that in a solution of throughput T , the weight of any edge c i, j is at most T (indeed, receiving data at a rate larger than T is useless). Hence, if node i uses all of its outgoing bandwidth, then its outdegree o i is at least b i T and small degree therefore means o i close to b i T . A solution that achieves (a fraction of) T * by using an outdegree o i ≤ b i T * + d is thus a d-additive resource augmentation (approximation) algorithm. As a consequence, we do not consider strict degree constraints, but rather analyze the outdegrees used by our solutions in terms of b i T .

Computing a solution that achieves throughput T * and such that the degree of each node is at most b i T * turns out to be an NP-complete problem (see Section 3.3.1), even for the special case where all nodes are open (m = 0). We are thus interested in this chapter in approximate solutions, both in terms of throughput (with respect to T * ) and additive resource augmentation on the degrees (with respect to b i T * ). We prove that the situation differs if we concentrate on acyclic or more general cyclic solutions. A broadcast scheme is said to be acyclic if its communication graph (represented by the matrix c) is acyclic, which is equivalent to the existence of an order σ on the nodes such that

∀i, j ∈ 0, n + m , i > j ⇒ c σ (i),σ ( j) = 0.
This condition states that σ (i), the node at position i in the ordering σ cannot feed σ ( j), the node at position j, if i > j. Figure 14 shows an example of an acyclic broadcast scheme associated with the order σ = 031245.

For a given instance and a given order σ , we denote by T * ac (σ ) the optimal acyclic scheme compatible with the order σ . For a given instance, we denote by T * ac the optimal acyclic throughput:

T * ac = max σ T * ac (σ ).

Simple Case

As we have already noted, the problem comes into several flavors. Among the parameters that strongly influence the complexity of the problem are (i) the presence of guarded nodes (nodes behind firewalls) and (ii) the acyclicity of the solution, what leads to four different problems. In Section 3.3.1, we recall from [START_REF] Beaumont | Broadcasting on large scale heterogeneous platforms under the bounded multi-port model[END_REF] the proof that all four problems are NP-Complete. Because we use slightly different model, that leads to modified proofs, not using arbitrary degree constraints d i (that are not present in our model, but were present in [START_REF] Beaumont | Broadcasting on large scale heterogeneous platforms under the bounded multi-port model[END_REF]). In Section 3.3.2, we concentrate on the easiest case, i.e. the case where we are looking for an acyclic solution with open nodes only.

Complexity Results

Introduction

In the case where guarded nodes are present, some of the communications are forbidden, what makes the combinatorial structure of the problem more complex. On the other hand, searching for an acyclic solution limits the search space and we will see throughout this chapter that it actually makes the problem easier. Of course, cyclic solutions can achieve higher throughput than acyclic ones, but we will see later in Section 3.6, that this only holds up to a (small) ratio 5/7.

NP-Completeness

We prove in this section that the problem of finding an optimal allocation while satisfying the degree constraints (keeping o i ≤ b i T ) is strongly NP-Hard. We prove this result by reduction to the 3 PARTITION problem.

3 PARTITION: Let a i , 1 ≤ i ≤ 3p be 3p integers, such that ∑ 3p 1 a i = pT and ∀i, T 4 < a i < T 2 . Is there a partition of the a i s into p disjoint sets S j , 1 ≤ j ≤ p containing exactly 3 elements and such that each set sums up to exactly T ?

3 PARTITION is well-known to be NP-Hard in the strong sense [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NPcompleteness[END_REF]. Given a particular instance of 3 PARTITION, let us consider the following instance I of our problem (see Figure 15), in which all nodes are open.

• The source (the upper node in Figure 15) has outgoing capacity b 0 = 3pT ;

• 3p intermediate nodes (middle nodes in Figure 15), where ∀1 ≤ i ≤ 3p, b i = a i ;

• p final nodes (lower nodes in Figure 15), where ∀3p + 1 ≤ i ≤ 4p, b i = 0;

• The target throughput to achieve is T .

If a solution to the 3 PARTITION instance exists, then it is easy to build a solution to I : the source serves all intermediate nodes with rate T , and intermediate nodes that correspond to the same set S j serve a final node C 3p+ j at their full capacity (see Figure 15 Conversely, let us assume that there exists a solution to I . We first note that since the total outgoing bandwidth is exactly 4pT and 4p nodes need to receive the message at rate T , it is not possible to waste any bandwidth. Hence, the source necessarily sends data at rate exactly T (i.e. the maximal useful possible rate) to 3p nodes (i.e. the maximal number of clients since b 0 T = 3p), and each intermediate node C i sends data at rate a i (its maximal rate) to exactly another client (the maximal number of clients since a i T = 1). On the receiving side, at most 3p nodes are served by the source, and the intermediate nodes collectively serve the remaining p nodes (note that nodes served by intermediate nodes may be intermediate nodes themselves, so that the situation is slightly more complicated than depicted in Figure 15). Since no bandwidth is wasted, the sum of the weights of the incoming edges for such a node is exactly T . Furthermore, since ∀i, T 4 < a i < T 2 , there are exactly 3 such incoming edges. It is thus possible to build a solution to the original 3 PARTITION instance.

a 2 b 1 + b 3 + b 3p = T b 0 = 3pT b 1 C 0 C 1 C 3p C 3p+1 C 4p
Note that this NP-Completeness result applies to all four different situations. Indeed, let us first remark that considered instances only contain open nodes, so that the NP-Completeness a fortiori holds in (the more complicated case in) presence of guarded nodes. Second, we a priori search for a general cyclic solution but we nevertheless prove that the optimal throughput (for our instances) can be reached using an acyclic solution (see Figure 15), so that above proof also shows that finding the optimal acyclic solution is NP-Hard.

The problem belonging in NP follows from the fact that Maxflow in arbitrary graphs is in P (and therefore in NP). This plus strong NP-Hardness shown above gives desired NP-Completeness.

Acyclic Solution with open nodes only Introduction

We consider the simplest case, where all nodes are open and we search for an acyclic solution. As we have just proved it, despite its apparent simplicity, this problem is NP-Complete in the strong sense. Nevertheless, it is possible to achieve the optimal throughput at the price of a very small additive increase of the degree of the nodes. To establish this result, we recall the proof of an upper bound on the achievable throughput of any acyclic solution. Then, we recall exhibit an algorithm that achieves this throughput while keeping the degree of the nodes small. This algorithm is used as a starting point to build a cyclic solution for instances without guarded nodes in Section 3.5, and it introduces some of the ideas that will be later adapted in Section 3.4 for instances with guarded nodes.

Upper Bound

The first idea which will be used throughout the chapter is that nodes should be ordered by nonincreasing order of bandwidth. In the remainder, we will thus consider that nodes are ordered so that b 1 ≥ . . . ≥ b n and we will denote S k = ∑ k i=0 b i . In any acyclic solution, nodes can be sorted in topological order such that a node only feeds nodes with larger indexes. In particular, there exists at least one node that does not send data to any other node. Therefore, the overall throughput achieved by any acyclic solution T * is upper bounded by S n-1 n since b n denotes the smallest capacity and n nodes C 1 , . . . ,C n must receive the message at a rate T * . Additionally, it is clear that T * ≤ b 0 .

Algorithm

Let us now describe an algorithm that provides an optimal acyclic solution for instances without guarded nodes.

The algorithm takes as input T * = min(b 0 , S n-1 n ), and returns a broadcast scheme that achieves throughput T * . Let us first remark that since the b i s are sorted in non-increasing order, and since

T * ≤ b 0 , then ∀0 ≤ k < n, S k ≥ (k + 1)T * .
The basic principle of the algorithm formalized in Algorithm 1 is to satisfy (i.e. send a complete message to) the nodes one after the other (considered in the previously defined sorting order), while maintaining the property that after each step, at most one node receives the message only partially, i.e. all previous nodes receive the message at rate T * and all following ones do not receive anything yet. C i thus sends data to a consecutive set of nodes, say from C α i to C β i . All intermediate nodes, except possibly α i and β i , will be served at rate T * . Since the total bandwidth used by C i is b i , there are at most b i T * -1 such intermediate nodes. Hence the number of nodes served at least partially by C i , i.e. its outdegree, is at most b i T * + 1. The behavior of Algorithm 1 is depicted in Figure 16. Furthermore, this algorithm produces an acyclic graph. Indeed, before each step i, the property S i-1 ≥ iT * ensures that the bandwidth available so far (S i-1 ) is always large enough to satisfy all

C 0 C 3 C 4 C 5 T b 1 b 3 c 2,4 C 1 C 2
Figure 16: Solution returned by Algorithm 1. The upper part represents how the capacity of C i is used (in column i) and the lower part describes which nodes the data sent to C i (in column i) come from.

nodes from 1 to i. Hence, each C i will only serve nodes with strictly larger indexes (i.e. α i > i with above notations).

Algorithm 1 Acyclic Algorithm on open nodes only.

Set t = 1 and ∀i, r i = T * and ∀i, s i = b i for i = 0 to n do while s i > 0 do c i,t := min(r t , s i )

s i := s i -c i,t ; r t := r t -c i,t if r t = 0 then t := t + 1 end if end while end for
From above remarks, we can conclude that Algorithm 1 builds an acyclic communication graph such that each node receives exactly T * from nodes with smaller indexes and that the degree of C i is at most b i T * + 1. Therefore, Algorithm 1 returns a solution of optimal throughput in which nodes have a degree that is larger by at most an additive factor of 1 with respect to the lower bound. Clearly, given the strong NP-Completeness of the problem, Algorithm 1 returns the best achievable result, with respect to the additive degree increase (provided, of course, that P = NP).

Acyclic algorithm with guarded nodes

In this section, we describe how to build an acyclic broadcast scheme with a small increase in the degree constraint in presence of guarded nodes: For instances with guarded nodes, there is no closed formula for T * ac , but the algorithm of Theorem 3.4.1 can be combined with a dichotomic search (on T ) to find the optimal acyclic throughput.

The proof of Theorem 3.4.1 can be decomposed into three steps: we start by proving dominance relations in order to characterize optimal acyclic schemes (Lemma 3.4.3). We then provide an algorithm for testing if throughput T is achievable. If this is the case, a valid ordering is computed (Lemma 3.4.4). Then, we show how to compute a low degree solution from the computed valid ordering (Lemma 3.4.8).

Dominance relations

Before entering into the details of the algorithm, let us start with an intuitive property of ordering of nodes. An ordering σ is said to be increasing if its restriction to O is the identity on O, and its restriction to G is the identity on G . This means that nodes of the same color are ordered by non-increasing order on their bandwidth. The order σ = 031245 is an increasing order for the instance of Figure 14 whereas σ = 041235 is not increasing.

In Section 3.3, we have proved (in the open nodes only case) that good solutions can be built with increasing orderings, and the next lemma shows that this also holds in the general case. Proof. Let c be an acyclic solution with order σ which is not increasing. Then, there exist two indices x < y such that p = σ (x) > q = σ (y) (and thus b p ≤ b q ). We will exhibit another acyclic solution c ′ with order σ ′ = σ • (x, y) (where (x, y) denotes the transposition that exchanges x and y, which means that the nodes in position x and y are swapped) and whose throughput is not smaller than c. The transformation is depicted on Figure 17. For most indices i, j, it is sufficient to set c ′ σ ′ (i),σ ′ ( j) = c σ (i),σ ( j) . However, this would break the bandwidth constraint of node p = σ (x), and the solution is to give the connections in excess (denoted as E in Figure 17) to node q = σ ′ (x). Since x < y, this does not break acyclicity.

Recursively, we can thus transform any acyclic solution into an increasing acyclic solution with at least the same throughput.

An increasing order can be naturally encoded by a binary word π with n letters (corresponding to open nodes) and m letters (corresponding to guarded nodes): it is sufficient to specify if σ (i) belongs to O or to G . We denote by |π| the length of the word π, and by |π| (resp. |π| ) the

x y C q A B C D E x y C p C q A B C D E b p ≤ b q C p
Figure 17: Exchange argument for dominance of increasing solutions number of letters (resp. ) in π. For instance, the word π = encodes the increasing order σ = 031245 for the instance of Figure 14.

The notation π ′ ⊑ π (resp. π ′ ⊏ π) means that π ′ is a prefix (resp. a strict prefix) of π.

From now on, when no confusion is possible, π will be identified with its corresponding increasing order. For instance, T * ac (π) corresponds to the optimal acyclic throughput associated with the order encoded by π. A word π is said to be valid (with respect to an instance I and a throughput T ) if T * ac (π) ≥ T . A solution c is said to be conservative with respect to order σ , if there are no triplets of distinct indices i, j, k, such that i < k and j < k, σ (i) ∈ G , σ ( j), σ (k) ∈ O, and c σ ( j),σ (k) > 0 and ∑ k l=i+1 c σ (i),σ (l) < b σ (i) simultaneously. The idea behind this definition is to consider solutions that feed the open nodes from guarded nodes as soon as possible. Indeed, the firewall constraint prevents transfer from guarded nodes to guarded nodes: transfer from open nodes is thus a valuable resource, and it is a "waste" to use it to feed open nodes when it is not necessary. Figure 14 shows an example of a conservative acyclic broadcast scheme and Figure 18 shows an example of a non-conservative one.

This means that when creating a conservative solution incrementally (by satisfying the nodes in a given order σ ), there is no choice for the type of nodes that should feed the next node to add: a guarded node must be fed by open nodes (because of the firewall constraint), and an open node should be fed by guarded nodes as long as some of them have remaining outgoing capacity. Lemma 3.4.3. For every order σ there exists a conservative solution c that achieves T * ac (σ ).

Proof. Let c be a solution that achieves T * ac (σ ). If there exists a triplet of indices i, j, k that violates conservativeness, we can build a solution c ′ that is conservative with respect to these indices. Let 57

C 0 C 3 C 2 C 4 C 5 3 4 4 2 2 1 b 0 = 6 b 3 = 4 b 1 = 5 b 2 = 5 b 4 = 1 b 5 = 1 C 1 2 2
Figure 18: A non-conservative acyclic broadcast scheme: if we take i = 1, j = 0, k = 2, we see that node C 1 = C σ (k) could be totally fed by a guarded node

C 3 = C σ (i) , but it uses the open bandwidth of the source C 0 = C σ ( j) . γ = min(b σ (i) -∑ k l=i+1 c σ (i),σ (l) , c σ ( j),σ (k) )
, and set:

c ′ σ ( j),σ (k) = c σ ( j),σ (k) -γ c ′ σ (i),σ (k) = c σ (i),σ (k) + γ.
and as in the proof of Lemma 3.4.2, σ ( j) will be in charge in c ′ of the upload toward nodes σ (l) with l > k that the node σ (i) will no longer be able to feed in c ′ ; on all other indices c and c ′ coincide. It is easy to see that c ′ is a valid solution of the same throughput, and that the number of triplets of indices violating conservativeness is lower in c ′ . Recursively, we create a conservative acyclic solution with respect to order σ , with throughput T * ac (σ ). Given a throughput T , and a coding word π with 0 ≤ i ≤ n letters and 0 ≤ j ≤ m letters , let C π be the set of partial conservative solutions on the partial increasing order encoded by π (that feeds nodes C 1 , . . . ,C i and C n+1 , . . . ,C n+ j ).

All partial conservative solutions of C π have the same amount of available throughput of each type. Let us denote by O(π) (respectively G(π)) the open (respectively guarded) bandwidth available at the end of the partial solutions of C π . O and G satisfy the following recursive equations:

O(ε) = b 0 , G(ε) = 0, O(π ) = O(π) -T, G(π ) = G(π) + b n+ j+1 , O(π ) = O(π) + b i+1 -max(0, T -G(π)), G(π ) = max(0, G(π) -T ).
The values O and G encompass all the capacity constraints of solutions in C π . Indeed, it is easy to see that a coding word π is valid for a throughput T if and only if

• for any prefix π ′ of π, O(π ′ ) ≥ T , and

• for any prefix π ′ of π, O(π ′ ) + G(π ′ ) ≥ T . π ε O(π) 6 2 7 3 5 1 G(π) 0 4 0 1 0 1 W (π) 0 0 0 0 3 3
W (ε) = 0, W (π ) = W (π), W (π ) = W (π) + max(0, T -G(π)).
From above, we obtain

G(π) = b n+1 + . . . + b n+ j -i • T +W (π) (1) O(π) = b 0 + b 1 + . . . + b i -j • T -W (π) (2)
and

O(π) + G(π) = ∑ |π| k=0 b k + ∑ n+|π| k=n+1 b k -|π|T .

Greedy algorithm

In this section, we present Algorithm 2 that decides whether a given throughput T is feasible. If T is feasible, Algorithm 2 also outputs a valid coding word. It works by iteratively building a partial conservative solution π, deciding at each step how to extend the partial solution (by or by ). This decision is made greedily, by choosing if it is possible. The algorithm is forced to take (see line 12):

• when it is not possible to choose at the current step (O(π) < T );

• or when choosing would make it impossible to continue afterwards

(O(π ) + G(π ) < T ).
Of course, if all guarded nodes have been used (line 6), the algorithm chooses . Another special case is when only one guarded node is left. In that case (see lines [START_REF] Beaumont | Heterogeneous resource allocation under degree constraints[END_REF][START_REF] Beaumont | Allocation of clients to multiple servers on large scale heterogeneous platforms[END_REF][START_REF] Beaumont | Using the last-mile model as a distributed scheme for available bandwidth prediction[END_REF][START_REF] Beaumont | Using the last-mile model as a distributed scheme for available bandwidth prediction[END_REF], the algorithm chooses at each step the node with the largest b i (unless it is guarded and O(π) < T ).

Table 3.4.2 shows an execution of Algorithm 2 on the instance of Figure 13. The generated scheme is shown in Figure 19.

The following lemma states that this algorithm is valid. if O(π) < 0 then return FAIL 18: end while

19: return π 2 C 0 C 3 C 5 4 4 4 1 b 0 = 6 b 3 = 4 b 1 = 5 b 5 = 1 C 1 b 2 = 5 C 2 C 4 b 4 = 1 1 4
Figure 19: The acyclic broadcast scheme of throughput 4 built by Algorithm 2. The order associated with this scheme is σ = 031425.

Lemma 3.4.4. Given an instance I and a throughput T , Algorithm 2 returns a valid word (a word π such that T * ac (π) ≥ T ) if and only if T is feasible for this instance (T * ac ≥ T ).

In order to prove Lemma 3.4.4, we now need to state two preliminary lemmas. The first one shows that this algorithm uses open nodes as late as possible, and is as conservative as possible. If

|π k | < m -1, then for every π ′ k ending with a such that |π ′ k | = k, we have W (π ′ k ) ≥ W (π k ) and |π ′ k | ≤ |π k | . Proof.
We prove this lemma by induction on k. Clearly the lemma holds true for k = 0, since

π 0 = ε = π ′ 0 .
(We treat source node as 0-th node.) Assume now that lemma holds true for k -1, and let us decompose the words maximally as follows 1) and ( 2), we get

π k = π k-1 a and note δ = π k-1 a , π ′ k = π ′ k-1 a ′ . Let l = |π k | and l ′ = |π ′ k | . From (
O(δ ) = b 1 + . . . + b k-1 -l • T -W (π k-1 ), G(δ ) = b n+1 + . . . + b n+l -(k -1) • T +W (π k-1 ).
Since Algorithm 2 chooses (after choosing δ ), and

|δ | < m -1, we have O(δ ) < T or O(δ ) + G(δ ) + b n+l+1 < 2T .
Let us first prove by contradiction that

|π ′ k | ≤ |π k | . Assume that |π ′ k | > |π k | . In this case, there exists δ ′ ⊑ π ′ k such that |δ ′ | = |δ |. By induction assumption, |π k-1 | ≥ |π ′ k-1 | , which implies that |π ′ k-1 | ≤ |π k-1 | ≤ |δ |. Hence, |δ ′ | = |π ′ | -1 = k -1. We can thus compute O(δ ′ ) = b 1 + . . . + b k-1 -l • T -W (π ′ k-1 ) ≤ b 1 + . . . + b k-1 -l • T -W (π k-1 ) = O(δ ), O(δ ′ ) + G(δ ′ ) = k-1 ∑ i=1 b i -l • T + n+l ∑ i=n+1 b i -(k -1) • T = O(δ ) + G(δ ). So, either O(δ ′ ) < T or O(δ ′ ) + G(δ ′ ) + b n+l+1 < 2T .
Both lead to a contradiction when we try to continue δ ′ with . This proves that |π

′ k | ≤ |π k | . Let us now prove that W (π ′ k ) ≥ W (π k ). As π k and π ′ k end with , W (π k ) = W (π k-1 ) + max(0, T -G(δ )) = max(W (π k-1 ), T • k -(b n+1 + . . . + b n+l )), W (π ′ k ) = max(W (π ′ k-1 ), T • k -(b n+1 + . . . + b n+l ′ )). Since l ′ ≤ l and W (π ′ k-1 ) ≥ W (π k-1 ) (the inductive assumption), we have W (π ′ k ) ≥ W (π k ).
Lemma 3.4.6. Let π 1 , π 2 be two conservative partial solutions such that

|π 1 | = |π 2 | and |π 1 | = |π 2 | . If W (π 1 ) ≤ W (π 2 ), then ∀ω ∈ { , } * ,W (π 1 ω) ≤ W (π 2 ω).
Proof. To prove the lemma, we only have to consider the cases where ω ∈ { , }. The case ω = is trivial since W (π ) = W (π).

Let us consider now the case ω = .

W (π 1 ) = max(W (π 1 ),W (π 1 ) + T -G(π 1 )) = max(W (π 1 ), T + i.T -b n+1 -. . . -b n+ j ) ≤ max(W (π 2 ), T + i.T -b n+1 -. . . -b n+ j ) ≤ W (π 2 ).
Proof. of Lemma 3.4.4. The first implication is trivial, since the tests performed at each step of Algorithm 2 ensure that the returned word is always valid.

For the reverse implication, we prove that if Algorithm 2 fails to find a solution, then there does not exist a valid ordering of the nodes with respect to throughput T . According to Lemmas 3.4.2 and 3.4.3, we only consider encoding words.

Let ω be the partial solution built by Algorithm 2 (before it failed), and let i = |ω| and j = |ω| .

There are four different cases to consider:

• j < m -
O(π ′ ) + G(π ′ ) = O(ω) + G(ω) + |π ′ | ∑ k=i+1 (b k -T ) ≤ O(ω) + G(ω) < T.
In conclusion, O(π ′ ) < T and thus π is not valid.

• j ≤ m -1 and ω ends with .

Because of the test at line 12, this implies that the last was added by the instruction on line 4, and thus |ω| = n.

Let π be an encoding word. We can decompose ω and π as ω ′ a and π ′ b , and we can apply Lemma 3.4.5 to words ω ′ and π

′ W (ω) = W (ω ′ ) ≤ W (π ′ ) = W (π)
Since |ω| = n and since Algorithm 2 failed, then either O(ω) + G(ω) < T or O(ω ) < 0. In both cases, O(ω) < T , and since O(ω) = O -jT -W (ω), we get O < mT +W (π), and thus O(π) < 0. Hence π is not valid.

• j = m. The main argument is that the bandwidth of the remaining open nodes is lower than that of the last guarded node. Since Algorithm 2 chose the last guarded node at some point (line 11), we have b i+1 ≤ b n+m .

The failure of the algorithm implies O(ω)+G(ω) < T . Let ω = ω ′ α. We know that O(ω ′ )+ G(ω ′ ) ≥ T , and also:

O(ω) + G(ω) = O(ω ′ ) + G(ω ′ ) -T + b i if α = , O(ω) + G(ω) = O(ω ′ ) + G(ω ′ ) -T + b n+m if α = .
So either b n+m < T or b i < T . In both cases, we have

b n ≤ b n-1 ≤ . . . ≤ b i+1 < T.
Let π = π ′ β be any encoding word. If β = , then

O(π ′ ) + G(π ′ ) = b 0 + O -b n -(n -1)T + G -mT = O(ω) + G(ω) + n-1 ∑ k=i+1 (b k -T ) ≤ O(ω) + G(ω) < T Hence π is not valid. Otherwise, β = , and O(π ′ ) + G(π ′ ) = b 0 + O -nT + G -b n+m - (m -1)T . Since b n+m ≥ b n
, we get the same conclusion.

• j = m -1 and ω ends with . The main argument is that the last guarded node can be delayed: minimizing waste is not so important since only open nodes remain to be fed. Just like in the first case, we have ∀k ≥ i, b k < T . Let us decompose ω as ω = ω ′ a (a ≥ 0).

We begin by showing that words π(x) = ω ′ x a-x are invalid for throughput T . The following lemma shows that it is possible to consider only words where the last is followed only by with smaller bandwidth. Lemma 3.4.7. If word π = π 1 a is a valid word in which the last has bandwidth g, the following has bandwidth o, and o ≥ g, then the word π ′ = π 1 a is also valid.

Proof. Let G = O(π 1 ), R = G(π 1 ) and π 2 = a . Since π is valid, we have O ≥ T and O -T + G + r ≥ T . We can thus bound O(π 1 ) O(π 1 ) = O + o -max(T -G, 0) = min(O + o + G -T, O + o) ≥ T.
This ensures that π 1 is a valid sequence.

Since π 2 is composed only of , and

O(π 1 ) + G(π 1 ) = O(π 1 ) + G(π 1 ), π 1 π 2 is a valid sequence.
So if π(x) is valid, we can iteratively use Lemma 3.4.7 to prove the existence of a valid π(y) in which the last is followed by a with smaller upload. If y < a, since Algorithm 2 at that point chose instead of , we know that O(ω ′ y ) < T and π(y) is invalid. If y = a, then π(y) = ω , which is invalid because Algorithm 2 failed.

Consider now any encoding word π. Let π = π 1 π 2 k be the decomposition with minimal π 1 having |π 1 | = |ω ′ | (applying Lemma 3.4.5 we have |π 1 | ≤ |ω ′ | = m -2, so decomposing is always possible).

For any word δ we have

W (δ ) = W (δ ) = W (δ ) + max(0, T -G(δ )) ≥ ≥ W (δ ) + max(0, T -G(δ )) = W (δ ).
We can apply it to word π

W (π 1 π 2 ) ≥ W (π 1 |π 2 | |π 2 | ).
Furthermore, since Lemma 3.4.5 applies to π 1 and ω ′ W (π 1 ) ≥ W (ω ′ ).

so by Lemma 3.4.6, (since

|π 1 | = |ω ′ | , |π 1 π 2 | = m -1 = |ω ′ | ) W (π 1 |π 2 | |π 2 | ) ≥ W (ω ′ |π 2 | ).
Composing it, we have

W (π 1 π 2 ) ≥ W (ω ′ |π 2 | )and ∀x,W (π 1 π 2 x ) ≥ W (ω ′ |π 2 | x ). So if π = π 1 π 2 k is valid, then ω ′ |π 2 |
k is also valid. But we proved previously that no such solution can exist. Thus, we reached a contradiction.

Low degree scheme for a word π

The output of Algorithm 2 is an encoding word and an ordering, together with the amounts of guarded or open bandwidths used for this purpose, but not the actual values of the c i, j s. There are several possibilities for the c i, j s. However, in order to prove bounds on the degree of the nodes, we will feed each node by the earliest possible nodes with unused upload bandwidth (as in the open nodes case described in Section 3.3.2). Lemma 3.4.8. From the word π given by Algorithm 2, it is possible to build a broadcast scheme such that

• for every guarded node j ∈ G , outdegree o j is bounded: o j ≤ b j T + 1; • for at most one open node i, o i ≤ b i T + 3; • for the other open nodes, o i ≤ b i T + 2.
Proof. Since guarded nodes can only upload to open nodes, and open nodes always receive from the earliest guarded node available, every guarded node uploads to a consecutive interval of open nodes. So at most 2 nodes will be partially fed by a specific guarded node: the first and the last one of the interval (see first example of Figure 20).

Let us now consider an open node i. Because Algorithm 2 rather chooses guarded nodes when it is possible, as long as there is enough open bandwidth available, node i will feed a consecutive interval of guarded nodes. When the amount of open upload available gets low, there are two cases to consider:

• i is the earliest open node that feeds the last guarded node.

The sequence of nodes fed by i first consists in a sequence of guarded nodes, then a sequence of open nodes, then the last guarded node and another sequence of open nodes (see second example of Figure 20). Since conservatism implies that G(π ) = 0 after feeding an open node from node i, a partially fed open node can only take place as the first node after guarded nodes. Hence, the only nodes partially fed by i are the first one, the last one and the opening nodes of the 2 open sequences. In total, at most 4 nodes are partially fed by node i.

• Otherwise (see last example of Figure 20), Algorithm 2 feeds guarded nodes with the upload of i as long as there is enough bandwidth. At some point,

O + G + g next < 2T ,
= T -G upload from i, the remaining upload of i is equal to β -α ≤ O + G -T ≤ T -g next ≤ T .
Thus, the next node fed by i uses all the remaining bandwidth of node i. Hence, node i feeds partially at most 3 nodes: the first node, one open node and the last node.

This concludes the proof of Theorem 3.4.1.

Cyclic case

This section considers cyclic broadcast schemes. We start by giving an upper bound on the optimal cyclic throughput T * : Lemma 3.5.1.

T * ≤ min b 0 , b 0 + O m , b 0 + O + G n + m ,
where O = ∑ n i=1 b i and G = ∑ n+m i=n+1 b i . For the instance of Figure 13, O = 10, G = 6. Hence, from this lemma, we know that the throughput of the broadcast scheme of Figure 13 is optimal since min(6, 16/3, 22/5) = 4.4.

Proof. Clearly T * ≤ b 0 , since the whole message has to be sent at least once by the source. Then, the m guarded nodes have to receive the message at rate T * and therefore consume mT * bandwidth. Since this bandwidth must come from the source and the open nodes, then mT * ≤ b 0 + O. Finally, all n + m nodes must receive the whole message at rate T * and the bandwidth must come from the source, the open and the guarded nodes, so that

(m + n)T * ≤ b 0 + O + G.
As shown in Figure 21, it is not always possible to achieve a solution of optimal throughput with low degree in presence of guarded nodes. However, after [START_REF] Beaumont | Broadcasting on large scale heterogeneous platforms under the bounded multi-port model[END_REF]: ...

Theorem 3.5.

([7]). There exists an algorithm which takes as input any instance without guarded nodes and a target value of T ≤ T

m-1 m

1 m

1 m b 0 = 1 b i = 1 m b 1 = m -1
Figure 21: An instance with guarded and open nodes where the optimal cyclic throughput is

T * = min b 0 , b 0 +b 1 m , b 0 +b 1 +mb 2 m+1 = 1.
In the optimal solution, the source has degree m,

whereas b 0 T * = 1.
Proof is a constructive one. It relies on incremental building of an acyclic solution (in a style resembling the Algorithm 1), and performing necessary local fixes when unable to perform another acyclic step.

Cyclic/Acyclic throughput comparison

In this section, we compare the optimal acyclic throughput with the optimal (cyclic) throughput. On the one hand we show that the ratio T * ac T * can be as small as 5 7 ≈ 0.71 for (small-size) instances and as small as 1+ √ 41 8 ≈ 0.925 for arbitrary large instances (by contrast, when there are only open nodes, this ratio tends to one when the number of nodes is large). On the other hand, we show that this ratio is larger than 5 7 for any instance, so that this bound is tight. Finally we present experimental results on the ratio T * ac T * on random instances, that prove that acyclic solutions achieve much better results than the 5 7 bound in practice.

Worst cases

Without guarded nodes Theorem 3.6.1. For any instance I of size n and without guarded nodes,

T * ac T * ≥ 1 - 1 n .
Proof. Let I be an instance of size n without guarded nodes. From Section 3.3 we know that

T * ac = min b 0 , b 0 + O -b n n .
From Lemma 3.5.1 we have

T * ≤ min b 0 , b 0 + O n .
If T * ac = b 0 then it is also the case for T * and the result holds. Else we have

T * ac T * ≥ b 0 + O -b n b 0 + O ≥ 1 - b n b 0 + O .
Because of the ordering of nodes we have O ≥ nb n . This concludes the proof.

With guarded nodes

We start this section by characterizing a special class of instances which are the worst possible cases for the acyclic throughput. An instance is said to be homogeneous if all open nodes except the source have the same throughput o and all guarded nodes have the same throughput g. An instance is said to be tight if b 0 = b 0 +O+G n+m = T * (i.e. if no bandwidth can be wasted in the optimal cyclic solution). The instance of Figure 13 is tight but not homogeneous and the instance of Figure 21 is tight and homogeneous. Proof. To prove this lemma we will show that given an instance, we can associate with it a tight homogeneous instance with the same optimal throughput T * and with no greater optimal acyclic throughput T * ac . First, if the instance is such that

b 0 + O + G n + m > T * ,
by reducing the throughput of the guarded nodes it is possible to make this inequality an equality. This transformation does not change the optimal throughput T * and any acyclic solution for the transformed instance is also an acyclic solution for the original one. Consider now a non-homogeneous instance I such that

b 0 + O + G n + m = T * .
Let I ′ be the homogeneous instance obtained from I as follows:

b ′ 0 = T * , b ′ i = o = N + b 0 -T * n for i ∈ 1, n , b ′ i = g = M m for i ∈ n + 1, n + m ,
where b ′ i is the throughput of the node C i in I ′ . Clearly I and I ′ have the same optimal throughput T * and I ′ is tight and homogeneous. Observe that since nodes of same type are ordered in the non-increasing order of their throughput,

∀ k∈ 0,n k ∑ i=0 b i ≥ k ∑ i=0 b ′ i and ∀ k∈ n+1,n+m k ∑ i=1 b i ≥ k ∑ i=1 b ′ i .
Hence, any acyclic scheme of I ′ can be turned into a scheme where I communications previously ensured by the k-th open (resp. guarded) node in I ′ are now ensured by the k first open (resp. guarded) nodes in I. The resulting scheme is acyclic and achieves the same throughput.

Our first result states that the optimal acyclic (low degree) solutions achieve a throughput that is at least 5 7 of the optimal cyclic solution (with possibly arbitrarily large degree) and that this 5 7 bound is tight.

Theorem 3.6.3. For any instance,

T * ac T * ≥ 5 7 .
Moreover, there exists an instance such that this ratio is reached.

Let us first show that the ratio 5/7 can be reached. For this purpose, let us consider the following instance (see Figure 22) consisting of one source of throughput 1, one open node of throughput b 1 = 1 + 2ε and two guarded nodes with throughput of b 2 = b 3 = 1/2 -ε each. For this instance, T * = 1 (see Lemma 3.5.1). There also exist 3 increasing orderings σ 1 = 0123, σ 2 = 0213 and σ 3 = 0231. Ordering σ 1 achieves a throughput of T * ac (σ 1 ) = (2/3).(1+ε) and ordering σ 2 achieves a throughput of T * ac (σ 2 ) = 3/4 -ε/2 (see Figure 22). The throughput of the last ordering is always smaller than the maximum of the two previous ones. When ε = 1/14, orderings σ 1 and σ 2 achieve the same throughput T * ac = 5/7. Let us now prove that for any instance T * ac T * ≥ 5 7 . Without loss of generality, we can consider only tight homogeneous instances. We can also assume that n ≥ 1, m ≥ 2 and n + m ≥ 4 since other cases are trivial or have been considered above.

Let us consider the following two words

ω 1 (n, m) = α 1 α 2 . . . α n , ω 2 (n, m) = β 1 β 2 . . . β n .
where

α i = ⌊i • m n ⌋ -⌊(i -1) • m n ⌋ and β i = ⌈i • n m ⌉ -⌈(i -1) • n m ⌉.
Intuition of introduction of those two encoding words is as follow: to spread or (whichever is necessary) almost uniformly on the whole word. Such words encode almost optimal acyclic solutions, however they represent much more regular inner structure. As observed in Section 3.4, these words encode increasing orders on vertices. To conclude the proof we only have to show that at least one of these two words encodes a valid scheme of throughput 5/7 max (T * ac (ω 1 (n, m)), T * ac (ω 2 (n, m))) ≥ 5/7. Recall that we consider tight homogeneous instances with b 0 = 1 such that n ≥ 1, m ≥ 2 and n + m ≥ 4. Without loss of generality, we can also assume that b

σ 1 2/3 + 2ε/3 2/3 + 2ε/3 1 3 + 4ε 3 1/3 -2ε/3 σ 2 1/4 + ε/2 1/2 -ε 3/4 -ε/2 3/4 -ε/2 C 0 C 0 C 2 C 1 C 3 C 3 C 2 C 1
0 = 1, b 0 + O ≥ m and b 0 + O + G = n + m. Hence for some 0 ≤ ∆ ≤ n, the bandwidth of each open node is o = m-1+∆
n and the bandwidth of each guarded node is g = n-∆ m . To show that max(T * ac (ω 1 (n, m)), T * ac (ω 2 (n, m))) ≥ 5/7, we will show a more precise statement

if o ≥ 1,T * ac (ω 1 (n, m)) ≥ 5/7 otherwise T * ac (ω 2 (n, m)) ≥ 5/7. (3)
Let us start with two additional technical lemmas.

Lemma 3.6.4. For a tight homogeneous instance, a word ω is valid for throughput T if and only if

• (c1) ∀ π ⊑ω b 0 + o • |π| + g • |π| -|π | • T ≥ 0 • (c2) ∀ π ′ ⊑π ⊑ω b 0 + o • |π| + g • |π ′ | -|π | • T -|π ′ | • T ≥ 0
Proof. As shown in Section 3.4, a word ω is valid for a throughput T if and only if for any prefix of ω of the form π , G(π) ≥ T, for any prefix of ω of the form π , G(π) + R(π) ≥ T.

For homogeneous instances, the second condition can be written as

∀ π ⊑ω b 0 + o • |π| + g • |π| -|π | • T ≥ 0 which is exactly (c1).
And the first condition is

∀ π ⊑ω b 0 + o • |π| -|π | • T -W (π) ≥ 0.
From the recursive equations which define W and G, we can deduce

W (π ) = max(W (π), |π | • T -(b n+1 + . . . + b n+|π| )).
Together with W (π ) = W (π), this implies

W (π) = max π ′ ⊑π {|π ′ | • T -(b n+1 + . . . + b n+|π ′ | )},
hence the first condition can be rewritten to

∀ π ′ ⊑π ⊑ω , b 0 + o • |π| g • |π ′ | -|π | • T -|π ′ | • T ≥ 0.
Lemma 3.6.5. If ω is an encoding word for a valid solution of a homogeneous instance with

(b 0 = b ′ 0 , o = o ′ , g = g ′
) with throughput T , and ω is also encoding a valid solution of a homogeneous instance with

(b 0 = b ′′ 0 , o = o ′′ , g = g ′′ ) with throughput T , and 0 ≤ λ 1 , λ 2 ≤ 1 are such that λ 1 + λ 2 = 1, then ω is also a valid solution for homogeneous instance with (b 0 = λ 1 • b ′ 0 + λ 2 • b ′′ 0 , o = λ 1 • o ′ + λ 2 • o ′ , g = λ 1 • g ′ + λ 2 • g ′′ ) with throughput T .
Proof. For fixed π , we can write (c1) as

b ′′ 0 + o ′′ • |π| + g ′′ • |π| -|π | • T = λ 1 (b 0 + o • |π| + g • |π| -|π | • T )+ + λ 2 (b ′ 0 + o ′ • |π| + g ′ • |π| -|π | • T ) ≥ 0.
Condition (c2) is proved analogously.

Now let us go back to the proof of statement (3).

Since when m > n, it is impossible to have o < 1, we need to consider only 3 cases

• m ≥ n + 1 and o ≥ 1, • m ≤ n and o ≥ 1,
• m ≤ n and o ≤ 1.

Using Lemma 3.6.5, we can eliminate the parameter ∆ from each of the cases, reducing each of them to two extreme cases

• m ≥ n + 1 and o ≥ 1 -(A1) o = m-1 n , g = n m , -(A2) o = n+m-1 n , g = 0.
• m ≤ n and o ≥ 1

-(B1) o = 1, g = m-1 m , -(B2) o = n+m-1 n , g = 0. • m ≤ n and o ≤ 1 -(C1) o = m-1 n , g = n m , -(C2) o = 1, g = m-1 m .
We now check for each case that the appropriate word (ω 1 (n, m) or ω 2 (n, m)) satisfies the condi- tions (c1) and (c2) of Lemma 3.6.4.

Lemma 3.6.6. In cases (A2) and (B2), T * ac ≥ 5/7.

Proof. Merging cases (A2) and (B2) together, we consider the following instance

o = n + m -1 n , g = 0,
(o ≥ 1 obviously holds), and the encoding word ω 1 (n, m).

It is enough to verify condition (c1), because open bandwidth is the only available bandwidth in this case. If we denote |π| as i, 0 ≤ i < n, (c1) becomes then

∀ 0≤i<n 1 + n + m -1 n • i -i + 1 + m n i • 5 7 ≥ 0. Since ⌊ m n i⌋ ≤ m n i, it is enough to prove 1 + n + m -1 n • i -i + 1 + m n • i • 5 7 ≥ 0 which simplifies to 2 7 + 2 7 • i + 2 7 • m n • i - i n ≥ 0 2 + (2n + 2m -7) • i ≥ 0 which holds, since n + m ≥ 4.
Lemma 3.6.7. In cases (B1) and (C2), T * ac ≥ 5/7.

Proof. Increasing n in those cases only results in adding open nodes with bandwidth 1 ≥ 5 7 . So it is enough to prove the two conditions for n = m.

So we now assume n = m. If m ≥ 4, then g ≥ 3 4 , and

ω 1 (n, n) = ( ) n ω 2 (n, n) = ( ) n ,
and every node is able to feed the next node.

If m ≤ 3, we can easily verify that the words ω 1 (2, 2) and ω 2 (2, 2) are valid for the case o = 1, g = 1 2 with throughput T = 5 7 , and that the words ω 1 (3, 3) and ω 2 (3, 3) are valid for the case o = 1, g = 2 3 with throughput T = 5 7 . Lemma 3.6.8. In case (A1), T * ac ≥ 5/7.

Proof. Let us check condition (c1). For the sake of readability, let us denote by i the value |π| (0 ≤ i < n). Condition (c1) can be rewritten to

1 + i • m -1 n + i • m n • n m ≥ 5 7 • 1 + i + i • m n which is equivalent to 2 7 + i • m -1 n - 5 7 ≥ i • m n • 5 7 - n m .
Since m-1 n ≥ 1, the left-hand side is always positive. We can safely assume that 5 7 ≥ n m (otherwise, the right-hand side is negative). And since ⌊i

• m n ⌋ < i • m n , it is enough to prove 2 7 + i • m -1 n - 5 7 ≥ i • m n • 5 7 - n m .
Simplifying, we get 2 7

+ i • 2 7 + 2 7 • m n - 1 n ≥ 0. Since 2 7 + 2 7 • m n ≥ 2 7 + 2 7 • 7 5 ≥ 1 2 ≥ 1 n , condition (c1)
holds. Let us now check condition (c2). We denote |π| = i and |π ′ | = j (it is enough to consider the longest such π ′ ), 0 ≤ j < i ≤ n.

1 + i • m -1 n + m n • j • n m - m n • i • 5 7 -( j + 1) • 5 7 ≥ 0.
Simplifying, we get

2 7 + m n • j • n m - 5 7 • j + 5 7 • m n • i - m n • i + i n • 2 7 • m -1 ≥ 0.
Now, we can also use this

∀ x≥0 ⌊x⌋ = ⌊x⌋ • ⌊x⌋ + 1 ⌊x⌋ + 1 ≥ x • ⌊x⌋ ⌊x⌋ + 1 . So we have m n • j ≥ m n • j • ⌊ m n • j⌋ ⌊ m n • j⌋ + 1 ≥ m n • j • j j + 1 .
Using this, condition (c2) holds if

2 7 + j • j j + 1 - 5 7 • j + 5 7 • m n • i - m n • i + i n • 2 7 • m -1 ≥ 0.
The case m ≤ 3 can be checked separately (m = 3, n = 2, o = 1, r = 2 3 ). When m ≥ 4, we have 2 7 m -1 > 0, and it remains to prove that

2 7 + j • j j + 1 - 5 7 • j ≥ 0
For j ∈ {0, 1, 2, 3} it can be checked, and for j ≥ 4 the following inequality allows us to conclude

j • j j + 1 ≥ 5 7 • j.
Lemma 3.6.9. In case (C1), T * ac ≥ 5/7.

Proof. If we denote i = |π| (the case i = 0 is trivial, so we can assume 0 < i < m), condition (c1) can be written as 1

+ n m • i + m -1 n i • n m ≥ 5 7 1 + i + i • n m which simplifies to 2 7 + n m - 5 7 i ≥ 5 7 - m -1 n • i • n m .
We can safely assume that 5 7 -m-1 n ≥ 0, because otherwise the right-hand side would be negative, while the left-hand side remains positive. Since ⌈x⌉ ≤ x + 1, the following equality implies (c1)

2 7 + n m - 5 7 i ≥ 5 7 - m -1 n • i • n m + 1
And simplifies to 2 7

• n m + m -1 m - 5 7 • i + m -1 n ≥ 3 7 .
We can observe that 2 7 • n m + m-1 m -5 7 ≥ 2 7 + 1 2 -5 7 > 0, so that the left-hand side of this inequality is minimized with i = 1. It is thus enough to check that

2 7 • n m + m -1 m + m -1 n ≥ 8 7 .
This is what we do here:

2 7 • n m + m -1 m + m -1 n ≥ 2 7 • n m + 1 2 + m -1 m • m n ≥ ≥ 1 2 + 2 7 • n m + 1 2 • m n ≥ 1 2 + 2 • 2 7 × 1 2 ≥ 8 7 .
Let us now check condition (c2). Here, we denote |π| by i and |π ′ | by j (0 ≤ j ≤ i < m ≤ n) (We only have to consider the longest π ′ ). Condition (c2) becomes ∀0 ≤ j ≤ i < m ≤ n

1 + i • n m • m -1 n + j • n m - 5 7 • 1 + j • n m + i ≥ 0.
Simplifying, and substituting ⌈x⌉ by x we get

2 7 + i • m -1 m + j • n m - 5 7 • j • n m - 5 7 • i ≥ 0.
First, we solve the case when j = 0

2 7 + i • m -1 m - 5 7 ≥ 0 • m = 2 2 7 + i • 1 2 - 5 7 ≥ 0 i ≤ 4 3 that holds true since i < m = 2 • m = 3 2 7 + i • 2 3 - 5 7 ≥ 0 i ≤ 6
that holds true since i < m = 3

• m > 3 m -1 m ≥ 5 7 .
Which solves case j = 0. Now we can safely assume j ≥ 1. Using ⌈ a b ⌉ ≤ a+b-1 b , it is sufficient to prove that 2 7

+ i • m -1 m + j • n m - 5 7 • j • n m + m -1 m - 5 7 • i ≥ 0, which simplifies to 2 7 • i + 2 7 • j • n m + 5 7 • 1 m ≥ i • 1 m + 3 7 .
Obviously, the left-hand side is minimized for j = 1:

2 7 • i + 2 7 • n m + 5 7 • 1 m ≥ i • 1 m + 3 7 .
We consider three cases:

• m = 2 (then, i = 1 must hold):

2 7 + 2 7 • n 2 + 5 7 • 1 2 ≥ 1 2 + 3 7
which is equivalent to n ≥ 2 (that holds).

• m = 3 (then, 1 ≤ i < 3 must hold)

2 7 • m 3 + 5 7 • 1 3 ≥ 1 21 • i + 3 7
which is equivalent to 2n ≥ i + 4 (that holds).

• m ≥ 4 2 7 - 1 m • i + 2 7 • n m + 5 7 • 1 m ≥ 3 7
right-hand side minimizes for i = 1

2 7 - 1 m + 2 7 • n m + 5 7 • 1 m ≥ 3 7
which simplifies to 2n ≥ 2 + m, that also holds.

We just proved that acyclic solutions have throughput at least 5 7 of the optimal solution. Looking at Figure 23, we see that the worst case happens for small n and m, and ratio grows with size of instances. One could hope, that ratio goes arbitrarily close to 1, but unfortunately that is not the case.

The second result states that the optimal acyclic throughput does not get arbitrarily close to the optimal cyclic throughput when the size of the instances grows. Theorem 3.6.10. For every ε > 0 and every K ∈ N, there exist instances with at least K open nodes and K guarded nodes such that

T * ac T * ≤ 1 + √ 41 8 + ε ≈ 0.925 + ε.
Proof. of Theorem 3.6.10. For a given α = p q < 1, (p and q have integer values), and for any k, let us consider the instance I(α, k) such that:

• b 0 = 1;
• n = kq open nodes have bandwidth α; and

• m = kp guarded nodes have bandwidth 1 α .

The first observation is that for all α and k, Lemma 3.5.1 implies that the optimal throughput T * is equal to 1.

For the second observation, let S be any acyclic solution to I(α, k) and x be the number of open nodes before the second guarded node in S. In other words, S starts with a prefix π = u v with u + v = x. The throughput T achievable by S is bounded by two constraints

• the source and the first x open nodes should be able to feed the first two guarded nodes, ie.

αx + 1 ≥ 2T , and

• the bandwidth of the source and of the first x + 1 nodes should be enough to feed the x + 2 nodes, ie. αx

+ 1 α + 1 ≥ (x + 2)T .
Hence T ≤ αx+1 2 = f α (x) and T ≤

αx+ 1 α +1 x+2
= g α (x). Since any optimal acyclic scheme must satisfy these two constraints for some x, we have T * ac ≤ max x∈N min( f α (x), g α (x)). Observe now that the function f α is increasing, and g α is decreasing (since α < 1), and that they coincide (with value 1) for x = 1 α . The minimum is thus achieved by f α for x < 1/α, and by g α for x > 1/α, and this minimum is maximized for x = 1/α. However, 1 α is not necessarily an integer, so the maximal value is achieved for x = 1 α or x = 1 α :

T * ac ≤ max f α 1 α , g α 1 α . If α = √ 41-3 8 , simple computations show that 1 α = 2, 1 α = 3, and f α (2) = g α (3) = √ 41+1
8 . Since this value of α can be approximated arbitrarily close with a rational number, and since the expressions f α (2) and g α (3) are continuous in α, we get the claimed result.

To conclude this subsection, we show an exhaustive exploration of all possible tight and homogeneous instances, for n and m between 0 and 100. For each of them we compute the ratio T * ac /T * (see Figure 23).

On the one hand, we can observe the result of Theorem 3.6.10: when m ≃ √ 41-3 8 n (for example n = 100 and m = 42), the ratio remains below 1, even for large values of n and m. On the other hand we can observe that except for few small instances, the ratio T * ac /T * is larger than 0.8.

Average cases

In addition to this worst-case analysis, we also analyze the average ratio between acyclic and cyclic throughput of randomly generated instances. In order to explore the performance of our algorithms in different heterogeneity conditions, we consider several probability distributions for the bandwidths of the nodes 1. a uniform distribution between 1 and 100 (Unif100); In each case, each node is independently chosen to be an open node with probability p (and a guarded with probability (1p)). In order to concentrate on difficult instances, the bandwidth of the source node is chosen equal to the optimal cyclic throughput -what ensures that the source is not a strong limiting bottleneck, and that it is also not sufficient by itself to feed all nodes. The results are shown on Figure 24, for different numbers of nodes and different values of p. For each set of parameters, 1000 random instances were generated, and the figure shows average values (connected by black lines) and boxplots with median, quantiles, and confidence intervals at 5% (the black dots are outliers, outside these confidence intervals).

The first conclusion of these simulations is that the average behavior of acyclic solutions is very close to the optimal cyclic throughput, and that this is true in a wide variety of scenarios. Furthermore, the results are very stable. We can note that more open nodes and moderate heterogeneity (with the Power1 and Power2 distributions) make the problem slightly more difficult for small size instances. Overall, however, we can see that even in these cases, producing low degree solutions comes at very little cost (at most 5%) with respect to the achievable throughput. The second conclusion is related to the acyclic throughput obtained considering only the best solution among those encoded by words ω 1 and ω 2 (blue lines on Figure 24). In all cases, these solutions are almost as competitive as the best acyclic ones and for all large instances they are as competitive. From a practical point of view these simpler schemes are of interest since they are easier to build in a distributed context once nodes have been ordered according their bandwidth. For comparison, the average throughput obtained by the word (either ω 1 or ω 2 ) used in the case analysis of the proof of Theorem 3.6.3 is shown by the red lines on Figure 24. We can see that there is a significant gap for smaller instances, hence it can be actually worthwhile to compute the best throughput among both words.

G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G

Conclusion

We have considered the classical problem of broadcasting a large message at an optimal rate in a large scale distributed and heterogeneous network. We have advocated the use of the LastMile model, that encompasses the advantages of both the bounded multiport model and the 1-port model.

The main originalities of our work are that we consider the case where some broadcast nodes lie in the open Internet whereas other broadcast nodes are guarded (behind NATs or firewalls), and that we search for either cyclic or acyclic solutions.

We propose algorithms that provide solutions with low degree (optimal up to a small constant additive term) and that achieve optimal throughput for the acyclic case. For the problem of finding cyclic solution, we prove that reaching the optimal throughput may require arbitrarily large degree at some nodes, but on the other hand, we prove a tight worst-case bound of 5/7 for the ratio between acyclic and cyclic cases. We also show, using a large set of simulations, that this ratio is even closer to 1 in practice, so that acyclic low degree solutions can be used for the cyclic case also.

Therefore, we provide low complexity algorithms (even if their proofs of correctness are sometimes sophisticated) that achieve optimal throughput (or quasi-optimal in the cyclic case) and where each node is connected to a minimal number of neighbors (up to a small additive constant ranging from 1 to 4 depending on the case), what makes implementation more efficient. We believe that this makes the proposed algorithms efficient both theoretically and practically.

Work presented in this chapter opens many perspectives. On the practical side, we rely on the LastMile model whose parameters can be easily evaluated at runtime, as shown in previous chapter, and we provide low degree acyclic solutions. Therefore, we expect that the theoretical results proved here can indeed be achieved in practice. On the theoretical side, since the use of the LastMile model enables to design (quasi-)optimal solutions with respect to both degree and throughput, we can introduce new objectives, such as dealing with the dynamicity of the platform (changing dynamically the set of participating nodes, or their communication abilities) or optimizing the depth of produced schemes in order to minimize delays.

Chapter 4

Power efficient communication over grid topologies 4.1 Introduction

Context

In previous chapters, we saw how the problem of instantiating the network parameters can be solved, when we assume certain models of networks. Also, when given such a model, we saw how we can solve certain combinatorial problems connected with efficient communication allocation over the network. That is the typical problem we will encounter when trying to model large scale communication over an unknown platform, e.g. peer-to-peer networks. However, when we try to move to different type of platforms, e.g. cloud computing, there arises a dual problem, concerning how to allocate transmission for just a known set of communications, or even a single communication. Previously we were free to decide on the amount of flow going through a given node, or the structure of point-to-point communication, without control of the actual routing of node to node communication. Now we will fix the endpoints of communication, and actually try and find efficient routing. We are free to do so, because it is possible to know the topology of the underlying network, or the infrastructure, when previously we could only assume the minimal knowledge. If we are going to analyze just the structure of communication over known network, we usually know in advance the transfer we want to achieve. Also, the maximal possible transfer in the flow related models is usually easy to compute (if we know bandwidth constraints over the edges), or infinite (when there are no constraints). So we have to provide a realistic cost function that will evaluate efficiency of the solution.

Motivation

In this chapter, we present results from our research on cost efficient routing over high performance computing platforms. Our point of interest is the search for power-efficient routing on rectangular grid topologies. We investigate the problem of routing communications between CMP (Chip Multiprocessors) cores using shortest paths, in a model where the power cost associated with activating a communication link at a transmission speed of f bytes/second is proportional to f α , for some constant exponent α > 2. Power usage is a natural factor to optimize when investigating chip multiprocessors (CMP). For them, a significant part of power consumption is attributed to communications between cores, and power inefficiency is one of main limits preventing from further miniaturization of CMP [START_REF] Owens | Research challenges for on-chip interconnection networks[END_REF]. Grid topology was chosen because it reflects well high performance platforms topologies. It can also be a basis for more complicated ones, and we hope for possible extensions of our results (for example planar topologies).

The starting point for our work in this chapter was the publication [START_REF] Benoit | Power-aware manhattan routing on chip multiprocessors[END_REF], that provided the setting (topology with power-transmission rate function) with an extensive theoretical and practical analysis of the problem. Key elements of the setting were already known and analyzed before. In [START_REF] Benoit | Power-aware manhattan routing on chip multiprocessors[END_REF], those ideas were for the first time put together and used to examine a wide category of routing algorithms. However, we felt that the part regarding efficient splitting of messages into atomic parts to be sent over single paths was underdeveloped, and we chose it as a way to improve this work.

With this research, we aimed at finding a balance between the simplicity of a model (that allows a deep mathematical analysis), and the complexity of actual processes (captures the real life setting of the problem). The setting we found allowed us for a very efficient theoretical analysis, while still reflecting the real life setting of high performance computing power efficiency.

Our main result is a trade-off showing how the power required for communication in CMP grids depends on the ability to split communication requests between a given pair of nodes, and then route each such request along multiple paths. For a pair of cores in a n × n grid, the number of available communication paths between them grows exponentially with n. By contrast, we show that the optimal power consumption (up to constant factors) can be achieved by splitting each communication request into k paths, starting from a threshold value of k = Θ(n 1/(α-1) ). This threshold is much smaller than n for typical values of α ≈ 3, and may be considered practically feasible in routing schemes on the grid. More generally, we provide efficient algorithms for routing multiple k-splittable communication requests between any two cores in the grid, providing solutions within a constant approximation of the optimum cost. We support our results with simulations, showing that for practical instances, our approach using k-splittable requests leads to a power cost close to the one of the optimal solution with arbitrarily splittable requests, starting from the stated threshold value of k.

Setting

The increase in the level of integration of single chip multiprocessors (CMPs) creates demand for high-speed communications on-chip, which in turn increases the power consumption on CMP. This trend is expected to continue in the future [START_REF] Blake | A survey of multicore processors[END_REF]. Numerous studies concern the optimization of power cost in integrated chip designs, taking into account that both processors and communication buses may operate at variable frequency, determining the speed of computations or transmissions (cf. [START_REF] Ishihara | Voltage scheduling problem for dynamically variable voltage processors[END_REF][START_REF] Langen | Leakage-aware multiprocessor scheduling[END_REF][START_REF] Mishra | Energy aware scheduling for distributed real-time systems[END_REF][START_REF] Pruhs | Speed scaling of tasks with precedence constraints[END_REF]). The increase of power cost P as a w α for α ≈ 3 (where w is a workload) in such designs is a well-established relation (cf. e.g. [START_REF] Pruhs | Speed scaling of tasks with precedence constraints[END_REF][START_REF] Aydin | Energy-aware partitioning for multiprocessor real-time systems[END_REF][START_REF] Chen | Multiprocessor energy-efficient scheduling for real-time tasks with different power characteristics[END_REF]).

A significant part of power in CMPs is consumed by maintaining communications within the chip, and that makes efficient allocation of communication routes a very important issue [START_REF] Owens | Research challenges for on-chip interconnection networks[END_REF]. On CMP grids, links with dynamic frequency and/or voltage scaling are used ( [START_REF] Lee | A variable frequency link for a power-aware network-on-chip (noc)[END_REF][START_REF] Shang | Dynamic voltage scaling with links for power optimization of interconnection networks[END_REF]), and power P dissipated on a link is related to the frequency f and voltage V on it by the following relation supported by both theory and experiments P ∼ f • V 2 (cf. e.g. [START_REF] Andrei | Simultaneous communication and processor voltage scaling for dynamic and leakage energy reduction in timeconstrained systems[END_REF]). However, for most designs, an increase in operating frequency also results in an increase in voltage, roughly according to the relation V ∼ f (cf. e.g. [START_REF] Shang | Dynamic voltage scaling with links for power optimization of interconnection networks[END_REF]), which results in the relation between power cost and transmission speed given as P ∼ f 3 ( [START_REF] Benoit | Power-aware manhattan routing on chip multiprocessors[END_REF][START_REF] Benoit | On the performance of greedy algorithms for power consumption minimization[END_REF]).

Such a model of power consumption was recently studied in the context of splittable Manhattan-path routing by Benoit et al. [START_REF] Benoit | Power-aware manhattan routing on chip multiprocessors[END_REF]. They introduced several routing schemes in an effort to minimize the overall power cost, but observed that this may require splitting each communication request, and routing its fragments along a potentially very large number of communication paths. Splitting a request, taking care of the route for each part, and merging it at the target imposes additional time and power overhead.

In this work, our goal is to show how to limit path splitting as much as possible, without increasing too much the communication power cost. Specifically, we consider the problem of optimizing the power consumption cost of a communication between two given cores, that may sometimes require the routing of multiple requests. Our power consumption model assumes that if an edge is transmitting at rate v, the power cost of maintaining the frequency over an edge is proportional to v α for a given constant α > 2, identical for every edge. We make the practically-motivated assumption [START_REF] Lee | A variable frequency link for a power-aware network-on-chip (noc)[END_REF][START_REF] Shang | Dynamic voltage scaling with links for power optimization of interconnection networks[END_REF] that only the dynamic part (associated with transmission) is dominant for high communication rate, and static effects do not have to be considered in optimization. We studied more general case of v α instead of fixed v 3 one, to provide much stronger argument for our analysis, that obtained results are not related to any 'special' properties of cubic function.

Outline and results.

Our study concerns routing between a single source-sink pair of nodes using Manhattan paths on a grid CMP. Communication between these nodes is assumed to be static, i.e. constant over time, and the cost of a transmission along an edge is assumed to be proportional to a fixed power function of the transmission rate. The considered model, power cost function, and rules of routing are formally presented in Section 4.2. We briefly outline the theory of Manhattan-path routing with arbitrarily splittable requests (Max-MP). We provide an optimal convex programming formulation of the problem, leading to a routing scheme denoted as OPT, and recall the properties of the routing scheme C introduced in [START_REF] Benoit | Power-aware manhattan routing on chip multiprocessors[END_REF]. We also provide a convenient formulation of Manhattan routings in terms of transmission through nodes.

Our main results are given in Section 4.3. They concern the variant of the Manhattan routing problem in which each request can be satisfied by at most k communication paths, where k is a parameter of the model (k-MP). We study the value of the ratio of the cost of the optimal solution in this case, denoted OPT k , to the cost of the routing scheme OPT with arbitrarily splittable paths. We establish that in general, cost(OPT k )/cost(OPT) = O(1 + n k α-1 ), whereas for the special case of d ≥ 1 identical requests of the same size, this ratio is given precisely as Θ(1 + n (kd) α-1 ). This means that for k = o(n 1/(α-1) ), the requirement that requests can be split into at most k paths impacts the cost of the routing scheme asymptotically, i.e., increases the cost by an unbounded factor for sufficiently large n. On the other hand, for k larger than the threshold value of Θ(n 1/(α-1) ), the obtained k-splittable routings are within a constant factor of the optimal solution to Max-MP routing problem. The proposed bounds are obtained through the analysis of three efficiently implementable algorithmic schemes for solving k-MP: F k routing and D k routing for uniform requests (requests of same size), and A k routing for non-uniform requests. The latter two are shown to have a constant approximation ratio with respect to the cost of OPT k for all k, while the former converges to the cost of OPT as k goes to infinity. The design of such approximate techniques results from the observation that solving optimally the non-uniform k-MP routing problem is NP-hard.

Finally, in Section 4.4, we perform an experimental validation through simulations, of the determined threshold value of k = Θ(n 1/(α-1) ), showing the effect of smaller and larger values of k on the routing cost. We also experimentally compare the performance of F k routing and D k routing, studying their convergence to asymptotic behavior for increasing values of k and different values of the power cost exponent α ≈ 3.

Framework

Platform and power consumption model.

We model the platform as a grid graph on a set of m × n uniform nodes V i, j , with 1 ≤ i ≤ m and 1 ≤ j ≤ n. Without loss of generality, we assume that m ≥ n. We will also assume for the purpose of analysis that the sides of the grid are of the same order of magnitude, i.e., m = O(n). Nodes are connected by bidirectional edges. The horizontal edge E i, j connects V i, j and V i, j+1 (for 1 ≤ i ≤ m, 1 ≤ j ≤ n -1), and the vertical edge E ′ i, j connects V i, j and V i+1, j (1 ≤ i ≤ m -1, 1 ≤ j ≤ n), see the Figure 25 for an illustration.

The power consumed on each edge is closely related to the amount of data sent through this edge in a unit of time. To simplify the analysis of the model, we discard constant factors, and (following [START_REF] Benoit | Power-aware manhattan routing on chip multiprocessors[END_REF]) set the cost of transmission at rate x as C (x) = x α , where α > 2 is an absolute

Problem definition.

For a given routing policy with parameter k and power coefficient α, we define our optimization problem as follows: Given a m × n grid and a set of requests of sizes (s 1 , . . . , s d ), with ∑ d i=1 s i = K, find a routing R of this set of requests minimizing the total power cost of transmission through all the edges of the grid, expressed by the cost function:

cost (R) = m ∑ i=1 n-1 ∑ j=1 R E i, j α + m-1 ∑ i=1 n ∑ j=1 R E ′ i, j α .

Solution to

Max-MP Routing.

For Max-MP, the routing policy does not impose a bound on k. We will denote the optimal solution to Max-MP by OPT and use it as a reference for k-splittable routing algorithms. The adopted definition of routing cost leads directly to a convex-programming formulation of Max-MP routing (see Algorithm 4), and thus applications of convex programming algorithms lead to polynomialtime schemes with arbitrarily good approximation of OPT (cf. e.g. [START_REF] Ahuja | Solving the convex cost integer dual network flow problem[END_REF][START_REF] Karzanov | Polynomial methods for separable convex optimization in unimodular linear spaces with applications[END_REF] for a discussion of convex programming in the context of finding min-cost flows).

Algorithm 4 OPT routing {for Max-MP} Input: A set of arbitrarily splittable requests of total size K in a m × n grid. Solve:

Minimize ∑ i, j OPT E i, j α + ∑ i, j OPT E ′ i, j α Subject to: OPT E i, j ≥ 0 OPT E ′ i, j ≥ 0 OPT E i, j-1 + OPT E ′ i-1, j = OPT E i, j + OPT E ′ i, j OPT (E 1,1 ) + OPT E ′ 1,1 = K Output: values of OPT E i, j , OPT E ′ i, j
We remark on the following lower bound on the cost of the OPT routing. Consider any Max-MP routing that transmits requests of total size K. The edges adjacent to node V 1,1 , i.e., {E 1,1 , E ′ 1,1 }, have to transmit requests of size K in total. It follows that:

cost (OPT) ≥ K 2 α = Θ (K α ) . (4)
Remarkably, as shown in [START_REF] Benoit | Power-aware manhattan routing on chip multiprocessors[END_REF], this lower bound is tight regardless of the size of the grid, since it can be achieved using a specific routing scheme. We will provide a definition of a scheme 1. Let 1 ≤ j < n, and 1

≤ i ≤ j. R (e i ) = (R (v 1 ) + . . . + R (v i )) -(R (u 1 ) + . . . + R (u i )) , R e ′ i = (R (u 1 ) + . . . + R (u i )) -(R (v 1 ) + . . . + R (v i-1 )) .
2. For n ≤ j < m, we can perform similar reasoning

R (e i ) = (R (v 1 ) + . . . + R (v i )) -(R (u 1 ) + . . . + R (u i-1 )) , R e ′ i = (R (u 1 ) + . . . + R (u i )) -(R (v 1 ) + . . . + R (v i )) . 3. For m ≤ j < n + m R (e i ) = (R (v 1 ) + . . . + R (v i )) -(R (u 1 ) + . . . + R (u i-1 )) , R e ′ i = (R (u 1 ) + . . . + R (u i )) -(R (v 1 ) + . . . + R (v i )) .
Furthermore, there are close connections between the costs measured in terms of nodes and edges. For any Manhattan routing R we have

R E i, j-1 + R E ′ i-1, j = R V i, j = R E i, j + R E ′ i, j .
Since the cost function f (x) = x α is convex, we get

R V i, j α ≥ R E i, j α + R E ′ i, j α ,
what leads to useful inequalities between the costs related to vertices and edges:

∑ v∈DV l R (v) α ≥ ∑ e∈DE l R (e) α and (7)
∑

v∈DV l R (v) α ≥ ∑ e∈DE l-1 R (e) α . (8)
4.2.6 Routing scheme C for Max-MP.

We define the routing scheme C for Max-MP by putting a limit on the transmission going through vertices. Since each diagonal of vertices has a total transmission of exactly K, we set an equal value of transmission for all vertices in the layer: Taking into account equation ( 5), this gives us the following value of transmission for vertices of the grid:

∀ v∈DV j C (v) = K |DVj| . (9)
C V i, j =      K i+ j-1 if 1 ≤ i + j -1 ≤ n, K n if n ≤ i + j -1 ≤ m, K n+m+1-i-j otherwise. ( 10
)
To verify that this routing is well-defined, we compute transfers over each edge based on the transfers on vertices. Examples of transfers obtained using this algorithm are shown in Fig. 29.

Algorithm 5 C routing {for Max-MP, cf. [START_REF] Benoit | Power-aware manhattan routing on chip multiprocessors[END_REF]} Input: A set of arbitrarily splittable requests of total size K in a m × n grid. Solution: For each diagonal DE j of the grid, 1 ≤ j < n + m, set the flow on its successive horizontal edges e i and vertical edges e ′ i , 1 ≤ i ≤ j, as follows:

• If 1 ≤ j < n, set C (e i ) := K i j -K i j+1 and C (e ′ i ) := K i j+1 -K i-1 j . • If n ≤ j < m, set C (e i ) := K i n -K i-1 n = K n and C (e ′ i ) := 0. • If m ≤ j < n + m, set C (e i ) := K i n+m-j -K i-1 n+m-j-1 and C (e ′ i ) := K i n+m-j-1 -K i n+m-j .
The scheme C is a reformulation of the algorithm studied in [START_REF] Benoit | Power-aware manhattan routing on chip multiprocessors[END_REF], where it was shown that it admits a constant (depending only on α) approximation ratio for Max-MP. Proof. To analyze the cost of C, we have:

cost (C) = n+m-2 ∑ k=1 ∑ e∈DE k C (e) α = m-1 ∑ k=n ∑ e∈DE k C (e) α + 2 n-1 ∑ k=1 ∑ e∈DE k C (e) α ≤ (m -n) • n • K n α + 2 n ∑ k=2 ∑ v∈DV k C (v) α = (m -n) K α n α-1 + 2 n ∑ k=2 K α k α-1 ≤ (m -n) K α n α-1 + 2 ∞ 1 K α x α-1 dx = K α • m -n n 1 n α-2 + 2 (α -2) = Θ (K α ) .
Although such a solution has (up to a constant factor) optimal power cost, it can result in a single request being split into a very large number of paths. Indeed, for a given graph G = (V, E) and any flow f on G, f can be represented as the union of at most |E| weighted paths. It follows that both OPT routing (computed through convex optimization) and C routing require O(nm) splits per request. We conjecture that those routings require in fact Θ(nm) requests. In the next section, we will show that it is possible to preserve a constant approximation ratio of the optimal cost, while using a much smaller number of splits, sublinear in the dimensions of the grid.

Schemes for k-Splittable Routing

In this section, we present three schemes for solving the k-Path Manhattan Routing problem (k-MP). The first two, denoted F k and D k , are designed for uniform sets of requests. As the bound k on the number of allowed paths per request tends to infinity, these approaches will be shown to converge to the performance of schemes OPT and C for Max-MP, respectively. The third scheme, denoted A k , is an extension of D k which also works for non-uniform sets of requests.

1-splittable routing with uniform requests

Let us start by considering the 1-MP routing policy, meaning that requests cannot be split. We can treat this problem as a discrete version of a continuous Max-MP problem. First, we will consider uniform requests (of equal sizes); without loss of generality, we can assume that the input consists of d requests of size 1, each.

This considered problem can be solved by the flow-based F 1 routing approach presented in Algorithm 6. The obtained solution is optimal, i.e. for uniform instances, we have cost(OPT 1 ) = cost(F 1 ). Moreover, using a classical min-cost flow algorithm, a F 1 routing can be found in polynomial time with respect to parameters n, m, and d. It is worth noting, that while designing F 1 algorithm, we did not use either the topology of the graph, or Manhattan Paths restriction. Thus, this approach (based on a folklore knowledge) will work in more general setting.

We will now provide asymptotic bounds on the size of the (optimal) solution to the uniform 1-MP problem. We obtain the lower bound by combining the lower bound for problem Max-MP (formula (4) with K = d), with an additional factor resulting from the discrete nature of 1-MP.

Algorithm 7 D 1 routing scheme {for uniform 1-MP} Input: A set of d unsplittable requests of size s = 1 in a m × n grid. Solution: For each diagonal DE j of the grid, 1 ≤ j < n + m, set the flow on its successive horizontal edges e i and vertical edges e ′ i , 1 ≤ i ≤ j, as follows: We consider two cases:

• If 1 ≤ j < n, set: D 1 (e i ) = d i j -d i j+1 and D 1 (e ′ i ) = d i j+1 -d i-1 j . • If n ≤ j < m, set D 1 (e i ) = d i n -d i-1 n and D 1 (e ′ i ) = 0. • If m ≤ j < n + m, set D 1 (e i ) = d i n+m-j -d i-1 n+m-j-1 and D 1 (e ′ i ) = d i n+m-j-1 -d i n+m-j .
• (i < d) Substituting x = d i , λ = d i -d i = d ′ i , we obtain ∑ v∈DV D 1 (v) α = (x -λ ) α (1 -λ ) i + (x + 1 -λ ) α λ i (using Taylor's series theorem, for some x -λ ≤ u 1 ≤ x ≤ u 2 ≤ x + 1 -λ ) = x α -λ αx α-1 + λ 2 2 α (α -1) u α-2 1 (1 -λ ) i+ + x α + (1 -λ ) αx α-1 + (1 -λ ) 2 2 α (α -1) u α-2 2 λ i (since u 1 ≤ x and u 2 ≤ x + 1 -λ ≤ 2x) ≤ ix α + iα (α -1) λ 2 2 (1 -λ ) + (1 -λ ) 2 2 λ 2 α x α-2 = i x α + O x α-2 = i d i α + O d i α-2 . • (i ≥ d) The sum simplifies to ∑ v∈DV D 1 (v) α = 0 • (i -(d mod i)) + 1 • (d mod i) = d.
Using the above lemma, we compute the cost of a D 1 routing as cost(D 1 ) = Θ(d α ) + Θ(nd). By Lemma 4.3.1, this cost is asymptotically the best possible for 1-MP. Proof. The lower bound follows from Lemma 4.3.1. We observe that cost(F 1 ) ≤ cost(D 1 ). Now, to provide an upper bound on cost of the D 1 routing scheme, we will consider two cases:

• (d ≥ n) Then, using Lemma 4.3.2 and inequalities (7-8), we have cost

(D 1 ) = n+m-2 ∑ i=1 ∑ e∈DE i D 1 (e) α = m-1 ∑ i=n ∑ e∈DE i D 1 (e) α + 2 n-1 ∑ i=1 ∑ e∈DE i D 1 (e) α ≤ (m -n) ∑ v∈DV n D 1 (v) α + 2 n ∑ i=2 ∑ v∈DV i D 1 (v) α = (m -n) n d n α + O d n α-2 + 2 n ∑ i=2 i d i α + O d i α-2
.

Moreover, we have

(m -n) • n • d n α + 2 n ∑ i=2 i d i α = (m -n) d α n α-1 + 2 n ∑ i=2 d α i α-1 ≤ (m -n) d α n α-1 + 2 n 1 d α x α-1 dx = d α • m -n n 1 n α-2 + 2 (α -2) 1 - 1 n α-2 = Θ(d α ). It follows that cost (D 1 ) ≤ Θ (d α ) + (m -n) n • O d n α-2 + O n ∑ i=2 i d i α-2 = Θ (d α ) + O d α-2 n 4-α + O n • max d α-2 ,

k-splittable routing with uniform requests

We now extend the results of the previous section to the case of k-MP uniform routing. We will consider uniform sets of d requests of total size K, i.e., of size K/d each. A natural generalization of D 1 routing, called D k routing, is presented in Algorithm 8. Since in a D k routing, we split the transmission of each request equally along its k paths, the cost of such a routing is the same as that of a D 1 routing on the extended set of kd requests of size K kd each. Hence, the following result follows directly from Theorem 4.3.3 by a scaling argument: cost(D k ) = Θ (K α )+Θ(K α n (kd) α-1 ). Next, we show that although D k only splits requests into paths

We end this subsection with a remark on the asymptotic behavior of the considered routing schemes for uniform instances, when k → +∞. Taking into account Theorems 4.2.2 and 4.3.4, we obtain the following proposition. .

Taking the limit when k → +∞, the claim follows.

Since in general, cost(C) > cost(OPT), it is natural to ask for a different routing scheme for k-MP with improved limit behavior. A natural candidate is F k routing, obtained by a natural generalization of F 1 routing, as given by Algorithm 9. This algorithm turns out to by asymptotically optimal when k → +∞. Proposition 4.3.7. For a grid of fixed dimension, lim k→+∞ cost(F k ) = cost(OPT).

Proof. Let us denote by OPT ′ an assignment of transfer sizes to edges of G obtained by rounding up the value of the transfer size in an OPT routing to the nearest integer multiple of K kd , i.e., for all edges e, OPT ′ (e) = K kd ⌈ kd K OPT(e)⌉. By the properties of the min-cost flow used in the design of F k , the assignment OPT ′ dominates the cost of the F k routing for the considered instance. Thus, we have, cost(F k ) ≤ cost(OPT ′ ) ≤ cost(OPT) + O nm • K kd α-1

.

Taking the limit when k → +∞, the claim follows.

k-splittable routing with non-uniform requests

We close our considerations with a discussion of the general (non-uniform) case, where no assumptions are made about the sizes of the routed requests. We first observe that the considered problem is computationally hard. Proof. The problem is obviously in NP, as one can easily calculate the cost of any solution in polynomial time.

The proof proceeds by reduction from PARTITION PROBLEM [START_REF] Karmarkar | The differencing method of set partitioning[END_REF]: "Given a set I of integers, decide if it is possible to partition I into subsets I 1 and I 2 such that ∑ I 1 = ∑ I 2 ."

For such an instance, we select the instance of 1-MP routing as follows: n = 2, m = 2, K = I and C = 4 1 2 ∑ s∈I s α .

Observe that by identifying the sets of requests routed along the 2 different paths of the grid with I 1 and I 2 , we have:

cost (I 1 , I 2 ) = 2 ∑ s∈I 1 s α + 2 ∑ s∈I 2 s α ≥ 4 1 2 ∑ s∈I s α = C
and equality in the bound is achieved only if ∑ s∈I 1 s = ∑ s∈I 2 s.

Despite the hardness of the considered problem, one can try to look for approximate solutions. Note that applying D k routing naively to a set of non-uniform requests could lead to excessive additional cost. However, by applying a careful modification of D k routing, called the A k routing scheme (Algorithm 10), we obtain a good tool for routing non-uniform requests on the grid.

For example, in the case of unsplittable requests (1-MP) of sizes {1, . . . , 1 t , ε, . . . , ε n•t }, D 1 treats each request equally, and so it could lead to grouping all t large requests into one path, giving:

cost = Θ(n • t α )
while the following cost is achievable by routing t requests of size 1

+ n • ε ≈ 1: cost = Θ(n • t + t α )
However, the Algorithm 10 gives an approximate solution for non-uniform k-MP routing.

Theorem 4.3.9. For non-uniform requests, A k finds a solution to k-MP whose cost is within a constant factor of the optimum k-splittable routing: cost(A k ) ≤ 2 4α-2 • cost(OPT k ).

Proof. It is enough to prove that for each edge diagonal DE, the cost induced by A k on this diagonal is bounded by a constant with relation to the possible cost of the optimal solution OPT k ∈ k-MP on this diagonal. 1. Partition the set of request sizes into the union of disjoint subsets, S = S 0 ∪ S 1 ∪ . . ., such that ∀ s∈S i 2 i ≤ s < 2 i+1 .

2. For all non-empty sets S i :

• Find a D k routing for the uniform instance consisting of |S i | requests of size 2 i+1 each.

• For all 1 ≤ j ≤ |S i |, route the j-th input request belonging to S i using the paths assigned to the j-th request in the corresponding D k routing. (taking into account that for s ∈ S i we have s < 2

• 2 i ) ≤ ∑ v∈DV ∑ i D[c i ] (v) • 2 • 2 i k α = 2 α ∑ v∈DV ∑ i : c i •k≤p D[c i ] (v) • 2 i k + ∑ i : c i •k>p D[c i ] (v) •
∑ v∈DV ∑ i : c i •k≤p D[c i ] (v) • 2 i k α ≤ ∑ v∈DV 2 • max i : c i k≤p D[c i ] (v) • 2 i k α ≤ 2 α ∑ v∈DV ∑ i : c i •k≤p D[c i ] (v) • 2 i k α = 2 α ∑ i : c i •k≤p k • c i 2 i k α For c i k > p, we have D[c i ](v) ≤ ⌈ c i •k p ⌉ ≤ 2 c i k p : ∑ v∈DV ∑ i : c i •k>p D[c i ] (v) • 2 i k α ≤ ∑ v∈DV ∑ i : c i k>p 2 • c i • k p • 2 i k α = 2 α • 1 p ∑ i : c i k>p c i • 2 i α • p.
OPT k [S i ] (v) + ∑ i : c i k>p OPT k [S i ] (v) α ≥ 1 2 α-1 ∑ v∈DV ∑ i : c i k≤p OPT k [S i ] (v) α + ∑ i : c i k>p OPT k [S i ] (v) α .
We put bounds on both parts of sum: The implementation and tests were implemented in GNU C++. The min-cost flow subroutines were implemented using the standard cycle-canceling method [START_REF] Klein | A primal method for minimal cost flows[END_REF].The results of the tests are deterministic and fully reproducible, independent of the test environment and the details of the implementation of the flow algorithms.

∑ v∈DV ∑ i : c i k≤p OPT k [S i ] (v) α = ∑ v∈DV ∑ i : c i k≤p ∑ s∈S i OPT k [s] (v) α ≥ ∑ i : c i k≤p ∑ s∈S i ∑ v∈DV OPT k [s] (v) α

Impact of k on the routing cost.

We start by studying the approximation ratio of algorithms F k and D k for increasing values of k, the allowed number of splits of each requests. In the first plot (Fig. 31), we fix the dimensions of the grid n, m = 30, model power cost exponent α = 2.5, plotting the values of cost(F k )/cost(OPT) and cost(D k )/cost(OPT) for k in the range k ∈ [START_REF] Beaumont | Using the last-mile model as a distributed scheme for available bandwidth prediction[END_REF]100]. For reference, we also provide the approximation ratio of C routing for the studied instance.

We observe that, as predicted by theory (Theorems 4.3.6 and 4.3.7), lim k→+∞ cost(F k ) = cost(OPT) and lim k→+∞ cost(D k ) = cost(C), and the respective costs converge to their limits quickly, reaching a point 10% over the respective limit already for k < n. In general, the convergence need not be monotone for either of the approximation algorithms, since partitioning a request into k + 1 equally-weighted paths may give worse results than partitioning it into k equallyweighted paths.

In our second plot (Fig. 32), we present more compelling evidence of the relation k = Θ n 1/(α-1) for the threshold split value resulting in asymptotically-optimal cost, derived theoretically as Theorem 4.3.5. Once again, we choose model parameter α = 2.5. In the experiment, we consider square grids of increasing size in the range n = m ∈ [10, 120], testing three different relations between n and k (k = 2n 1/2 , k = 3 2 n 2/3 , k = n). For each of these relations, we plot the approximation ratios cost(F k )/cost(OPT) and cost(D k )/cost(OPT). Based on the plot, we can presume that: We remark that the relation k ∼ n 2/3 precisely corresponds to the threshold exponent 1/(α -1) = 2/3 for the considered value of α. Thus, the limit behavior of all the algorithms is consistent with the theory derived in the previous section. We note that the cost achieved by both F k routing and D k routing is highly satisfactory, and that the performance of F k routing shows to be better than of D k in all of performed tests.

Effect of power exponent α.

In auxiliary experiments, we studied the effect of the power exponent α (which is a constant of the model) on the required threshold value of split parameter k. We tested the rate of convergence of the approximation ratio cost(F k )/cost(OPT) to 1 in a grid of dimensions n = m = 30 for three different values of the power exponent, α ∈ {2.5, 3, 3.5}. It was observed that the convergence is faster for larger values of α. This is consistent with the theoretical threshold, k = Θ n 1/(α-1) , whose growth rate decreases with the increase of α. (Results are depicted in Figure 33.)

Conclusion

The contribution of our study is twofold. On the one hand, we advance the theory of splitting of requests in Manhattan routing on the grid, and point out that in practice, only a relatively small number of splits per request will be beneficial from a power-cost perspective. On the other hand, we propose efficient approximation schemes for such a k-path routing problem. Experimental evidence corroborates the theoretical results, showing that the designed algorithms lead to routings with a cost which is, in practice, even superior to that resulting from our theoretical bounds.

In future work, it would be beneficial to improve the constant bounds on the approximation ratios of our algorithms, establishing more tightly their dependence on the power exponent α.

Another promising direction of study would consist in extending the model to be more general. We have put several limitations on grid topology, requests, routing policies and cost function, in order to simplify the problem. However, lifting or weakening some of the restrictions would make the model more realistic. One of possible ways of extending is allowing routing requests between multiple sources and targets on the grid. In such a study, we could try to repeat the framework used here, that is, start with continuous solutions and try a discretization. Starting point could be multi-commodity flows, or convex programming formulation. Another way of extending the model is by taking in consideration more general network topologies. The techniques used here could be translated into planar graphs.

105

In Chapter 3, we describe algorithms for the construction of efficient broadcast overlay networks. We consider the setting under LastMile model, where each node has strict incoming and outgoing connection capabilities. This broadcast problem is time-independent, i.e. we consider steady-state solutions. While incoming limits can be trivially discarded from the model, we name the outgoing capabilities of node i by b i . We also put restriction, that out-degree of each node d i is limited by b i T , where T is the achieved throughput. Such a limitation of the out-degree is justified by assuring that on average the outgoing edges of each node are close to T .

We show, that under such constraints, it is in general NP-Complete to decide if a given instance is feasible for given value of T . If we consider the problem of finding maximal possible T , our results are as follow. On the one hand, by dropping either degree constraints we can give simple expression for maximal possible T without those constraints, thus putting upper limit on the value of solution to the original problem. On the other hand, by restricting solutions to be represented by acyclic graph, we reduce original problem to one solvable by polynomial time algorithms, if we allow resource augmentation, that is d i ≤ b i T + O(1). Such a solution is in a constant ratio from our upper bound (factor of 2), thus giving us a provable constant ratio approximation algorithm under degree augmentation.

We also consider the original problem with an extended model, by introducing a classification of nodes into open and behind firewalls. The nodes behind firewalls are prohibited to communicate between each other, and can only communicate with open ones, which are under no restriction whatsoever. We repeat the same reasoning, providing on the one hand simple upper bound by analyzing unrestricted communication, and on the other hand a greedy algorithm for finding best acyclic solution. We end the chapter with a lengthy proof of a upper bound on ratio between both of them equal to 7 5 , thus proving that the greedy acyclic algorithm provides a constant approximation ratio to the original problem when considering firewalls.

Chapter 4 considers the problem of finding optimal routing strategies in a platform corresponding to a grid graph, with costs being power-usage aware (in the sense of integrated circuits scale). Thus, we assume that power usage on each edge is proportional to f α (for α ≈ 3), where f is the data transmission rate. Such assumption is justified by physical model of power usage and data transmission.

We are able to show, that in such a model, when considering simple model of routing connections between two endpoints only, and considering only Manhattan Paths, one can solve the underlying combinatorial problem, and achieve simple and elegant solutions when considering just one highly splittable request. We were able to reduce problem of unsplittable requests to solved problem of routing one splittable request, thus getting similar combinatorial schemes for routing. For the problem of routing several different requests, we provide an approximation algorithm.

a stronger model can be analyzed algorithmically. Our various attempts to solve similar problems to the ones considered in this chapter, but for a more general problem of trees (instead of star-like topology) proved unsuccessful: analogous approach of considering acyclic solutions does not lead to problems being easily solvable in polynomial time. The model described in Chapter 4 is simplistic, as it allows only a very limited cost function, limited routing policies, and considers only one pair of endpoints for requests. However there are plenty of possible routes to improve it. One can either try to solve similar problems, but for a more general class of graphs, for example planar graphs instead of grids. We believe this can be achieved using the same "analyze partial sums on diagonals" approach. A different approach would be to consider more general cost functions, for example with the incorporation of constant factors, or with weights varying between different edges. This seems necessary if we want the model and solutions derived here to better reflect real-life behaviors, furthermore the solution proposed considers pairs of endpoints as isolated and not interfering. This seems restrictive, and we hope to be able to derive solutions that can handle multiple arbitrary communications.

Figure 1 :

 1 Figure 1: Plot of total cumulative data sent or received, with one node sending simultaneously: to one node (on the left) or to two nodes (on the right).

Figure 2 :

 2 Figure 2: Plot of total cumulative data sent or received when one sending node transmits simultaneously to three receiving nodes.

Figure 3 :

 3 Figure 3: Plot of total cumulative data sent or received when one sending node transmits simultaneously to two receiving nodes.

Figure 4 :

 4 Figure 4: Two examples of shared bandwidth distributions when connecting repeatedly to the same two nodes.

Figure 5 :

 5 Figure 5: Plot of variability of individual measurements.

Figure 6 :

 6 Figure 6: Plot of variability of sharing bandwidth measurements.

Figure 7 :

 7 Figure 7: An asymmetry ratio cumulative distribution function (CDF), taken for all edges in the dataset. Calculated for S 3 dataset and bedibe dataset.

Figure 8 :

 8 Figure8: Plots showing values of measured outgoing bandwidth, sorted, for a given selected node from a S 3 dataset (planetlab7.millennium.berkeley.edu on the left,planetlab3.hiit.fi on the right). Plots taken from[START_REF] Beaumont | Using the last-mile model as a distributed scheme for available bandwidth prediction[END_REF].

Figure 9 :

 9 Figure 9: Comparison of performance of DMF (d = 10) and LastMile, done on S-cube dataset (on the left), bedibe dataset (on the right), full information (top) and partial information (bottom).

Figure 10 :

 10 Figure 10: Distribution of error ratios for 7 estimates of total throughput when one sender sends to two receivers.

Listing 2 . 1 :

 21 bedibe -example of usage d e f main ( a r g s ) : [V] = i n p . i n i t ( [ a r g s [ 1 ] ] ) M = m a k e c o m p l e t e (V) M = s e l e c t (M, g e t f i r s t ) A = n e i g h b o u r s (M, 3 2 ) LM = l a s t m i l e (A, l o g e x p = F a l s e , i t e r a t e d = True , a l p h a = 0 . 1 ) DMF = dmf (A, l o g e x p = F a l s e , d = 1 0) SEQ = s e q u o i a (M, t h e o r e t i c a l = True , n b t r e e s = 1 5 ) w i t h p l o t . P l o t ( " F i g u r e 4 a " ) a s p : p . a d d p l o t ( p l o t . s i m p l e c o m p (LM,M) , " l a s t m i l e -0.1-32 " ) p . a d d p l o t ( p l o t . s i m p l e c o m p (DMF,M) , "DMF-10-32" ) p . a d d p l o t ( p l o t . s i m p l e c o m p ( SEQ ,M) , " S e q u o i a " )

Figure 11 :

 11 Figure 11: Picture of a graph representation of a LastMile model, with thick red edges used to communicate between nodes in black.

Figure 12 :

 12 Figure 12: Picture of a graph representation of a Two-level LastMile model, with red edges used to communicate between nodes in black.

1 .

 1 In the presence of open and guarded nodes or with open nodes only, finding the best acyclic solution and finding the best cyclic solution are both NP-Complete in the strong sense (this is a new result, presented in Section 3.3.1).

5 b 3 = 4 b 5 = 1 b 4 = 1 b 1 = 5 Figure 13 :

 53451411513 Figure 13: An instance with n = 2 open nodes (in green) plus the source (in gray), m = 3 guarded nodes (in red) together with an optimal broadcast scheme of throughput 4.4. In this broadcast scheme, the outdegree of the source is o 0 = 5, the outdegree of every guarded node is o 3 = o 4 = o 5 = 2 and the outdegree of the two open nodes is o 1 = o 2 = 3.

  ).

Figure 15 :

 15 Figure 15: Solution used for the instances used in the reduction.

Theorem 3 . 4 . 1 .T + 1 ;

 3411 Given an instance I and a throughput T , it is possible to decide in linear time if T ≤ T * ac . Moreover if T ≤ T * ac , it is possible to compute in linear time a broadcast scheme of throughput T such that • for every guarded node j ∈ G , outdegree o j is bounded: o j ≤ b j • for at most one open node i, o i ≤ b i T + 3; • for all other open nodes, o i ≤ b i T + 2.

Lemma 3 . 4 . 5 .

 345 Let π k be the value of π in Algorithm 2 when the k-th open node has just been added. (|π k | = k, and π k ends with a ).

  1 and ω ends with . Since Algorithm 2 failed after ω, O(ω) + G(ω) < T . On the other hand, O(ω) ≥ b i , what implies b i < T and ∀k ≥ i, b k < T . Let π be any encoding word, and let us consider the largest sub-word π ′ ⊑ π such that |π ′ | = |ω| . If |π ′ | < |ω| , then there exists a word ρ ⊑ π such that |ρ| = |ω| and |ρ| > |ω| . Since this violates the conclusions of Lemma 3.4.5, π is not valid. If |π ′ | ≥ |ω| , then

Figure 20 :

 20 Figure 20: 3 examples of upload node repartition. A guarded node feeds at most 2 nodes partially (first example). An open node that is the first to feed the last guarded node (second example). General case for an open node (last example).

  * = min b 0 , b 0 +O n , and which builds a cyclic solution of throughput T , in which any node has outdegree o i ≤ max b i T + 2, 4 .

Lemma 3 . 6 . 2 .

 362 Let α > 0. If for every tight homogeneous instance, T * ac T * ≥ α, then for every instance T * ac T * ≥ α.

Figure 22 :

 22 Figure 22: Optimal acyclic schemes of σ 1 and σ 2 .

2 .Figure 23 :

 223 Figure 23: Worst case ratio between cyclic and acyclic optimal solutions on tight homogeneous instances. The bottom plane is5 7 ≃ 0.714.

Figure 24 :

 24 Figure 24: Average ratio between cyclic and acyclic optimal solutions of randomly generated instances.

Figure 25 :

 25 Figure 25: Notations used in the CMP grid model.

Figure 29 :

 29 Figure 29: Example of C routing on a 5 × 7 grid, with highlighted values of transfer on edges (on the left) and vertices (on the right)

Theorem 4 .

 4 2.2 ([13]). cost (C) = Θ (K α ) = Θ(cost(OPT)).

Figure 30 :

 30 Figure 30: Comparison of transfer values over one diagonal for a C routing with K = 14 (on the left) and a D 1 routing with d = 14 (on the right)

Theorem 4 . 3 . 3 .

 433 For a uniform set of d requests (with total size K = d): cost (D 1 ) = Θ (d α ) + Θ (nd) and cost (F 1 ) = Θ (d α ) + Θ (nd) .

D 1 D 1 2 ==

 112 d α-2 n 3-α = Θ (d α ) + O d α-2 n 4-α + O d α-2 n + O d α-2 n 4-α = Θ (d α ) ,where the last step holds since 1 ≤ n ≤ d and α > 2.• (d < n) In this case, we have:cost (D 1 ) = (e) α ≤ ≤ (n + m -2d + 2) d + 2 (v) α = O (nd) + 2 O (nd) + Θ (d α ) + O d max d α-2 , d = O (nd) + Θ (d α ) .

Proposition 4 . 3 . 6 .

 436 For a grid of fixed dimension: lim k→+∞ cost(D k ) = cost(C). Proof. Let us denote by C ′ an assignment of transfer sizes to edges of G obtained by rounding up the value of the transfer size in an C routing to the nearest integer multiple of 2K kd , i.e., for all edges e, C ′ (e) = 2K kd ⌈ kd 2K OPT(e)⌉. By the properties of the rounding operation used in the design of D k , the assignment C ′ dominates the cost of the D k routing for the considered instance. Thus, we have, cost(D k ) ≤ cost(C ′ ) ≤ cost(C) + O nm • K kd α-1

Algorithm 9 F

 9 k routing scheme {for uniform k-MP} Input: A set of d k-splittable requests, of size K/d each, in a m × n grid. Solution: Split each of the requests into k smaller ones, each of size K kd . Return the F 1 routing of the new set of requests.

Theorem 4 . 3 . 8 .

 438 The following decision version of non-uniform 1-MP routing is (weakly-)NPcomplete: "Given (n, m, K = (K 1 , . . . , K i ) ,C, α), decide if it is possible to perform 1-MP routing with cost ≤ C."

Algorithm 10 A

 10 k routing scheme {for non-uniform k-MP} Input: A set of d k-splittable requests, of given sizes S = (s 1 , s 2 , . . . , s d ) (with 1 = s 1 ≤ s 2 ≤ . . . ≤ s d ), in a m × n grid. Solution:

  We keep the notation c i = |S i |, and recall that DV denotes the vertex diagonal adjacent to DE. Also, let p = |DV |, and let D[S i ] refer to the discrete D 1 routing scheme applied inside S i . We havecost (DE, A k ) = ∑ e∈DE A k (e) α ≤ ∑ v∈DV A k (v) α

.

  account that ∀ a,b≥0 (a + b) α ≤ 2 α-1 (a α + b α )) ≤ 2 2α-1 ∑ v∈DV ∑ i : c i •k≤p D[c i ] (v) • 2 i k α + ∑ i : c i •k>p D[c i ] (v) • 2 i k α Observe that D[c i ](v) ≤ ⌈ c i •k p ⌉. Consequently, for c i • k ≤ p, we have D[c i ](v) ∈ {0,1}, and since 2 d + 2 d-1 + . . . < 2 • 2 d :

99α 1 2

 1 Adding the two sums, we can write in general:cost (DE, A k ) ≤ 2 3α-1 •Now we proceed to bound the cost induced on diagonal DE by OPT k routing. By OPT k [S i ], we will denote OPT k restricted to requests from S i , and by OPT k [s] we will understand OPT k restricted to request s. We havecost (DE, OPT k ) = ∑ e∈DE OPT k (e) α ≥

(α

  observing that ∑ v∈DV OPT k [s](v) = s, and s can be split into at most k parts)In the second part, we obtain:∑ v∈DV ∑ i : c i k>p OPT k [S i ] (v) α ≥ p • 1 p ∑ v∈DV ∑ i : c i k>p OPT k [S i ] (v)

.

  Combining the lower-bound on the cost of OPT k and the upper bound on the cost of A k , we finally obtain cost (DE, A k ) ≤ 2 4α-2 cost(DE, OPT k ), which proves that A k is a (2 4α-2 )-approximation algorithm for non-uniform k-MP.

Figure 31 :

 31 Figure 31: Effect of k on the cost of F k and D k routing for a 30 × 30 grid.

Figure 32 :•••

 32 Figure 32: Approximation ratio for F k and D k routing schemes in a n × n grid. We considered split parameter k ∼ n β , for β greater, equal and smaller than 1/(α -1), [α = 2.5].

5 Figure 33 :

 533 Figure 33: Effect of α on cost(F k )/cost(OPT), working on a 30 × 30 grid.

Table 1 :

 1 Mean and median relative error for 7 estimation techniques two receivers. Hence summing the individual performance of both receivers yields a large overestimate of the actual total throughput. This explains why using average or maximum values give better predictions. Actually, using the Max estimate gives the best results in most cases, because the maximum measured individual throughput is very often close to the outgoing bandwidth of the sender. This explains that the median error ratio of Max is much lower than all other estimates.

	Est.	LM	Avg	Sum	Max	AvgDMF	SumDMF MaxDMF
	Mean	0.851	1.32	1.62	0.983	1.89	2.04	0.941
	Median 0.236	0.217	0.823	0.15	0.564	0.755	0.218

Table 2 :

 2 Execution of Algorithm 2 on the instance of Figure 13. Observe that the amount of openopen transfer (W (π)) is only 3 whereas in the acyclic scheme proposed in Figure 14 this amount is 4. Another parameter that is common to each partial conservative solution of C π is W (π), the amount of transfer going from open nodes to other open nodes. This parameter satisfies the following recursive equations

  Algorithm 3 GreedyTest(T ), Acyclic Algorithm on open/guarded nodes.

	3:	if O(π) + G(π) < T then return FAIL
	4: 5:	i ← |π| ; j ← |π| ; l ← if i = n then
	6:	if j = m then
	7: 8: 9:	l ← else if j = m -1 then if O(π) < T or b n+ j+1 < b i+1 then
	10: 11:	l ← end if
	12:
	13: 14:	l ← end if
	15:	end if
	16: 17:	π ← πl

1: π ← ε 2: while |π| < n + m do else if O(π) < T or O(π ) + G(π ) < T then

  where g next is the bandwidth of the next guarded node to be fed. Let β be the remaining bandwidth of node i at that point. By the definition of O, β ≤ O. At this moment, Algorithm 2 decides to switch to open nodes. Open nodes are fed using guarded bandwidth at first. If any open node is fed using α

http://www.planet-lab.org

http://www.splay-project.org

Communication and routing rules.

The study of routing with Manhattan-type paths (of shortest length) is motivated by practical concerns, in particular, the need to minimize communication latency, and to confine communications between nearby processors to a local area of the grid. For the purpose of the study of single sourcesink communications, it is assumed that the source and target are placed in the opposite corners of the grid; for communications between a different pair of nodes, considerations can be restricted to the respective rectangular sub-grid.

A routing R of a single communication request of size s is a weighted set of paths, {(w 1 , p 1 ) , . . . , (w k , p k )}, where each path p i starts at the same source vertex V 1,1 , and ends at the same target vertex V m,n in the opposite corner of the grid. The real-valued weights w i satisfy w i ≥ 0 and ∑ i w i = s. This definition of a routing naturally extends to a set of d ≥ 1 requests, which may be uniform (with identical request size s = K/d, where K is total size of requests), or non-uniform (with possibly distinct request sizes s 1 , . . . , s d ).

Given a routing R, we define R (e) as the size of the transmission going through an edge e, i.e.: R(e) = ∑ i : e∈p i w i . We will adapt this notation accordingly for routings denoted by letters different from R.

The routing policy is expressed by the bound k on the splitability of each request:

• In 1-Paths Manhattan Routing (1-MP), single communications are atomic and we are not allowed to divide them into smaller parts. However, there may be several requests between the same pair of endpoints, so in fact this model doesn't differ much from the following ones. • In Max-Paths Manhattan Routing (Max-MP), the number of paths allowed for each request is unbounded (k = +∞). called C which has equivalent properties, but is described from a different perspective, based on load balancing on so-called vertex diagonals. We will then use this scheme as a starting point for schemes solving k-MP.

A better lower bound (in terms of constant) for max-MP routing can be obtained by a carefull estimation. Based on a remark that every diagonal DE k has to transmit K in total.

.

However, one can easily see that this construction is unfeasible in Manhattan Paths, even for small values of n (it violates network flow property of equal incoming and outgoing transmission for vertices). We give example of the construction in the Figure 27.

Our approach: load balancing on vertex diagonals.

In all of the routing schemes we propose in this chapter, we will attempt to perform "load balancing" of paths with respect to transmission through vertices rather than edges. Hence, in a similar We introduce the notion of the l-th vertex diagonal, denoted as DV l (1 ≤ l ≤ n + m -1) by splitting the set of vertices according to their distance from the source, as follows (see Fig. 28 for an illustration): V i, j ∈ DV l , iff i + j = l + 1. Likewise, by the l-th edge diagonal, denoted DE l (1 ≤ l ≤ n + m -2), we mean the set of edges connecting vertices from DV l and DV l+1 , namely:

and

We start by observing that the values of R(v) uniquely determine the values of R(e). This property will allow us to design routing schemes simply by setting R(v) for all nodes.

Lemma 4.2.1. Given arbitrary Manhattan-Paths routing R, we can compute the values of R(e) from the values of R(v).

Proof. We will look at DE j for various values of j. We denote DV j = {v 1 , v 2 , . . .} and DV j+1 = {u 1 , u 2 , . . .}, with vertices reverse-ordered by first coordinate. Also, the edges in DE j = {e 1 , . . .} ∪ {e ′ 1 , . . .} are assumed to be reverse-ordered by first coordinate respectively horizontal and vertical edges.

Algorithm 6 F 1 routing scheme {optimal solution to uniform 1-MP} Input: A set of d unsplittable requests of size s = 1 in a m × n grid. Solution:

2. For every directed edge e ∈ E(G), add d weighted directed edges to G ′ , having the same endpoints as e, and weights given as:

3. Return the min-cost flow of size d in G ′ , using the two opposite corners of the grid as the source and sink.

Proof. The bound Ω (d α ) holds since we cannot get a better solution than the one of Max-MP with the same set of requests. Since each message of size 1 induces a cost at least n + m -2, by the convexity of the cost function, we get a total cost of Ω (nd) for d of them.

To provide a complementary upper bound on the size of 1-MP routings, we do not analyze the optimal scheme F 1 , but instead propose an approximation scheme called D 1 routing, which turns out to be easier to analyze.

We design the D 1 routing through a discretization of the construction of C routing proposed in the previous section for Max-MP. Similarly to equation ( 9), we will place limits on the size of the transfer going through vertices. Consider the vertex diagonal DV p with 1 ≤ p ≤ n + m -1, and let i = DV p . Suppose that the vertices of DV p are ordered by decreasing first coordinate, as DV p = {v 1 , . . . , v i }. Then, for 1 ≤ j ≤ i, we successively set D 1 v j so that at each step, the following condition holds: D 1 (v 1 ) + . . . + D 1 v j = ⌊d • j i ⌋. This is achieved by setting

To verify the correctness of this construction, we deduce transfer values over vertical and horizontal edges from values over vertices; a formal implementation of D 1 routing is provided in Algorithm 7.

An exemplary comparison of the vertex and edge transfers for C routing and D 1 routing is shown in Fig. 30.

We start the analysis of the cost of D 1 routing with the following lemma.

Lemma 4.3.2. Let DV be an arbitrary vertex diagonal, and let

Proof. By equation [START_REF] Beaumont | Using the last-mile model as a distributed scheme for available bandwidth prediction[END_REF] we get (substituting

Algorithm 8 D k routing scheme {for uniform k-MP} Input: A set of d k-splittable requests, of size K/d each, in a m × n grid. Solution: Split each of the requests into k smaller ones, each of size K kd . Return the D 1 routing of this new set of requests.

of equal weight, one cannot achieve a better asymptotic result by using unequal splits, i.e. for any R ∈ uniform k-MP : cost(R) = Ω (K α ) + Ω(K α n (kd) α-1 ). Combining these results, we obtain the following theorem, stating the optimality of D k in the class of k-splittable routings.

, where OPT k denotes the optimal cost solution of the considered set of requests for k-MP.

Proof. We have already established that for R ∈ Max-MP, cost(R) is in Ω(K α ), which also holds for k-MP. For the second part of the lower bound, we use the convexity of the cost function and the fact that on any diagonal, the stream of the routing of the d requests can be split into at most kd distinct paths, i.e.

Combining the bound on cost(OPT k ) in the above Theorem with the bound on cost(OPT) in Theorem 4.2.2 for Max-MP routing, we obtain our main result: the threshold value of k for which imposing a limit of k into which each request can be split does not affect the asymptotics of power cost.

Theorem 4.3.5. For uniform requests, imposing a routing policy with a split limit of k

does not affect the power cost, i.e. cost(OPT k ) = Θ(cost(OPT)), and 1 α-1 is the smallest possible exponential.

Proof. To prove that Θ

) and by Theorem 4.3.4 we obtain:

), the lower bound on cost becomes:

We end this section with a similar threshold theorem as Theorem 4.3.5 for the uniform case, obtaining bounds on value of k for which a split limit of k does not affects the asymptotics of the routing cost. However, in this case, the threshold depends on the structure of the set of requests, hence we only provide lower and upper bounds. Theorem 4.3.10. For non-uniform requests, imposing a routing policy with a split limit of k 1. always increases the asymptotic power cost (i.e. cost

does not affect the asymptotic power cost (i.e. cost (OPT

Proof.

1. The optimal-cost routing for a set of d requests of total size K, each of which can be split into k paths, cannot be better than the optimal-cost routing on a single request of size K, which can be split into kd parts. The latter routing problem belongs to uniform (k • d)-MP and so, using Theorem 4.3.4, we can write

2. Only the upper bound needs to be shown. Observe that the cost of an optimal k-MP routing cannot decrease if we replace a pair of requests of size s 1 , s 2 by a single request of size s 1 +s 2 . By iterating the argument, we can upper-bound the value of OPT k for a given instance of d requests of total size K by the value of OPT k for an instance consisting of a single request of size K. Once again, the claim follows by an application of Theorem 4.3.4.

Experimental results

In this section we provide the results of experimental evaluation of the algorithms presented in the previous section. We analyze the effect of n, k and α on the efficiency of solutions found for k-MP routing of instances with uniform (identical-size) requests. Throughout the section, we choose the number of requests as d = 1 (for uniform instances, other values result only in a scaling factor for k in k-MP, and do not affect Max-MP). We focus on the approximation ratio, looking at the cost of the routing obtained using the two schemes designed for uniform k-MP (D k , F k ), relative to the cost of the optimal solution OPT to Max-MP, which is treated as the reference solution. In some graphs, we also provide the cost of the sub-optimal Max-MP routing C as an additional reference.

We recall that the cost of the optimal solution to Max-MP, cost(OPT k ), is bounded from below by cost(OPT), and from above by both cost(D k ) and cost(F k ).

Conclusion Summary of the Results

In this work we present results concerning various topics.

In Chapter 1, we discuss bandwidth measurements between hosts over the Internet. First, we present point-to-point measurements. Such measurements are available in the form of datasets. We provide our dataset, named bedibe, together with measurement methodology that was used to obtain it. The platform used was PlanetLab, together with SPLAY middleware used to deploy Lua code.

We also present a new kind of dataset, a bandwidth sharing dataset. We discuss why is it enough to collect data in the form of one-to-two experimental setting. This dataset was also obtained using PlanetLab and SPLAY.

Our bandwidth sharing dataset shows very high variability, when looking at the repeated measures over the same configuration of nodes, of individual values over the edges. This variability is greatly reduced when looking at the sum of bandwidth achieved to both receiving nodes. We conjecture that this is due to the fact that the output bandwidth of the sending node is the limiting factor in those scenarios.

Chapter 2 introduces the notion of Network Prediction Systems. We describe various existing algorithms used for latency and bandwidth predictions. We show that DMF algorithm, based on matrix factorization, can be successfully adapted from predicting latencies to bandwidth predictions. We also describe LastMile model, together with several algorithms to instantiate this model, varying in form of complexity.

We also provide in this chapter an evaluation of these prediction algorithms using two datasets, S 3 (obtained by HP project on PlanetLab) and bedibe. We analyze the differences between the performance of the algorithms (in general DMF outperforms other algorithms), and also we analyze the differences between these datasets (S 3 proved easier to predict).

We also discuss the topic of predicting bandwidth in a scenario with congestion. We show that the LastMile model naturally extends its usability to such scenarios. We also provide validation of such predictions using one-to-two datasets described above.

Another contribution presented in this chapter is bedibe, a software created to automatize prototyping, testing and evaluation of various prediction algorithms. This software package, in the form of Python libraries, was extensively used when preparing this work.

Concluding Remarks

Based on our findings, we conclude that LastMile is a proper model to be used for construction of bandwidth-aware algorithms. The experimental evaluation done in Chapter 2 shows that LastMile performs worse than Matrix Factorization based algorithms, when we compare prediction ability for point-to-point scenarios. However, by sacrificing strength of prediction, we can gain a model with an intuitive interpretation of parameters, that can be easily instantiated. and that is much better suited for algorithmic design. Experimental data described in Chapter 1 exhibit high variability (in point-to-point case), and prove it impossible to predict the bandwidth sharing scenario. Still, we can derive prediction models from LastMile able to predict with ratio similar to variability of original data, the value of total bandwidth used by the sender.

We believe that this is advantageous, as it makes algorithmic analysis as presented in Chapter 3 possible. The model coupled with a method of instantiation of its parameters leads us to an algorithm for constructing an efficient broadcast overlay network. This overlay does not specify which chunk of data to be transferred when, and gives us only information on usage of edges between any two given nodes of the network. We resolve the issue by using Massoulié's distributed algorithms ( [START_REF] Massoulie | Randomized decentralized broadcasting algorithms[END_REF]), which by a simple randomized algorithm achieves optimal broadcast throughput.

We believe that this framework, where we start with proposing a model, then we design algorithms to instantiate a parameters of the model, use them to construct efficient overlay broadcast network, and finally apply distributed broadcast algorithm to achieve optimal broadcast rate, proves to be an important contribution in creation of bandwidth-aware solutions deployable over the Internet.

Future works

There are many topics left for future work.

Our datasets described in the Chapter 1 are relatively small. We feel that it would be very valuable to obtain larger ones. It might be hard to use highly limited platform as PlanetLab and still use brute-force method of measures. We consider two possible routes, either usage of different measure methodology, or moving to a different platform. The former solution, while still feasible when obtaining point-to-point measures (in fact S 3 dataset was obtained this way), may prove impossible when performing one-to-many measures. The latter one may prove a huge organizational problem, as the machines used in the platform should be spread across the globe to provide insightful measures over the Internet.

Chapter 2 leaves open question of designing improved version of LastMile prediction algorithm. We hope that the model we presented (2-level LastMile) or other models (one can think for example of trying to merge LastMile with a multi-level structures) can be proven to be easily instantiable and provide significantly better predictions than those based on basic LastMile model.

We encountered similar problem in the Chapter 3, in the sense of finding extension to the LastMile model. We would hope to develop further algorithmic approach derived there. We hope that either another extension to the LastMile model can be made (similar to the firewalls one), or