DemoMultipathRouting - RP

DemoMultipathRouting


Sommaire

[modifier]

Routage Multichemins


[modifier]

Contexte

Le routage multichemins est un mécanisme de routage auto-adaptatif permettant d'utiliser plusieurs routes pour relier un même couple de noeuds. Ainsi, si le réseau est suffisament maillé, ce type de routage présente l'avantage d'offrir plus de diversité et de réactivité que le traditionnel routage Shortest Path First (SPF). Chaque noeud dispose d'une table de routage dont une même destination peut être atteinte par différents prochains sauts (Next Hop, NH). De ce fait, il est également nécessaire d'attribuer des proportions de partage à chacun de ces prochains sauts. D'une part, il est nécessaire d'adapter la répartition de charge aux variations du trafic enregistré et d'autre part à la nature du trafic écoulé. En effet, un même flux TCP ne peut être systématiquement redirigé, sous peine de déséquencement dont l'impact peut activer le plan de détection de congestions.

Dans cette démonstration nous allons insister sur deux aspects fondamentaux du multiroutage :

[modifier]

Principes et objectifs

Il existe plusieurs manières de mettre en oeuvre une technique de routage multichemins. La premiè re, une solution centralisé et global que nous n'allons pas dévelloper ici pour des notions évidentes d'extensibilité. Une seconde méthode regroupe les protocoles de réservations (RSVP et RSVP-TE) et de de labellisation (MPLS et CR-LDP) que nous désignerons comme du routage à la source bien que les paquets ne portent pas réellement l'ensemble du chemin mais un label de routage. Ces techniques permettent de router le trafic en fonction d'une Forwarding Equivalent Class (FEC) qu'il leur ai attribué afin de réaliser de la qualité de service (QoS). Nous nous intérresserons plus particulièrement aux méthodes de multiroutage distribués où la décision de routage est prise saut par saut ( DT(p) ).

Le but intrinsèque du multiroutage est l'équilibrage de la charge supporté par le réseau mais des objectifs plus concrets sont notamment :

[modifier]

Multiroutage saut par saut avec DT(p)

Le multiroutage distribué présente l'avantage de pouvoir réagir localement si une solution alternative existe mais se doit d'éviter la création de boucle de routage. Pour cela, nous avons dévellopé un algorithme de découverte de chemins nommé Dijstra Tranverse (DT) et un protocole de validation de route à profondeur p, DT(p). Notre méthode est plus extensible que le multiroutage à la source et profite d'une grande diversité de chemins, qu'aucune technique existante de même type ( Equal Cost Mulipath, ECMP ou Loop Free Invariant, LFI) ne peut égaler. La première partie ( Diversité ) de notre démonstration viendra étayer notre propos et nous analyserons également une méthode de routage acceptant le bouclage sur noeud mais évitant le bouclage sur liens (Source routing via Path Deflection, SPD).

[modifier]

Démonstration


[modifier]

Environnement

Cette démonstration illustre de manière très simple avec le simulateur NS2 et son interface graphique NAM la mise en oeuvre statique et dynamique du multiroutage.

[modifier]

Scénario

Pour cette démonstration, nous étudierons deux cas d'écoles :

[modifier]

Résultats


[modifier]

Diversité

Le graphe ci dessus est une approximation grossière de la topologie du réseau de recherche Renater.
Les coûts affichés sur cette carte ne constituent pas une métrique réaliste mais permettront de mettre en avant les caractéristiques de chaque type de routage évalué (valuation symétrique, les autres coûts sont à 1).
Sur l'exemple étudié dans ces démonstrations, 4 agents source TCP Linux
[7>0: bleu et jaune, 8>4: rouge et rose, 3>6: vert et orange, 2>5: blanc et chocolat]
émettent chacun deux flux en direction d'agents TCP SACK qui se charge de receptionner ce trafic. Les deux séries de flux sont espacées d'une seconde dans les simulations.
Les simulations exposées dans les gifs animés (screencast de NAM) qui suivent représentent chacune un type de (multi)routage au partage statique et orienté flux (fonction de hachage *):

Les coûts des meilleurs chemins sont exprimés ici: 7>0: 3, 8>4: 3, 3>6: 4, 2>5: 7

ECMP (Equal Cost MultiPath, bibtex entry): Seules les routes de même coûts sont exploités.
DT-p : Algorithme Dijkstra Transverse, (bibtex entry) élaguage distribué à profondeur p (**).
DT-LOOPY : Toutes les routes calculées avec DT sont utilisées sans élaguer les boucles.
LFI : Loop Free Invariant (bibtex entry), vision à un saut de profondeur (***).
SPD : Source routing via Path Deflection (bibtex entry), vision à deux sauts avec routage par interface entrante (****).


Fig.3 : Démonstration diversité
Test 1 - SPF : Test 2 - ECMP :
Test 3 - LFI : Test 4 - DT1 :
Test 5 - DT-LOOPY : Test 6 - DT2 :
Test 7 - DT3 : Test 8 - SPD :


DESCRIPTION ET COMMENTAIRES
Les paramètres de simulation sont fixés pour toute les simulations (à savoir: débits, délais, fenêtres d'émission, coûts, algorithme de partage ...) sauf pour DT-LOOPY et LFI. En effet, nous avons choisi de profiter de ces simulations en particulier pour réaliser un partage orienté paquet de type round robin. A noter qu'un flux (ou plutôt le premier paquet le constituant) peut boucler indéfiniment à cause de son hash positionné à la source en ce qui concerne DT-LOOPY. Cette simulation illustre bien l'importance de la notion d'élaguage de boucle pour obtenir un routage cohérent (on peut aussi noter les pertubations liées aux déséquencements des trames TCP). Pour ce qui est de la démonstration LFI, on peut beaucoup mieux apprécier de cette manière ce que cette technique peut apporter en terme de diversité de chemins. Il faut néanmoins relativiser par rapport à un partage par flux avec seulement 8 flux en transit (par flux età hash égal, LFI n'apporterait visiblement aucune différence avec ECMP sur ces exemples). Par ailleurs, nous avons également modifié la bande passante des liens pour visualiser correctement les flux paquet par paquet plutot que par burst (série de paquets consécutifs). La première simulation, représentant SPF, sert de démonstration témoin pour toutes celles qui suivent. On notera que lorsque la destination est directement connecté, le simulateur NS2 ne prend plus en compte correctement le coût des arcs, d'où cet étrange bug qui empêche les flux de 3 vers 6 d'emprunter le meilleur chemin en terme de coût (celui ne passant pas par le lien 9-6). On observe que l'utilisation d'ECMP n'apporte qu'une seule solution aternative pour le couple 7>0 et le couple 8>4. Avec DT-p, on constate que la profondeur p utilisé a une incidence directe sur le nombre de chemins générés. La simulation DT-3 notamment, illustre bien les défauts d'une telle diversité lorsque le partage de charge est statique. Certains flux (le flux orange notamment) empruntent un chemin nettement plus long que le meilleur sans pour autant apporter un bénéfice visible pour harmoniser la charge sur le réseau. Nous avons également émulé la solution proposée par SPD pour illustrer la notion de boucle sur noeud sans obtenir pour autant une boucle sur lien. Sur l'exemple choisi, on remarque que les flux blanc et chocolat bouclent entre les noeuds 1 et 0.
(Le hash sur ces deux flux a été forcé pour truquer le routage afin obtenir ce cas spécifique)

Nous évaluons également des modèles dynamiques et distribués de répartition de charge afin de présenter des solutions réactives. La notion de hash est aussi un enjeu majeur, il peut permettre, s'il est global, de facilement réaliser de la QoS (Quality of Service) pour distribuer les flux sur des routes de qualité variable. Si ce hash est recalculé de manière différente à chaque saut (sur l'entêete IP par exemple), le routage se veut plus équitable. Sur ces exemples, si le hash attribué à un flux par la source correspond à un routage degradé (5), il a alors de forte chance de goûter à la pire alternative à chaque saut.




* - Les proportions attribuées à chaque prochain saut sont statiques et déterminées en fonction des coûts des chemins. Le partage de charge se fait gràce à un hachage, global (chaque noeud ordonne identiquement ses proportions en fonction des coûts) et positionné à la source, pour éviter des déséquencements nuisant à TCP et son algorithme de congestion avoidance.
** - Il s'agit du protocole de routage que nous avons elaboré pour, d'une part, calculer à la source un ensemble de routes dites tranverses en plus des meilleurs routes de coûts egales, et d'autre part veiller, en considérant l'interface d'entrée des flux, à eviter qu'un flux ne puisse boucler en traversant deux fois le même routeur. Cette seconde *etape passe par un protocole distribué à profondeur p pour tester les coûts du voisinage plus ou moins direct. Le fait de considérer l'interface d'entrée des flux permet d'utiliser une relation de décroissance des coûts non stricte.
*** - LFI se contente d'éxecuter simplement l'algorithme de Dijkstra sur chaque noeud, puis un protocole de voisinage vérifie la validite des noeuds adjacents comme prochains sauts gràce a une relation de coût strictement décroissante.
**** - SPD éxecute un algorithme de Dijkstra modifié sur chaque noeud source pour calculer plusieurs chemins vers une méme destination. Cette méthode ne nécessite donc pas d'élaguage distribué mais elle se base néanmoins aussi sur la connaissance des coûts des voisins calculés dans ce cas localement.
Ici, tout le calcul de validation des prochains sauts se fait à la source en prenant compte de l'interface d'entrée du trafic pour finalement obtenir une vision des coûts à deux sauts. Cette méthode autorise le bouclage sur noeud mais pas le bouclage sur lien car elle peut utiliser une relation non obligatoirement décroissante à un saut mais strictement décroissante à deux sauts. (C'est a dire qu'un paquet peut traverser deux fois le même routeur sans emprunter deux fois le même lien).
*5 - Par exemple, si les proportions de partage sont définis de 0 a 100 et que le hash du flux est proche de 100, sur un routeur proposant des chemins de coûts 10, 20 et 30 vers une destination et une métrique donné, il y a de forte chance pour que flux emprunte la troisième solution de coût 30 au premier saut, et ainsi de suite à chaque saut. Avec comme intervalle [0,100], et un partage statique inversement proportionelle au coût, on obtient, à titre d'exemple, les proportions de partage : [0,54,81,100], c'est à dire, 54, 27 et 19 %. En d'autres termes, si le hash est tiré au hasard entre 0 et 100, un flux a 19% de chances d' être routé sur le prochain saut correspondant au chemin de coût 30.
[modifier]

Réactivité


Sur ces exemples le réseau est constitué de 6 noeuds connectés par des liens aux coûts identiques. Afin d'illustrer le partage de charge avec une méthode réactive, nous avons décider d'utiliser une solution de Traffic Engineering (TE, pour DT(p)_TE) simplement local et basé sur des mesures de débits résiduel. Les quatres test qui suivent représentent 4 secondes de simulations. Chaque seconde, chaque routeur sélectionne son lien le plus chargé (s'il dépasse 30% de charge sur cette intervalle de temps), et redistributie cette charge sur des NH alternatifs moins chargé. Nommenclature utilisé pour désigné les test: nom_technique_Rintervalle_de_temps(en s)-débit_relatif(en%).



Fig.4 : Démonstration de réactivité
Test 1 - SPF : Test 2 - ECMP/LFI>R1-30 :
Test 3 - DT1>R1-30 : Test 4 - DT2>R1-30 :