The success of modern networked systems has led to an increased reliance and greater demand of their services. To ensure that the next generation of networks meet these demands, it is critical that the behaviour and performance of these networks can be reliably predicted prior to deployment. Analytical modeling is an important step in the design phase to achieve both a qualitative and quantitative understanding of the system. This thesis contributes towards understanding the behaviour of such systems by providing new results for two fluid network models: The stochastic fluid network model and the flow level model. The stochastic fluid network model is a simple but powerful modeling paradigm. Unfortunately, except for simple cases, the steady state distribution which is vital for many performance calculations, can not be computed analytically. A common technique to alleviate this problem is to use the so-called Heavy Traffic Approximation (HTA) to obtain a tractable approximation of the workload process, for which the steady state distribution can be computed. Though this begs the question: Does the steady-state distribution from the HTA correspond to the steady-state distribution of the original network model? It is shown that the answer to this question is yes. Additionally, new results for this model concerning the sample-path properties of the workload are obtained. File transfers compose much of the traffic of the current Internet. They typically use the transmission control protocol (TCP) and adapt their transmission rate to the available bandwidth. When congestion occurs, users experience delays, packet losses and low transfer rates. Thus it is essential to use congestion control algorithms that minimize the probability of occurrence of such congestion periods. Flow level models hide the complex underlying packet-level mechanisms and simply represent congestion control algorithms as bandwidth sharing policies between flows. Balanced Fairness is a key bandwidth sharing policy that is efficient, tractable and insensitive. Unlike the stochastic fluid network model, an analytical formula for the steady-state distribution is known. Unfortunately, performance calculations for realistic systems are extremely time consuming. Efficient and tight approximations for performance calculations involving congestion are obtained.

The success of modern networked systems has led to an increased reliance and greater demand of their services. To ensure that the next generation of networks meet these demands, it is critical that the behaviour and performance of these networks can be reliably predicted prior to deployment. Analytical modeling is an important step in the design phase to achieve both a qualitative and quantitative understanding of the system. This thesis contributes towards understanding the behaviour of such systems by providing new results for two fluid network models: The stochastic fluid network model and the flow level model. The stochastic fluid network model is a simple but powerful modeling paradigm. Unfortunately, except for simple cases, the steady state distribution which is vital for many performance calculations, can not be computed analytically. A common technique to alleviate this problem is to use the so-called Heavy Traffic Approximation (HTA) to obtain a tractable approximation of the workload process, for which the steady state distribution can be computed. Though this begs the question: Does the steady-state distribution from the HTA correspond to the steady-state distribution of the original network model? It is shown that the answer to this question is yes. Additionally, new results for this model concerning the sample-path properties of the workload are obtained. File transfers compose much of the traffic of the current Internet. They typically use the transmission control protocol (TCP) and adapt their transmission rate to the available bandwidth. When congestion occurs, users experience delays, packet losses and low transfer rates. Thus it is essential to use congestion control algorithms that minimize the probability of occurrence of such congestion periods. Flow level models hide the complex underlying packet-level mechanisms and simply represent congestion control algorithms as bandwidth sharing policies between flows. Balanced Fairness is a key bandwidth sharing policy that is efficient, tractable and insensitive. Unlike the stochastic fluid network model, an analytical formula for the steady-state distribution is known. Unfortunately, performance calculations for realistic systems are extremely time consuming. Efficient and tight approximations for performance calculations involving congestion are obtained.

La demande croissante pour les services de cloud computing encourage les opérateurs à optimiser l’utilisation des ressources dans les grappes d’ordinateurs. Cela motive le développement de nouvelles technologies qui rendent plus flexible la gestion des ressources. Cependant, exploiter cette flexibilité pour réduire le nombre d’ordinateurs nécessite aussi des algorithmes de gestion des ressources efficaces et dont la performance est prédictible sous une demande stochastique. Dans cette thèse, nous concevons et analysons de tels algorithmes en utilisant le formalisme de la théorie des files d’attente.Notre abstraction du problème est une file multi-serveur avec plusieurs classes de clients. Les capacités des serveurs sont hétérogènes et les clients de chaque classe entrent dans la file selon un processus de Poisson indépendant. Chaque client peut être traité en parallèle par plusieurs serveurs, selon des contraintes de compatibilité décrites par un graphe biparti entre les classes et les serveurs, et chaque serveur applique la politique premier arrivé, premier servi aux clients qui lui sont affectés. Nous prouvons que, si la demande de service de chaque client suit une loi exponentielle indépendante de moyenne unitaire, alors la performance moyenne sous cette politique simple est la même que sous l’équité équilibrée, une extension de processor-sharing connue pour son insensibilité à la loi de la demande de service. Une forme plus générale de ce résultat, reliant les files order-independent aux réseaux de Whittle, est aussi prouvée. Enfin, nous développons de nouvelles formules pour calculer des métriques de performance.Ces résultats théoriques sont ensuite mis en pratique. Nous commençons par proposer un algorithme d’ordonnancement qui étend le principe de round-robin à une grappe où chaque requête est affectée à un groupe d’ordinateurs par lesquels elle peut ensuite être traitée en parallèle. Notre seconde proposition est un algorithme de répartition de charge à base de jetons pour des grappes où les requêtes ont des contraintes d’affectation. Ces deux algorithmes sont approximativement insensibles à la loi de la taille des requêtes et s’adaptent dynamiquement à la demande. Leur performance peut être prédite en appliquant les formules obtenues pour la file multi-serveur. / The growing demand for cloud-based services encourages operators to maximize resource efficiency within computer clusters. This motivates the development of new technologies that make resource management more flexible. However, exploiting this flexibility to reduce the number of computers also requires efficient resource-management algorithms that have a predictable performance under stochastic demand. In this thesis, we design and analyze such algorithms using the framework of queueing theory.Our abstraction of the problem is a multi-server queue with several customer classes. Servers have heterogeneous capacities and the customers of each class enter the queue according to an independent Poisson process. Each customer can be processed in parallel by several servers, depending on compatibility constraints described by a bipartite graph between classes and servers, and each server applies first-come-first-served policy to its compatible customers. We first prove that, if the service requirements are independent and exponentially distributed with unit mean, this simple policy yields the same average performance as balanced fairness, an extension to processor-sharing known to be insensitive to the distribution of the service requirements. A more general form of this result, relating order-independent queues to Whittle networks, is also proved. Lastly, we derive new formulas to compute performance metrics.These theoretical results are then put into practice. We first propose a scheduling algorithm that extends the principle of round-robin to a cluster where each incoming job is assigned to a pool of computers by which it can subsequently be processed in parallel. Our second proposal is a load-balancing algorithm based on tokens for clusters where jobs have assignment constraints. Both algorithms are approximately insensitive to the job size distribution and adapt dynamically to demand. Their performance can be predicted by applying the formulas derived for the multi-server queue.

La demande croissante pour les services de cloud computing encourage les opérateurs à optimiser l’utilisation des ressources dans les grappes d’ordinateurs. Cela motive le développement de nouvelles technologies qui rendent plus flexible la gestion des ressources. Cependant, exploiter cette flexibilité pour réduire le nombre d’ordinateurs nécessite aussi des algorithmes de gestion des ressources efficaces et dont la performance est prédictible sous une demande stochastique. Dans cette thèse, nous concevons et analysons de tels algorithmes en utilisant le formalisme de la théorie des files d’attente.Notre abstraction du problème est une file multi-serveur avec plusieurs classes de clients. Les capacités des serveurs sont hétérogènes et les clients de chaque classe entrent dans la file selon un processus de Poisson indépendant. Chaque client peut être traité en parallèle par plusieurs serveurs, selon des contraintes de compatibilité décrites par un graphe biparti entre les classes et les serveurs, et chaque serveur applique la politique premier arrivé, premier servi aux clients qui lui sont affectés. Nous prouvons que, si la demande de service de chaque client suit une loi exponentielle indépendante de moyenne unitaire, alors la performance moyenne sous cette politique simple est la même que sous l’équité équilibrée, une extension de processor-sharing connue pour son insensibilité à la loi de la demande de service. Une forme plus générale de ce résultat, reliant les files order-independent aux réseaux de Whittle, est aussi prouvée. Enfin, nous développons de nouvelles formules pour calculer des métriques de performance.Ces résultats théoriques sont ensuite mis en pratique. Nous commençons par proposer un algorithme d’ordonnancement qui étend le principe de round-robin à une grappe où chaque requête est affectée à un groupe d’ordinateurs par lesquels elle peut ensuite être traitée en parallèle. Notre seconde proposition est un algorithme de répartition de charge à base de jetons pour des grappes où les requêtes ont des contraintes d’affectation. Ces deux algorithmes sont approximativement insensibles à la loi de la taille des requêtes et s’adaptent dynamiquement à la demande. Leur performance peut être prédite en appliquant les formules obtenues pour la file multi-serveur. / The growing demand for cloud-based services encourages operators to maximize resource efficiency within computer clusters. This motivates the development of new technologies that make resource management more flexible. However, exploiting this flexibility to reduce the number of computers also requires efficient resource-management algorithms that have a predictable performance under stochastic demand. In this thesis, we design and analyze such algorithms using the framework of queueing theory.Our abstraction of the problem is a multi-server queue with several customer classes. Servers have heterogeneous capacities and the customers of each class enter the queue according to an independent Poisson process. Each customer can be processed in parallel by several servers, depending on compatibility constraints described by a bipartite graph between classes and servers, and each server applies first-come-first-served policy to its compatible customers. We first prove that, if the service requirements are independent and exponentially distributed with unit mean, this simple policy yields the same average performance as balanced fairness, an extension to processor-sharing known to be insensitive to the distribution of the service requirements. A more general form of this result, relating order-independent queues to Whittle networks, is also proved. Lastly, we derive new formulas to compute performance metrics.These theoretical results are then put into practice. We first propose a scheduling algorithm that extends the principle of round-robin to a cluster where each incoming job is assigned to a pool of computers by which it can subsequently be processed in parallel. Our second proposal is a load-balancing algorithm based on tokens for clusters where jobs have assignment constraints. Both algorithms are approximately insensitive to the job size distribution and adapt dynamically to demand. Their performance can be predicted by applying the formulas derived for the multi-server queue.

La demande croissante pour les services de cloud computing encourage les opérateurs à optimiser l’utilisation des ressources dans les grappes d’ordinateurs. Cela motive le développement de nouvelles technologies qui rendent plus flexible la gestion des ressources. Cependant, exploiter cette flexibilité pour réduire le nombre d’ordinateurs nécessite aussi des algorithmes de gestion des ressources efficaces et dont la performance est prédictible sous une demande stochastique. Dans cette thèse, nous concevons et analysons de tels algorithmes en utilisant le formalisme de la théorie des files d’attente.Notre abstraction du problème est une file multi-serveur avec plusieurs classes de clients. Les capacités des serveurs sont hétérogènes et les clients de chaque classe entrent dans la file selon un processus de Poisson indépendant. Chaque client peut être traité en parallèle par plusieurs serveurs, selon des contraintes de compatibilité décrites par un graphe biparti entre les classes et les serveurs, et chaque serveur applique la politique premier arrivé, premier servi aux clients qui lui sont affectés. Nous prouvons que, si la demande de service de chaque client suit une loi exponentielle indépendante de moyenne unitaire, alors la performance moyenne sous cette politique simple est la même que sous l’équité équilibrée, une extension de processor-sharing connue pour son insensibilité à la loi de la demande de service. Une forme plus générale de ce résultat, reliant les files order-independent aux réseaux de Whittle, est aussi prouvée. Enfin, nous développons de nouvelles formules pour calculer des métriques de performance.Ces résultats théoriques sont ensuite mis en pratique. Nous commençons par proposer un algorithme d’ordonnancement qui étend le principe de round-robin à une grappe où chaque requête est affectée à un groupe d’ordinateurs par lesquels elle peut ensuite être traitée en parallèle. Notre seconde proposition est un algorithme de répartition de charge à base de jetons pour des grappes où les requêtes ont des contraintes d’affectation. Ces deux algorithmes sont approximativement insensibles à la loi de la taille des requêtes et s’adaptent dynamiquement à la demande. Leur performance peut être prédite en appliquant les formules obtenues pour la file multi-serveur. / The growing demand for cloud-based services encourages operators to maximize resource efficiency within computer clusters. This motivates the development of new technologies that make resource management more flexible. However, exploiting this flexibility to reduce the number of computers also requires efficient resource-management algorithms that have a predictable performance under stochastic demand. In this thesis, we design and analyze such algorithms using the framework of queueing theory.Our abstraction of the problem is a multi-server queue with several customer classes. Servers have heterogeneous capacities and the customers of each class enter the queue according to an independent Poisson process. Each customer can be processed in parallel by several servers, depending on compatibility constraints described by a bipartite graph between classes and servers, and each server applies first-come-first-served policy to its compatible customers. We first prove that, if the service requirements are independent and exponentially distributed with unit mean, this simple policy yields the same average performance as balanced fairness, an extension to processor-sharing known to be insensitive to the distribution of the service requirements. A more general form of this result, relating order-independent queues to Whittle networks, is also proved. Lastly, we derive new formulas to compute performance metrics.These theoretical results are then put into practice. We first propose a scheduling algorithm that extends the principle of round-robin to a cluster where each incoming job is assigned to a pool of computers by which it can subsequently be processed in parallel. Our second proposal is a load-balancing algorithm based on tokens for clusters where jobs have assignment constraints. Both algorithms are approximately insensitive to the job size distribution and adapt dynamically to demand. Their performance can be predicted by applying the formulas derived for the multi-server queue.

Nous étudions des modèles mathématiques issus de la théorie des files d’attente pour évaluer et optimiser les performances des mécanismes de partage de ressources entre flots dans les réseaux. Dans une première partie, nous proposons des approximations simples et explicites des principales métriques de performance des flots élastiques dans les réseaux à partage de bande passante opérant sous le mode ”équité équilibré”. Nous étudions ensuite le partage de bande passante entre flux élastiques et flux de streaming en supposant que le nombre de ces derniers est limité par un mécanisme de contrôle d’admission et proposons des approximations de performance basées sur une hypothèse de quasi stationnarité. Les résultats de simulation montrent le bon niveau de précision des approximations proposées.Dans une deuxième partie, nous étudions le compromis entre délai et énergie dans les réseaux à partage de bande passante dont les noeuds peuvent réguler leur vitesse en fonction de la charge du système. En supposant que le réseau est initialement dans un état de congestion, on s’intéresse à la politique optimale d’allocation de débit permettant de le vider à coût minimal. L’analyse de la politique stochastique optimale via la théorie des processus de décision markoviens étant extrêmement difficile, nous proposons de l’approximer en utilisant un modèle fluide déterministe qui peut être résolu grâce à des techniques de contrôle optimal. Pour le cas d’un seul lien partagé par plusieurs classes de trafic, on montre que la politique optimale correspond à la règle cμ et on propose une expression explicite de la vitesse optimale. Enfin, dans une troisième partie, on s’intéresse aux plateformes de Cloud Computing dans le cadre du modèle SaaS. En supposant un partage équitable des ressources physiques entre machines virtuelles s’exécutant de manière concurrente, nous proposons des modèles de file d’attente simples pour prédire les temps de réponse des applications. Les modèles proposés prennent explicitement en compte le comportement des différentes classes d’application (tâches interactives, de calcul ou permanentes). Les expérimentations menées sur une plateforme réelle montrent que les modèles mathématiques obtenus permettent de prédire les temps de réponse avec une bonne précision. / We study queueing-theoretic models for the performance evaluation and optimization of bandwidth-sharing networks. We first propose simple and explicit approximations for the main performance metrics of elastic flows in bandwidth-sharing networks operating under balanced fairness. Assuming that an admission control mechanism is used to limit the number of simultaneous streaming flows, we then study the competition for bandwidth between elastic and streaming flows and propose performance approximations based on a quasi-stationary assumption. Simulation results show the good accuracy of the proposed approximations. We then investigate the energy-delay tradeoff in bandwidth-sharing networks in which nodes can regulate their speed according to the load of the system. Assuming that the network is initially congested, we investigate the rate allocation to the classes that drains out the network with minimum total energy and delay cost. We formulate this optimal resource allocation problem as a Markov decision process which proves tobe both analytically and computationally challenging. We thus propose to solve this stochastic problem using a deterministic fluid approximation. For a single link sharedby an arbitrary number of classes, we show that the optimal-fluid solution follows thewell-known cμ rule and give an explicit expression for the optimal speed. Finally, we consider cloud computing platforms under the SaaS model. Assuming a fair share of the capacity of physical resources between virtual machines executed concurrently, we propose simple queueing models for predicting response times of applications.The proposed models explicitly take into account the different behaviors of the different classes of applications (interactive, CPU-intensive or permanent applications). Experiments on a real virtualized platform show that the mathematical models allow to predict response times accurately