View
108
Download
1
Category
Preview:
Citation preview
31 Mars 2005 - © RUN, ULG 1
Architecture d'une boîte à outils d'algorithmes d'ingénierie de trafic et
application au réseau GÉANT
Université de Liège - BelgiqueRéseaux informatiques (RUN)
Présentation : Fabian Skivée
Auteurs : Fabian Skivée - Simon Balon - Olivier DelcourtJean Lepropre - Guy Leduc
http://totem.run.montefiore.ulg.ac.be
31 Mars 2005 - © RUN, ULG 2
Sommaire
Introduction et objectifs Architecture Algorithmes d'ingénierie de traffic Format de données Etude de cas : le réseau GEANT Nouvelles fonctionnalités Conclusion
31 Mars 2005 - © RUN, ULG 3
Introduction et objectifs
Actuellement, la plupart des fournisseurs internet surdimensionnent leur réseau.
Vu l'augmentation de la demande et pour fournir des garanties de services, cette approche est de moins en moins viable.
L'ingénierie de trafic a pour objectif d'optimiser la répartition du trafic pour maximiser l'utilisation des ressources d'un réseau.
31 Mars 2005 - © RUN, ULG 4
Introduction et objectifs
Beaucoup de recherches dans le domaine mais peu sont utilisées vu leur complexité d'implémentation et d'utilisation
Notre boîte à outils a deux objectifs : permettre à un chercheur de promouvoir ses
nouvelles méthodes de TE et de les comparer avec d'autres
permettre à un opérateur de tester ces méthodes sur son réseau.
31 Mars 2005 - © RUN, ULG 5
Sommaire
Introduction et objectifs Architecture Algorithmes d'ingénierie de traffic Format de données Etude de cas : le réseau GEANT Nouvelles fonctionnalités Conclusion
31 Mars 2005 - © RUN, ULG 6
Architecture
L'architecture doit respecter plusieurs exigences :minimiser l'effort d'intégration d'un nouvel
algorithmeêtre interopérable avec d'autres outilsproposer différents modes d'execution
on-line dans un réseau réel off-line pour une simulation
multi langages
31 Mars 2005 - © RUN, ULG 7
Boîte à outils
TOTEM
Outil de configuration
de réseaux
Outil de gestion
de réseaux
Intégration dans un réseau réel
31 Mars 2005 - © RUN, ULG 8
Environnement de simulation
Boîte à outils
TOTEM
Scenario.xml
MatriceTrafic.xml
Topologie.xml
31 Mars 2005 - © RUN, ULG 9
Toolbox Architecture
CoreCLI
Scénariode simulation
Module de matrice de traffic
Répertoire d'algorithmes
Outilde gestionde réseaux
Module de topologie
GUI
Interface utilisateur
simulation BGP
BGP
DAMOTE calcul de LSP primairescalcul de LSP de backup
MPLS
Optimisation de métriques
IGP
IP
CSPF
TopGen génération de
topologies et de trafic
Générique
31 Mars 2005 - © RUN, ULG 10
Sommaire
Introduction et objectifs Architecture Algorithmes d'ingénierie de traffic Format de données Etude de cas : le réseau GEANT Nouvelles fonctionnalités Conclusion
31 Mars 2005 - © RUN, ULG 11
Algorithmes d'ingénierie de traffic
Algorithmes classiquesSPFCSPF (avec différentes métriques : inverse de
la capacité, nombre de sauts, inverse de la bande passante résiduelle)
Optimisation des métriques IGP (B. Fortz) Simulation BGP (C-BGP - B. Quoitin)
31 Mars 2005 - © RUN, ULG 13
TopGen
Générateur de topologies et de trafic La génération de topologie se fait en
utilisant Brite La génération de trafic selon deux modèles
modèle de gravitéaléatoire respectant différentes loi de
distribution (Poisson, uniforme, etc)
31 Mars 2005 - © RUN, ULG 14
Sommaire
Introduction et objectifs Architecture Algorithmes d'ingénierie de traffic Format de données Etude de cas : le réseau GEANT Nouvelles fonctionnalités Conclusion
31 Mars 2005 - © RUN, ULG 15
Format de topologie
Topologie: Noeud: id, IP, localisation, interfaces Lien: id, source, destination, type, bande passante, délai, SRLG
MPLS: LSP: id, chemin, bande passante, DiffServ, niveau de
préemption, backup (bypass, détour) IGP :
Lien: métrique, métrique TE, bande passante, bande passante réservable par niveau de priorité
BGP : Routeur: neighbour, in-filter, out-filter, localpref
31 Mars 2005 - © RUN, ULG 16
Format de matrice de trafic
Représente la matrice de trafic d'un domaine Cette matrice représente le trafic échangé entre
chaque paire origine/destination Ces matrices peuvent être utilisées pour générer
des scénarios de simulation.
<src id="source_node1"> <dst id="destination_node1">
3.57 </dst> ....</src>....
31 Mars 2005 - © RUN, ULG 17
Sommaire
Introduction et objectifs Architecture Algorithmes d'ingénierie de traffic Format de données Etude de cas : le réseau GEANT Nouvelles fonctionnalités Conclusion
31 Mars 2005 - © RUN, ULG 18
Etude de cas : le réseau GEANT
Réseau européen de la recherche
30 pays et 26 réseaux nationaux
23 nœuds 38 liens
31 Mars 2005 - © RUN, ULG 19
La matrice de trafic de GÉANT
Réseau GÉANT
= Nœud d'accès
= Lien d'accès
Modèle de gravité
31 Mars 2005 - © RUN, ULG 20
La matrice de trafic de GÉANT
Réseau GÉANT
= Nœud d'accès
103
6
2
5
4
6+2+4+5+3 = 20
10 * (6/20)
10 * (2/20)
10 * (4/20)
10 * (5/20)
10 * (3/20)
TM-max : matrice de trafic au la somme du trafic entrant est maximum - jour de semaine en octobre 2004
31 Mars 2005 - © RUN, ULG 21
Analyse du trafic
Objectif : comparer différents algorithmes de routage MCF (Multi Commodity flow) dont l'objectif est de
minimiser la charge du lien le plus chargé. CSPF avec les métriques de GEANT CSPF avec une métrique de 1 pour chaque lien CSPF avec l'inverse de la bande passante pour
métrique CSPF avec l'inverse de la bande passante résiduelle DAMOTE
31 Mars 2005 - © RUN, ULG 22
Analyse du trafic
Algorithmes Max Per 10 Moyenne Ecart type
MCF 29,9 % 26,9% 10,4% 9,6%
CSPF 50,5% 18,1% 7,4% 8,4%
CSPFHopCount 83,5% 19,8% 10,2% 15%
CSPFInvCap 43,5% 16,5% 7,1% 7,2%
CSPFInvFreeBW 30,3% 13,7% 7,1% 6,2%
DAMOTE 30,3% 14,9% 8,9% 5,3%
Comparaison de différents algorithmes de routage sur TM-max
31 Mars 2005 - © RUN, ULG 23
Analyse du coût des backups
Etude de la protection des flux en cas de panne d'un nœud ou d'un lienHypothèse : une seule panne à la foisPartage bande passante entre primaire et
backupDeux stratégies de protection :
protection de bout en bout protection locale
31 Mars 2005 - © RUN, ULG 24
Analyse du trafic
Algorithmes Protection locale
Protection de bout en bout
Surcoût en bande passante
86,8 % 71,7%
Utilisation maximale 64,8% 85,7%
Utilisation moyenne 13,2% 10,7%
Nombre de LSP primaires
506 506
Nombre de LSP de backup
1638 506
Comparaison de différents algorithmes de routage sur TM-max
31 Mars 2005 - © RUN, ULG 25
Analyse de la panne la plus grave
Objectif : étudier le changement de charge suite à une panne de lien et determiner la panne de lien la plus grave.
Comparaison des différents algorithmes de routage
31 Mars 2005 - © RUN, ULG 26
Analyse de la panne la plus grave
Algorithmes Max Per 10 Moyenne Ecart typeMCF 32,9 % 32,4 % 11,6 % 10,5 %
(sans panne) 29,9 % 26,9% 10,4% 9,6%
CSPF 55,4 % 18,2 % 7,7 % 8,9 %
(sans panne) 50,5 % 18,1 % 7,4 % 8,4 %
CSPFInvFreeBW 37 % 24,4 % 9,3 % 8,4 %
(sans panne) 30,3 % 13,7 % 7,1 % 6,2 %
DAMOTE 36,2 % 24,1 % 11,3 % 7,6 %
(sans panne) 30,3% 14,9% 8,9% 5,3%
Comparaison de différents algorithmes de routage en cas de panne
31 Mars 2005 - © RUN, ULG 27
Sommaire
Introduction et objectifs Architecture Algorithmes d'ingénierie de traffic Format de données Etude de cas : le réseau GEANT Nouvelles fonctionnalités Conclusion
31 Mars 2005 - © RUN, ULG 28
Nouvelles fonctionnalités
Version 1.0 Scénarios de simulation très flexibles qui permettent
une exécution automatique de la boîte à outils. Ex : panne de lien, optimisation de métrique IGP, calcul de LSP,
etc.
Optimisation de métrique IGP Simulation BGP grâce à C-BGP Interface graphique
Future Version 1.1 Matrice Netflow SPF multipath
31 Mars 2005 - © RUN, ULG 29
Sommaire
Introduction et objectifs Architecture Algorithmes d'ingénierie de traffic Format de données Etude de cas : le réseau GEANT Nouvelles fonctionnalités Conclusion
31 Mars 2005 - © RUN, ULG 30
Conclusion
Cette boîte à outils fournit une architecture ouverte et interopérable unique pour comparer et valoriser des nouveaux algorithmes.
Prochaines étapes : Nouvelles méthodes d'inférence de matrice de
trafic Intégration de nouveaux algorithmesAmélioration des rapports d'analyse
31 Mars 2005 - © RUN, ULG 31
Références
Financé par la Région Wallonne dans le cadre du projet TOTEM
Collaboration dans le WG4 du réseau d'excellence européen E-Next
Contact : fabian.skivee@ulg.ac.be
Boîte à outils : http://totem.run.montefiore.ulg.ac.be
Project URL : http://totem.info.ucl.ac.be
Recommended