Actes du 11ème Atelier en Évaluation de Performances › ... › aep11 › AEP11_CFP.pdf · 2016-03-09 · –Heavy-tailed asymptotics : We will explain the fundamental difference

Actes du 11ème Atelier enÉvaluation de Performances

Toulouse, 15–17 mars 2016

Éditeurs :Urtzi AYESTA, Balakrishna PRABHU, Maaike VERLOOP

site web : aep11.sciencesconf.org/

Soutiens :

aep11.sciencesconf.org/

Table des matières

Avant-propos 3

Programme 4

Exposés invités 6Exposés de synthèses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6Tutoriel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7Tutoriel-Démo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8Démo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

Résumés 9

Liste des inscrits 35

Liste des contributeurs 36

2

Avant-propos

Objectif

L’Atelier en Évaluation de Performances est une réunion destinée à faire s’exprimer etse rencontrer les jeunes chercheurs (doctorants et nouveaux docteurs) dans le domaine dela Modélisation et de l’Évaluation de Performances, une discipline consacrée à l’étude etl’optimisation de systèmes dynamiques stochastiques et/ou temporisés apparaissant en In-formatique, Télécommunications, Productique et Robotique entre autres.

La présentation informelle de travaux, même en cours, y est encouragée afin de renforcerles interactions entre jeunes chercheurs et préparer des soumissions de nouveaux projetsscientifiques. Des exposés de synthèse sur des domaines de recherche d’actualité, donnéspar des chercheurs confirmés du domaine renforcent la partie formation de l’atelier.

Historique

Démarré sous l’impulsion de l’équipe de Raymond Marie en 1991, l’atelier en évalua-tion de performance a eu lieu à Rennes (1991-93), Grenoble (95), Versailles (96), Paris ENS(01), Reims (03), Aussois (08) et Sophia Antipolis (14). L’objectif est de fédérer une com-munauté allant des probabilités aux expérimentations en informatique. Elle recouvre doncd’une part les thématiques portant sur la modélisation des systèmes complexes avec lesméthodes théoriques récentes, les environnements logiciels d’évaluation de performancesjusqu’aux retours d’expérimentations en vraie grandeur.

Comité Scientifique

Le comité scientifique est composé de : Jean-Michel Fourneau, Bruno Gaujal, Marc Le-large, Jean Mairesse, Laurent Truffet, et Bruno Tuffin.

Comité d’Organisation

Le comité d’organisation de la 11ème edition est composé de : Urtzi Ayesta, BalakrishnaPrabhu et Maaike Verloop. Il a pu compter sur l’aide précieuse de Caroline Malé.

Soutiens

L’Atelier a reçu le soutien du : ANR RACON, CNRS, GDR ASR, GDR RO, IRIT, LAAS,et NOKIA.

3

Programme

Mardi 15 mars 2016

12h00-12h30 : Accueil des participants au LAAS-CNRS

12h30-14h00 : Repas au hall central du LAAS-CNRS

14h00-15h00 : Exposé de synthèse

Patrick LoiseauStrategic resource allocation in adversarial environments (p. 5)

15h00-15h15 : Pause café

15h15-16h15 : Session : Performance Evaluation and Quality of Service, I

Farah Ait SalahtBornes stochastiques sur les mesures de performance pour desréseaux de files d’attente en tandem (p. 9)

Marziyeh BayatiManaging Energy Consumption and Performance in Data Centers (p. 11)


16h30-17h30 : Session : Performance Evaluation and Quality of Service, II

Yves MocquardCompter avec les Protocoles de Population (p. 13)

Jean Marie Garcia, Mohamed El Hedi BoussadaEvaluation des performances bout en bout du trafic TCPsous le régime "Équité Équilibrée" (p. 15)

18h30 - 19h30 : Réception avec cocktail à la mairie de Toulouse

Mercredi 16 mars 2016

09h30-10h30 : Tutoriel

Rudesindo Núñez-QueijaAsymptotic analysis techniques for performance evaluation - Part I (p. 6)


10h45-12h15 : Session : Game Theory

Stéphane Durand, Bruno GaujalAverage complexity of the Best Response Algorithm in Potential Games (p. 17)

Baptiste Jonglez, Bruno GaujalOptimal adaptive routing in packet-switched networks (p. 19)

Josu Doncel, Nicolas Gast, Bruno GaujalA Mean-Field Game with Explicit Interactions for Epidemic Models (p. 21)

4

Programme

12h15-14h00 : Repas au hall central du LAAS-CNRS14h00-15h00 : Exposé de synthèse

Nidhi HegdeTools for the analysis of content dissemination in social networks (p. 5)

15h00-15h30 : Pause café15h30-17h00 : Tutoriel-Démo

Jean-Michel Fourneau, Jean-Marc Vincent et Alain Jean-MarieOutils logiciels du projet ANR MARMOTE (p. 7)

19h30- : Dîner en ville

Jeudi 17 mars 2016

09h30-10h30 : TutorielRudesindo Núñez-QueijaAsymptotic analysis techniques for performance evaluation - Part II (p. 6)

10h30-10h45 : Pause café10h45-12h15 : Session : Control

Maialen Larranaga, Onno J Boxma., Rudesindo Núñez-Queija,Mark S. SquillanteEfficient content delivery in the presence of impatient customers andmultiple content types (p. 23)

Jérémie Leguay, Lorenzo Maggi, Moez Draief, Stefano Paris,Symeon ChouvardasAdmission Control with Machine Learning in Software Defined Networks (p. 25)

Nicolas Jara, Reinaldo Vallejos, Gerardo RubinoBlocking Evaluation of dynamic WDM networks withoutwavelength conversion (p. 27)

12h15-14h00 : Repas au hall central du LAAS-CNRS14h00-15h30 : Session : Streaming and resource allocation

Zakaria Ye, Rachid El Azouzi, Tania Jimenez, Stefan ValentinBackward-Shifted Coding (BSC) for HTTP Adaptive Streaming (p. 29)

Apostolos Destounis, Georgios Paschos, Iordanis KoutsopoulosResource Allocation for in-Network Computations (p. 31)

Imen Triki, Rachid El Azouzi, Majed HaddadAnticipating Resource Management and QoE Provisioning forVideo Streaming (p. 33)

15h30-15h45 : Pause café15h45-16h15 : Démo

Ahmad Al SheikhNEST - A demonstration on network modeling and simulation (p. 7)

16h15-17h00 : Discussions autour de l’organisation du prochain atelier

5

Exposés invités

Exposés de synthèse

Nidhi HegdeNokia, Paris

Tools for the analysis of content dissemination in social networks

Résumé : Information propagation in networks has been studied for decades. In the past,such "rumour spread" has been based on a model where a source emits an information whichthen spreads in the network according to push, pull, or hybrid mechanisms. The goal in suchwork has been to characterize the rate of spread across the whole network. More recently,information propagation from the perspective of social networks has been studied, where amore realistic model of multiple sources of information, and multiple ’types’ of informationis considered. In such a model, each node in the network has resource constraints and mustchoose on how to relay the information. In this overview, we will go over some recent workon information spread in social networks, covering analysis and algorithms for efficient dis-semination. In particular, we will consider distributed algorithms for optimal informationpropagation, and we review game-theoretic tools used in the characterisation of such distri-buted control problems in this model and its variants.

Patrick LoiseauEURECOM Institute, Sophia Antipolis

Strategic resource allocation in adversarial environments

Résumé : Allocation of resources is a well-known problem that is often solved by optimi-zation techniques. In adversarial environments, however, the objective function (or payoff)depends on on how an adversary allocates his resources. Examples of such situations are nu-merous and include allocation of security defenses to different targets (where the payoff de-pends on how an attacker allocates his attack resources) and allocation of advertisement/lob-bying resources to customers/voters (where the payoff depends on how a competitor allo-cates his resources). In such scenarios, the resource allocation problem becomes a game. Inthis talk, we review strategic resource allocation games. The fundamental model of strate-gic resource allocation is the Colonel Blotto game, proposed by Borel in 1921. Two playersallocate an exogenously given amount of resources to a fixed number of battlefields withgiven values. Each battlefield is then won by the player who allocated more resources to it,and each player maximizes the aggregate value of battlefields he wins. Despite its apparentsimplicity, the Colonel Blotto game is still unresolved in its most general form. We reviewexisting solutions and briefly mention some interesting variants of this game.

6

Exposés invités

Tutoriel

Rudesindo Núñez QueijaUniv. of Amsterdam et CWI, Amsterdam

Asymptotic analysis techniques for performance evaluation

Résumé : For many queueing systems exact analysis of performance measures such as queuelengths, waiting times and sojourn time is often out of reach. Also, average values may noteven be the most informative measures to describe a system’s performance, but one mayrather be interested in performance quantiles for example. For such cases a wide range ofasymptotic techniques are available that may serve to develop suitable approximations andprovide valuable insights. In this course we will briefly outline several such techniques (largedeviations and tail asymptotics, fluid and diffusion limits, perturbation analysis, heavy traf-fic limits) and illustrate them on queueing models such as GPS queues, DPS queues, andbandwidth-sharing networks. The main part of the tutorial will focus on a more detaileddiscussion of two particular techniques :– Heavy-tailed asymptotics : We will explain the fundamental difference with light tailed

asymptotics ("conspiracy" versus "disaster" scenarios) and illustrate several analysis tech-niques that one may resort to in obtaining asymptotically accurate estimates, includinganalytic asymptotics, probabilistic bounds and coupling arguments.

– Perturbation analysis (in particular time-scale separation) : analyzing Markovian que-ueing networks as multi-dimensional Markov processes may be notoriously difficult. Oneabstraction is to isolate the behavior of a single queue, and capture the influence of otherqueues in what is called the random environment. As the random environment changesstate, the queue can move from one mode of operation to another (for example from lightlyloaded conditions to overloaded conditions and back). Perturbation techniques provideapproximations when the state changes of the random environment occur on a much fas-ter or much smaller time scale than the queueing dynamics.

7

Exposés invités

Tutoriel-Démo

Jean-Michel Fourneaua, Jean-Marc Vincentb, Alain Jean-Marieca Université de Versailles Saint Quentin

b Université Joseph Fourierc INRIA Sophia-Antipolis Méditerranée

Outils logiciels du projet ANR MARMOTE

– Jean-Michel Fourneau : Xborne : génération, comparaison, résolution de chaînes de Mar-kov.

– Jean-Marc Vincent : Psi3 : modélisation par événements et simulation exacte de chaînes deMarkov.

– Alain Jean-Marie : marmoteCore : créer et résoudre des chaînes de Markov en C++.

Démo

Ahmad Al SheikhQoS Design, Toulouse

NEST - A Demonstration on Network Modeling and Simulation

Résumé : In this technical demonstration we will highlight key functionalities of NEST,QoS Design’s software suites aimed at network operators. We will first demonstrate NESTIP/MPLS as we focus on defining an IP/MPLS network and associated parameters and pro-tocols. Features such as tracing traffic flow routes throughout the network interfaces, editingaccess populations and technologies, and interpreting main simulation and performanceevaluation results will be presented. Afterwards, we will overview other NEST softwareconcerning optical networks and network supervision.

8

11ème Atelier en Evaluation de PerformancesToulouse, du 15 au 17 mars 2016

Bornes stochastiques sur lesmesures de performance pour desréseaux de files d’attente entandemFarah AIT SALAHT ∗

LIP6, Université Paris Ouest Nanterre4 place Jussieu, 75252 Paris cedex 05, FranceEmail : [email protected]

1. Introduction

Nous nous sommes intéressés dans ce travail àl’évaluation de performance de réseaux de filesd’attente en tandem, en temps discret. L’analysenumérique exacte de ces systèmes est très difficile,voire impossible à effectuer lorsque leur taille estgrande. Parmi les méthodes souvent utilisées dansla littérature, on cite la simulation qui est simpleet l’approche par décomposition. Cependant, cesapproches ne sont que des méthodes d’analyseapproximatives. Dans ce travail, nous proposonsd’avoir une démarche tout à fait différente quiconsiste à déterminer des bornes plutôt que desapproximations sur les processus exacts de sortiedu réseau (distributions de sortie, distribution depertes et délais de bout en bout).Pour notre étude, nous avons considéré des ar-rivées par batch, des services déterministes etdes files d’attente à capacité finies. Nous avonsainsi développé quatre approches d’analyse dis-tinctes permettant de déterminer des bornes sto-chastiques sur les mesures de performance du ré-seau sans aucune hypothèse sur le trafic en en-trée. Pour ces systèmes, nous avons montré grâceà certains résultats théoriques prouvés [1] et souscertaines conditions, la possibilité de déterminerdes encadrements fiables sur les mesures de per-formance. La garantie de la qualité de service re-présente bien évidemment notre objectif principaldans ce travail.

2. Bornes sur les mesures exactes des réseaux defiles d’attente en tandem

Nous considérons un réseau de files d’attenteen tandem en temps discret noté comme suit :H1/D/S1/B1→ /D/S2/B2 → . . . → /D/SN/BN,

∗. Ce travail a été réalisé avec H. Castel-Taleb, J.M. Fourneauet N. Pekergin.

composé de N files d’attente en série. Chaque filed’attente i possède un tampon de longueur finie Bi

et un service constant de capacité Si. Le systèmeest supposé vide au départ. Les données entrentdans la première file d’attente selon une distribu-tion d’arrivée H1, puis passent à travers les filesd’attente dans l’ordre : les données sortantes de lapremière file d’attente entrent au bout d’au moinsun intervalle de temps dans la deuxième file d’at-tente (système slotté), et ainsi de suite (voir fig. 1).

H1

S1 S2 SN

B1 B2 BN

FIGURE 1 – Réseau en tandem composé de N filesd’attente.

Lors de l’analyse de réseaux en tandem, nous re-marquons que lorsque la séquence des capacitésde service est croissante, l’analyse du réseau re-vient à étudier uniquement la première file. Si-non, des modifications peuvent être apportées auréseau initial simplifiant ainsi sa résolution. Pourcela nous introduisons les notions suivantes :Definition 1 (Bottlenecks) .– Une file i est bottleneck local (noté BL) si∀ j < i, Sj > Si.

– Une file i (i ≥ 1) est bottleneck global, noté BG si1. ∀j > 1, j 6= i : Sj > Si ;2. ou si Sj = Si, alors i < j.

Selon l’emplacement des bottlenecks dans le réseau,nous distinguons les cas suivants :

1. Bottleneck global en tête du réseau. Le faitque la file d’entrée du réseau soit un BG re-vient à dire que les files de 2 à N ne perdentaucune données. Dans ce cas, l’analyse du sys-tème peut être effectuée de façon exacte. Lapremière file est analysée. Pour les autres files,seuls les délais de traversée seront considérés.

2. Sinon, nous proposons de dériver une formeréduite du réseau initial (postprocessing sur ledélai et la taille du réseau) comme suit :

(a) Si nous avons une file i telle que i >BL(ou i >BG) et i n’est ni BL ni BG, alors lafile i est supprimée du réseau.

(b) Si nous avons une file i telle que i > 1 etqui est située avant le premier BL, alorsnous pouvons également l’éliminer.

Nous définissons au final un nouveau réseau ré-duit, composé uniquement de la première file d’at-tente du réseau initial, des bottlenecks locaux et

9

6 5 6 4 2 3

S1 S2 S3 S4 S5 S6

BL BL BG

BL BL BG

6 5 4 2

S1 S2 S4 S5

FIGURE 2 – Exemple de simplification d’un réseauen tandem.

du bottleneck global. Notre but à présent consisteà analyser ce nouveau réseau et déterminer desbornes sur ses mesures de performances. Une gé-néralisation au réseau initial sera ensuite effectuéeen ajoutant les temps de traversée des files nonconsidérées. Nous proposons quatre approchesd’analyse permettant de définir des bornes sto-chastiques (bornes "st") supérieures ou inférieuressur les paramètres du réseau en tandem : nombrede données traitées, délais de bout en bout etnombre de pertes dans le réseau. Notons que lacomparaison stochastique [3] est utilisée dans cetravail. Une brève description de la nature desbornes ainsi que de la démarche suivie pour laconstruction de ces approches est donnée ci-après.

2.1. Approche 1 : Bornes st-supérieures sur la dis-tribution de sortie et le délai de traversée duréseau

Nous utilisons dans cette approche le théorème deFriedman [2] sur l’interchangeabilité des files dansun réseau en tandem. Ce résultat stipule que pourdes tampons de capacité infinis, le délai de bout enbout dans un réseau en tandem ne dépend pas del’ordre des files dans le réseau. Ainsi, reposant surce résultat, nous proposons de fixer toutes les lon-gueurs des tampons des files d’attente du réseau àl’infinie, ce qui nous permet de dériver des bornessupérieures sur les mesures de performance du ré-seau initial. Puis, en utilisant la propriété d’inter-changeabilité, de déplacer la file bottleneck globalen tête du réseau et se ramener ainsi à l’analysed’une seule file d’attente (file BG).

2.2. Approche 2 : Bornes st-supérieures sur lesperformances d’une file i

Pour calculer les performances d’une file i du ré-seau, nous proposons de suivre les étapes sui-vantes : 1) fixer tous les tampons des files j < i àl’infini, ce qui nous permet de définir des bornessupérieures sur les performances de la file i ; 2) dé-terminer le BG parmi les files 1 à i − 1 et utiliserle théorème d’interchangeabilité de Friedman [2]pour déplacer la file BG en tête du réseau et enfin

3) éliminer les files 2 à i − 1. Cette approche nousramène à l’étude du système résiduel composé dela file 1 (file BG) et de la file i.2.3. Approche 3 : Bornes st-inférieures sur les

performances d’une file i

Pour cette approche, nous fixons les longueursdes tampons des files j < i à zéro. En effectuantcette modification, nous définissons des bornes in-férieures sur les paramètres de sortie de la file i. Deplus, l’analyse du réseau peut se résumer à l’ana-lyse de la file i uniquement, tel que l’histogrammed’entrée de la file i correspond au filtrage de la sé-quence d’entrée H1 du réseau sur tous les servicesdes files d’attente qui précèdent la file i.2.4. Approche 4 : Bornes st-supérieures sur les

performances d’une file i

Pour une file d’attente i (i > 1) du réseau, nousproposons de fixer les capacités de service des filesj < i à l’infini. Cette modification permet nonseulement de dériver des bornes supérieures surles nombres de données en sortie et le nombre totalde pertes dans le réseau, mais également de sim-plifier son analyse en se ramenant à l’analyse de lafile d’attente i uniquement avec comme séquenced’entrée H1.

3. Conclusion

Pour l’analyse d’un réseau en tandem, nous propo-sons dans un premier temps une simplification duréseau initial par la recherche de bottlenecks. Nousproposons par la suite d’utiliser l’une des quatreapproches proposées afin de dériver des bornes in-férieures ou supérieures prouvées sur des indicesde performance du réseau. Grâce à ces approches,on se ramène souvent à l’analyse de réseaux ré-duits plus simples qui permettent d’avoir des ga-ranties sur les mesures de performances exactes duréseau. Notons également que cette approche peutêtre étendue aux réseaux en arbres, car l’analysede ces réseaux peut s’effectuer en décomposant leréseau initial en sous-réseaux en tandem.

Bibliographie

1. F. Aït-Salaht. Chaînes de Markov Incomplètement Spé-cifiées : analyse par comparaison stochastique et appli-cation à l’évaluation de performance des réseaux. PhDthesis, Université de Versailles Saint-Quentin, 2014.

2. H. D. Friedman. Reduction methods for tandemqueueing systems 13 : 121–131, 1965.

3. A. Müller and D. Stoyan. Comparison Methods forStochastic Models and Risks. Wiley, New York, NY,2002.

10


Managing Energy Consumptionand Performance in Data CentersM. Bayati

AffiliationLACLUniversité Paris Est Cré[email protected]

1. Introduction

The increasing development of Date Centers is cau-sing problems in energy consumption. More than1.3% of the global energy consumption is due tothe electricity used by data centers, a rate that isincreasing, revealed by a survey conducted in [3],which says a lot about the increasing evolutionof data centers. Therefore, to ensure both a goodperformance of services offered by these data cen-ters and reasonable energy consumption, a detai-led analysis of the behavior of these systems isessential for designing efficient optimization algo-rithms to reduce the energy consumption. Two re-quirements are in conflict : (i) Switching on a maxi-mum number of servers leads to less waiting timeand decreases the loss of jobs but requires a highenergy consumption. (ii) Switching on a minimumnumber of servers leads to less energy consump-tion, but causes more waiting time and increasesthe loss of jobs. The goal is to design better ma-naging algorithms which take into account thesetwo constraints to minimize : waiting time, lossrate and energy consumption. In [4] Mitrani stu-dies the problem of managing a data center to keepa low energy consumption. This problem is mode-led by a queue in which jobs can leave the systemif the waiting time is too long. The proposed stra-tegy is to consider some servers as a reserve groupthat are gradually switched on when the numberof jobs in the buffer exceeds a certain threshold.Similarly these server groups are gradually swit-ched off when the number of jobs in the buffer de-creases and exceeds another threshold. The thre-sholds are analytically determined based on an ob-jective function that takes into account the parame-ters of the systems.In [2] we present, with other co-authors, a tool tostudy the trade-off between energy consumptionand performance evaluation. The tool uses realtraffic traces and stochastic monotonicity property

to insure fast computation. Given a set of para-meters that are fixed by the modeler, the tool de-termines the best threshold based policy. Our ap-proach differs from the methods presented in [1,4, 5] by several points. First it is numerical ratherthan analytical or simulation based. Thus, this pa-per considers less regular processes than the Pois-son process considered by Mitrani. Note that theMarkovian assumptions (Poisson arrivals, expo-nential services and switching times) and the in-finite buffer capacity are not mandatory for thisanalysis. However, here, the arrival process is as-sumed to be stationary for short periods of timeand change between periods. This allows us torepresent for instance hourly or daily variationsof the job arrivals. Real traffic traces are used toconstruct build discrete distributions for the job ar-rival.

2. Queuing model

In this work a data center is modeled by a discretetime queue with a finite buffer capacity and witha time slot equals to the sampling period used tosample the traffic traces. The job arrivals are speci-fied by a discrete distribution. The system is ana-lyzed for a finite time period (a day, a week). Thistime period is divided into sub-intervals where thebatch of arrivals are supposed i.i.d. We design anoptimization algorithm in order to manage energyconsumption and QoS in the data center. The costof the consumed energy depends on the numberof operational servers. The QoS cost depends onthe number of waiting time (which depends on thenumber of jobs in the buffer) and the losing rate(which depends on the number of lost jobs). Everyslot, our algorithm minimizes an objective functionthat combines the cost of energy and the cost ofQoS, in order to increase or decrease the number ofoperational servers according to traffic variation.As the model is solved numerically, it is much fas-ter and more accurate than simulation. The workconsiders several tests for various types of arri-vals : (i) arrivals with constant rate, (ii) arrivals de-fined by an i.i.d. discrete distribution, (iii) arrivalsspecified by a variable discrete distribution overtime, (iv) and arrivals modeled by discrete distri-butions obtained from real traffic traces.

3. Tests & results

The algorithm is tested by numerical analysis un-der various types of job arrivals. We use real traffictraces to model arrivals, using the open clusterdata-2011-2 trace [6], and we focus on the part that

11

contains the job events corresponding to the re-quests destined to a specific Google data center forthe whole month of May 2011. The optimizationalgorithm that we suggest, adapts and adjusts dy-namically the number of operational servers accor-ding to : traffic variation, workload, cost of kee-ping a job in the buffer, cost of losing a job, andenergetic cost for serving a job. The job events areorganized as a table of eight attributes ; we onlyuse the column timestamps that refer to the arrivaltimes of jobs expressed in micro-sec. This traffictrace is sampled with a sampling period equal tothe slot duration. We consider frames of one mi-nute to sample the trace and construct seven em-pirical distributions corresponding to arrivals du-ring each day of the week. Such an assumptionis consistent with the week evolution of job arri-vals observed by long traces. These distributionshave different statistical properties reflecting thefluctuation of traffic over the week. High arrivalsrate is observed on Thursday, low arrivals rate onSaturday, Sunday and Monday, and medium arri-vals rate during the rest of the week. For instance,we observe an average of 39 (resp. 58) jobs per mi-nute during Sunday (resp. Thursday) with a stan-dard deviation of 22 (resp. 38). Figure 1 shows theresults of analyzing numerically the system whoseparameters are :

Parameters Value Unit Description

Max 100 servers total number of serversS 1 jobs/server processing capacity of a serverB 300 jobs buffer size

4. Conclusion

In this work we present an optimization stochasticalgorithm in order to manage energy consumptionand QoS in a data center modeled by discrete timequeue. Every slot, the algorithm minimizes an ob-jective function that combines the cost of energyand the cost of QoS, in order to change the num-ber of operational servers according to traffic va-riation. We show the ability of our algorithm toadapt dynamically to arrivals changes. Test wereshown through various numerical analysis for se-veral types of arrivals, and specially for arrivalsmodeled by discrete distributions obtained fromGoogle real traffic traces. The system starts turningon servers progressively when high arrivals rate isdetected. And turn off gradually the servers whenarrivals rate becomes low. Doing a closer analysisof the relationship between cost of energy, cost ofQoS, workload and optimal number of operatio-nal servers is considered for future work to deter-mine more accurate link between these parame-

ters. We also intend to extend this study for thecase in which, the number of served jobs in a slotby a server, is also defined by a distribution.

Week days

Num

ber

ofop

erat

iona

lser

vers

M(t

)

51

58

64

71

77

84

90

Monday Tuesday Wednesday Thursday Friday Saturday Sunday

FIGURE 1 – Evolution, over a week, of the num-ber of operational servers. Our algorithm adaptsthe number of operational server according to thetraffic variation.

Bibliographie

1. K. Aidarov, Paul D. Ezhilchelvan, and Isi Mi-trani. Energy-aware management of custo-mer streams. Electr. Notes Theor. Comput. Sci.,296 :199–210, 2013.

2. M. Bayati, M. Dahmoune, J.M. Fourneau,N. Pekergin, and D. Vekris. A tool ba-sed on traffic traces and stochastic monotoni-city to analyze data centers and their energyconsumption. In Valuetools ’15 : 9th internatio-nal conference on Performance evaluation methodo-logies and tools, page to appear. Acm, 2015.

3. Jonathan Koomey. Growth in data center elec-tricity use 2005 to 2010. A report by AnalyticalPress, completed at the request of The New YorkTimes, page 9, 2011.

4. Isi Mitrani. Managing performance and po-wer consumption in a server farm. Annals OR,202(1) :121–134, 2013.

5. C. Schwartz, R. Pries, and P. Tran-Gia. Aqueuing analysis of an energy-saving mecha-nism in data centers. In Information Networking(ICOIN), 2012 International Conference on, pages70–75, Feb 2012.

6. John Wilkes. More Google clus-ter data. Google research blog, No-vember 2011. Posted at http://googleresearch.blogspot.com/2011/11/more-google-cluster-data.html.

12


Compter avec les Protocolesde PopulationYves Mocquard

Université de Rennes [email protected]

1. Introduction

Le modèle des protocoles de population, introduitpar Angluin et al. [1], fournit les bases théoriquespour analyser les propriétés émergeant d’un sys-tème constitué d’agents anonymes interagissantdeux à deux. Nous définissons dans [2], un pro-tocole de population permettant de compter exac-tement le nombre d’agents d’un type particulier.Nous montrons que ce protocole converge de ma-nière logarithmique en temps distribué.Beaucoup de travaux existent sur le problème dela majorité, Angluin et al. [4] ont mis au point unprotocole rapide et simple, mais qui n’est exact quequand la majorité est large, ça reste un bon ou-til pour trouver un consensus. Alistarh et al. [4]ont récemment mis au point un protocole de ma-jorité exact en en temps logarithmique mais avecune constante très grande.Nous allons décrire un protocole de population quirésout le problème du comptage, lequel généralisecelui de la majorité en l’affinant. En interrogeantn’importe quel agent, on peut connaître le nombred’agent d’un type particulier en O(logn) interac-tions, avec une probabilité aussi grande que l’onsouhaite.

2. Protocoles de Population

La définition qui suit est tirée de Angluin et al. [5].Un protocole de population est caractérisé par un6-uplet (Q,Σ, Y, ι,ω, f), Σ est l’ensemble fini dessymboles d’entrée, Y est l’ensemble fini des sym-boles de sortie, ι : Σ → Q est la fonction d’entréequi détermine l’état initial d’un agent, ω : Q → Yest la fonction de sortie qui détermine le symbolede sortie d’un agent, et f : Q × Q → Q × Q estla fonction de transition qui décrit comment deuxagents interagissent et mettent à jour leur état.Au début, tous les agents démarrent avec un sym-bole initial venant deΣ. La fonction ι initialise l’étatde chaque agent à partir de son symbole, puis au

gré des interactions, les agents mettent à jour leurétat utilisant la fonction de transition f.Soit C = {Ct, t ≥ 0} un processus stochas-tique à temps discret avec comme ensemble d’étatsQn. Nous l’appellerons configuration un état de ceprocessus stochastique pour ne pas le confondreavec l’état des agents du protocole de population.Pour tout t ≥ 0, la configuration à l’instant tde ce processus stochastique est notée par Ct =

(C(1)t , . . . , C

(n)t ), C(i)

t représente l’état de l’agent ià l’instant t.A chaque instant t, deux indices distincts i et j sontsuccessivement choisis parmi 1, . . . , n avec la pro-babilité pi,j(t). Nous nommons Xt la variable aléa-toire représentant ce choix, c’est-à-dire

P{Xt = (i, j)} = pi,j(t).

Nous considérons que les variables aléatoires Xt etCt sont indépendantes.

3. Compter avec les Protocoles de Population

3.1. IntroductionChaque agent possédant un symbole d’entrée issude l’ensemble Σ = {A,B}, soit NA et NB le nombred’agents ayant pour symbole respectivement A ouB, le but est de connaître la différence invarianteκ = NA−NB. Et c’est ce que doit rendre la fonctionde sortieω.Au début la fonction ι attribut à chaque agent l’étatm ou −m selon que son symbole soit respective-ment, A ou B.La fonction de transition consiste à attribuer àchaque agent la moyenne des deux valeurs.Cet algorithme garde constant la somme de tousles états de chaque agent, somme qui est égale àm(NA −NB).La fonction de transition égalise progressivementl’état de tous les agents qui finissent par approcherde la même valeur m(NA−NB)

n. A partir de laquelle

la fonction de sortie peut calculer κ = NA −NB.

3.2. Compter avec un ensemble d’états finiNous travaillons avec un ensemble fini d’étatsQ qui est un ensemble d’entier. Les paramètresQ,Σ, Y, ι et ω dépendent de l’application et serontdéfinis à la fin de cette section pour le calcul de ladifférence invariante κ. La fonction de transition fest définie par

f(a, b) =

{(a+b2, a+b

2

)si a+ b est pair(

a+b−12

, a+b+12

)si a+ b est impair

13


Une fois que le couple (i, j) est choisi à l’instant t,Ct+1 est défini par

(C

(i)t+1, C

(j)t+1

)=

(C

(i)t +C

(j)t

2,C

(i)t +C

(j)t

2

)si C(i)

t + C(j)t pair

(C

(i)t +C

(j)t −1

2,C

(i)t +C

(j)t +1

2

)si C(i)

t + C(j)t impair

et C(m)t+1 = C

(m)t pourm 6= i, j.

Le lemme suivant est fondamental, il établit que lasomme des états des agents reste invariante.

Lemme 1 Pour tout t ≥ 0, nous avonsn∑

i=1

C(i)t =

n∑

i=1

C(i)0 .

Nous notons ` la moyenne des coordonnées de Ct

et L le vecteur de Rn dont toutes les coordonnéessont égales à `, c’est-à-dire

` =1

n

n∑

i=1

C(i)t et L = (`, . . . , `).

Théorème 2 En supposant un choix uniforme ducouple (i, j), c’est-à-dire si, pour i 6= j,

pi,j(t) =1

n(n− 1),

alors nous avons

E(‖Ct − L‖2

)≤(1−

1

n− 1

)t

E(‖C0 − L‖2

)+n

4.

En utilisant l’inégalité de Markov on obtient le co-rollaire suivant qui donne une δ-approximation del’écart maximum entre les coordonnées de Ct et `.

Corollaire 3 Pour tout δ ∈ ]0, 1[, s’il existe uneconstante K telle que E(‖C0 − L‖∞) ≤ K alors, pourtout t ≥ (n− 1) ln(4K2) nous avons

P{‖Ct − L‖∞ ≥√n

2δ} ≤ δ.

Nous pouvons maintenant appliquer ces résultatsau calcul de la différence invariante κ. L’ensembledes entrées est Σ = {A,B}, et la fonction d’entrée ιest définie par ι(A) = m et ι(B) = −m, m étant unentier strictement positif. Cela signifie que, pourtout i = 1, . . . , n, C(i)

0 ∈ {−m,m}. Nous avons

` =1

n

n∑

i=1

C(i)0 =

κm

n,

ce qui montre à partir du Lemme 1 que κ est inva-riant. L’ensemble des états Q est maintenant l’en-semble {−m,−m+ 1, . . . ,m− 1,m}. La fonction desortie est, pour tout x ∈ Q,

ω(x) = bnx/m+ 1/2c.

L’ensemble de sortie Y est l’ensemble des valeurspossibles de κ, i.e. Y = {−n,−n+ 1, . . . , n− 1, n}.

Théorème 4 Pour tout δ ∈ ]0, 1[, en prenantm =

⌈√2n3/2/

√δ⌉

et pour tout t ≥ (n −

1)(5 ln 2+ 3 lnn− ln δ+ 2

m−1

), nous avons

P{ω(C(i)t ) = κ, pour tout i = 1, . . . , n} ≥ 1− δ.

Donc le temps de convergence pour obtenir κ avecune probabilité aussi grande que l’on veut estO (n logn) et ainsi le temps de convergence pa-rallèle pour obtenir κ avec une probabilité aussigrande que l’on veut est O (logn).Ce protocole nécessite la connaissance préalabledu nombre d’agents n.Dans le futur nous comptons proposer un pro-tocole qui n’a plus cette nécessité. Deux voiessont possibles, la première consiste à calculer ladifférence en terme de pourcentage, la deuxièmeconsiste, en utilisant une élection de leader, à cal-culer, au préalable, la taille du système.

Bibliographie

1. Dana Angluin, James Aspnes, Zoë Diamadi,Michael J. Fisher, and René Peralta. Conputationin netWorks of passively mobile finite-state sen-sors. Distributed Computing, 18(4):235-253,2006.

2. Yves Mocquard, Emmanuelle Anceaume, JamesAspnes, Yann Busnel, and Bruno Sericola.Counting with Population Protocols. In Pro-ceedings of the 14th IEEE International Sympo-sium on Network Computing and Applications (IEEENCA15), September 2015.

3. Dan Alistarh, Rati Gelashvili, and Milan Vo-jvonic. Fast and exact majority in populationprotocols. Technical report, Microsoft Research,2015.

4. Dana Angluin, James Aspnes, and David Eisen-stat. A simple population protocols for fast ru-bust approximate majority. 20(4) :279-304, 2008.

5. Dana Angluin, James Aspnes, David Eisenstat,and Eric Ruppert. The computationnal powerof population protocols. Distributed Computing,20(4) :278-304,2007.

14


Evaluation des performancesbout en bout du trafic TCP sous lerégime "Équité Équilibrée"

Jean Marie Garcia1, Mohamed El Hedi Boussada

2

1LAAS-CNRS, SARA

7 avenue du Colonel Roche, 31077Toulouse,[email protected]

2SUP’COM, MEDIATRON

Technopôle El Gazala, 2088 Ariana, [email protected]

1. Introduction

Aujourd’hui, la plupart du trafic circulé dans l’In-ternet est généré par un transfert de documentscomme les fichiers ou les pages Web [1]. Ce traficest élastique dans le sens où la durée de chaquetransfert dépend de l’etat du réseau.Chaque document est divisé en une séquence depaquets, appelé flux, dont le débit d’envoi estadapté selon l’état de congestion dans le réseau,généralement sous le contrôle du protocole TCP.La qualité du transfert dépend alors du temps né-cessaire pour transférer avec succés tous les pa-quets du flux. En ce sens, les performances dutrafic élastique se manifestent principalement auniveau flux et peuvent être traduits par le débitmoyen de chaque flux de données [3].Comme il y a plusieurs classes des flux, l’évolu-tion du nombre des flux pour chaque classe dé-pend toujours de la nature de l’allocation des res-sources. La plupart des travaux sont concentréssur des allocations basés sur des fonctions d’utili-tés comme l’allocation classique << équité max-min>> et << l’équité proportionnelle de Kelly >> . En

général, l’analyse d’un réseau fonctionnant sousrégime de ces allocations est assez difficile. Unedes raisons est qu’ils ne conduisent pas à une ex-pression explicite pour la distribution stationnaire,qui détermine le nombre typique de flux concur-rents de chaque classe[2]. Dans ce contexte, Lanotion de l’équité équilibré (Balanced Fairness enanglais) a été introduite par Bonald et Proutiérecomme un moyen d’évaluer approximativement laperformance de ces allocations équitables[1]. Unepropriété clé de l’équité équilibrée est son insen-sibilité : la distribution stationnaire de nombre des

flux est indépendante de toutes les caractéristiquesfines du trafic[2]. La seule hypothése requise estque les flux arrivent comme un processus de Pois-son, qui est effectivement satisfaite dans la pra-tique des grands réseaux avec de nombreux abon-nés.Toutefois, l’équité équilibrée reste complexe à uti-liser dans un contexte pratique car elle requiert lecalcul de la probabilité de chacun des états pos-sibles du système, et est donc confrontée à l’ex-plosion combinatoire de l’espace d’états pour degrands réseaux. Dans ce contexte, il est primordialde proposer des solutions (ou bien des approxima-tions) permettant de calculer efficacement les mé-triques de performance sans nécessiter l’évaluationdes probabilités individuelles des états.Ce papier vise à proposer des approximationssimples et explicites pour évaluer les performancesde bout en bout des flux élastiques sous le régimed’équité équilibrée.

2. Modèle

Le modèle consiste en un ensemble de L liens oùchaque lien l a une capacité Cl.Un certain nombrede flots élastiques sont en compétition pour le par-tage de la bande passante de ces liens. Soit E l’en-semble de classes de ces flots. Chaque flux d’uneclasse i ∈ E est caractérisé par leur débit maximumnoté di et la taille moyenne de fichier à transférernoté σi.La congestion force les flux à réduire leursdébits et par suite d’augmenter le délai du trans-fert.Les flux arrivent suivant un processus de Poissonde moyenne λi pour les flux de classe i ∈ E. L’in-tensité du trafic d’une classe i est donné par le pro-duit ρi = λiσi. On désigne par A la matrice d’inci-dence définit comme :ail = 1 si les flots de classe iutilisent le lien l ∈ L, et 0 sinon.Soit θl =

∑i∈E ailρi le trafic offert à un lien l ∈ L.

Pour maintenir la stabilité du système, on supposeque la charge totale de chaque lien l ∈ L est stricte-ment inférieure à sa capacité : θl < Cl.On note par xi le nombre des flux présents dans leréseau pour la classe i et on désigne par x = (xi)i∈E

l’état du réseau.Pour la suite, on évalue les performances du traficélastique à travers le débit moyen de chaque flux.En utilisant la formule de Little, le débit moyen dechaque flux d’une classe i ∈ E est donné par :

γi =ρi

E[xi](1)

où E[xi] est le nombre moyen des flux de la classei.

15

3. Analyses

On partage les ressources du réseau selon le ré-gime équité équilibrée.

3.1. Cas d’un seul lienOn suppose ici que le réseau est limité à un lienunique de capacité C. On note θ =

∑i∈E ρi le trafic

offert à ce lien.La probabilité de congestion d’une classe i ∈ E estdonnée par la probabilité de l’ensemble Bi = {x :C− di < n} où n =

∑k∈E dk xk :

π(Bi) =1

C− θ

∑

k∈E

ρkπ(Wk) + π(Wi) (2)

Où Wk = {x : C− dk < n ≤ C} ∀k ∈ E.

π(Wk) = π(0)∑

C−dk<n≤C

∏

j∈E

(ρj

dj)xj

xj!(3)

Avec :

π(0) =

( ∑

C−dk<n≤C

∏

j∈E

(ρj

dj)xj

xj!

+1

C− θ

∑

k∈E

ρk∑

C−dk<n≤C

∏

j∈E

(ρj

dj)xj

xj!

)−1

(4)

Le nombre moyen des flux d’une classe i ∈ E estdonné par :

E[xi] =ρi

di

[1− π(Bi)

+1

C− θπ(0)∑

k∈E

ρk∑

C−di−dk<n≤C−di

∏

j∈E

(ρj

dj)xj

xj!

]

+ρi

C− θπ(Bi) (5)

On montre que :

E[xi] ≤ρi

di+

ρi

C− θπ(Bi) (6)

L’inéquation (6) donne une borne supérieure aunombre moyen des flux de chaque classe. Bienqu’il soit difficile de le démontrer mathéma-tiquement, toutes nos observations numériquesconcordent sur le fait que cette borne supé-rieure fournit une très bonne approximation deE[xi].Donc on peut écrire :

E[xi] ≈ρi

di+

ρi

C− θpi(Bi) (7)

3.2. Généralisation vers le cas d’un réseauPour le cas d’un réseau, on propose l’approxima-tion suivante :

E[xi] ≈ρi

di+∑

l∈L

ail π(Bli)

ρi

Cl − θl(8)

Où :

π(Bli) =

1

Cl − θl

∑

k∈E

akl ρk π(Wlk) + π(Wl

i) (9)

Pour tout i ∈ E ,les ensembles Bli et Wl

i (ainsi leursprobabilités) sont définis de la méme façon que lasection précedente en remplacant C par Cl, θ parθl et n par nl =

∑k∈E akl dk xk.

La validité de cette approximation a été prouvéepar simulations sur NS-2 où l’erreur relative n’apas dépassé le 5% pour des petites et moyennesvaleurs de θl.

4. Conclusion

Malgré son efficacité dans l’étude des perfor-mances du trafic élastique, l’allocation équitééquilibrée reste complexe à utiliser dans uncontexte pratique, et surtout pour des réseauxassez larges. Dans ce sens, on a proposé desapproximations pour évaluer le débit moyen debout-en-bout du trafic élastique sous une telleallocation. Les approximations données sontprécises et permettent une généralisation pourde grands réseaux avec un temps de calcul rai-sonnable. Ces résultats conduisent directement àdes règles simples d’ingénierie de trafic et à desméthodes robustes d’évaluation des performancesnécessaires à la maîtrise des réseaux actuels.

Bibliographie

1. Bonald, T., Virtamo, J. (2004). Calculating theflow level performance of balanced fairness intree networks. Performance Evaluation, 58(1),1-14.

2. Bonald, T., Haddad, J. P., Mazumdar, R. R. (2011,September). Congestion in large balanced multi-rate links. In Proceedings of the 23rd Internatio-nal Teletraffic Congress (pp. 182-189). Internatio-nal Teletraffic Congress.

3. Brun, O., Al Sheikh, A., Garcia, J. M. (2009,September). Flow-level modelling of TCP traf-fic using GPS queueing networks. In TeletrafficCongress, 2009. ITC 21 2009. 21st International(pp. 1-8). IEEE.

16


Average complexity of the BestResponse Algorithm in PotentialGamesStéphane Durand and Bruno Gaujal

Univ. Grenoble [email protected]@inria.fr

1. Introduction

The computation of Nash Equilibria (NE) in gameshas been investigated of many papers. The mostgeneral result is in [2] and says that the problem ofcomputing NE is PPAD complete.Potential games have been introduced in [7] andhave proven very useful, especially in the contextof routing games, first mentioned in [1] and ex-haustively studied ever since, in the transporta-tion as well as computer science litterature, see forexample [6]. For potential games, efficient poly-nomial time algorithms exist in symmetric cases(see [4]). However, the same paper shows that thecomputation of NE for general potential gamesis PLS complete. The Best Response Algorithm(BRA) is probably the most popular algorithm thatconverges to a pure Nash equilibrium (NE) in po-tential games [5]. However, its complexity has at-tracted surprisingly little attention.In this paper, we analyze the performance of BRAover a potential game with N players, each withA possible actions. We show that on average, theBest Response Algorithm takes log(N)+eγ (γ is theEuler constant) effectives steps and makes eγANcomparisons before finding a NE.These numbers say that BRA is very efficient onaverage to compute NE, even if this is a PLE com-plete problem. Our analysis is based on two ingre-dients, one is the construction of an approximationof the behavior of BRA, where each state is exa-mined at most once and the second is the use ofa continuous space discrete time Markov chain toanalyze the average complexity.

2. Best Response Algorithm and Potential games

We consider a game with a finite number N ofplayers and a finite strategy space for each player,each of size A, and the corresponding utility func-

tions. The game Gdef= G(N ,A, u) will be a tuple

consisting of– a finite set of players N = {1, . . . ,N} ;– a finite set Ak of actions (or pure strategies) for

each player k ∈ N ; The set of action profiles or

states of the game is A def=∏kAk ;

– the players’ payoff functions uk : A→ R.We define the classical best response correspondencebrk(x) as the set of all actions that maximizes thepayoff for player k under profile x :

brk(x)def=

{argmaxα∈Ak

uk(α; x−k)

}. (1)

A Nash equilibrium (NE) is a fixed point of the cor-respondence, i.e. a profile x∗ such that x∗k ∈ brk(x∗)for every player k.

Definition 1 (Potential games) A game is a poten-tial game [5] if it admits a function (called the po-tential) Φ : A → R such that for any player k andany unilateral deviation of k from action α to α ′,uk(α, x−k)−uk(α

′, x−k) = Φ(α, x−k)−Φ(α ′, x−k).

We consider a version of Best Response Algorithm(BRA) where the next player is selected accordingto a round robin pattern. Other patterns can alsobe considered using the same approach and can beshown to have a similar behavior.

Algorithm 1: Best Response Algorithm (BRA)Input :Game utilities (ui(·)),Initial state (x(0)),Infinite seq. of players R = (1, 2, . . . , N, 1, . . . ).

foreach player k ∈ K dostopk := false

repeatPick next player k := Rt+1Select new action αk := brk(x(t))stopk := 1{αk=xk(t)} ;xk(t+ 1) := αk ;

until stop1 ∧ stop2 ∧ · · ·∧ stopN;

A famous result first proved in [5] states that forany potential game G, Algorithm 1 converges infinite time to a Nash Equilibrium of G.

3. Complexity

Let us consider three complexity measures (relatedto each other) : TBRA is the number of iterations

17

(or the number of times that the function br wascalled) before BRA reaches a Nash equilibrium.The total number of comparisons is denotedCBRA.One should expect that CBRA ≈ (A − 1)TBRA. Fi-nally, the number of different states visited by BRAis denoted MBRA. Of course, MBRA 6 TBRA. Theproofs of Theorems 1 and 2 are not provided dueto lack of space. They are available in a researchreport [3].

Theorem 1 In the worst case, under round robin revi-sions, TBRA = NAN−1.

3.1. RandomizationIn the following we will analyze the average com-plexity of BRA.We randomize over all the potential games overwhich BRA is used. Since the behavior of BRA onlydepends on the potential function, we randomizedirectly over the potential Φ. The natural rando-mization is to consider all possible total orderingsof the set {Φ(x), x ∈ A} (there are (AN)! of them)and pick one uniformly. This is equivalent to pickiid potentials in all states, uniformly distributed in[0, 1].

3.2. Markovian AnalysisWe will be analyzing the intersection-free approxi-mation of the behavior of BRA (where no state isvisited twice) whose behavior is asymptotically thesame as BRA.Let y be the potential of the current state x : (y def

=Φ(x)). If k−1 players have already played best res-ponse without changing the state, then the evolu-tion at the next step of BRA is as follows. The k-thplayer computes its best response. This player has

adef= A − 1 new actions whose potential must be

compared with the current potential (y). With pro-bability ya none of the new actions beat the currentchoice. The state remains at y and it is the turn ofthe k+1-st player to try its best response. With pro-bability 1 − ya, one of the new actions is the bestresponse. The current state moves to a new statewith a larger potential and the number of playersfor which the new state is a best response is setback to 1.This says that the couple (Yt, Kt) is a Markovchain, where Yt is the potential at step t, in [0, 1]and Kt is the current number of players whosebest response did not change the current state (in{1, 2, . . . , N}). Its transitions are :

P((Y, K)t+1 = (y, k+ 1)

∣∣∣∣(Y, K)t = (y, k)

)= ya,

and, if z > y,

P((Y, K)t+1 ∈ ([z, 1], 1)

∣∣∣∣(Y, K)t = (y, k)

)= 1− za.

Let C(y, k) be the average number of comparisonsrequired to reach a NE, starting in a state withpotential y where k players have played withoutchanging their action. The forward equation forC(y, k) is :

C(y, k) =ya(C(y, k+ 1) + a)

+

∫1

y

aua−1(C(u, 1) + a)du,

with the boundary conditions C(1, 1) = a(N − 1)and C(y,N) = 0.Solving these equations leads to the following pro-position (quantities MBRA and TBRA are analyzedsimilarly).

Theorem 2 The average number of moves in BRA ve-rifies EMBRA 6 log(N) + eγ +O(1/N).The average number of comparisons verifiesECBRA 6 eγ(A− 1)N+ o(A)and the average number of steps verifiesETBRA 6 eγN+ o(1).

Bibliographie

1. M. Beckman, C. B. McGuire, and C. B.Winsten.Studies in the Economics of Transportation. YaleUniversity Press, 1956.

2. P.W. Goldberg C. Daskalakis and C.H. Papa-dimitriou. The complexity of computing anash equilibrium. SIAM Journal on Computing,39(3) :195–259, 2009.

3. Stéphane Durand and Bruno Gaujal. Effi-ciency of the best response algorithm in poten-tial games. Technical report, Inria, 2015.

4. Alex Fabrikant, Christos Papadimitriou, andKunal Talwar. The complexity of pure nashequilibria. In Proceedings of the Thirty-sixth An-nual ACM Symposium on Theory of Computing,STOC ’04, pages 604–612. ACM, 2004.

5. Dov Monderer and Lloyd Shapley. Potentialgames. Games and economic behavior, Elsevier,14(1) :124–143, 1996.

6. A. Orda, R. Rom, and N. Shimkin. Com-petitive routing in multeuser communicationnetworks. IEEE/ACM Trans. on Networking,1(5) :510–521, 1993.

7. Robert W. Rosenthal. A class of games pos-sessing pure-strategy nash equilibria. Int. J. ofGame Theory, Springer, 2(1) :65–67, 1973.

18


Optimal adaptive routing inpacket-switched networksBruno Gaujal and Baptiste Jonglez

Univ. Grenoble AlpesInriaENS [email protected]@inria.fr

1. Introduction

Communication networks are becoming increasin-gly multipath and a common challenge is to exploitthis path diversity. More precisely, the problem canbe modelled as a multi-commodity flow problem :Given a number of concurrent source-destinationflows, the problem is to assign these flows to net-work paths, while respecting capacity constraints.Here, we present a novel algorithm for adaptiverouting in arbitrary network topologies, mappingsource-destination flows to paths. We claim that itprovides a viable and stable solution to adapt totraffic conditions, and effectively avoids conges-tion. Our algorithm is based on theoretical groundsfrom game theory, while our implementation leve-rages SDN protocols to ease deployment.On the theoretical side, our distributed routing al-gorithm is endowed with the following desirableproperties for efficient implementation :

— It is fully distributed without any informa-tion sharing ;

— It is oblivious to the network topology ;— It only uses on-line and local information ;— There are no endless oscillations and it is

numerically stable ;— It is robust to out-dated information and

measurement errors ;— It does not require time synchronization

between routers ;— and it converges fast even if the number of

flows is very large.

2. Routing Algorithm

Let us consider a routing problem in a communica-tion network. Several flows of packets must be rou-ted over a communication network. The topologyof the network is fixed but arbitrary.Each flow k ∈ K is characterized by a source-node, a destination-node and a nominal arrival

rate of packets, λk. Also, each flow is affected aset Pk of paths in the network from its source toits destination, made of Pk paths. A configurationis a choice of one path per flow. The delay overeach link and each node in the network dependson the the load on the link (node), in an unspe-cified manner. For one flow, say k, we denote bydk(p1, · · · , pk, · · · , pK) the end to end average delayexperienced by packets of flow k under the confi-gutration where flow 1 uses path p1, flow 2 usespath p2, and so forth.The following algorithm is run by each flow k, in-dependently. It is probabilistic and maintains twovectors of size Pk. The probabilistic choice vector,qk = (q1 . . . qPk

) gives at each step the probabi-lities to choose the paths and the score vector Yk =(Y1 . . . YPk

) that attributes a score to the paths.The main loop of the algorithm is as follows (indexk is skipped).At each local clock tick, a path p is chosen accor-ding to q, and packets are sent along p. The ave-rage delay of packets over this path is measured.The score Yp is updated according to a discrete dy-namics inspired from game theory and in turn, theprobability vector is modifed for the next path se-lection. This repeats forever, or until a stable pathhas been reached for all flows, i.e. q becomes adegenerate probability vector (all coordinates arezero but one) for all flows. The algorithm uses 3 pa-rameters : τ is a discounting factor over past scores,(γn)n∈N is a vanishing sequence of step sizes and(βn)n∈N is a sequence of bounding terms control-ling the growth rate of the scores. In the algorithm,∧ denotes the minimum operator.

Algorithm 1: OPS : Online Path Selection for kInitialize :n← 0 ; q← ( 1

P, . . . , 1

P) ; Y← (0, 0, . . . , 0) ;

repeatWhen local clock ticks for the nth time ;n← n+ 1 ;select new path pw.r.t. probability vector q ;Use path p and measure its delay D ;Update score of p :

Yp ←(Yp − γn(D+ τYp)/qp

)∧ βn ;

update proba. : ∀s ∈ Pk, qs ← exp(Ys)∑` exp(Y`)

;until end of time;

Theorem 1 (Convergence to equilibirum)Under mild technical assumptions, for all ε > 0, there

exist τ > 0 such that the algorithm converges to an ε-optimal configuration, in the following sense :

19

For each flow `, the probability vector q converges to analmost degenerate probability : qp becomes smaller thanε for all p ∈ P` except for one path, say p∗` , for which itgrows larger than 1− ε.Furthermore, after convergence, no flow can reduce itsdelay : ∀p ′ ∈ P`,d`(p

∗1, . . . , p

∗` , . . . , p

∗K) 6 d`(p∗1, . . . , p ′, . . . , p∗K).

The proof is based on a general convergence theo-rem from game theory, proved in [1]. It is es-sentially based on two facts. The empirical delayD measured on packets using path p for flow fhas no bias, conditionally on the past : At stepn, E(D|Fn) = dk(p1, . . . , pK). This implies thatthe scores Y form a stochastic approximation of acontinuous deterministic dynamics that convergesto Nash Equilibria in all potential games.

3. Implementation and experimental Results

Looking at our OPS algorihtm, we can note thatit is completely distributed : it requires only lo-cal measures, local choices, and no coordination isneeded between routers. This eases implementa-tion. The only difficulty lies in the ability to selectpaths from source to destination : this is not practi-cal in current next-hop forwarding networks. Ourimplementation is based on an equivalent versionof OPS, where one gateway router makes a choiceamong all possible next-hop routers for each of itsflow. Thus, the local actions of several routers bet-ween source and destination implicitely determinethe path from source to destination.Our implementation takes the form of an Open-flow controller, using the Ryu library. The routingtable of each gateway router is programmed andconstantly updated by a dedicated controller. Fur-thermore, each gateway router sends packet hea-ders to its controller, for delay computation.To run realistic experiments, we use Mininet [2], awidely adopted network emulator. Mininet is usedto build a virtual network topology, thanks to thenetwork namespaces feature of the Linux kernel. Onthis virtual topology, we can run our implementa-tion exactly as if we had a real network at hand.To validate our approach, we use a simple topo-logy, with two gateway routers and three hosts.Two hosts are simply connected to their gateway,while the third host can be reached via two dif-ferent paths. The topology is shown in Figure 1.We consider two TCP flows from host 1 and host2, both destinated to host 3. Each flow is restric-ted by the sender to use no more than 8 Mbit/s,to avoid saturating all links whatever the choice offlow assignment. If both flows are forwarded over

next−hop router

next−hop router

Gateway 1

Gateway 2 20 ms, 10 Mbit/s

Host 1 20 ms, 10 Mbit/s

Host 3

Host 2

FIGURE 1 – Simple topology, where the two right-most links have limited capacity (10 Mbit/s) and alatency of 20 ms. Both host 1 and host 2 send a flowto host 3.

the same rightmost link, congestion will occur, be-cause of the limited capacity.

●●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●●●●●●

●

●

●

●

●

●

●●●●

●

●

●

●

●

●

●

●

●

●

●●

●

●

●

●

●

●

●●

●●

●

●

●

●●

●

●●

●

●●●

●

●●

●

●●●

●

●●

●

●●●

●

●

●●

●●

●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●

0.00

0.25

0.50

0.75

1.00

0 200 400 600Time (s)

Pro

babi

lity

to s

elec

t upp

er p

ath

●

●

Flow 1

Flow 2

FIGURE 2 – Probability over time to select the up-per path for each flow.

Figure 2 shows our experimental results. For eachflow, the probability to use the upper path is plot-ted over time. After an initial period of exploration,the gateway routers converge to a stable state, inwhich each path to host 3 supports a single flow.

Bibliographie

1. Pierre Coucheney, Bruno Gaujal, and PanayotisMertikopoulos. Penalty-Regulated Dynamicsand Robust Learning Procedures in Games.Mathematics of Operations Research, 40(3) :611–633, 2015.

2. Bob Lantz, Brandon Heller, and NickMcKeown. A network in a laptop : rapidprototyping for software-defined networks.In Proceedings of the 9th ACM SIGCOMMWorkshop on Hot Topics in Networks, page 19.ACM, 2010.

20


A Mean-Field Game with ExplicitInteractions for Epidemic ModelsJosu Doncel, Nicolas Gast, Bruno Gaujal ∗

INRIA Grenoble Rhônes-Alpes655 Avenue de l’Europe38330 Montbonnot-Saint-Martin{josu.doncel, nicolas.gast,bruno.gaujal}@inria.fr

1. Introduction

Game theory studies the rational behavior ofdecision-makers (called players in the following).A crucial notion is the concept of Nash equili-brium. A Nash equilibrium is an allocation of stra-tegies such that no player can benefit from unilate-ral deviation. Although any finite game has at leastone Nash equilibrium, it is shown in [1] that com-puting a Nash equilibrium is a PPAD-complete 2

problem. This suggests that the computation of aNash equilibrium is not tractable when the num-ber of players or of strategies is large. As an al-ternative, the notion of mean-field games has beenintroduced by Lasry and Lions in [6], which is agame where an individual object is infinitesimaland does not affect the global system behavior.Here, we study mean field games with two specificfeatures : Each player has a finite state space (ins-tead of a continuous one in [6]), and the dynamicsof one player depends explicitly on the behaviorof the others (unlike in most works in mean fieldgames [6, 3]). The general theory is developed in[2]. In this document, we illustrate the theory witha vaccination problem.

2. Model Description

2.1. Epidemic ModelWe consider a population of N homogeneous ob-jects that evolve in continuous time from 0 to T .The objects can be susceptible, infected, recoveredor vaccinated. We denote by S(t), I(t), R(t) andV(t) the proportion of the population that is, res-pectively, susceptible, infected, recovered and vac-cinated at time t.The dynamics of one object is a Markov process

∗. This work is partially supported by the EU projectQUANTICOL, 600708.

2. PPAD stands for “polynomial parity arguments on direc-ted graphs”. It is a complexity class that is a subclass of NP andis believed to be strictly greater than P.

that can be described as follows. An object encoun-ters other objects with rate β. If the initial objectwas susceptible and the encounter was infected,the first object becomes infected. An infected ob-ject recovers at rate γ. We also consider that thereis a vaccination policy b that is applied to each ob-ject of the susceptible population. The vaccinationrate b is a function from 0 to T that takes valuesin the interval [0, bmax]. Once an object is vaccina-ted or recovered, it does not change its state. Thedynamics of an object is described in Figure 1.

Susc

Infec Reco

Vac

βI(t)

b(t)

γ

FIGURE 1 – The dynamics of an object in the epide-mic model.

We are interested in the analysis of this epidemicmodel for a large number of objects. WhenN→∞,the dynamics of the population converges [4] to thefollowing system of differential equations :

S(t) = −β · S(t) · I(t) − b(t) · S(t)I(t) = β · S(t) · I(t) − γ · I(t)R(t) = γ · I(t)V(t) = b(t) · S(t)

(1)

In [5] the authors develop an approximation of thisepidemic model and characterize the solution ofthe derived mean-field game. In the rest of the pa-per, we show that the mean-field game correspon-ding to this model is tractable and can be analyzedrigorously.

2.2. Mean-Field GameWe focus on a particular object, that we callPlayer 0. Let X(t) ∈ {Sus, Infec, Reco, Vac} be thestate of Player 0 at time t. We note that the evo-lution of X(t) depends on the infected population.We assume that the rest of the population applies afixed vaccination policy b. Player 0 chooses its vac-cination policy b0, so as to minimize its expectedindividual cost, which is

Cind(b0,b) =∫T

0

(cVb0(t)P(X(t) = Susc) + cIP(X(t) = Infec))dt,

21

where cV is the vaccination cost and cI is the unittime cost of being infected.We call the best response to b and denote by BR(b)the set of vaccination policies that minimize thecost of Player 0 for a given vaccination policy ofthe population b :

Definition 1 (Best-Reponse)

BR(b) = arg minb0

Cind(b0,b). (2)

We now define the notion of a mean-field equili-brium for this game. It is a vaccination strategybMFE such that when the population chooses thevaccination policy bMFE, a selfish Player 0 wouldalso choose the same vaccination policy bMFE :

Definition 2 (Symmetric Mean-Field Equilibrium)The vaccination policy bMFE is a symmetric mean-fieldequilibrium if and only if

bMFE ∈ BR(bMFE).

The rationale behind this definition is when oneconsiders that the population is made of playersthat each take self-interested decisions. As thepopulation is homogeneous, each object best-response is the same as Player 0. In other words,for a given population vaccination policy b, allthe objects of the populations choose the stra-tegy BR(b). A mean-field equilibrium is a situationwhere no object has incentive to deviate unilate-rally from its strategy.

2.3. Centralized Control ProblemThe mean-field game scenario corresponds to acase where the decisions are selfish and decentra-lized. The corresponding centralized control pro-blem can also be defined naturally. For a given vac-cination population b,the average system cost is

Csys(b) =∫T

0

(cV b(t) S(t) + cI I(t)) dt.

This cost represents the cost in the system whenthe population vaccination policy is b. A global op-timum is a vaccination policy that minimizes thesystem cost

Definition 3 (Global Optimum)

bOPT ∈ arg minb

Csys(b). (3)

3. Main Results

The mean-field game we analyze here is a particu-lar case of the model of [2]. In [2], we introduce the

mean-field games with explicit interactions, whichis a discrete state space model where the transi-tion rates between states depend not only on theactions taken, but also on the empirical measureof the system. This explicit interactions between ob-jects makes our model distinct from most work onmean-field games.To characterize a symmetric mean-field equili-brium of the epidemic model, we model the best-response of the generic object as a ContinuousTime Markov Decision Process and we show that,for any population vaccination policy b, the best-response strategy of the generic object is of thre-shold type. This result yields the following propo-sition.

Proposition 1 There exists a symmetric mean-fieldequilibrium that is pure and of threshold type.

We also analyze the global optimum of the epide-mic model.

Proposition 2 There exists a global optimum of thre-shold type.

Unfortunately, in all but degenerated cases, thethresholds do not coincide, so that the price ofanarchy of this model is never equal to 1. Nume-rical simulations show that the price of anarchy issmall in general. A pricing mechanism can be usedto force the equilibrium to coincide with the globaloptimum. Our numerical experiments show thatto encourage selfish individuals to vaccinate opti-mally, vaccination should be subsidized.

Bibliographie

1. C. Daskalakis, P. W. Goldberg, and C. H. Pa-padimitriou. The complexity of computing anash equilibrium. SIAM Journal on Computing,39(1) :195–259, 2009.

2. J. Doncel, N. Gast, and B. Gaujal. Mean-fieldgames with explicit interactions. In preparation,2015.

3. D. Gomes, J. Mohr, and R. Souza. Continuoustime finite state mean field games. Applied Ma-thematics & Optimization, 68(1) :99–143, 2013.

4. T. G. Kurtz. Approximation of population pro-cesses, volume 36. SIAM, 1981.

5. L. Laguzet and G. Turinici. Individual vacci-nation as Nash equilibrium in a SIR model : theinterplay between individual optimization andsocietal policies. June 2015.

6. J.-M. Lasry and P.-L. Lions. Mean field games.Japanese Journal of Mathematics, 2(1) :229–260,2007.

22


Efficient content delivery in thepresence of impatient customersand multiple content typesM. Larrañaga1, O. J. Boxma2, R. Núñez-Queija3,M. S. Squillante4∗

1 L2S UMR CNRS 8506, CentraleSupelec2 Eurandom, The Netherlands3 CWI, Amsterdam, The Netherlands4 Mathematical Sciences Department, IBM, [email protected]

1. Introduction

In this paper we investigate a system that com-bines batch services with abandonment of cus-tomers. This model consists of a multi-classM/M/1 multi-server queue with an adapted ser-vice process. This service process consists in delay-ing the customers that demand the delivery of thesame content for batching of service. Delays due tobatching come at the cost of abandonment. In par-ticular, customers may abandon the system whilewaiting to be served (expiration of their deadlines),for which we penalize the system at a fixed costper abandoning customer. Such penalties can ei-ther represent the loss of the customer or the costof serving the customer on an expensive back-upservice.The characterization of an optimal control for thecase in which customers require a different contenttype is out of reach. We therefore develop approx-imations to tackle the problem, in particular, westudy Whittle’s index.Index Rules have enjoyed a great popularity, sincea complex control problem whose solution might,a priori, depend on the entire state space turns outto have a strikingly simple structure. In a semi-nal work, Whittle introduced the so-called RestlessMulti Armed Bandit Problems (RMABP), see [2].In a RMABP all bandits (in our study a bandit is agroup of customers that demand a specific type ofcontent) in the system incur a cost, the schedulerselects one bandit to be made active, but all ban-dits might evolve over time according to a stochas-tic kernel that depends on whether the bandit wasactive or frozen. The objective is to determine thecontrol policy that, based on the entire state-space

description, selects the bandit with the objectiveof optimizing the average performance criterion.Whittle introduced an approximate control policyof index-type, which is nowadays referred as Whit-tle’s index.The model under study can be cast as an RMABP.We will therefore aim at deriving the Whittle indexto obtain a heuristic for the original problem.

2. Model Description

We consider a multi-class M/M/1 queue withbatch service, M servers with infinite service ca-pacity and customers abandonment. Customersthat demand content type k ∈ {1, . . . ,K} arriveaccording to a Poisson process with rate λk andhave an exponentially distributed service require-ment with mean 1/µk, which is independent ofthe batch size. Customers that are waiting in thequeue abandon after an exponentially distributedamount of time with mean 1/θk. Furthermore, allinterarrival times, service requirements and aban-donment times are independent.Each server can only deliver one content type at atime. In every decision epoch the policy φ chooseswhether to process the demands for a content ornot. Once a customer has been admitted for ser-vice we assume that it can not abandon the sys-tem. Let Nφ

k (t) ∈ {0, 1, . . .} denote the number ofcustomers with a demand for content k that arewaiting in the queue at time t under the policyφ. We will denote them class-k customers. LetSφk (

~Nφ(t)) ∈ {0, 1} denote the decision with re-spect to class-k customers at time t under policyφ when there are ~Nφ(t) customers present in thesystem, with ~Nφ(t) = (Nφ

1 (t), . . . , NφK(t)). Namely,

Sφk (~Nφ(t)) = 0 if the server does not serve class k,

and Sφk (~Nφ(t)) = 1 if the server decides to take a

class-k batch into service. Due to the infinite ca-pacity of the server we assume that, as soon asthe server is activated, i.e., Sφk ( ~N

φ)(t) = 1, all cus-tomers that are waiting in the queue k initializetheir service. Hence, the batch size upon activa-tion equals the number of customers waiting in thequeue, Nφ

k (t).We assume that the service requirements are expo-nentially distributed with rate µk < ∞. Upon ac-tivation of queue k the server takes a batch of sizeNφk (t) into service, and allocates an exponentially

distributed amount of time to process it. While theserver is busy, new customers might arrive to thequeue. In this case, the server is not allowed to takea new batch into service until service completion of

23

0 10 20 30 40 50 600

2

4

6

8

t

N(t)

Arrival at m=n−1, the system is immediately cleared.

Arrival at m=n−1. Since server is busy,the customers that are waiting in the queueare not taken into service.

exp(µ) exp(µ) exp(µ)

Figure 1: Simulation of process N(t) under thresh-old n = 3. exp(µ) refers to the busy period of theserver. N(t) not only depends on n (the policy) butalso on the length of each busy period.

the previous batch; see Figure 1 around t = 37.Let us denote by ck the cost per unit of time class-kcustomers are held in the queue, δk the penalty forclass-k customers abandoning the queue and by cskthe cost per unit of time the server is busy. Theobjective of the present work is to find the policy φso as to minimize

lim supT→∞

1

TE

[∫ T

0

[

K∑

k=1

ckNφk (t) + cskS

φk (~Nφ(t))]dt

],

if µ < ∞, where ck = ck + δkθk. Due to ergodic-ity of the system, the time-average optimal policyis equivalent to the optimal policy in steady-state,and hence we want to find φ such that

minφ

K∑

k=1

(ckE[Nφ

k ] + cskE(1{Sφk ( ~Nφ)=1})), (1)

subject to∑Kk=1 S

φk (~Nφ) ≤ M . The problem de-

scribed above is a Markov Decision Process andobtaining an optimal solution is out of reach. In thenext section we propose a well-performing heuris-tic.

3. Whittle’s index

The approach by Whittle is based on relaxing theoriginal problem, allowing the constraint on theservers to be satisfied on average, that is,

lim supT→∞

1

T

∫ T

0

K∑

k=1

Sφk (~Nφ(t))dt ≤M. (2)

This allows to decompose the original controlproblem into individual problems for each class ofcustomers (we therefore drop the dependency onk from now on). Whittle’s index can then be inter-preted as the Lagrange multiplier of the constraintsuch that a given state joins the passive set.

The objective is now to determine the policy thatsolves (1) under Constraint (2). This can be solvedby considering the uni-dimensional unconstrainedcontrol problems

lim supT→∞

(cE[Nφ] + (cs +W )E(1{Sφ(Nφ)=1})

), (3)

where W is the Lagrange multiplier that can be in-terpreted as a subsidy for passivity.We first prove that an optimal policy that solves(3) is of threshold type, that is, there exists n suchthat it is optimal not to allocate the server for allstates m ≤ n and it is optimal to allocate the serverotherwise. The proof can be found in [1].

Proposition 1 There exists n = 0, 1, 2, . . . such thatSn(m) = 0 for all m ≤ n and Sn(m) = 1 otherwise.

Having proven threshold type of policies to be op-timal, one can define Whittle’s index as describedin the following algorithm.

Proposition 2 Let Ni = N ∪ {0}\{0, . . . , ni} fora given ni, let Pn = E(1{Sn(Nn)=1}) and be non-increasing, and define β(·) as follows: Define n0 = 0andStep i. Compute

βi := infn∈Ni−1

cE(Nn)− E(Nni−1)

Pni−1 − Pn − cs, i ≥ 1, (4)

and denote by ni the largest n ∈ Ni−1 such that (4) isminimized and define β(n) = βi for all ni > n ≥ ni−1.If ni = ∞ stop and let β(n) = βi for all n ≥ ni,otherwise jump to step i+ 1.Then, βi is strictly non-decreasing in i. and β(n) de-fines Whittle’s index.

Whittle’s index policy prescribes to serve the Mclasses of customers with highest Whittle’s index.We have numerically observed that Whittle’s indexpolicy behaves close to optimal for heavy-trafficand light-traffic regimes. The latter however hasnot been proven analytically.

Bibliographie

1. M. Larrañaga, O.J. Boxma, R. Nunez-Queija, M.S.Squillante – Efficient content delivery in the pres-ence of impatient jobs. – Proceedings of ITC 2015.

2. P. Whittle – Restless bandits: Activity allocation ina changing world. – Journal of Applied Probability,25:287-298, 1988.

24


Admission Control with MachineLearning in Software DefinedNetworksJérémie Leguay, Lorenzo Maggi, Moez Draief,Stefano Paris, Symeon Chouvardas,Huawei Technologies, FRC Research Lab(Boulogne-Billancourt, France)Email: [email protected]

1. Admission control in SDNs

Software-Defined Networking (SDN) technologieshave radically transformed network architectures.They provide programmable data planes that canbe configured from a remote controller platform.This creates an opportunity to implement rout-ing processes that are more efficient than classicones: in fact, the controller can take real-time de-cisions at a (logically) centralized location using anaccurate and global view of the network. More-over, SDN controllers have a tremendous compu-tational power compared to legacy embedded de-vices. This encourages the development of smarternetwork control planes using cutting-edge opti-mization and machine learning techniques. A keytask of the SDN controller is the Admission Con-trol on incoming connection requests, in an on-line manner. Its goal is to gracefully manage ser-vice requests when the network becomes highlyutilized, as new incoming requests arrive. It ac-cepts or drops new requests depending on the re-source availability. Non-myopic decisions have tobe made to maximize a given profit, such as thetotal accepted throughput, the financial revenuegenerated or the quality of service experienced byusers. Admission Control can be formulated asan online packing problem, as the goal is to max-imize the number of accepted requests (subject tofeasibility constraints). The challenge in this con-text comes from the online nature of the optimiza-tion problem. New variables and additional con-straints are revealed sequentially, as soon as an ar-rival or departure of a flow occurs in the system.The theory on online algorithms has evolved sig-nificantly in the last decade for this type of prob-lems. Algorithms with guaranteed over the offlineoptimal, which has full information on the futurestate of the system, have been proposed for onlinepacking problems. For these guarantees to hold,admission decisions need to be consistently taken.

The centralized nature of SDN lies the ground toapply online algorithms for admission control.

2. Online Algorithms

Motivated by the considerations above, we firstreview and adapt, well-known and recent algo-rithms from the online literature to the admissioncontrol problem in SDN. We then test their perfor-mance under different traffic conditions to under-stand and highlight the strengths and weaknessesof each of them. Traditionally, online algorithmsfor admission control fall into two main categories:i) worst-case and ii) average-case. Worst-case al-gorithms are characterized by max-min perfor-mance guarantees under specific worst-case sce-narios where a malicious adversary chooses theworst possible sequence of connection requests.Due to their conservative nature, they generallyunderperform under more standard traffic condi-tions. One of the first online algorithms for admis-sion control has been AAP [3]. The algorithm isO(logn)-competitive, meaning that it cannot rejectO(logn) times more requests than the offline opti-mal (n being the number of nodes). Buchbinderet al. proposed in [2] a framework to derive al-gorithms for online packing and covering prob-lems with performance guarantees in the worst-case scenario. Such framework developed the the-ory behind the initial intuition of AAP. On theother hand, ii) average-case algorithms show highexpected performance over random traffic condi-tions, but cannot guarantee good performance inspecific adversarial scenarios. The Primal-Beats-Dual (PBD) algorithm has been introduced byKesselheim et al. in [3]. It computes the optimal(fractional) solution of the relaxed Linear Program(LP), by considering all the past requests and scal-ing the capacity of the graph. It then attempts toroute the request over a path randomly selected,with a probability proportional to the value of thecomputed fractional solution. PBD suffers fromcomputation complexity. Agrawal et al. [4] haveproposed a fast algorithm with multiplicative up-dates to solve this issue. It applies to i.i.d. andrandom order inputs. It implements an efficientstochastic gradient descent that we adapted for ouradmission control problem.

3. Admission Control with Experts

As observed in practice, worst-case and average-case online algorithms for admission control arebetter than the naive and greedy strategy whichaccepts every demand until bottlenecks appears.

25

However, there is no algorithm outperforming allthe remaining ones under all traffic conditions.Luckily, modern SDN control platforms, whichare running on top of commodity servers andare built upon cutting-edge distributed computingtechnologies, enable the parallel execution of dif-ferent algorithms to solve a single decision prob-lem. Such algorithmic architecture, called boost-ing or prediction with expert advice setting [6],is commonly used in machine learning. It exe-cutes all the algorithms in parallel and attemptsto track the best one in an online fashion. Thebulk of the literature on experts focuses on provingtheoretical performance bounds in the basic non-reactive scenario where the action taken by the de-cision maker does not affect the state of the sys-tem, which is definitely not the case for admis-sion control. We identified that the Strategic Ex-pert meta-Algorithm (SEA) [5] applies to out reac-tive setting. Under some stationary conditions onthe system (in our case, on the traffic load on thelinks), SEA is proven to perform at least as well asthe oracle which steadily selects the algorithm withbest average performance. We finally show thatthis approach achieves very good performance inpractice, and is able to successfully overcome theseveral limitations imposed by the inherent onlineand hard-to-predict nature of the problem at hand.We evaluate the performance of the online algo-rithms under realistic conditions, using the real-lifedataset captured in 2006 by Uhlig et al. [7] on theGEANT network.

Bibliography

1. B. Awerbuch, Y. Azar, and S. Plotkin, “Throughput-competitive on-line routing”’, in Proc. FOCS, 1993.

2. N. Buchbinder and J. Naor, “Improved bounds foronline routing and packing via a primal-dual ap-proach”, in Proc. FOCS, 2006.

3. T. Kesselheim, A. Tönnis, K. Radke, and B. Vöck-ing, “Primal beats dual on online packing LPs in therandom-order model”, in Proc. ACM STOC, 2014.

4. S. Agrawal and N. R. Devanur, “Fast algorithms foronline stochastic convex programming”, in Proc.ACM SODA, 2015.

5. D. P. de Farias and N. Megiddo, “How to combineexpert (and novice) advice when actions impact theenvironment?”, in Advances in Neural InformationProcessing Systems, 2003.

6. N. Cesa-Bianchi and G. Lugosi. Prediction, Learn-ing, and Games. New York, NY, USA: CambridgeUniversity Press, 2006.

7. S. Uhlig, B. Quoitin, J. Lepropre, and S. Balon, “Pro-viding public intradomain traffic matrices to the

research community”, ACM SIGCOMM ComputerCommunication Rev, vol. 36, no. 1, 2006.

26


Blocking Evaluation ofdynamic WDM networkswithout wavelengthconversionNicolás Jara1,2, Reinaldo Vallejos2,Gerardo Rubino1

Affiliation1INRIA Rennes - Bretagne Atlantique, Rennes,France2Universidad Técnica Federico Santa Maria,Valparaíso, [email protected], [email protected],[email protected]

1. Introduction

The rapid increase on demand for bandwidth fromexisting networks has caused a growth in the useof technologies based on WDM optical infrastruc-tures [4]. Currently, this type of network is oper-ated statically [4], i.e., the route assigned to anyuser is permanently assigned from source to des-tination. However, this type of operation is ineffi-cient in the usage of network resources, especiallyfor low traffic loads, which is the most commoncase.One way to help overcome the inefficiencies ofstatic networks is to migrate them to networksworking dynamically. This operation mode con-sists in allocating the resources required only whenthe user has data to transmit. A possible lack ofresources to successfully transmit can happen be-cause dynamic networks are designed to save costswith the less possible amount of resources and alsoto be efficient avoiding burst losses (blocking). Toachieve a balance between these two aspects, thenetwork must be designed such that the connec-tion blocking probability is less than or equal to adesign parameter B. The evaluation of this metricallows to determine whether or not each networkuser (each connection) is being treated with the re-quired quality of service.Another technology useful to improve this staticnetwork operation is the optical switches wave-length conversion capacity. In the specialized lit-erature the architecture of dynamic WDM opticalnetworks without wavelength conversion is con-sidered the next generation of optical networks,

due the dynamic resource assignment (who originsoptical networks) already exist and the wavelengthconversion capacity is still in an embryonic phase.Usually the blocking probability is evaluatedthrough simulation [3, 5]. However, this tech-nique is in general very slow compared with thesolution obtained via an appropriate mathemati-cal method. The evaluation speed is relevant, be-cause when solving problems of higher order (e.g.routing or fault tolerant mechanism), it is neces-sary to calculate this metric several times. Thus,a mathematical computational method is requiredfast and efficient. However, this is difficult due toimportant aspects to take into account such as traf-fic load, wavelengths capacity and continuity, net-work topology, etc. Several models have been pro-posed to evaluate the blocking probability [2, 1].In this document we propose a new approach toevaluate the blocking probability (burst losses) inDynamics WDM optical networks without consid-ering wavelength conversion.

Network and Traffic model

The network is represented by graph G = (N ,L),where N is the set of network nodes , and L isthe set of unidirectional links, with respective car-dinalities N and L. The set of connections X ⊆N 2, with cardinality X, is composed of all thesource-destination pairs with communication be-tween them.To represent the traffic between a given source-destination pair an ON-OFF model is used. Duringthe ON period, with average length tON, the sourcetransmits at a constant transition rate. During theOFF period, with average length tOFF, the sourcerefrains from transmitting data. Consequently, thetraffic load for each individual connection ρ, isgiven by the following expression:

ρ =tON

tON + tOFF. (1)

Blocking evaluation strategy

LetR = {rc | c ∈ X } be the set of routes that enablecommunication among the different users (connec-tions) in the network, where rc is the route associ-ated with connection c ∈ X . For every link ` ∈ L,we denote byW` the number of wavelengths asso-ciated with link ` ∈ L.Given the complexity of the exact evaluation ofthe blocking probability considering the aspectsexplained before, we developed a strategy to ob-tain an accurate while light cost computational

27

scheme. Note that the most important aspect toconsider is the wavelength continuity problem, be-cause there is not wavelength conversion capabil-ity. This means that when a connection transmits,it must use the same wavelength on each link thatbelongs to its route. We explain below the differentsteps of this procedure.

• First, the network G with W` wavelengths onlink `, is divided into a sequence of W` net-works denoted G1, G2, . . . , GW`

, where eachlink capacity is equal to 1. This will avoid theproblem of wavelength continuity due to thefact that there is only 1 wavelength per net-work. However, to emulate the operation ofthe this optical networks, exists a sequentialinteraction between this networks Gw. Thismeans, all the blocked connection request ratein the Gw network will be considered as theconnection request rate on the Gw+1 network.To consider the interaction between the W`

networks, we consider a dependency betweentONc,w

and tOFFc,w, the mean ON and OFF pe-

riods “seen” on any network Gw by all the con-nections c ∈ X . These values will be explainedbelow.

• Next, an analytical model to evaluate theblocking probability of each network of thesequence is developed. The blocking proba-bility of the Gw network, which we denote byBCw

c , is evaluated assuming that the states ofthe links that constitute route rc are indepen-dent, that is,

BCwc = 1−

∏

`∈rc

(1− BLc`,w) (2)

whereBLc`,w is the blocking probability of con-nection c on link ` with ` ∈ rc in the net-work Gw. BLc`,w is evaluated as follows:

BLc`,w =1− π`,w0 − π`,wc

1− π`,wc

, (3)

where π`,wc is the probability that connectionc is using link ` in network Gw, and π`,w0 isthe probability that no connection is using thelink ` in network Gw. These probabilities arecalculated by means of a Markov Chain anal-ysis considering the tONc,w

and tOFFc,wvalues,

not shown here for lack of space.

• The interaction between the networks in thesequence is considered in the tONc,w

and

tOFFc,wvalues of network Gw. The parame-

ter tONc,wdoes not depend of Gw, because it

is the time used by the source to transmit, i.e.tONc,w

= tONc, for each network Gw. To rep-

resent the dependencies between the W` net-works, the tONc,w

value must change with w.This changes carries 3 types of dependencies.

– Bottom-top: All non blocked connectionsin the network Gw make tOFFc,w+1

growby 1 cycle.

– Top-Bottom: All blocked connections innetwork G1, but non blocked in networkGm+1, with 1 ≤ m ≤W`−1, make tOFFc,1

grow by 1 cycle.– General blocking: All blocked connec-

tions in the final network GW`make the

first network increase by tOFF.

Then, to consider these dependencies, a fixedpoint procedure is proposed.

• Finally, the average network blocking proba-bility of a dynamic optical network, Bnet, isevaluated as follows:

Bnet =

∑c∈X

λ · BCc

∑c∈X

λ, (4)

where BCc is the general connection blockingprobability, calculated by BCc =

∏all w

BCwc .

Bibliographie

1. V. Abramov, Shuo Li, Meiqian Wang, E.W.M.Wong, and M. Zukerman. Computation ofblocking probability for large circuit switchednetworks. Communications Letters, IEEE,16(11):1892–1895, November 2012.

2. Luiz H. Bonani and Iguatemi E. Fonseca. Esti-mating the blocking probability in wavelength-routed optical networks. Optical Switching andNetworking, 10(4):430 – 438, 2013.

3. Biswanath Mukherjee. Optical WDM networks.Springer Science & Business Media, 2006.

4. A. A M Saleh and Jane M. Simmons. Tech-nology and architecture to enable the explosivegrowth of the internet. Communications Maga-zine, IEEE, 49(1):126–132, January 2011.

5. A. Zapata-Beghelli and P. Bayvel. Dy-namic versus static wavelength-routed opti-cal networks. Lightwave Technology, Journal of,26(20):3403–3415, Oct 2008.

28


Backward-Shifted Coding (BSC)for HTTP Adaptive StreamingZakaria Ye∗, Rachid EL Azouzi∗, Tania Jimenez∗,Stefan Valentin+

University of Avignon, France∗, HuaweiTechnologies, France+

{ zakaria.ye, rachid.elazouzi,tania.jimenez}@univ-avignon.fr,[email protected]

1. Backward-Shifted Coding

Before introducing our Backward-Shifted Coding,we describe the SVC [1], which composed of aH264/AVC-compatible base layer and one or moreenhancement layers. These layers increase the SNRfidelity, spatial and/or temporal quality of the vi-deo when added to the base layer. In fact, thedescription of our scheme will be based on theH.264/SVC codec.The BSC scheme is entirely client driven. The mainidea of this scheme is to decompose the segmentor the GoP in base layer frames and enhancementlayer frames and shift them. The lag between thebase layer and the enhancement layer frames isφ. The base layer frames are less quality and theyare sent before the enhancement layer frames. Eachframe n has it enhancement layer in subsequentframe n+φ− 1 (see fig. 1). Thus, when the enhan-cement layer is missed, the player can still playoutthe base layer frame.In our BSC scheme, each segment or block is en-coded with different rates based on the networkconditions and the scheduling technique. Typi-cally, that means the encoding rate of the base layerand the encoding rate of the combined base andenhancement layers. The encoding rate of the baselayer may differ from one segment to another. Thatis an interesting property of the BSC system to beexplain later. At the user side, incoming bits are

seq=1720p

BL(seq=1)360p

seq=2720p

seq=Ø-1720p

BL(seq=2)360p

BL(seq=Ø-1)360p

BL(seq=Ø+1)360p

BL(seq=Ø)360p

EL(seq=Ø)720p

EL(seq=Ø+1)720p

seq=1720p

BL(seq=Ø)360p

seq=2720p

seq=Ø+1360p

seq=Ø-1720p

seq=2Ø-2360p

BL(seq=2Ø-1)360p

EL(seq=Ø)720p

BL(seq=2Ø)360p

EL(seq=Ø+1)720p

BL(seq=N)360p

EL(seq=N-Ø+1)720p

EL(seq=N-Ø)720p

EL(seq=N)720p

EL(seq=N)720p

BL(seq=Ø+1)360p

Frames encoding on

the server side

Frames transmission

FIGURE 1 – Using SVC in Backward-Shifted Coding

reassembled into video frames by the decoder.Under DASH, each video client is divided intomultiple small segments at the media server. Va-rious representations of a segment or block are pro-posed by using different encoding rates. Hence,the BSC scheme can be used with evident clientusing the DASH framework. The base layer is re-encoded for each segment, possibly with a dif-ferent encoding rate, depending on the networkthroughput measurements. It is a runtime enco-ding process like in live video streaming systems.Therefore, with BSC under DASH, the adapta-tion engine requests the two appropriate segmentswith different bitrates (base layer and enhance-ment layers).

2. Bitrate Adaptation with Backward-Shifted Co-ding

2.1. System DescriptionWe consider a video streaming system using theBackward-Shifted Coding described. The serverholds the media segments and a HTTP server. Theclient holds an adaptation engine and a playoutbuffer where the video frames are decoded andstored to be display on the screen. The main goalof the adaptation engine is to estimate the through-put and select the bitrates of the next segment to bedownloaded.We assumeN to be the size of the video file in num-ber of frames. Let d be the buffer playout frequency(e.g., 30fps). The video duration ∆ (in seconds) isN/d. A video file is a set of consecutive video seg-ments or chunks, ν = {1, 2, ..., K}, each of whichcontains L seconds of video and encoded with dif-ferent bitrates. The number of segments K in thevideo is ∆/L. We assume R = {R1, R2, ..., Rr} tobe the set of available bitrates. In BSC system, theplayer downloads the video segment kwith bitrate(Rki, Rkj) ∈ R where Rki is the bitrate of the basiclayer and Rkj is the bitrate of the combined basiclayer and enhancement layer.

2.2. Adaptation methods in BSCThe goal of the bitrate adaptation is to maximizethe quality of experience of the user. We consi-der the throughput based method (TBA) (currentsegment throughput) and the buffer based me-thod (BBA) (buffer level) algorithms. For TBA, thealgorithm selects the adequate bitrates after thedownload of the current segment. The pseudo-code is provided in algorithm 1 where R<(ti),R>(ti), Rmin and Rmax are such that Rmin < ... <R<(ti) < A(ti) < R>(ti) < ... < Rmax.

29

Algorithm 1: Adaptation AlgorithmInput:A(ti) : the estimated throughput of the previous segment iRi(BL) : the bitrate of the base layer of the previous segment iOutput:Ri+1(BL) : the bitrate of the base layer of the next segment i+ 1Ri+1(BL + EL) : the bitrate of the combined layers of the nextsegment i + 1

1 R<(ti)← A(ti)↓ ;

2 R>(ti)← A(ti)↑ ;

3 if A(ti) ≤ Rmin then4 Ri+1(BL) := Ri+1(BL + EL) := Rmin ;5 else6 if A(ti) ≥ Rmax then7 Ri+1(BL) := Ri+1(BL + EL) := Rmax ;8 else9 if A(ti) < Ri(BL) then

10 Ri+1(BL) := R<(ti) ;11 Ri+1(BL + EL) := R>(ti) ;12 else13 Ri+1(BL) := Ri(BL)

↑ ;14 Ri+1(BL + EL) := Ri+1(BL)

↑ ;

For BBA we define three buffer thresholds Bmin,Blow and Bhigh and make the bitrate selection de-cision on the buffer filling level. Algorithm 1 isused at the beginning of this method to increasequickly the bitrate at the beginning of the videoplayback in order to maximize the video quality.

3. Simulations and Numerical results

3.1. Simulation setupWe use MATLAB to simulate the event-driven bi-trate switching system. Our traffic model (see fig.

0 10 20 30 40 50 60 70 800

0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

Time (sec)

Mb

ps

BandwidthThroughput

FIGURE 2 – Background traffic with Level shift

2) simulates a realistic network bandwidth varia-tions with congestion level shift where they injectbackground TCP traffic between the server and theclient. The link capacity between the server and theclient is set to be 5Mbps. The traffic rate jumps bet-ween four different levels, oscillations within thesame level are due to TCP congestion control me-chanisms. The link capacity is higher than the TCPthroughput.

3.2. Numerical ResultsThis set of experiments compares the reques-ted bitrate with BSC and DASH under thenetwork conditions of fig. 2. The file size inthe experiments is up to 100 seconds of videowhile the playabck frequency is 25 fps. Weconsider the following set of available bitrates{140, 250, 420, 760, 1000, 1500, 2100, 2900}(Kbps).The video segment duration is set to 2 seconds.Figure 3 shows the requested bitrate for BSC and

0 5 10 15 20 25 30 35 40 45 500

0.5

1

1.5

2

2.5

3

3.5

Time (Seconds)M

bp

s

BSC vs DASH, φ=51, instant throughput estimation

requested bitrate BSCrequested bitrate DASH

FIGURE 3 – BSC vs DASHinstant throughput estimationmethod

0 10 20 30 40 50 60 70 80 90 1000

0.5

1

1.5

2

2.5

3

3.5

Time (Seconds)

Mb

ps

BSC vs DASH, φ=51, buffer based method

requested bitrate BSCrequested bitrate DASH

FIGURE 4 – BSC vs DASH buf-fer based method

DASH for TBA where the throughput is estimatedover 1 segment. The average video bitrate is muchhigher with BSC system for a few additionalbitrate swithcings. These bitrate switchings aretolerable since they are between two consecutivebitrates. We can still cope these switchings byforcing the system to stay at the base layer framesif the time spent at the base level does not exceeda certain threshold.Figure 4 shows the requested bitrate for BSCand DASH for BBA Bmin = 5sec, Blow = 7sec,Bhigh = 50sec. BSC system achieves a bettervideo quality and decreases the bitrate switchingscompared to TBA.

4. Conlusion

We proposed a novel coding scheme to improvethe performance of the HTTP adaptive video strea-ming. BSC is inspired from the FEC method. Themedia server transmits two shifted segments withdifferent bitrates, i.e., a base layer with enhance-ment layers, in order to enhance the video quality.We proposed bitrate adaptation algorithms in BSC.We further performed simulations to show the effi-ciency of BSC system compared to existing DASHsolutions.

Bibliographie

1. ISO/IEC – Coding of Audio-visual Objects - Part10 : Advanced Video Coding 14496-10 :2012 In-formation Technology, 2012.

30


Resource Allocation forin-Network Computations

Apostolos Destounis1, Georgios S. Paschos1,Iordanis Koutsopoulos2

1Mathematical and Algorithmic Sciences Lab,Huawei technologies FRC20, quai du Point du Jour92100 Boulogne-Billancourt, [email protected]

2Department of Informatics, Athens University ofEconomics and Business (AUEB)76, Patission Str., 104 34, Athens, [email protected]

1. Introduction

In this work, we ask the following question : Givena network graph G = (N ,L) with links of limitedcommunication bandwidth and nodes of limitedcomputation resources, what are the performance li-mits of in-network computation throughput ? Na-mely, what is the maximum rate with which com-putation results can be conveyed to the destinationwhen computations take place in the network ?We assume there exist two source nodes s1, s2 ∈ Nand a destination node d. Edge (m, l) ∈ E betweennodes m and l has a fixed capacity of Rml packetsper slot. A network example is given in Fig. 1.We study a stream of queries, where each queryconcerns the computation of the sum of a datumfrom source 1 and a datum from source 2, while thenetwork is agnostic to specificities of data. Uponarrival of each query, a corresponding packet (da-tum) is generated at each of the two source nodes,and both packets are given the same tag. These pa-ckets need to be summed somewhere in the net-work, and the result needs to be delivered to thedestination d. Time is slotted, and at each slot tthere are A(t) newly arrived queries belonging tothe same stream, random with E[A(t)] = λ.Combination of packets corresponding to a querymay take place in one among a subset of nodes,denoted by NC = {n1, n2, ..., nNC

} ⊆ V ; these arereferred to as the computation nodes. Node ni hascomputational capacity of Cni

, measured in num-ber of produced processed packets per slot, whereeach processed packet concerns the sum of tworaw packets with the same tag when both are avai-lable to the computation node.

The objective of this work is to characterize themaximum rate of queries that can be accommoda-ted by the network (referred to as the computationcapacity of the network), and provide an online al-gorithm to achieve this capacity. We restrict our-selves to policies that use only packet routing (i.e.no network coding).

2. Queueing Structure

To capture all packet classes in the network we de-fine the following queues (A calligraphic sign de-notes a set with the tags of the corresponding pa-ckets, normal sign denotes the cardinality of thisset) :

— Q(i,n)k (t), i = 1, 2 : Data queue at node k contai-

ning raw packets generated at node si that haveto be computed at node n.

— X (i)n (t), i = 1, 2 : Computation queue at noden containing raw packets generated at node sithat have to be computed at this node.

— Q(0,n)k (t), i = 1, 2 : Data queue at node k contai-

ning processed packets from computing noden, that have to be delivered at the destinationnode.

In addition, each computation node has queuesYn(t) keeping the results of computations (see alsoFig. 2) and virtual queues Hn(t) tracking the com-putation capacity budget.Moving packets between queues corresponds tocontrol decisions to be taken each slot :— The set of raw packets originated from node si,

destined to computation node n, to be transmit-ted from nodem to node k.

— The pairs of raw packets to be combined at eachcomputation node n

— The set of processed packets, combined at noden, to be transmitted from nodem to node k.

We have the following constraints : (i)The totalnumber of transmitted packets over a link (kl) arelimited by link capacity Rkl (ii) the number of com-bined pairs cannot exceed the computation capa-city or any of the individual raw packet queuelengths, and (iii) a pair of packets can be combi-ned only if both packets with the same tag havealready arrived at the computation node.

3. Upper Bound on the Network ComputationCapacity

We define a set C3 with 3NC unicast commodities,as follows : there are three commodities for each

31

s1

d

+

s2

data source 1 data source 2

destination for query response

computation node

FIGURE 1 – Illustration of network computations.Shaded nodes are forwarding ones, i.e. withoutcomputation capabilities, and white nodes havecomputation capabilities. Arrows denote routingof raw and processed data.

computation node n ∈ NC ; (1, n) delivering pa-ckets from s1 to n, (2, n) delivering packets froms2 to n, and (n, d) delivering combined packets at(computation) node n to the destination. Let Λ(G)be the feasible rate region for these commoditieson network G. We can characterize the computa-tion capacity as follows :

Theorem 1 An upper bound on the computation capa-city is given by the following optimization problem :

λ∗ = max(λn)

∑

n∈NC

λn (1)

s.t. 0 ≤ λn ≤ Cn, ∀n ∈ NC (2)(λ1, λ1, λ1, ..., λNC

, λNC, λNC

) ∈ Λ(G) (3)

4. Algorithm

The dynamic policy we consider here is the follo-wing :

1. Load Balancing : At each slot, choose n∗(t)equal to

arg minn∈NC

[(1+ εB)Q

(0,n)n (t) +

∑

i=1,2

Q(i,n)i (t)

+Hn(t)

]

where εB ∈ (0, 1) is a control parameter.Then, all newly arrived queries are assigned tothe class that corresponds to this computationnode.

2. Routing and scheduling : Use Backpressureover class pairs. For every link (m,k) ∈ Echoose the class pair(i∗mk(t), n

∗mk(t)

)

= arg maxi∈{0,1,2}n∈NC

∣∣∣Q(i,n)m (t) −Q

(i,n)k (t)

∣∣∣ .

5789

6710

34+

1

D

2

D

DD

dummy packets pool

network

queueing structure of computation node n

F(n)(t)

YnX (1)n

X (2)n

Q(0,n)nQ(1,n)

n Q(2,n)n

FIGURE 2 – Illustration of queueing structure forcomputation node n. Numbered packets are eitherraw or processed (green) useful packets, while pa-ckets noted with “D” are dummy packets.

Then use the capacity of the link to route (any)packets of the above class pair, from the biggestto smallest corresponding queue.

3. Computation : At every node n ∈ NC, allpossible computations are done. If there aremore pairs than the computation capacity ofthis node, then Cn pairs are selected using anytie breaking rule.

4. Randomization with dummy packets :F(n)(t) = 1{n=n∗(t)}A(t)

(1+ B(n)(t)

)packets

resulting from a computation are pushed toqueue Q(0)

n (t), where B(n)(t) are an i.i.d. Ber-noulli random variables with mean εB. If thereare not enough processed packets available atqueue Yn, dummy packets are used.

5. Update Virtual Queues :

Hn(t+ 1) = [Hn(t) − Cn]+ + 1{n=n∗(t)}F

(n)(t).

The main result of this work is the performance ofthe online algorithm :

Theorem 2 The online policy satisfies any query rateλ <

(1− εB

1+εB

)λ∗.

Theorem 2 implies that the online algorithmachieves a computation rate arbitrarily close to theupper bound.

32


Anticipating ResourceManagement and QoEProvisioning for Video StreamingImen TRIKI, Rachid ELAZOUZI, MajedHADDAD

University of Avignon Franceimen.triki/rachid.elazouzi/[email protected]

1. Resume

This study provides important insights in the de-sign and optimization of adaptive video streamingby exploiting the knowledge of future capacityvariations. We develop a framework that allowsto extend the model developed in [1] by balancingsystem utilization and adaptive video quality. Ourmain contributions can be summarized as follows

i) We provide a general optimization frameworkfor stored adaptive video delivery that accountsfor operators’ and clients’ preferencesii) Under the constraint of no rebuffering events,we formally obtained the optimal solution wherethe transmission schedule is of a threshold typeand the coding strategy is of an ascending typeiii) We propose an efficient mechanism thatperforms close to the optimal solution, and weevaluate its performance and robustness usingrealistic traces.

2. Problem Formulation

We propose an optimization model in which weminimize an objective function F in respect ofsome constraints. The trend of this function de-pends on a fixed parameter a that adjusts thetrade-off between the network utilization cost andthe user QoE.

min(r,γ)

F(r, γ) = 1

T

∫T

0

r(t)

c(t)dt− a

∑j=Lj=1 wj

∫T0γj(t)r(t)dt

SL(1)

s.t

∫t0λ c(t)γ1

bL≥ l(t) ∀t ≤ T

∫t0

∑j=Lj=1

λ r(t)γj(t)bL

≥ l(t) ∀t ≤ T∫T0

∑j=Lj=1

λ r(t)γj(t)bL

= l(T)

where :c : characterizes the network available capacityr : characterizes the network transmission sche-dulebi designs bitrate level i ; bi ≤ bj for i ≤ jγj : characterizes bitrate level jwj : a score assigned to bitrate level jT : the video length in sSL : the video size in bits with the highest qualityλ : the video speed lecturel : the constraint function of the buffer state evolu-tion

3. Problem Resolution

3.1. Threshold strategyDefinition 1. Giving the network capacity c, we definethe threshold transmission schedule by

rth(t) =

{c(t) if c(t) ≥ α0 otherwise, (2)

Proposition 1. Assume that there exists a feasible solu-tion that satisfies the constraints in (1), then there existsan optimal strategy (rth, γrth) of optimisation problem(1), where rth is a threshold transmission schedule.

3.2. Ascending coding rate approachDefinition 2. We say a bitrate level strategy is ascen-ding if the quality level of segments increases duringthe session, i.e., for all 0 ≤ t ≤ t ′ ≤ T

b(t) ≤ b(t ′) i.e., γ(t) ≥ γ(t ′)Proposition 2. Assume that there exists a threshold-based solution (rth, γ) that satisfies constraints in (1),then there exists a threshold-based ascending bitrate le-vel solution (r′th, γ

′) that optimizes problem in (1).

4. Algorithmic approaches

4.1. Principal of optimal solution(i) We first look at all the possible values of α ∈[αmin, αmax] that satisfy the constraints in (1)while associating to each one the highest possiblevideo quality, (ii) Suppose that we obtain a set ofM possible thresholds {αi, i = 1, 2, . . . ,M; αi <αj , i < j}. Therefore, for each threshold and itscorresponding video quality, we compute the re-sulting cost function F , (iii) The optimal solutioncorresponds to the one that minimizes F . The ac-curacy of this algorithm increases with M at theexpand of increasing complexity.

4.2. Heuristic for a near-optimal solutionLet γα and Fα be, respectively, the ascending bi-trate level strategy and the cost function under rα-based transmission schedule. The main steps of the

33

proposed heuristic are described in Algorithm 1,where INVEST represents the approach for gene-rating sub-optimal thresholds and AWARE repre-sents the heuristic for setting sub-optimal ascen-ding bitrate levels.

Algorithm 1: Heuristic for a near-optimal solutionData: c, VideoProperties, L,w,Q

1 α← cmin; i← 1;2 [PossibleTransmission, rα, γα] =

AWARE(c, α, videoProperties, L)3 while PossibleTransmission do4 Fα = computeObjFunction(c, rα, γα, w)5 i = i+ 16 α = INVEST(c, i,Q)7 [PossibleTransmission, rα, γα] =

AWARE(c, α, videoProperties, L)end

8 F∗α∗ = min{Fα}9 αth = α∗

10 return (αth, γαth)

4.2.1. Heuristic for generating thresholds : IN-crease with VariablE foot STep (INVEST)

The increase on α is performed by adding a va-riable footstep at each iteration depending onthe dynamic of the network capacity. We fix theamount of data that we wish to abandon at eachstep (denoted by Q). Then, we adjust the value ofαwhich gives the corresponding variable footstep.

4.2.2. Heuristic for Anticipating qoe With Ascen-ding bitRate lEvels (AWARE)

We start by assigning the lowest level to all videosegments. Then, we keep increasing the levels pro-gressively starting by the end of the video as longas the constraints are satisfied. Once a constraint isviolated, we choose the previous level of the seg-ment. The number of loops is equal to L − 1. Toreduce at maximum the startup delay, we set bydefault the buffering-cache segments to the lowestvideo quality and use a greedy 1 transmission ins-tead of using a threshold-based transmission. Aninherent advantage of this algorithm is that it en-sures a progressive increase of the quality levelsinstead of an aggressive increase as in the optimalsolution, which is quite more appreciable for theuser’s perception.

1. A greedy transmission uses all the available network ca-pacities.

5. Results

t (s)

0 50 100 150

fram

es

0

2000

4000

a=4.5

u

l

Segment

0 50 100 150

Bitr

ate

leve

l (M

bps)

0

1

2

3a=4.5

t (s)

0 50 100 150

fram

es

0

2000

4000

a=4.6

u

l

Segment

0 50 100 150

Bitr

ate

Leve

l (M

bps)

0

1

2

3a=4.6

t (s)

0 50 100 150fr

ames

0

2000

4000

a=4.7

u

l

Segment

0 50 100 150

Bitr

ate

leve

l (M

bps)

0

1

2

3a=4.7

FIGURE 1 – Playback buffer state evolution and cor-responding bitrate levels for different a.

FIGURE 2 – Experimental real spacial variations of the capa-city for the tramway Ljabru-Jernbanetorget trajectory.

a

10 15 20 25 30

Qo

E e

rro

r

-0.1

0

0.1

0.2

0.3

0.4

a

10 15 20 25 30

Syste

m C

ost

err

or

-0.1

0

0.1

0.2

0.3

0.4

FIGURE 3 – Average error rate on the system per-formance under throughput prediction errors.

1. Lu, Zheng and de Veciana, Gustavo. – Optimizingstored video delivery for mobile networks : The va-lue of knowing the future. – INFOCOM , 2013.

34

Liste des inscrits

– Farah Ait Salaht, LIP6 Paris– Ahmad Al Sheikh, QoS Design Toulouse– Urtzi Ayesta, LAAS Toulouse– Mohamed El Hedi Boussada, MEDIATRON Tunis– Olivier Brun, LAAS-CNRS Toulouse– Hind Castel, SAMOVAR Evry– Apostolos Destounis, Huawei France Research Lab Boulogne Billancourt– Josu Doncel, INRIA Grenoble– Stephane Durand, INRIA Montbonnot– Rachid Elazouzi, Laboratoire Informatique d’Avignon– Samer El Zant, IRIT, Toulouse– Jean-Michel Fourneau, Université de Versailles Saint Quentin– Nicolas Gast, INRIA Grenoble– Bruno Gaujal, INRIA Grenoble– Lennart Gulikers, INRIA Palaiseau– Nidhi Hegde, Nokia Paris– Nicolas Jara, INRIA Rennes– Alain Jean-Marie, Inria Montpellier– Baptiste Jonglez, ENS de Lyon– Maialen Larrañaga, Centrale-Supélec Gif-sur-Yvette– Patrick Loiseau, EURECOM Sophia-Antipolis– Xiaoyan Ma, ENSEEIHT/IRIT TOULOUSE– Lorenzo Maggi, Huawei France Research Lab Boulogne Billancourt– Cristian Maxim, Inria Paris– Yves Mocquard, IRISA Rennes– Thi Thu Hang Nguyen, LAAS-CNRS Toulouse– Rudesindo Núñez-Queija, CWI et Univ. van Amsterdam– Balakrishna Prabhu, LAAS-CNRS Toulouse– Florian Simatos, ISAE SUPAERO Toulouse– Baya Takhedmit, LAMOS Béjaia, Algérie– Imen Triki, Laboratoire Informatique d’Avignon– Maaike Verloop, IRIT/ENSEEIHT Toulouse– Jean-Marc Vincent, LIG Grenoble– Zakaria Ye, Laboratoire Informatique d’Avignon

35

Liste des contributeurs

Ait Salaht Farah, 9, 10Al Sheikh Ahmad, 8

Bayati Marziyeh, 11, 12Boussada Mohamed El Hedi, 15, 16Boxma Onno J., 23, 24

Chouvardas Symeon, 25, 26Destounis Apostolos, 31, 32Doncel Josu, 21, 22Draief Moez, 25, 26Durand Stéphane, 17, 18

El Azouzi Rachid, 29, 30, 33, 34

Fourneau Jean-Michel, 8Garcia Jean Marie, 15, 16Gast Nicolas, 21, 22Gaujal Bruno, 17–22

Haddad Majed, 33, 34Hegde Nidhi, 6

Jara Nicolas, 27, 28Jean-Marie Alain, 8Jimenez Tania, 29, 30Jonglez Baptiste, 19, 20

Koutsopoulos Iordanis, 31, 32

Larranaga Maialen, 23, 24Leguay Jérémie, 25, 26Loiseau Patrick, 6

Maggi Lorenzo, 25, 26Mocquard Yves, 11, 12

Núñez-Queija Rudesindo, 6, 23, 24

Paris Stefano, 25, 26Paschos Georgios, 31, 32

36

Liste des contributeurs

Rubino Gerardo, 27, 28

Squillante Mark S., 23, 24

Triki Imen, 33, 34

Valentin Stefan, 29, 30Vallejos Reinaldo, 27, 28Vincent Jean-Marc, 8

Ye Zakaria, 29, 30

37

Documents

Actes du 11ème Atelier en Évaluation de Performances › ... › aep11 › AEP11_CFP.pdf · 2016-03-09 · –Heavy-tailed asymptotics : We will explain the fundamental difference