GESTION DES RÉSEAUX DÉDIÉS DE SERVICE 

GESTION DES RÉSEAUX DÉDIÉS DE SERVICE 

Réseau dédié P2P

Les premiers réseaux dédiés commerciaux sont apparus dans l’Internet comme réseaux P2P au début des années 2000, dont BitTorrent (BitTorrent Inc., 2001), Napster (Napster Web Team, 2003) et Kazaa (Kazaax) servant le partage et la distribution de contenu musical et multimédia, et Skype (Khamsi, 2004), (Evers, 2003) servant la téléphonie sur Internet. Dès ce moment, une définition du réseau P2P a été donnée dans (Schollmeier, 2002) distinguant son architecture de celle des réseaux clients/serveurs traditionnels. Un bon article de vue d’ensemble sur les réseaux P2P est (Eng Keong et al., 2005), avec une mise à jour fournie par (Hyojin et al., 2008). Ces réseaux servent des usagers individuels et les applications les plus communes incluent le partage de données, la distribution de contenu divers et la transmission multipoints. De nombreuses fonctions sont offertes, par exemple la recherche efficace de peers et de contenu, la duplication d’objets pour des transferts plus rapides, la multidiffusion (multicasting) efficace (Cui, Li et Nahrstedt, 2004), ainsi que la sécurité du réseau. Des réalisations de diverses qualités pour ces réseaux, comme la robustesse (Zhao et al., 2004) et l’extensibilité (Gao et Steenkiste, 2004), ont été proposées.
Ces réseaux peuvent être classifiés selon leur architecture :
• centralisée, comme Napster. Dans cette architecture, la table d’index des objets du contenu est centralisée dans un serveur auquel sont dirigées toutes les requêtes. Ces réseaux sont en général limités par la capacité du serveur.
• distribuée non structurée, comme BitTorrent, Kazaa et Gnutella (Ripeanu, 2002). La table d’index est distribuée aux nœuds du réseau, ce qui facilite sa croissance. Le réseau ne présente pas de structure topologique particulière et les nœuds sont organisés dans un graphe aléatoire. La localisation d’un objet du contenu se fait bond par bond, avec un nombre de bonds indéterminé.
• distribuée structurée, comme Tapestry (Zhao et al., 2004), Chord (Stoica et al., 2003), CAN (Ratnasamy et al., 2001) et Butterfly (Datar, 2002). Ici, la table d’index est distribuée, avec des clés assignant chaque objet à un nœud désigné. Le plus souvent, l’indexation des objets est réalisée utilisant une table de hachage distribuée (Distributed Haching Table). Cette technique permet de borner par la suite le nombre de bonds requis dans la localisation des objets.
Alternativement, les réseaux peuvent aussi se distinguer par leur appartenance à une génération donnée:
• Première génération : réseaux de base comme Napster et Gnutella. Ces réseaux présentent une performance et une capacité d’expansion réduites.
• Deuxième génération : un grand nombre de réseaux P2P appartiennent à cette génération. On en retrouve structurés en maille (Tapestry), en anneau (Chord et Viceroy (Malkhi, Naor et Ratajczak, 2002)), en Tore (CAN) ou en arbre K-aire (Fry et West, 2004). Des algorithmes plus efficaces de placement et localisation de contenu sont réalisés dans cette génération.
• Troisième génération : comme Butterfly et Low-Diameter (Pandurangan, Raghavan et Upfal, 2003). Cette génération est plus axée sur la robustesse du réseau, par exemple par la duplication d’objets et la recherche de chemins alternatifs de localisation.

Réseau SON

Contrastant avec les réseaux P2P qui servent chacun une application spécifique pour des usagers individuels, le réseau SON est un réseau dédié générique permettant le service concurrent de différentes applications. La propriété recherchée par le SON est la capacité d’offrir la QoS de bout en bout aux connexions de ses usagers. Ainsi, il peut bien supporter les services en temps réel tels que VoIP (Amir et al., 2005), streaming multimédia ou jeux  interactifs. Aussi, il convient bien aux besoins en qualité de télécommunications d’entreprises. L’intérêt accru du milieu de la recherche pour le SON a suscité la publication d’un numéro spécial (Li et al., 2004) de IEEE Journal on Selected Areas in Communications sur le sujet. Un SON est constitué en plaçant des nœuds overlay (ON) dans l’Internet et en les reliant avec des liens overlay (OL) établis utilisant la connectivité de l’Internet.
Diverses techniques ont été proposées pour supporter la QoS de bout en bout sur Internet. Nous distinguons pour le SON deux modèles d’utilisation du transport internet pour obtenir cette QoS :
• Modèle 1 : le SON achète la capacité d’accès à l’Internet pour les connexions de ses usagers. Le transport des données-usager est effectué par l’Internet best effort. Pour acheminer les données dans ce modèle, le SON doit trouver dans l’Internet le meilleur chemin pouvant supporter la QoS. Par exemple, le protocole de routage QRON utilisant le concept de l’overlay broker pour trouver des chemins supportant la QoS dans un réseau dédié a été proposé dans (Li et Mohapatra, 2004), et un algorithme de sélection de chemin considérant les délais sur les liens a été présenté dans (Fry et West, 2004). Un autre exemple d’amélioration de la QoS est donné par (Andersen, Snoeren et Balakrishnan, 2003), où les auteurs comparent le routage par sélection du meilleur chemin à celui comportant un dédoublement de transmission sur deux chemins différents.
Comme il ne peut contrôler le trafic total dans le chemin utilisé, le SON doit continuellement en surveiller l’état et si une congestion survient, réadapter rapidement le chemin pour préserver la QoS. Le mécanisme de reroutage rapide présenté dans (Amir et al., 2005) pourrait par exemple être utilisé à cette fin. Ce modèle est moins onéreux car il n’y a pas de coût pour le transport. Cependant, bien que la QoS puisse être améliorée de façon significative, la disponibilité d’un chemin avec QoS ne peut être garantie en tout temps.
• Modèle 2 : afin d’assurer la capacité de ses liens pour le trafic de ses connexions, le SON achète des ISP, par le biais des SLA, de la bande passante avec QoS dans les AS  concernés (Duan, Zhang et Hou, 2003). Ainsi, le SON peut fournir une couverture globale avec garantie de QoS en utilisant la bande passante achetée d’une multitude d’AS. Le réseau de Virtela a été construit de façon similaire à ce modèle (Allen, 2002).
La quantité de bande passante achetée peut être statique comme dans un dimensionnement traditionnel. Cependant, avec la possibilité envisagée de changements aux termes des SLA, la quantité peut aussi être dynamique (Duan, Zhang et Hou, 2003) pour s’adapter à la demande variable de trafic. Ce modèle, couplé à un contrôle d’admission de connexion, permet une garantie de QoS en tout temps, cependant à un coût supérieur au Modèle 1. On pourrait aussi utiliser un modèle hybride plus économique, où le Modèle 1 serait utilisé quand la QoS est possible avec Internet best effort, mais qui serait remplacé par le Modèle 2 quand un chemin avec QoS n’est plus disponible. Dans cette thèse, nous nous concentrons sur ce modèle du SON établi par SLA avec QoS.

Gestion du SON pour la maximisation du bénéfice d’exploitation

En plus de la QoS fournie aux connexions des usagers, l’autre objectif majeur de l’opérateur est la maximisation du bénéfice de son réseau. Ceci peut être obtenu par un dimensionnement optimal du réseau en fonction de la demande de trafic, couplé à un routage optimal des connexions. Pour garantir la QoS, la bande passante effective requise pour les connexions admises est réservée tout au long des chemins des connexions. Dans le cas où la capacité résiduelle courante est insuffisante, la connexion est refusée, produisant un taux de blocage qui définit le GoS. Pour garder la satisfaction des clients, la maximisation de bénéfice doit s’effectuer tout en respectant les contraintes de GoS.
Les dimensionnements de réseaux sont fondés traditionnellement soit sur la demande maximale de trafic ou sur la demande moyenne. Comme la demande subit des variations journalières importantes reliées au schéma d’activités des usagers (Thompson, Miller et Wilder, 1997), (Roberts, 2004), un dimensionnement basé sur la demande maximale respectera la GoS, mais la capacité du réseau est gaspillée en périodes de faible demande. Un dimensionnement basé sur la demande moyenne produira une utilisation plus rationnelle de la capacité, mais le réseau subira en périodes de forte demande des congestions entrainant la détérioration de la GoS.

Maximisation de bénéfice du réseau

La politique de CAC et routage, désignée par MDPD, est fondée sur la théorie de Décision de Markov qui, pour la simplification de l’approche, a été décomposée aux liens du réseau. Dans cette approche, un shadow price dépendant de l’état du lien et représentant le coût dynamique d’admission d’une connexion est calculé pour chaque lien du réseau. La politique utilise alors ces shadow price dans sa décision d’admission et de routage des connexions. Notre proposition de maximisation de bénéfice se sert de cette approche de CAC et routage MDPD comme fondation, sur laquelle nous ajoutons les considérations de coût réel des SLA et l’adaptation  de capacité. N

Adaptation de capacité supportée par mesures de trafic

Quelques approches d’adaptation de capacité supportées par mesures de trafic, pour différents types de réseaux, ont été proposées dans la littérature. Une proposée des réseaux Ad-Hoc ajuste la capacité du réseau à la charge de trafic (Seok et al., 2003), où la charge sur chaque nœud est constituée par le total de la bande passante requise par les applications des sessions passant par ce nœud. Une autre pour des réseaux CDMA adapte dynamiquement la capacité de garde des cellules pour satisfaire la contrainte d’abandon de connexion durant le transfert intercellulaire (Wang, Ramjee et Viswanathan, 2005). Les taux d’abandon sont mesurés et leurs déviations du taux cible sont utilisées pour adapter la capacité de garde.
Dans cette approche, la vitesse d’adaptation est contrôlée par un facteur appliqué à la déviation mentionnée. Dans (Recker, Ludiger et Geisselhardt, 2003), les variations de trafic dans les chemins et leurs effets sur le délai des paquets sont échantillonnés et lissés exponentiellement dans une fenêtre mobile de taille variable. Une technique de logique fuzzy est ensuite appliquée sur ces variations pour en déduire l’allocation minimale de ressources respectant les contraintes de QoS. La taille de la fenêtre est ajustée périodiquement, aussi par logique fuzzy, dans le but de capturer les variations importantes de trafic.

Estimation de demande de trafic

Plusieurs techniques d’estimation de demande de trafic ont été proposées dans la littérature. Une parmi les précurseurs a été proposée pour le réseau de téléphone public (Tu, 1994), où l’estimé des demandes de trafic point à point est obtenu par la résolution d’un ensemble d’équations linéaires de mesures de charges et de taux de blocage dans les liens du réseau.
Avec la possibilité plus récente d’optimisation de réseau par allocation dynamique de capacité, plusieurs propositions d’estimation de trafic en temps réel ont été avancées. Une méthode simple de mesure et d’estimation supportant l’allocation dans le SON est présentée dans (Duan, Zhang et Hou, 2003). Une méthode de dimensionnement utilisant un filtre ARIMA est proposée dans (Krithikaivasan, Deka et Medhi, 2004), dans (Anjali et al., 2004).
Les auteurs présentent un algorithme approximatif de filtrage fondé sur le modèle du processus stochastique de naissance et de mort, et dans (Dasgupta, de Oliveira et Vasseur, 2008) une allocation en ligne de tunnels MPLS supportée par l’estimation par moyenne pondérée de la tendance de trafic est proposée.

Table des matières

INTRODUCTION
0.1 Problématique de recherche
0.2 Contributions de recherche
0.2.1 Adaptation de capacité fondée sur le processus de décision de Markov
0.2.2 Intégration de la politique de routage et de l’adaptation de capacité
0.2.3 Réalisation distribuée de l’algorithme d’adaptation
0.2.4 Maintien de GoS par adaptation de paramètre de récompense
0.2.5 Estimation de la tendance de demande de trafic
0.2.6 Estimation de demande de trafic par filtre de Kalman
0.2.7 Amélioration du respect de la GoS fondée sur l’erreur d’estimation
0.3 Liste des publications produites
0.3.1 Journaux
0.3.2 Conférences
0.4 Méthodologie de recherche
0.5 Plan de la thèse
CHAPITRE 1 GESTION DES RÉSEAUX DÉDIÉS DE SERVICE 
1.1 Introduction
1.2 Les réseaux dédiés
1.2.1 Réseau dédié P2P
1.2.2 Réseau SON
1.3 Gestion du SON pour la maximisation du bénéfice d’exploitation
1.4 Travaux connexes
1.4.1 Maximisation de bénéfice du réseau
1.4.2 Adaptation de capacité supportée par mesures de trafic
1.4.3 Estimation de demande de trafic
1.5 Résumé
CHAPITRE 2 MAXIMISATION DU BÉNÉFICE DU SON PAR ADAPTATION DE CAPACITÉ 
2.1 Introduction
2.2 Approche de CAC et routage pour la maximisation de récompense
2.2.1 Solution optimale de réseau
2.2.2 Décomposition du problème aux liens du réseau
2.2.2.1 Simplifications du modèle
2.2.2.2 Shadow price moyen
2.3 Cadre économique pour la maximisation de bénéfice du SON
2.3.1 Adaptation de la politique de CAC et de routage
2.3.2 Adaptation de capacité
2.3.3 Adaptation de paramètre de récompense
2.4 Modèles d’adaptation de capacité
2.4.1 Modèle d’adaptation de capacité MDP
2.4.2 Modèle d’adaptation de capacité MDPD
2.4.3 Modèle d’adaptation de paramètre de récompense
2.5 Analyse comparative des modèles d’adaptation
2.5.1 Adaptation de capacités de lien
2.5.2 Adaptation de paramètres de récompense
2.5.3 Conclusion de l’analyse
2.6 Analyse de performance du modèle d’adaptation MDPD
2.6.1 Estimation du trafic admis de lien .
2.6.2 Métriques pour la performance de l’adaptation de capacité
2.6.2.1 Métriques de convergence
2.6.2.2 Métriques de stabilité
2.6.3 Évaluation de performance
2.6.3.1 Performance de l’adaptation de capacité
2.6.3.2 Performance de l’adaptation de paramètres de récompense
2.7 Résumé
CHAPITRE 3 ESTIMATION DU TRAFIC EN TEMPS RÉEL POUR LA GESTION DES RESSOURCES 
3.1 Introduction
3.2 Méthodes connues d’estimation de la demande de trafic
3.2.1 Estimation par lissage exponentiel
3.2.1.1 SES-f : α k fixe
3.2.1.2 SES-a : α k adaptatif selon AEES
3.2.1.3 DES-a1 : α k adaptatif selon AEES, k γ fixe
3.2.1.4 SES-a2 : α k , k γ selon AEES-C
3.2.2 Utilisation du filtre de Kalman
3.3 Estimation de tendance pour lissage exponentiel adaptatif
3.3.1 Estimation de tendance par fonction d’autocorrélation
3.3.2 Estimation de tendance par fonction de distribution cumulée
3.3.3 Adaptation du coefficient de lissage fondée sur l’estimation de tendance
3.4 Approche fondée sur le filtre de Kalman
3.4.1 Modèle proposé de filtre de Kalman
3.4.1.1 Algorithme du filtre
3.4.1.2 Détermination des paramètres d’entrée du filtre
3.4.2 Application au degré de service du réseau
3.5 Analyse de performance
3.5.1 Métriques de performance
3.5.1.1 Stabilité d’estimation en trafic stationnaire
3.5.1.2 Réponse de l’estimation en trafic tendanciel
3.5.2 Résultats de l’analyse
3.6 Résumé
CHAPITRE 4 ÉVALUATION DE PERFORMANCE 
4.1 Introduction
4.2 Demande de trafic
4.3 Résultats de l’évaluation
4.3.1 Analyse de degré de service
4.3.2 Bénéfice du réseau
4.4 Résumé
CONCLUSION 
A. Sommaire et avantages de notre approche de gestion de ressources
B. Travaux subséquents et direction future de recherche
LISTE DE RÉFÉRENCES BIBLIOGRAPHIQUES

Télécharger le rapport complet