Etude du délai maximal pour des serveurs en tandem : politique de service a priorité fixe

Introduction a la théorie du Network Calculus

Aujourd’hui les systèmes embarques représentent une grande part du marche mondial des technologies. Nous les retrouvons dans les téléphones, les GPS et les avions…etc. L’ AFDX [04] (Avionic Full Duplex Switched Internet ) est le support de communication embarque dans les avions. Il utilise des lignes de communication full duplex (communication dans les deux sens) reliées par des switchs (commutateurs réseaux). Un enjeu majeur réside dans le fait de savoir borner le délai d’attente dans les buffers des switchs. Il est également nécessaire de savoir calculer une borne maximale du délai subi par une donnée d’un bout a l’autre du réseau. En effet, dans le cas du système AFDX, on sait qu’il fonctionne correctement si les données traversent le réseau avant un certain laps de temps.
Avant de placer ce système dans un avion il est nécessaire de s’assurer que cette condition est toujours vérifiée.
Le Network Calculus [05] et [08], est une théorie qui permet de calculer des bornes de performance dans les réseaux de communication, compos´es de flux de données traversant certains (ou tous) éléments du réseau. Un exemple est représenté sur la figure 1. Il comporte 2 serveurs et trois flux. Le premier est traverse par tous les flux mais le second uniquement par 2 d’entre eux. Les bornes calculées grâce au Network Calculus sont des bornes supérieures subies par les données d’un ou plusieurs flux telles que le délai ou la charge maximale d’un système ou du réseau entier, ainsi que d’autres valeurs permettant de déterminer la qualité de service. Les calculs sont effectues par le biais de fonctions. Par exemple la courbe des arrivées est une fonction qui majore la quantité de données arrivant `a travers un flux, la courbe de service délivré une borne minimale de la quantité de données traitées a chaque instant par le serveur étudié. Nous utiliserons une structure mathématique sur l’espace R [ {+1} ayant pour lois internes le minimum et l’addition, deux opérations couramment utilisées sont la convolution et la déconvolution. Un peu plus loin, nous donnerons une définition formelle de ces opérations.
Exemple introductif Considérons le réseau de la figure 2, compos´e d’un système et d’un flux. Nous pressentons ici, les systèmes leacky bucket, que l’on peut traduire par seau perce, qui sont tr`es souvent utilises pour la modélisation de systèmes contraints. Le livre [05] présente une étude complets de ces systèmes.
Soit un flux traversant un tel système. Les données y sont acheminées afin d’y être traitées. Nous allons introduire une notion : la courbe arrive qui sera présente formellement plus loin.
Les données `a l’entrée d’un système arrivent avec un certain débit. Celui-ci peut varier au cours du temps. Pour se donner une image concrète on peut faire l’analogie avec la transmission de bits dans un cˆable allant d’un point A a un point B, lors d’une communication téléphonique.
La fonction de contrainte des systèmes leacky bucket est définie par : 8t 2 R, (t) = + (t). Le paramètre définit la taille du buffer. Du point de vue des arrivées, cela signifie que la quantité maximale de données arrivant d’un coup dans le système est . Le paramètre , quant a lui définit le taux d’arrivée des données : `a chaque unit´e de temps, au maximum données sont acheminées jusqu’au système.
Sur le schéma ci-dessous, nous avons représente par la courbe bleue (R) les arrivées cumulées des données au système. Visuellement (R) est contrainte par si sa courbe est toujours en dessous de cette dernière. On dira alors que le système est (, )-contraint.
Nous avons cherche, durant ce stage, `a fournir une méthode de calcul du délai subi par un flux dans un réseau de manière déterministe, lorsque la politique de service est a priorité fixe. Il existe bien sur des méthodes, [10] et [02], fournissant des délais dans ce genre de situations. Notre but sera de fournir des résultats plus fins. Nous allons tout d’abord introduire la base théorique sur laquelle repose les calculs de délai, appelée Network Calculus, ainsi que les différentes méthodes qui en découlent et qui permettent ces calculs. Nous présentons ensuite un premier résultat sur le délai borne. Puis, nous énoncerons le travail que nous avons réalise, avant de le comparer aux méthodes concurrentes. Enfin, nous exposerons une limite actuelle de notre travail, avant de conclure.

Premiers résultats sur les caractéristiques des réseaux

Deux questions sont tr`es importantes lorsque l’on considère les systèmes comportant plusieurs flots et plusieurs composants `a la suite : comment obtenir la capacité non utilisée a chaque instant ? Comment obtenir la courbe d’arrivée associée a un composant quelconque du réseau, ne connaissant que les courbes arrives des flux `a l’entrée du réseau ?
Définition 9 (Flux résiduel) Considérons deux flux f1 et f2 tel que f1 est 1-contraint, et supposons que soit la courbe de service strict associe `a un système S. Alors une courbe de service associée a f2 est ( − 1)+.
On peut ainsi calculer la capacité résiduelle qui est donc apportée aux flux les moins prioritaires. Grace a ce résultat on peut définir la capacité de traitement qu’un serveur accorde a un flux quelconque. Sur la figure 8, si f2 est moins prioritaire que f1 on peut calculer la courbe de service résiduel associée et en déduire le délai. C’est ce que nous faisons dans l’exemple ci-dessous.
Exemple Nous examinons maintenant un serveur de courbe de service 1, telle que 1(t) = R(t − T)+ travers´e par deux flux f1 et f2 de courbe d’arrivée respective 1, 2 avec : 1(t) = 1 + 1t, et 2(t) = 2 + 2t. Ce réseau est représenté sur la figure 8 ci-dessus. Calculons 0 le flux résiduel associe au second flux.

Méthodes de calcul du délai maximal d’un réseau

Dans cette partie du rapport nous faisons l’inventaire des méthodes existantes permettant de calculer le délai maximal d’un flux passant `a travers un réseau. Nous commençons par présenter des travaux dont la politique de service ne considèrent pas de priorités sur les flux, [03] et [09]. C’est ce que l’on appelle des politiques ”arbitraires” : tout les flux sont servis ensemble par le serveur dont on connait une borne minimale de la capacité de traitement. Enfin nous présentons une méthode de calcul prenant en compte des priorités, [10]. Apres avoir présente notre travail nous comparerons les délais obtenus par ces méthodes avec la notre.

Réseaux a flux multiplex´es et regroupes

Nous nous intéressons dans cette partie aux réseaux dont les flux sont regroupes et o`u l’on ne peut pas supposer que la politique de service est FIFO (politique aveugle). L’analyse [09] commence par calculer la quantité de données traitées en chaque nœud pour chaque flot considéré séparément. Autrement dit, elle calcule la bande passante associée a chaque nœud. Pour déduire le délai maximum, il reste `a prendre la déviation horizontale (comme le montre la figure 7). Cette méthode s’appelle Separate Flow Analysis (SFA).
Prenons un exemple du calcul de délai grˆace `a cette méthode. La figure 9 présente un réseau compos´e de deux serveurs s1 et s2 de courbes de service respectives 1, 2. Deux flux, f1 et f2 de courbes d’arrivée respectives 1, 2 traversent l’ensemble du réseau. Alors le délai du flux f1, note d, est :

Algorithme de programmation linéaire (LP)

L’article [03] apporte une nouvelle méthode de calcul des bornes de délai et de charge de ces réseaux, en utilisant la programmation linéaire, grâce au théorème suivant :
Théorème 6 Soit S un système contenant n nœuds et f flots. Si S est acyclique alors pour un flot i(resp. un serveur j) il existe une collection finie de programmes linéaires avec pour valeur optimale opt 2 tel que max(opt) soit le pire délai d’un bout `a l’autre du réseau (resp. la pire charge).

Etude des réseaux quelconques

On considère dans cette partie les réseaux quelconques dans lesquels les flux sont soumis `a des priorites. Dans la suite, les flux sont indic´es selon leur priorité : soient fu, fv tels que u < v alors prio(fv) < prio(fu). Nous considérons un réseau contenant n serveurs tel que sk dispose d’une courbe de service minimale k telle que, k(t) = Rk(t − Tk)+ et m flux tels que le flux fi est contraint par i(t) = i + it. On ne pose aucune contrainte sur la fa¸con dont les flux traversent le réseau. Un exemple de réseau concerne est donne sur la figure 11.
Le but est de formuler une condition nécessaire et suffisante pour obtenir un délai borne dans ce réseau.
Dans un premier temps, nous allons calculer la contrainte sur le flux de sortie du serveur sk pour le flux fi. Comme les flux sont soumis `a des priorités dans ce réseau, pour obtenir la contrainte de sortie d’un flux fi, il nous faut d’abord connaitre les contraintes des flux plus prioritaires en ce serveur. Soit Mk i l’ensemble des serveurs travers´es par fi avant d’arriver en sk (sk est inclu dans cet ensemble).

Etude du délai maximal pour des serveurs en tandem : politique de service a priorité fixe

Topologie des réseaux étudies

Cette ´étude prend en compte une restriction de l’ensemble des réseaux, pour une topologie donnée. Il serait en effet complexe de considérer tous les types imaginables, qui ne se traitent pas tous de la même fa¸con. Prenons l’exemple des réseaux cycliques : leur étude est complexe de part la dépendance de la charge `a l’instant t par rapport au passe. Ainsi ces réseaux disposent d’une étude particulière. C’est pourquoi, dans notre travail nous nous restreignons `a la classe des réseaux en tandem. De plus, les réseaux ´étudies dans la suite respectent les hypothèses de stabilité énonce dans le théorème 7.

Méthodologie

Dans le paragraphe 2.2 nous avons présente une étude des réseaux acycliques dans le cas d’une politique de service arbitraire (i.e. `a tout instant le serveur traite un des flux présente a son entrée choisi de manière arbitraire). Afin de déterminer le délai maximal subi par un flux f du réseau, ils définissent des contraintes linéaires traduisant le comportement du réseau pour une politique de service arbitraire et cherchent `a maximiser la durée nécessaire `a f pour traverser le réseau grˆace `a un solveur. Parmi ces contraintes, on repère notamment les -contraintes sur les arrivées et -contraintes sur les services.
Notre objectif est de définir un ensemble de contraintes assurant le système de priorité entre les flux choisis. Pour cela, nous allons reprendre le travail effectue dans l’article [03], et l’enrichir en ajoutant des contraintes de priorité.

Généralités

Si l’on intéresse au délai maximal subi par les données du flux f` alors il n’est pas nécessaire de considérer les flux moins prioritaires que lui. En effet, si `a une date donnée, f` pressente des paquets `a traiter, alors f` sera toujours exécuté avant les flux moins prioritaires. Au contraire, la présence de flux moins prioritaires peut réduire le temps d’attente. En effet, supposons que f` exécute entièrement et que les autres flux plus prioritaires soient vides, alors le serveur se met en pause. Supposons qu’au bout d’un certain temps, des données du flux f` arrivent, elles peuvent alors attendre jusqu`a T unit´es de temps avant d’etre traitées (dans le pire cas), comme le montre la figure 12. Cela correspond au temps de latence du serveur. Maintenant, si l’on ajoute des flux moins prioritaires que f`, alors ils seront trait´es après f` et le serveur ne sera pas en pause. Ainsi d`es que des données de f` arrivent, elles seront traitées sans délai. C’est pourquoi, dans la suite on supposera disposer uniquement de ` flux lors de Etude du délai maximal subit par f`.

Comparaison des résultats

Sur la figure 17, nous avons regroupe les résultats obtenus pour les différentes méthodes présentées précédemment. Ici, nous avons fait varier le nombre de serveurs (et donc le nombre de flux). Chaque serveur du réseau est contraint par la même courbe de service : (t) = 28(t − 5)+. Aux flux est associée une même contrainte : (t) = 2 + 3t.
Les barres bleues représentent les délais obtenus par notre méthode. Les violettes désignent les bornes calcul´es par la méthode introduite dans l’article [02], pour qu’une donnée du flux le moins prioritaire traverse le réseau. Nous avons obtenu les résultats grâce au lemme 5 énonce précédemment. Enfin le jaune donne ce délai par la méthode SFA. Ces derniers ont ´et´e calcul´es `a partir des formules définies au lemme 6.
On constate que les résultats de la méthode de programmation linéaire avec priorités et celle de l’article [02] fournissent des résultats assez proche, bien que l’ecart tende `a augmenter en même temps que le nombre de serveurs. Cependant que la méthode SFA fournit des valeurs tr`es pessimistes. Helas pour que la méthode de l’article [02] soit applicable il faut pouvoir isoler les serveurs travers´es par le flux le plus prioritaire, afin de calculer sa courbe de service résiduelle, puis faire de même pour le second flux et ainsi de suite. En l’occurrence la méthode est applicable car le flux fi+1 passe au moins `a travers les serveurs par lesquels passe fi, mais pour le réseau de la figure 19 ce n’est plus le cas. Ainsi, en plus de fournir des résultats plus fins des délais, notre méthode s’applique `a un plus grand spectre de réseaux.
La démarche utilisée par SFA, elle aussi, s’applique `a tous les réseaux, cependant ces résultats sont bien plus pessimistes. En moyenne, sur cet exemple, les délais calcul´es sont 50% `a 100% plus élevés que notre approche.
Nous souhaitons étudier sur cet exemple l’impact que la variation des paramètres des fonctions et . Nous avons effectue cette étude, en considérant un réseau a 9 serveurs, sur le paramètre R qui correspond au taux de données traitées par les serveurs `a chaque instant. Nous avons représente les résultats sur la figure 18 ci-dessous, pour les méthodes de calcul de programmation linéaire et l’approche de l’article [03].
L’approche de l’article [03] procure des résultats supérieurs `a ceux de notre travail. De plus, plus le taux d’utilisation du réseau est important, moins les résultats de cette méthode sont proches des nôtres, et sont donc moins fiables.

Limite du calcul de délai pour les politiques a priorité fixe a l’aide des contraintes linéaires

Jusqu’ici nous avons montre que nos contraintes permettaient d’assurer les priorités sur la première période activité du serveur étudie et que les contraintes du Network Calculus ( et contraintes, croissance, causalité étaient satisfaite sur cet intervalle. Une question reste en suspens : que se passe-t-il dans les serveurs en-dehors de la période d’activité étudiée ? Intuitivement, on pourrait penser que s’il se passe des phénomènes bizarres sur les autres intervalles de temps, ce n’est pas un problème puisque la donnée, du flux le moins prioritaire,
dont on étudie le délai est passée. Evidemment ce n’est pas aussi simple. Nous avons exprimé les contraintes entre toutes les dates intermédiaires existantes. Donc on sait que ces contraintes seront toujours assurées. Il en est de même pour la croissance et la causalité. Ainsi seules les contraintes sur le service peuvent nous faire défaut. Nous avons recherche un exemple dans lequel une telle contrainte ne serait pas assurée.
Il est a noter qu’aucune donnée n’est servie pour f1 dans l’intervalle [t0, t2] ce qui, intuitivement, paraît anormal puisque c’est le flux le plus prioritaire.
Avant t1 c’est normal puisque 1 y est nulle. Mais passée cette date ce n’est plus le cas. La trajectoire B1 est nulle jusqu’a t3. Ainsi f1 n’est servi qu’`a partir de cette date alors que des données de ce dernier attendent a l’entrée du serveur d`es t0. Quel est l’impact de ce phénomène sur le délai calcul´e ?
Nous avons simule ce réseau par programmation linéaire avec une politique de service a priorité fixe ou arbitraire, puis nous avons comparé les valeurs obtenues. Quelque soit la politique de service appliquée le délai calcul´e est le même. Il est évident que l’on ne peut obtenir une valeur plus élevée avec une politique de priorité fixe qu’avec une politique aveugle. En effet, l’ensemble
de contraintes de nos programmes inclus toute les contraintes de la politique arbitraire. Ainsi, les trajectoires possibles dans notre cas le sont également pour la politique arbitraire. Comme le délai maximal est égale au pire délai calcul´e sur l’ensemble des trajectoires possibles, le délai que nous obtenons ne peut qu’etre plus faible.
Nous voulons maintenant comparer notre délai avec celui obtenu par la méthode SFA.
Calcul du délai par la méthode SFA Nous devons donc commencer par le calcul de service résiduel total du réseau.

Conclusion

L’enjeu de ce stage était de déterminer des bornes de performances déterministes telles que le délai ou la charge d’un réseau dans le cas de politique de service a priorités fixes. Nous avons découvert des méthodes basées sur l’application directe du Network Calculus effectuant deja ce genre de calculs (tel que SFA).
Nous avons tente une autre approche pour fournir des résultats plus fins. Pour cela, nous nous sommes intéressés a la programmation linéaire. Alors, nous avons forge un ensemble de contraintes linéaires qui permettaient de d´écrire le comportement d’un tel réseau (en créant un programme de génération automatique de contraintes). Ainsi, nous avons mis les contraintes nécessaires au bon fonctionnement du réseau (contraintes du Network calculus) que l’on retrouvait déjà dans la programmation linéaire pour une politique arbitraire. Puis nous avons ajout´e les contraintes définissant les priorités. Nous avons trouve des résultats toujours inférieurs a la politique arbitraire. Mais, plus intéressant encore, nous avons montre que la méthode SFA généré des délais pessimistes.
Helas, dans certains cas, les priorités ne sont pas assurées en-dehors des periodes chargees des serveurs. Dans ce cas, notre délai est égal a celui obtenu par programmation lineaire avec la politique arbitraire, mais est toujours inferieur aux resultats de SFA.
Desormais notre enjeu consiste `a trouver des hypotheses sous lesquelles le delai obtenu est exactement le pire delai du r´eseau. De plus, nous souhaitons ´etablir dans quel cas les priorites ne sont pas respectees, pour tenter d’y remedier.

Table des matières
1 Introduction a la théorie du Network Calculus
2 Le Network Calculs 
2.1 Outils mathématiques : convolution et déconvolution
2.2 Courbes de contrôle des flux et des serveurs
2.2.1 Courbe d’arrivée
2.2.2 Courbe de service
2.3 Bornes caractéristiques
2.4 Premiers résultats sur les caractéristiques des réseaux
3 Méthodes de calcul du délai maximal d’un réseau 
3.1 Réseaux a flux multiplexes et regroupes
3.2 Algorithme de programmation linéaire (LP)
3.3 Priorités fixes
3.4 Nœuds a capacités variables
4 Etude des réseaux quelconques 
5 Etude du délai maximal pour des serveurs en tandem : politique de service a priorité fixe 
5.1 Topologie des réseaux étudies
5.2 Méthodologie
5.3 Généralistes
5.4 Programmes linéaires
5.4.1 Contraintes Lineaires
5.4.2 Application des nœuds a capacités variables
5.4.3 Reconstruction des trajectoires
5.4.4 Contraintes linéaires
6 Comparaison des méthodes de calcul de délais 
6.1 ´Etude d’un premier type de réseau
6.1.1 Méthode de composition des courbes de services résiduelles
6.1.2 Méthode SFA
6.1.3 Comparaison des résultats
6.2 ´Etude d’une seconde topologie de réseau
6.2.1 Méthode SFA
6.2.2 Comparaison des résultats
6.3 Limite du calcul de délai pour les politiques a priorité fixe a l’aide des contraintes linéaires
7 Annexe A : Preuve du lemme

Télécharger le rapport complet