View
105
Download
2
Category
Preview:
Citation preview
Sélection des routes
Equipe de Recherche Réseau et Protocoles- LSIIT – ULPhttp://www-r2.u-strasbg.fr
Premières simulations
Pascal Merindol – merindol@lsiit.u-strasbg.fr
Les protocoles de routage actuellement déployés sur Internet ne profitent pas pleinement des ressources que lui offre le réseau sous jacent, notamment en terme de bande passante. En effet, les techniques actuelles réalisent un routage uni-chemin d’une source S vers une destination D, monopolisant ainsi les mêmes ressources de S vers D. Certains mécanismes d’ingénierie de trafic existants permettent de réaliser du routage multi-chemins grâce à la labellisation de bout en bout de routes pré calculées sur S vers D, alors que d’autres méthodes proposent de construire de manière distribuée un ensemble de multi-chemins dépourvus de boucle de S vers D.
Le multiroutage distribué par interface entrante (MIE)
Évaluation de l’existant
But : Réaliser un multiroutage de proche en proche extensible et présentant les mêmes avantages qu’un routage à la source sans faire exploser la complexité des tables de commutations.
Méthode: Ne considérer que l’interface d’entrée des flux en transit pour différencier leurs origines afin d’éviter le bouclage des données.
Multiroutage, les autres problématiques
La
Nature et échange des informations de ressources
A la différence de la construction des chemins qui est proactive, comment définir un mécanisme réactif pour interpréter les variations de charge sur le réseau ?
Distribution de la charge
Comment traiter efficacement les informations de variation de charge reçues pour définir une répartition sans oscillations perturbatrices?
Méthode de distribution
Quelles techniques utiliser pour répartir à proprement dit le trafic selon sa nature (TCP/UDP) une fois les proportions de distributions attribuées ?
Le multiroutage à la source sur routes labellisées
Le multiroutage distribué avec évitement des boucles
Références : [CRA] S. Nelakuditi et Z.-L. Zhang, On Selection of Paths for Multipath Routing, Proceedings of IWQoS, 2001.
[MPLS] E. Rosen, A. Viswanathan, et R. Callon, "Multiprotocol Label Switching (MPLS) Architecture", IETF RFC 3031, Janvier 2001.
[OSPF, ECMP] J. Moy, "OSPF version 2." Internet Engineering Task Force (IETF), RFC 2178, Avril 1998.
[MPDA] S. Vutukury, “Multipath routing mechanisms for traffic engineering and quality of service in the Internet”, Ph.D thesis, University of California, Santa Cruz, Mars 2001.
Calcul de multi-chemins disjoints du premier arc par destination vers chacun des noeuds du graphe
Sur chaque nœud s, le réseau est modélisé par un graphe G(S,A) où s réalise la suite d’opérations suivante : (En entrée, deux paramètres, k et p, respectivement restrictif topologique et contrôleur du temps de convergence protocolaire)
Vérification de la faisabilité (absence de boucle) des chemins proposés par ses voisins directs pour chaque destination
Validation des chemins du voisinage avec positionnement des lignes de routage à un saut
Validation de ses chemins en fonction des résultats obtenus chez les voisins
Phase de découverte à la source
Phase de validation distribuée
Solutions de routage proposées par
coût
coût
coût
Interface entrante
Phase de validation à la source
Prochain saut
Coût du meilleur chemin par
Comparatif topologique des protocoles distribués Chemins et bande passante selon la profondeur p d’analyse
0
500
1000
1500
2000
2500
Nombre de chemins Bande passante
moy enne (Mo/s)
OSPF
ECMP
MPDA
MIE (k=2, p=0)
MIE (k=2, p=3) 0
500
1000
1500
2000
2500
3000
0 1 2 3 4
Nombrechemins
Bandepassantemoyenne(Mo/s)
Pour être sélectionné, un chemin doit garantir à une profondeur donnée p un coût inférieur au meilleur calculé à la source
Coût des chemins calculés compris entre le meilleur coût et k *le meilleur coût selon une métrique d’état des liens comme [OSPF]
Optimisation bande passante
Réduction des délais
Répartition de la charge rigide
Coût de labellisation proportionnel au nombre de paires (S,D)
Distribution de charge réactive
Extensibilité
Peu de multi-chemins générés
Faible gain de bande passante
Combinaison d’un algorithme de recherche dans les graphes ([CRA], par exemple) à une technique de construction de route par label ([MPLS]), sans router explicitement les données.
Ce type de méthode doit prévenir la formation de boucles par :
-des chemins de même coût ([ECMP])
-la garantie que le coût du meilleur chemin des voisins empruntés par ses multichemins soit strictement inférieur au sien ([MPDA])
Label Switch Path 1 ([MPLS])
LSP 2
LSP 3
LSP 4
Source
Destination
Nœud distributeur
Arcs possibles pour la répartition de charge sur nœud distributeur
(k=2)
Modélisation graphique d’une ligne de routage
Destination
sur renater 3
Nœud international
Noeud national
Deux classes d’ingénierie de trafic s’opposent par leur forme :
La première construit les chemins à la source sur des critères d’optimisation, la seconde, distribuée, doit garantir l’absence de boucles de routage sur le réseau.
k=2
Contrôle de ressources par multiroutageContrôle de ressources par multiroutage
Recommended