Plan de connaissance pour les réseaux sémantiques 

 Modélisation du comportement d’un lien réseau par un modèle de type file d’attente Objectif

En se basant sur les résultats obtenus précédemment, nous choisissons de modéliser le comportement d’un lien réseau par un modèle de type file d’attente. Ce modèle de type file d’attente est approximativement capable de décrire le comportement d’un routeur ou d’un lien réseau. Il s’agit de proposer une abstraction mathématique du système réel permettant de concentrer, dans un modèle, les comportements et les paramètres reproduisant aux mieux le fonctionnement étudié du lien réseau. Notons que dans la suite de ce chapitre nous considérons le débit en sortie de lien à la place du taux d’utilisation.

ORIGINE DE LA SOLUTION KBAC CHAPTER 

KBAC Taux d’utilisation CoV de l’utilisation Temps de service CoV sur les temps d’interarrivées CoV sur les débits des arrivées 0 0 0 0 0 1 0.5 1 3.5 0.5 Temps Figure 3.4 – Evolution du comportement de quelques facteurs de la trace en fonction du temps. 

ORIGINE DE LA SOLUTION KBAC

Principe. Un modèle de file d’attente monoserveur (cf. figure 3.5) est une entité constituée d’une file d’attente (buffer) et d’un serveur unique. Les clients arrivent de l’extérieur, patientent éventuellement dans le buffer, re¸coivent un service, puis quittent la file. Départ des clients Serveur Arrivée des clients File d’attente Figure 3.5 – File d’attente monoserveur. Afin de spécifier complètement une file monoserveur, il faut caractériser le processus d’arrivée des clients, la distribution du temps de service, la taille du buffer, ainsi que la structure de la discipline de service de la file d’attente (dans notre étude, la discipline de service de la file est FIFO). Modèles de type file d’attente. Dans la suite, nous présentons successivement les files M/M/1, M/M/1/K, M/GI/1, M/GI/1/K, GI/M/1, GI/M/1/K, GI/GI/1 et GI/GI/1/K. [1] M/M/1 : Une file de type M/M/1 représente un système de file d’attente avec un processus d’arrivée des clients dans la file qui suit un processus de Poisson et un temps de service d’un client modélisé par une variable aléatoire ayant une distribution exponentielle. [2] M/M/1/K : Une file de type M/M/1/K est un système de file d’attente M/M/1 avec une taille finie K pour le buffer du lien. [3] M/GI/1 : Une file M/GI/1 représente un système de file d’attente o`u le processus d’interarrivée des clients est modélisé par une variable aléatoire ayant une distribution exponentielle et le temps de service d’un client est distribué selon une variable aléatoire générale. [4] M/GI/1/K : Une file de type M/GI/1/K est un système de file d’attente M/GI/1 avec une taille finie K pour le buffer du lien. [4] GI/M/1 : Une file GI/M/1 peut être vue comme un ≪ duale ≫ d’une file M/GI/1, puisque les temps d’interarrivée et de service sont respectivement exponentiels et généraux pour une file M/GI/1, généraux et exponentiels pour une file GI/M/1.  KBAC [4] GI/M/1/K : Une file de type GI/M/1/K est un système de file d’attente GI/M/1 avec une taille finie K pour le buffer du lien. [5] GI/GI/1 : Dans une file GI/GI/1 le processus d’interarrivée ainsi que le temps de service sont distribués selon une variable aléatoire générale. [6] GI/GI/1/K : Une file de type GI/GI/1/K est un système de file d’attente GI/GI/1 avec une taille finie K pour le buffer du lien. Il existe aussi d’autres modèles de files d’attente (par exemple les files M/M/C, les files M/GI/C, etc.), ainsi que des extensions possibles des modèles des files, comme par exemple les techniques d’identification à des lois de type ≪ phase ≫, que nous ne présentons pas dans cette thèse car ils modélisent des comportements inutiles dans notre cas d’étude. Analyse des modèles de type file d’attente. Nous analysons les différents modèles de type file d’attente décrits précédemment afin de choisir un modèle fiable, simple et capable de modéliser adéquatement le comportement d’un lien réseau. Paramètre de performances Débit de sortie Coude M/M/1 M/G/1 Figure 3.6 – Comportement qualitatif des modèles de type file d’attente. [1] M/M/1 et M/M/1/K : Ces systèmes de file d’attente sont les plus simples à résoudre. En revanche, ils n’arrivent pas à bien modéliser le comportement du trafic réseau transitant sur un lien. La figure 3.6 montre que ces files d’attente ne sont pas flexibles et n’arrivent pas à couvrir la variabilité des paramètres de performances (cf. figure 3.3). 

 NOUVELLE SOLUTION KBAC [2] M/GI/1 et M/GI/1/K 

Ces modèles de files peuvent reproduire le comportement d’un lien réseau et sont simples à résoudre (comparé aux systèmes de file d’attente de type GI/GI/1 et GI/GI/1/K). Ces modèles peuvent englober un large spectre de performances en faisant varier le coefficient de variation sur la distribution du temps d’interarrivées entre les paquets successifs. [3] GI/M/1 et GI/M/1/K : Ces modèles sont capables reproduire le comportement d’un lien réseau et peuvent également englober un large spectre de performances. Cependant, ils sont plus compliqués à résoudre. [4] GI/GI/1 et GI/GI/1/K : Ces systèmes de type file d’attente sont certainement capables de modéliser adéquatement le comportement du trafic transitant sur un lien réseau. En revanche, ces systèmes sont, la plupart du temps, très difficiles à résoudre (voir parfois impossible à résoudre). Choix de modèles de type file d’attente. Pour conclure, nous avons décidé de considérer uniquement les modèles de type d’attente monoserveur car dans un routeur réseau un seul paquet peut être transmis à la fois. Dans la suite de notre travail, notre choix s’est porté sur les modèles de file d’attente moneserveur de type M/GI/1 et M/GI/1/K. 3.2 Nouvelle solution KBAC Principe. Notre solution de contrôle d’admission repose (i) sur l’élaboration en continu d’un plan de connaissance (ii) et sur la modélisation du comportement d’un lien réseau par une file monoserveur. KBAC vs MBAC. Contrairement aux solutions MBAC (cf. section 2.2.2 du chapitre 2), notre solution comprend une étape supplémentaire, le plan de connaissance, qui s’interpose entre l’algorithme de mesure et l’algorithme de décision. Nous détaillons maintenant chacune de ces étapes. 

Algorithme de mesure

Fenêtre de temps de mesure. L’algorithme de mesure surveille continuellement l’activité du lien de communication de fa¸con à collecter des données de mesure. Ces données sont mesurées sur une courte fenêtre de temps de mesure WT . Ces mesures à court terme prennent en compte le comportement “instantané” du trafic transitant.  Points de mesure. Pour chaque fenêtre de temps de longueur WT , nous mesurons le débit moyen en sortie du lien du trafic transitant, noté par X (paquets/ms), avec un autre paramètre de performance QoS, noté par P. Ce paramètre de QoS peut être un délai d’attente moyen des paquets dans le buffer du lien ou un taux de perte des paquets. Les valeurs mesurées de X et P sont rassemblées en une paire de mesures. Nous nommons ces couples de mesures, (X, P), points de mesure. 

Construction du plan de connaissance

Principe Un plan de connaissance (cf. section 1.2 du chapitre 1) définit un ensemble de mesures, diverses dans l’espace du réseau et dans le temps, dont les valeurs reflètent de fa¸con collective le comportement d’un réseau. Sa constitution doit permettre une meilleure gestion du réseau. Ici, nous en proposons une définition pensée pour le contexte du contrôle d’admission sur un lien de communication. Points de fonctionnement. Notre plan de connaissance comprend un ensemble de k points, que l’on désigne comme points de fonctionnement. Chacun de ces points correspond à un couple de valeurs associant (i) un débit moyen en sortie du lien et (ii) un délai d’attente moyen des paquets dans le buffer du lien (respectivement, un taux de perte). Ces points sont des agrégats (clusters) dont les coordonnées seront régulièrement mises à jour par la collecte de nouveaux points de mesure. Pour cela, nous mesurons, sur toutes les fenêtres de temps de longueur WT , quels ont été le débit et le délai d’attente (respectivement le taux de perte) observés sur le lien. Puis, toutes les Tkp secondes (c’est-à-dire une fois collectées 100 nouvelles mesures pour WT = 200 ms et Tkp = 20 secondes), nous calculons les nouvelles coordonnées des points de fonctionnement. Dans nos expériences, nous limitons le nombre de points de fonctionnement à 10 (k = 10). Clusterisation. Pour mener l’étape de clusterisation, nous nous appuyons sur l’algorithme k-means. Au final, ce plan de connaissance permet de produire un ensemble de k points de fonctionnement représentant une courbe de performances du lien. La figure 3.7 illustre ce principe pour un exemple avec un lien de 10 Mb/s soumis a un trafic issu d’une trace réelle. Cette figure repr´ ` esente les nouveaux points de mesures collectés et les nouvelles cordonnées des points de fonctionnement calculés. Elle montre aussi la courbe de performances du lien. Premièrement, nous remarquons que l’allure de cette courbe est conforme à nos attentes et aux résultats issus de la théorie des files d’attente. Ces observations sont vérifiées par le comportement qualitatif suivant : à mesure que le débit moyen en sortie progresse, le délai d’attente (respectivement le taux de perte) s’accroˆıt. Notons que selon la nature du lien et du trafic soumis en entrée du lien, les caractères quantitatifs de ces courbes de performances diffèrent (cf. section 3.1.2).  Débit de sortie (packet/ms) Temps d’attente (ms) Points de mesure récents Points de fonctionnement Modèle de type file d’attente Figure 3.7 – Exemple d’un plan de connaissance comprenant les mesures, les points de fonctionnement et le modèle type file d’attente associé. Modélisation du plan de connaissance. Nous nous appuyons sur une méthode rapide et automatique pour associer un modèle de type file d’attente au comportement du lien réseau tel qu’il est décrit par les points de fonctionnement [Begin et al., 2010]. Cette méthode de modélisation, nommée HLM (High Level Modeling) permet la modélisation rapide et automatique de systèmes opérationnels de type ≪ boˆıte noire ≫ pour lesquels on dispose uniquement de mesures. Le principe de la méthode HLM consiste à rechercher parmi un ensemble présupposé de modèles génériques, si une fois correctement calibré, l’un de ces modèles permet de reproduire le comportement d’entrée/sortie du système considéré tel qu’il est décrit par les mesures. Enfin, cette méthode délivre une file monoserveur qui reproduit au plus près les performances observées du lien (cf. figure 3.7). Selon la section 3.1.3, nous limitons la recherche du modèle aux files de type M/GI/1 (respectivement M/GI/1/K) lorsqu’on s’intéresse au délai d’attente (respectivement au taux de perte). La figure 3.7 montre un exemple de la modélisation du plan de connaissance par une file monoserveur. Nous observons qu’une file de type M/GI/1, avec un taux de service de 5,01 paquets/ms et un coefficient de variation de 2,02, reproduit adéquatement le comportement du lien réseau tel qu’il est décrit par les points de fonctionnement. 3.2.3 Algorithme de décision Prédiction de la performance. La décision de notre contrôle d’admission d’accepter ou de rejeter un nouveau flux se base sur une prédiction de la performance. Cette prédiction repose sur l’exploitation du modèle de type file d’attente trouvé. Nous réalisons une projection de charge (capacity planning) sur ce nouveau modèle afin d’évaluer quelles seraient les performances du lien réseau si la charge soumise en entrée du lien venait à augmenter. La résolution du modèle pour ce niveau de charge nous permet d’estimer le risque que, une fois le nouveau flux accepté, la nouvelle valeur du délai d’attente (respectivement du taux de perte) dépasse le seuil exigé par la QoS des flux.  KBAC Lorsqu’un flux cherche à entrer sur un lien de communication en demandant un débit crête r, la prédiction de la performance, notée P est calculé de la manière suivante : P = fP (X + r) (3.1) o`u fp définit l’évolution de P en fonction du débit du lien, et X reflète le débit ajusté du trafic transitant. Notons que nous utilisons une valeur ajustée du débit afin d’éviter le comportement volatile de la valeur de X, mesurée sur une petite fenêtre de temps WT . Nous expliquerons plus tard la fa¸con dont la valeur de X est calculée. Test d’admission. Un nouveau flux est admis si : P + ασp < P∗ (3.2) o`u P ∗ est une constante représentant la contrainte de la QoS (cette constante peut être un temps si on considère le délai d’attente comme critère de QoS ou un taux dans le cas du taux de perte), σp represente l’écart-type de P, fourni par le modèle type file d’attente associé à la courbe de performances, et α est une constante spécifiant la probabilité de la violation de la performance. Dans la forme actuelle de notre solution KBAC, nous considérons que σp = P. A savoir, le calcul de l’écart-type de P, σp, est une tˆache complexe à réaliser. Ce calcul peut être parfois possible à obtenir mais, la plupart du temps, il représente une tˆache impossible [Gross and Harris, 1985]. Dans ces conditions, afin de simplifier le calcul de σp, nous considérons que la moyenne est égale à l’écart type, ce qui est vrai, si on suppose une distribution exponentielle de moyenne P. Nous détaillons à présent les paramètres énumérés ci-dessus : 

Choix de la valeur de α Contrôle d’admission probabiliste

Notre solution KBAC garantit le critère de QoS de manière probabiliste. Plus précisément, la valeur de α est définie de sorte que les flux transitant sur le lien de communication ne dépassent pas la cible de QoS, avec une probabilité Q. Nous définissons α en utilisant l’inégalité de Tchebychev [All, ]. Dans notre étude, nous définissons la valeur de α a 1 ` .7, de sorte que Q = 0.75.

Calcul du débit ajusté X

Nous rappelons que X reflète le débit ajusté du trafic transitant utilisé dans la prédiction de la performance, P, en utilisant l’équation 3.1. Le débit ajusté X est déterminé sur les M dernières fenêtres de mesure de longueur WT comme suit : X = 1 M  M m=1 Xm +  M m=1 m M ×  Fm f=1 r f m (3.3) o`u Xm correspond au débit moyen en sortie de lien obtenu sur la me fenêtre de mesure, Fm représente le nombre des flux acceptés sur la me fenêtre de mesure, et r f m correspond au débit crête estimé du f e flux sur la me fenêtre de mesure.   X WT X σt trac transitant nouveaux ux accéptés X1 Xm XM Figure 3.8 – Calcul du débit ajusté X. La figure 3.8 illustre le calcul du débit ajusté en sortie de lien. Ce type de calcul permet d’avoir une valeur plus lisse du débit en sortie que le débit d’un seul point de mesure X. En particulier cette méthode utilise une pondération des débits crêtes des nouveaux flux acceptés auquel s’ajoute la valeur moyenne du débit de sortie. La valeur de X doit être régulièrement mise à jour. Dans nos expériences, le calcul du débit de sortie ajusté est répété sur chaque fenêtre de mesure WT . C’est cette valeur qui est utilisée dans notre algorithme de décision. Il faut aussi noter que la valeur de X peut aussi être mise à jour à l’intérieur d’une fenêtre de mesure. A chaque fois qu’un nouveau flux est accepté, la valeur de X est alors modifiée et prend comme valeur le débit de sortie ajusté courant auquel s’ajoute le débit crête du flux entrant, r, pour être X + r. De cette manière, cette mise à jour permet de tenir compte des événements de type “Flash Crowd” (i.e., plusieurs nouveaux flux qui arrivent dans une fenêtre de mesure WT ).