Optimisation dynamique de réseaux IP/MPLS

Optimisation dynamique du placement des LSP avec l’algorithme Best Response

 Les résultats obtenus pour le placement initial de l’ensemble des LSP sont très intéressants, et nous font penser que l’algorithme proposé doit pouvoir être utilisé à des fins de reconfiguration dynamique des LSP. La vitesse avec laquelle l’algorithme proposé fournit une solution le rend particulièrement attractif dans le cadre d’une utilisation en ligne, où le temps d’optimisation doit être limité le plus possible. Une telle reconfiguration dynamique permettrait d’adapter automatiquement les chemins des LSP aux variations de trafic observées sur le réseau. Ici, contrairement au cas de l’optimisation des poids OSPF, l’incertitude de mesure sur les trafics est bien moindre, car les trafics peuvent être mesurés LSP par LSP (en observant leurs interfaces via le protocole SNMP). Nous considérons pour nos simulations que nous disposons toutes les 5 minutes du trafic moyen de chaque LSP sur les 5 dernières minutes. Afin d’illustrer l’utilisation de l’algorithme de meilleure réponse dans un cadre dynamique, nous avons effectué des simulations de variations de trafic sur les 8 topologies testées précédemment (voir Table 5.2). Pour chaque topologie, nous choisissons une matrice de trafic aléatoire pleine à l’instant τ = 0, comportant donc un LSP par couple source/destination. Chaque minute, la matrice de trafic est mise à jour via l’ajout d’un bruit gaussien sur la demande de chaque LSP k : d t k = d t−1 minute k + N (0, σ2 ) k = 1, . . . , K. (5.22) La déviation standard de ce bruit est choisie telle que 99.7% des demandes varient d’au plus ±8.5% par minute (et cette borne est forcée pour les 0.3% restants). En conséquence, chaque demande peut varier d’au plus ±50% sur un intervalle de 5 minutes : 0.5d τ−5min k ≤ d τ k ≤ 1.5d τ−5min k (5.23) Toutes les 5 minutes, nous exploitons les informations de trafic moyennes de la dernière fenêtre temporelle (de 5 minutes) pour optimiser le placement des LSP. Afin de limiter le nombre le nombre de LSP reroutés par l’algorithme de BestResponse, nous introduisons un gain seuil GSeuil conditionnant le choix de chaque joueur : un joueur ne change sa propre stratégie que si cela lui permet de diminuer son propre coût d’au moins GSeuil par rapport à sa précédente stratégie. Pour ces simulations, nous fixons arbitrairement GSeuil à 5% de gain minimum. Nous considérons des simulations de 250 minutes (environ 4 heures), comportant donc 50 déclenchements de l’algorithme d’optimisation dynamique (toutes les 5 minutes). 

Coûts moyens sur la période de simulation 

Les Tables 5.6 et 5.7 résument les coûts moyens obtenus sur l’ensemble des topologies, pour la durée de la simulation, pour les deux types de fonction coût étudiées. Trois configurations y sont représentées pour chaque topologie : — Statique : configuration statique de tous les LSP, basée sur un routage OSPF avec des métriques unitaires sur chaque lien. Les LSP sont alors routés sur les plus courts chemins entre leur source et leur destination. — Optim hors ligne : résultats obtenus avec un placement optimisé hors ligne avec l’algorithme de Best Response, à partir de la matrice de trafic moyenne de l’ensemble de la simulation. Cette configuration est purement hypothétique, car elle suppose que l’on puisse prévoir à l’avance une matrice de trafic moyenne sur la période. — Optim dynamique : obtenus en exécutant l’algorithme Best Response toutes les 5 minutes, en exploitant les informations moyennes de trafic des 5 dernières minutes. À l’instant τ = 0, le placement des LSP correspond à la configuration statique (plus courts chemins). Table 5.6 – Coût moyen sur la période de simulation avec la fonction quadratique sur les différentes topologies. Topologie Statique Optim hors-ligne Optim dynamique ABOVENET 5.7 – Coût moyen sur la période de simulation avec la fonction M/M/1 sur les différentes topologies. On remarque la proximité entre les résultats obtenus avec l’algorithme en ligne et ceux obtenus avec la configuration statique optimisée. Nous insistons sur le fait que cette configuration statique optimisée est purement théorique car elle nécessite la connaissance des trafics futurs pour l’ensemble de la période étudiée, ce qui est impossible dans la réalité. De plus, la durée de la simulation considérée est relativement courte (250 min), ce qui signifie que les demandes en trafic peuvent rester « proches » de leurs valeurs moyenne sur la période. Plus la période de temps considérée pour déterminer cette configuration optimisée s’allongera, plus la probabilité que la matrice de trafic réelle dévie significativement de la matrice de trafic moyenne augmentera, et moins la configuration statique optimisée restera intéressante par rapport à une reconfiguration dynamique. Ces valeurs ne sont que des moyennes sur les durées de simulations, et il est donc intéressant d’observer les variations réelles de la fonction coût au cours d’une simulation. Nous illustrons pour cela l’évolution temporelle des coûts sur deux exemples pour la  fonction coût M/M/1 dans les Figures 5.6 et 5.7. 16 18 20 22 24 26 28 30 32 0 50 100 150 200 250 0 10 20 30 40 50 60 Cout M/M/1 Nombre de LSP modifies Temps (min) Routage Statique Optim hors ligne Routage dynamique BR LSP modifies Figure 5.6 – Optimisation en ligne sur topologie ARPANET avec fonction coût de type M/M/1. L’observation de ces graphiques nous révèle la dynamique suivie par le coût de la configuration dynamique (courbe bleue) et les modifications proposées et appliquées par l’algorithme Best Response (barres grises sur les graphiques). Sur toutes les topologies testées, l’algorithme commence par proposer, dès sa première exécution, un certain nombre de modifications, permettant une certaine réduction du coût (la configuration statique étant uniquement basée sur l’utilisation de plus courts-chemins). L’exécution périodique de l’algorithme lui permet par la suite de suivre l’évolution du trafic, en proposant ponctuellement des modifications permettant d’améliorer la fonction coût. On remarque sur l’exemple de la topologie ARPANET que les augmentations brutales et imprévisibles du coût sur le réseau entraînent des réactions de l’algorithme. On observe également la même tendance sur tous les scénarios : la configuration optimisée hors ligne prodigue une solution meilleure lors des premiers instants, mais la configuration dynamique devient plus intéressante au fil du temps et des évolutions du trafic.Nombre de LSP modifies Temps (min) Routage Statique Optim hors ligne Routage dynamique BR LSP modifies Figure 5.7 – Optimisation en ligne sur topologie METRO avec fonction coût de type M/M/1. 

 Modifications appliquées 

Les nombres de modifications appliquées pour chaque simulation sont exposés dans les Tables 5.8 et 5.9. La première colonne présente le nombre d’instants où une reconfiguration a été proposée et appliqué par l’algorithme dynamique. Nous présentons trois valeurs pour appréhender correctement le nombre de LSP modifiés sur chaque simulation : — Cumul total : la somme totale des LSP modifiées au cours d’une simulation. Autrement dit le nombre total cumulé de LSP dont la route a été touchée au cours d’une simulation de 250 minutes, il est donc possible d’y retrouver plusieurs fois un même LSP. — 1ère reconfiguration : le nombre de LSP distincts qui ont été modifiés lors de la toute première reconfiguration proposée par l’algorithme (la plupart du temps dès la première exécution à t=5 minutes). — Cumul restant : la somme du nombre de LSP modifiés après la 1ère reconfiguration (on peut à nouveau y retrouver plusieurs fois un même LSP).  On remarque que le nombre d’instants de modifications reste modéré, et ce pour les deux fonctions coût : sur l’intégralité des simulations, au maximum 5 reconfigurations distinctes auront été nécessaires pour des simulations de 250 minutes. Le nombre cumulé de LSP re-routés est plus ou moins proportionnel à la taille du scénario considéré. On remarque qu’une portion importante des modifications appliquées le sont dès la première reconfiguration : cela s’explique par le fait que l’on démarre avec une configuration statique de type OSPF qui n’est absolument pas optimisée. La première reconfiguration procède donc à un replacement général et poussé des LSP. Les modifications appliquées après la première reconfiguration (« cumul restant ») sont en nombre bien moins important, ce qui indique que l’algorithme tente de se limiter aux reconfigurations minimales permettant de suivre efficacement les variations de trafic. Malgré tout, certaines valeurs restent parfois élevées (ABOVENET, ARPANET et EON pour la fonction coût quadratique). Cela nous laisse penser qu’un travail supplémentaire pourrait s’avérer nécessaire pour restreindre plus intelligemment le nombre de modifications proposées.