Retour au site du LAAS-CNRS

Abstract

This paper considers networks operating under ±-fair bandwidth sharing. When imposing a peak rate (i.e., an upper bound on the users transmission rates, which could be thought of as access rates), the equilibrium point of the fluid limit is explicitly identified, for both the single-node network as well as the linear network. More specifically, a criterion is derived that indicates, for each specific class, whether or not it is essentially transmitting at peak rate. Knowing the equilibrium point of the fluid limit, the steady-state behavior under a diffusion scaling is determined. This allows an explicit characterization of the correlations between the number of flows of the various classes.

Abstract

We consider bandwidth-sharing networks, and show how the SRPT (Shortest Remaining Processing Time) discipline can be used in order to improve the delay performance of the system. Our main idea is not to use SRPT globally between the traffic classes, which has been shown to induce instability, but rather deploy SRPT only locally within each traffic class. We show that with this approach, the performance of any stable bandwidth allocation policy can be improved. Importantly, our result is valid for any network topology and any flow size distribution. A numerical study is included to illustrate the results.

Abstract

Nous obtenons la politique optimale pour l'ordonnancement dans une file d'attente multi-classe avec un serveur unique. Nous appliquons les résultats de Gittins \cite{Git89}, où il avait trouvé la politique optimale qui minimise le temps moyen de sejour dans le système dans la file d'attente $M/G/1$ avec un serveur unique parmi toutes les politiques non-anticipatoires. Nous montrons que l'extension des résultats de Gittins permet de caractériser la politique d'ordonnancement optimale dans la file d'attente $M/G/1$ multi-classe. Nous appliquons le résultat général dans plusieurs cas, lorsque la distribution de temps de service a un taux de hasard décroissant, comme Pareto et hyper-exponentielle. Nous montrons que dans le cas de plusieurs classes, la politique optimale est la politique prioritaire, dans laquelle les tâches de classes différentes sont classifiés sur plusieurs niveaux de priorité en fonction de leur service obtenu. Nous obtenons pour chaque classe l'expression du temps moyen conditionnel de séjour en utilisant une approche de tâche marquées. Avec ça, nous comparons numériquement le temps moyen de séjour dans le système entre les politiques de Gittins et les politiques populaires comme PS, FCFS et LAS. Comme dans Internet, la distribution de la taille des fichiers est "heavy-tailed" et possède la propriété de DHR, la politique optimale de Gittins peut être appliquée dans les routeurs d'Internet, où les paquets générés par des applications différentes doivent être servis. Typiquement, le routeur n'a pas d'accès au temps exact de séjour requis (en paquets) de la connexion TCP, mais il peut avoir l'accès au service atteint de chaque connexion. Ainsi, nous implémentons l'algorithme optimal de Gittins en NS-2 et nous faisons des simulations numériques pour évaluer le gain de performance possible.

Abstract

In this paper, we investigate optimal load balancing strategies for a multi-class multi-server processor-sharing system with a Poisson input stream, heterogeneous service rates, and a server-dependent holding cost per unit time. Specifically, we study $(i)$ the centralized setting in which a dispatcher routes incoming jobs based on their service time requirements so as to minimize the weighted mean sojourn time in the system; and $(ii)$ the decentralized, distributed non-cooperative setting in which each job, aware of its service time, selects a server with the objective of minimizing its weighted mean sojourn time in the system. For the decentralized setting we show the existence of a potential function, which allows us to transform the non-cooperative game into a standard convex optimization problem. For the two aforementioned settings, we characterize the set of optimal routing policies and obtain a closed form expression for the load on each server under any such policy. Furthermore, we show the existence of an optimal policy that routes a job independently of its service time requirement. We also show that the set of servers used in the decentralized setting is a subset of set of servers used in the centralized setting. Finally, we compare the performance perceived by jobs in the two settings by studying the so-called Price of Anarchy (PoA), that is, the ratio between the decentralized and the optimal centralized solutions. When the holding cost per unit time is the same for all servers, it is known that the PoA is upper bounded by the number of servers in the system. Interestingly, we show that the PoA for our system can be unbounded. In particular this indicates that in our system, the performance of selfish routing can be extremely inefficient.

Mots-Clés / Keywords

Abstract

We consider the mean delay optimization in the M/G/1 queue for service time distributions that have a tail with decresing hazard rate (DHR). If the DHR property is valid for the whole distribution, then it is known that the Foreground-Background (FB) discipline, which gives full priority to the job with least amount of attained service, is optimal among nonanticipating scheduling disciplines. However, FB may fail to be optimal if the DHR property is valid only for the tail of the distribution. An important example is the Pareto distribution bounded away from zero. In this paper we show that for a wide class of service time distributions with a DHR tail (including the Pareto distribution), the optimal nonanticipating discipline is a combination of FCFS and FB disciplines, which gives full priority to the jobs with attained service less than some fixed threshold $\theta^*$. These priority jobs are served in the FCFS manner. If there are no jobs with attained service less than $\theta^*$, the full priority is given to the job with least amount of attained service.