Admin CliCours
Télécharger le fichier original (Mémoire de fin d’études)
Modéliser un réseau : système entrée/sortie
Un réseau N est généralement modélisé par un graphe dans lequel les serveurs sont représentés par les sommets du graphe, et les flux de données doivent suivre les arêtes du graphe (un flux traverse généralement plusieurs sommets et arêtes). La modélisation d’un réseau de communication en NC consiste donc généralement en :
la partition du réseau en sous-systèmes (souvent appelée noeuds) qui peuvent corres-pondre à plusieurs échelles (du petit élément matériel comme un processeur, jusqu’à un grand sous-réseau);
la description des flux de données, où chaque flux suit un chemin prédéterminé à travers une suite de noeuds et/ou chaque flux est contraint par une courbe d’arrivée juste avant d’entrer dans le réseau ;
la description du comportement de chaque noeud : d’une part des courbes de service qui donnent des bornes sur les performances du noeud ; d’autre part la description de la politique de service en cas de multiplexage (lorsque plusieurs flux se partagent le service offert par un noeud).
Remarque 2.6. Chaque système ou sous-système est défini comme un système entrée/sortie où le nombre d’entrées est le même que le nombre de sorties.
Définition 2.7 (Trajectoire acceptable — plusieurs flux). Une trajectoire (acceptable) pour un système traversé par p flux est l’ensemble ((Ak)1 k p; (Bk)1 k p) où les Ak et les Bk appartiennent à F%, et correspondent respectivement aux fonctions cumulées pour le flux k à l’entrée et à la sortie du système.
Ainsi, dans le cas général, un système S de p flux sera défini par l’ensemble de toutes ses trajectoires acceptables, et on aura S F% F%. Voir un système comme une boîte noire est habituel en théorie du filtrage classique et permet de manipuler des systèmes d’une échelle quelconque.
Cadre mathématique
Cette définition permet d’étudier des dynamiques déterministes mais aussi des dynamiques non déterministes.
La définition suivante, limitée a priori à un seul flux, permettra aussi de travailler sur des systèmes traversés par plusieurs flux agrégés.
Définition 2.8 (Système entrée/sortie — un flux). Un système entrée/sortie est un sous-ensemble S de f(Fin; Fout) 2 F% F% j Fin Foutg.
Un système entrée/sortie modélise un flux traversant un système où Fin (resp. Fout) est la fonction cumulée à l’entrée (resp. la sortie) du système et Fin Fout indique que le système fait uniquement de la transmission de données. Le système peut aller d’un simple serveur à un grand réseau avec du trafic transverse. Une trajectoire du système S est un élément (Fin; Fout) de S.
Enveloppes : courbe d’arrivée et courbe de service
Les contraintes sur les flux dans le réseau sont modélisées par des enveloppes :
les courbes d’arrivée, qui permettent de modeler le trafic en entrée du système étudié ; les courbes de service, qui décrivent le comportement du système ou du serveur.
Courbes d’arrivée : une seule définition
Étant donné un flux traversant un réseau, soit A 2 F% sa fonction cumulée en un certain point du réseau, c’est-à-dire A(t) représente le nombre de bits qui ont traversé ce point jusqu’au temps t, avec A(0) = 0. On dit qu’une fonction 2 F est une courbe d’arrivée pour A si : 8 s; t 2 R+;0 s t,
A(t) A(s) (t s).
Définition 2.9 (Courbe de service universelle [Chang 2000]). De plus, on dit qu’une courbe de service est universelle si elle est une courbe de service pour tout flux entrant. Autrement dit si elle est indépendant de .
Remarquons que toutes les courbes de services définies ci-dessus sont des courbes de service minimal. Rien n’empêche les serveurs de se comporter comme un « fil », et de transmettre toutes les données qui arrivent instantanément.
Définition 2.10 (Serveur exact (simple)). On parlera de service exact, ou plutôt de serveur exact lorsque le serveur fournit exactement son service simple minimum : B = A
On n’a pas abordé ici la question des courbes de service maximum ([Le Boudec 2001], ou [Wandeler 2006a] dans le cadre du Real-Time Calculus), car elles ne sont pas étudiées dans la suite de ce manuscrit. Néanmoins nous sommes conscient qu’elles peuvent être d’un grand intérêt, tant théorique que pratique.
Remarque 2.7. Il est tout à fait possible d’utiliser des courbes de service qui ne sont pas dans F%, par exemple des fonctions qui prennent des valeurs négatives, qui sont décroissantes ou qui ont des discontinuités. Néanmoins il est pratiquement nécessaire d’imposer (0) 0, sans quoi on aurait Ssimple( ) = Swstrict( ) = Sstrict( ) = Svcn( ) = ;.
Remarquons que dans les définitions précédentes, c’est le service qui est simple ou strict, et pas la courbe . Le type de service décrit comment se comporte le serveur, et la courbe permet de décrire les contraintes pour ce comportement. La courbe n’est pas tantôt stricte, tantôt simple : elle ne change pas. Par abus de langage, il nous arrivera de dire « est une courbe stricte pour le serveur » pour dire « le serveur fournit un service strict de paramètre la courbe ».
Exemples de fonctions fréquemment utilisées comme courbes de service
Attention, les fonctions ci-dessous ne permettent pas à elles seules de définir le compor-tement du serveur. C’est avant tout le type de service qui le définit (voir figure 2.6).
Fonctions classiques souvent utilisées comme courbes de service :
délai pur T 2 R+ [ f+1g : T(t) = 0 si t T, = +1 sinon ;
débit constant r 2 R+ [ f+1g : r (t) = rt (si r = +1, on définit r = 0) ;
latence-débit : R;T(t) = R(t T)+ où R; T 2 R+ et a+ représente max(a; 0).
Mesures de performance
L’objectif du Network Calculus est d’obtenir des bornes pire-cas sur les performances du réseau étudié.
Une des premières questions qui peut se poser est la question de la stabilité du réseau, à savoir si tous les délais subis par les données dans le réseau sont finis, et si les files d’attente sont suffisamment dimensionnées.
Définitions importantes en Network Calculus
Performances caractéristiques et bornes : délai et charge
Dans un système entrée/sortie, des bornes sur la charge pire-cas et sur le délai pire-cas peuvent être déterminées simplement à partir des courbes d’arrivée et de service.
Étant donné un flux traversant un réseau modélisé par un système entrée/sortie S, notons (Fin; Fout) sa trajectoire 3 pour S. La charge pour ce flux au temps t est donnée par b(t) = Fin(t) Fout(t);
Pour le système S, la charge pire-cas (resp. délai) est le supremum sur toutes les trajec-toires.
Le théorème suivant montre comment l’on peut obtenir des bornes sur les performances du réseau, et comment les contraintes de trafic peuvent être propagées dans le réseau.
Théorème 2.2 ([Chang 2000, Le Boudec 2001]). Soit S un système entrée/sortie fournissant une courbe de service simple et soit (Fin; Fout) une trajectoire telle que est une courbe d’arrivée pour Fin. Alors on a :
1. Bmax supf (t) (t) j t 0g = v( ; ) (distance verticale) ;
2. Dmax inffd 0 j 8t 0; (t) (t + d)g = h( ; ) (distance horizontale) ;
3. est une courbe d’arrivée pour Fout.
La figure 2.7 illustre les bornes Bmax et Dmax. La figure 2.8 illustre le dernier point, à savoir la propagation de la courbe d’arrivée en sortie du serveur.
Bit/flux observé
On souhaite généralement donner des bornes pire-cas globales sur le réseaux. Cepen-dant, il arrive fréquemment de s’intéresser à un flux en particulier on parlera alors du flux observé), voire à un bit en particulier (on parlera du bit observé).
Bornes « tight »
Comme vu précédemment, le Network Calculus permet d’obtenir des bornes supérieures sur certaines caractéristiques du réseau, comme les délais subis par les données ou la charge au niveau de chaque serveur. Il est évidemment intéressant d’obtenir les bornes les plus précises possibles : le terme « tight » est traditionnellement utilisé. Nous avons choisi de garder ce terme anglais dans ce tapuscrit. En effet, il revêt plusieurs sens, et plusieurs traductions sont donc possibles. Une borne tight peut ainsi être dite : serrée : c’est la traduction littérale, mais elle n’est pas assez précise ; juste, exacte : cela sous-entendrait que c’est la meilleure borne possible, et qu’il n’y en a pas d’autre. Mais les bornes calculées dépendent aussi du modèle utilisé pour les obtenir ;
atteignable : ce n’est pas toujours vrai, ou alors difficilement démontrable dans certains cas. La plupart des résultats obtenus ne nous permettent pas d’affirmer qu’il existe une trajectoire qui réalise la borne pire-cas ;
non améliorable : c’est finalement la traduction qui serait la plus précise…
Dans la littérature, le terme « tight » est utilisé selon les contextes dans différents sens. Souvent dans le sens « non améliorable » pour un modèle, ou dans le sens « atteignable » ; et il est généralement précisé lorsque les bornes sont effectivement atteignables.
On pourra se référer à la section 11.3 pour comprendre la distinction entre bornes atteintes et atteignables.
Caractéristiques d’un réseau
Topologies
La topologie est la définition de l’architecture du réseau, c’est-à-dire l’ensemble des restrictions qui s’appliquent soit au graphe sous-jacent, soit à la disposition des flux dans le réseau. Étudier un réseau dans le cas général est souvent très compliqué. La plupart des résultats de Network Calculus se limitent donc à des topologies plus simples. On pourra se référer à [Lenzini 2007, Lenzini 2008].
Réseaux « acycliques » / sans dépendances cycliques : (ou feed-forward) On peut nu-méroter les serveurs dans N de telle sorte que lorsqu’il existe un flux qui va du noeud i au noeud j, alors on a i < j ;
Réseau en tandem : (ou serveurs mis en tandem) Réseau N dont le graphe orienté induit est un chemin orienté sans raccourcis (donc sur une ligne). On observe généralement un flux principal qui peut être rejoint puis quitté (une seule fois) par des flux transverses.
Réseaux sink-tree : On observe un flux principal qui traverse des serveurs numérotés 1; 2; ::; n. Des flux transverses peuvent rejoindre le flux principal, mais restent agrégés avec lui dans tous les serveurs jusqu’au serveur n ;
Nested flow : (flux imbriqués) On observe encore un flux principal sur une ligne, qui peut être rejoint puis quitté par des flux transverses sur un sous-chemin, mais si deux flux transverses interfèrent avec le flux principal respectivement sur les noeuds e1; : : : ; s1 et e2; : : : ; s2, on doit avoir : e1 e2 < s2 s1 ou e2 e1 < s1 s2 ;
Réseau en diamant : Un exemple très simple de réseau sans dépendance cyclique, à quatre serveurs et deux flux (figure 9.2).
Cas général : étudier un réseau qui peut comporter des dépendances cycliques est à l’heure actuelle un problème ouvert, sauf dans certains cas très précis. Il peut donc être intéressant d’essayer de se ramener au cas acyclique, quitte à « supprimer » certains liens dans le réseau. C’est le but par exemple des études sur la turn prohibi-tion [Fidler 2003].
Politiques de service
La politique de service, la plupart du temps au niveau d’un serveur, détermine l’ordre dans lequel les paquets — ou les bits d’information — présents dans la file d’attente du serveur vont être servis.
On parle de multiplexage lorsque plusieurs flux entrent dans un seul serveur et qu’il sont agrégés : ils sont « mélangés » et traités comme un seul flux, mais il faut tout de même déterminer un ordre pour les différents paquets des flux de départ.
Les différentes « politiques de service » ci-dessous n’ont pas toutes le même statut : certaines déterminent quel est le prochain paquet à traiter, d’autres donnent simplement des contraintes sur ce que doit être l’ordre de traitement des paquets. La dernière — multiplexage aveugle ou blind multiplexing — ne donne pas d’information sur l’ordre de service des paquets, mais sur la façon dont on pourra étudier la politique de service elle-même.
FIFO : (First In First Out) Premier arrivé, premier servi. Tous les paquets sont servis dans leur ordre de leur arrivée au niveau du serveur.
FIFO par flux : À l’intérieur d’un même flux, les paquets sont servis dans l’ordre d’arrivée. Mais si plusieurs flux sont traités par le serveur au même moment, il n’y a aucune garantie sur le flux qui sera traité en premier. Le serveur peut utiliser une autre politique de service que FIFO pour ordonner des paquets de flux différents.
Fixed Priority : (ou static priority) Les flux ont chacun une priorité, et c’est le flux le plus prioritaire qui est servi en premier. Dans le cas où l’on considère que l’arrivée des paquets n’est pas instantanée, ce type d’ordonnancement peut être préemptif (pour une étude dans le cadre du NC en non-préemptif, voir [Sofack 2011]).
Fair Queuing : Un serveur de débit maximum R qui doit servir n flux va fournir à chaque flux un débit R=n, par exemple en les servant alternativement.
Weighted Fair Queuing : Comme en fair qeueing, mais les différents flux se voient assi-gner des poids wi , et le service qu’ils reçoivent les uns les autres est proportionnel à ce poids.
FIFO* C’est une contrainte globale sur l’ensemble d’un système : les bits doivent sortir du sytème dans l’ordre de leur arrivée dans le système. À l’intérieur du système, les serveurs ne servent pas obligatoirement en FIFO.
TDMA (Time Division Multiple Access) Les flux, ou les paquets, ne peuvent être servis que dans des intervalles de temps déterminés à l’avance. Le service du serveur est donc « découpé » entre les différents flux. Il existe d’autres technique de partage du medium, comme par exemple par fréquences distinctes (FDMA) ou Code Division Multiple Access.
Multiplexage aveugle (multiplexage arbitraire, blind multiplexing) On suppose qu’on n’a pas d’information sur la politique de service. Il peut y en avoir une définie de manière très précise, mais on ne la connaît pas. Il est souvent fait l’hypothèse que le service est FIFO par flux.
Dans la suite de ce manuscrit, nous ferons souvent l’hypothèse de blind multiplexing avec FIFO par flux.
Remarque 2.8. Comme souligné dans [Rizzo 2005], l’hypothèse FIFO par flux est souvent faite, même si elle est parfois implicite.
Résultats classiques
Ci-dessous, deux théorèmes classiques du Network Calculus sur la mise en tandem (ou concaténation) de deux serveurs, et sur le service résiduel (appelé « Blind multiplexing » dans [Le Boudec 2001, théorème 6.2.1]), c’est-à-dire le service disponible pour l’un des flux lorsque deux flux agrégés traversent un serveur (on ne fait pas d’hypothèse sur la politique de service). Dans les deux cas, il est intéressant d’étudier ce que ces théorèmes peuvent nous apporter sur le calcul des bornes de performance.
Théorème 2.3 (Tandem [Le Boudec 2001, Chang 2000]). Soit un flux traversant deux ser-veurs en tandem de courbes de service respectives 1 et 2. Alors la concaténation des deux serveurs offre un service simple minimal de courbe 1 2 à ce flux.
Définition 2.11 (Pay Bursts Only Once). (PBOO, [Le Boudec 2001, p28]) Lorsqu’on étudie le délai pire-cas pour un flux traversant un système formé par la concaténation de deux serveurs, on peu utiliser au moins deux méthodes différentes :
1. utiliser directement la courbe de service du système (théorème 2.3) ;
2. calculer itérativement les bornes au niveau de chaque serveur (théorème 2.2).
Avec la deuxième méthode, les rafales du flux apparaissent plusieurs fois dans l’expression du délai alors qu’elles n’apparaissent qu’une fois dans l’expression de la première méthode. Ce qui conduit potentiellement à des résultats plus pessimistes. C’est le phénomène PBOO.
Théorème 2.4 (Service résiduel [Le Boudec 2001, Chang 2000]). Soit un noeud offrant une courbe de service strict , et deux flux (agrégés) entrant dans ce serveur, avec des courbes d’arrivée respectives 1 et 2. Alors une courbe de service simple pour le flux 1 est 1 = ( 2)+.
Définition 2.12. Pay Multiplexing Only Once ((PMOO), [Fidler 2003, Schmitt 2006a]) Par analogie avec PBOO, [Fidler 2003] étudie des systèmes où plusieurs fux agrégés traversent un serveur, et où il y a du trafic transverse. Lorsqu’on étudie un flux en particulier, on peut calculer une courbe de service résiduel pour ce flux, puis utiliser cette courbe de service pour calculer les bornes sur les performances. Procéder ainsi permet de ne « payer » qu’une seule fois pour les rafales du trafic transverse.
Des algorithmes sont donnés dans [Schmitt 2006a] pour les deux types de méthodes vues à la définition 2.11, et on trouvera un exemple à la section 9.4 :
total flow analysis (TFA) qui consiste à calculer — séparément — une borne supérieure sur le délai pour chaque serveur traversé par le flux observé puis faire la somme ;
separated flow analysis (SFA) qui consiste à calculer une courbe de service résiduelle pour chaque serveur sur le chemin du flux observé, puis calculer la convolution de ces courbes de service pour obtenir une courbe de service résiduelle pour le chemin complet, et finalement calculer une borne de bout en bout sur le délai en utilisant le théorème 2.2.
Avantages et limites du NC
Le Network Calculus, fondé sur l’utilisation d’enveloppes pour modéliser les contraintes du réseau et l’utilisation du dioïde (min; +) pour combiner ces contraintes, a intrinsèque-ment certains avantages et inconvénients par rapport à d’autres méthodes d’étude de performances d’un réseau. Les mêmes avantages et inconvénients se retrouveront donc aussi dans des modèles comme le Real-Time Calculus par exemple. Ces caractéristiques sont :
un formalisme mathématique précis (l’utilisation de (min; +)) ; ce qui permet a priori, par rapport à des modèles basés sur l’interprétation au cas par cas des mouvements de données dans le réseau, d’éviter les erreurs d’interprétation lors de l’application à des exemples pratiques.
la possibilité d’utiliser des types d’enveloppes plus ou moins précises pour les contraintes. Par exemple, pour accélérer les calculs, on peut décider d’utiliser des courbes d’arrivée / service de type concave / convexe : certes les bornes seront moins précises, mais on est assuré d’obtenir des bornes qui sont toujours valides.
la possibilité, en théorie, d’étudier des réseaux à n’importe quelle échelle. En effet, les notions de trajectoire entrée / sortie et de système ne font pas d’hypothèse sur l’objet étudié, et la combinaison de plusieurs sous-systèmes pour former un systèmes est aussi tout à fait possible. Dans la pratique, il est cependant difficile d’obtenir des bornes précises.
le pessimisme des bornes, qu’il est difficile de contrôler. C’est justement l’objet des recherches sur le Network Calculus…
On pourra trouver des comparaisons plus précises sur les avantages et inconvénients d’autres modèles dans, par exemple, [Boyer 2010b].
Table des matières
I Introduction
1 Network Calculus : rapide panorama
2 Définitions importantes en Network Calculus
2.1 Cadre mathématique
2.1.1 Fonctions manipulées en Network Calculus
2.1.2 Dioïde min-plus
2.1.3 Opérateurs
2.1.4 Modéliser un réseau : système entrée/sortie
2.1.5 Enveloppes : courbe d’arrivée et courbe de service
2.1.6 Mesures de performance
2.2 Caractéristiques d’un réseau
2.2.1 Topologies
2.2.2 Politiques de service
2.3 Résultats classiques
2.4 Avantages et limites du NC
3 État de l’art 39
3.1 Applications du Network Calculus
3.2 Domaines et modèles proches du NC
3.3 Logiciels NC
3.4 Contributions
Bibliographie personnelle
II Modèles et classes de fonctions
4 Quelles classes de fonctions utiliser en pratique
4.1 Introduction
4.1.1 Classes de fonctions
4.1.2 Formules algébriques
4.2 Deux exemples utiles : fonction indicatrice et distance
4.3 Problèmes de clôture
4.3.1 Fonctions affines par morceaux
4.3.2 Généralisation
4.3.3 Résultats de stabilité : résumé en image
4.4 Reconstruire une fonction à l’aide des opérateurs du Network Calculus
4.4.1 Partie transitoire d’une fonction continue
4.4.2 Partie pseudo-périodique d’une fonction continue
4.4.3 Conclusion et cas avec discontinuités
4.5 Fonctions suradditives : non-équivalence de deux propriétés
5 Comparaison avec RTC
5.1 Présentation de RTC
5.2 Théorème d’équivalence
5.3 Enveloppes en RTC
6 Comparaison de différents types de service
6.1 Introduction
6.2 Étude de courbes de service
6.2.1 Monotonie
6.2.2 Familles de courbes de service
6.2.3 Hiérarchie
6.3 Conclusion
7 Notion de service intermédiaire et service résiduel
7.1 Concaténation de serveurs : convolution
7.1.1 Résultats de stabilité/instabilité
7.1.2 Existence d’une notion intermédiaire pour les courbes de service ?
7.2 Courbes de service résiduel
7.2.1 Résultats de stabilité pour le modèle fluide
7.2.2 Qu’en est-il de la taille des paquets ?
7.3 « Composition » de services résiduels
7.3.1 Serveurs en tandem
7.3.2 Un flux transverse
7.3.3 Plusieurs flux imbriqués
III Utiliser le Network Calculus pour obtenir des bornes
8 Convolution multidimensionnelle
8.1 Quantifier le phénomène « Pay Multiplexing Only Once »
8.2 Analyse de performance avec la convolution multidimensionnelle
8.2.1 Convolution multidimensionnelle
8.2.2 Bornes sur les délais et les charges locales
8.3 Cas particulier : la convolution (min,+) classique
9 Étude des réseaux sans dépendances cycliques : optimisation linéaire
9.1 Modélisation du réseau
9.2 Analyse des réseaux sans dépendances cycliques
9.2.1 Les instances LP
9.2.2 Objectifs
9.2.3 Des trajectoires aux solutions LP
9.2.4 Des solutions LP aux trajectoires
9.3 Scénario en tandem : algorithme polynomial
9.3.1 Algorithme pour le scénario en tandem
9.3.2 Des délais aux courbes de service de bout en bout
9.3.3 Travaux connexes
9.4 Résultats
9.4.1 Scénario en tandem
9.4.2 Scénario sans dépendances cycliques
IV Remarques sur les notations et les preuves
10 Outils de preuve en Network Calculus
10.1 Première preuve : différenciation locale
10.2 Deuxième preuve : algorithmique
10.3 Troisième preuve : transformée de Legendre-Fenchel
11 Notations
11.1 Dioïde min-plus
11.2 Calcul réseau
11.2.1 Courbes d’arrivée et de service
11.2.2 Délais et occupation mémoire
11.2.3 Courbes de service strict, courbes de service maximal
11.2.4 Séquence de serveurs
11.2.5 Serveur partagé
11.3 Précisions sur les bornes calculées
12 Perspectives
Bibliographie
