Projets/Renater

D-CART : Dynamic reConfiguration Analysis with Routing Traces

Fig.1 : La première flotte de Rasprobes

Le projet D-CART s'inscrit dans le cadre d'une collaboration entre RENATER et ICube. L'objectif prioritaire est l'étude expérimentale des boucles de routage transitoires dans un réseau d'opérateur. Dès lors qu'un changement topologique (panne, maintenance et modification de configuration du routage) intervient sur un réseau IP utilisant un routage à état des liens, des incohérences transitoires dans les états de routage des différents routeurs peuvent se produire. 
 Ces incohérences peuvent se traduire notamment sous la forme de micro-boucles de routage dégradant potentiellement la qualité de service en produisant les effets suivants : pertes de paquets, augmentation des délais et micro-congestions, oscillations de routes et dé-séquencements.

L'équipe Réseaux du laboratoire ICube a développé des solutions algorithmiques de re-routage progressif permettant d'éviter ces boucles [1]. 
La quantification par mesures actives de telles boucles est le premier objectif du projet D-CART : quelle est leur durée type ? quel est leur impact réel ? est-ce que le bénéfice des solutions de prévention développées est significatif ? 
quelle est la nature des corrélations avec les évènements qui les ont provoqués ?

Fig.2 : Déploiement actuel (3 types de noeuds de mesure)


En pratique, et dans un premier temps, ces mesures seront réalisées dans le cadre de campagnes de sondage dont les émetteurs/récepteurs (de nombreux équipements de mesure légers, e.g, Raspberry Pi, voir Fig.1) sont répartis sur un sous ensemble des routeurs du réseau RENATER (voir Fig.2 : en plus des point de sondage R-PI en bleu, nous disposons d'accès aux noeuds PlanetLab en vert). Ces campagnes nous permettront d'évaluer l'évolution d'indicateurs de performance du réseau en fonction des événements de routage. Ceux-ci seront enregistrés par un agent passif collectant les paquets de signalisation (en rouge sur la Fig.2). 
Le réseau RENATER offre en effet la possibilité de mener une telle étude : son routage interne est basé sur un protocole dynamique à états des liens, IS-IS.


A plus long terme, le déploiement d'une infrastructure de mesure complète (i.e. une couverture exhaustive du réseau pour des mesures "dirigées") nous permettra d'envisager d'étendre nos analyses vers de nombreuses autres formes d'études expérimentales pour l'évaluation de la qualité de routage et de sa dynamique.

Fig.3 : Illustration potentialité de boucles

Les figures 3 et 4 illustrent la première boucle de routage transitoire observée sur le réseau RENATER grâce à notre infrastructure de mesures. La figure 3 permet de localiser l’événement déclencheur, la boucle et le flux perturbé : il s'agit d'une panne de lien entre Bordeaux et Nantes qui a provoqué une incohérence entre les routeurs de Montpellier et Marseille pour le flux dirigé entre Toulouse et Quimper. On peut observer que l'acheminement initial entre ces nœuds (avant coupure : arcs rouges et noirs -- respectivement, les arcs pré et commun, i.e., ceux utilisés avant seulement ou avant et après la panne) était unique et constitué d'un chemin de routage de cinq sauts, alors que l'acheminement post-coupure (arcs verts et noirs) est multiple grâce à ECMP (technique de partage de charge par fonction de hachage sur plusieurs chemins de coût identique) et constitué de huit combinaisons de chemins de 10 à 11 sauts (selon l'aiguillage à Paris). On peut observer qu'en théorie quatre boucles de longueur 2 sont possibles dans cette configuration, mais qu'une seule a été effectivement enregistrée via la plateforme (flèches grisées sur la figure 3 : interfaces entre les routeurs de Marseille et Montpellier). Cet exemple est remarquable car il illustre un cas de boucle non adjacent aux routeurs directement impliqués dans le changement topologique.

Fig.4 : La première boucle enregistrée

La figure 4 permet de quantifier le temps de coupure ainsi que la durée de la période d'incohérence du routage. Le flux entre Toulouse et Quimper a été interrompu pendant approximativement une seconde : aucun paquet n'a été collecté sur le récepteur durant cette période. On peut également observé que durant près de 900ms, des messages TTL Time-Exceeded provenant des routeurs de Montpellier et Marseille ont été récoltés sur le point de mesure connecté à Toulouse. Il s'agit d'une preuve expérimentale de l’occurrence d'une boucle sur le réseau (dont l'impact est potentiellement significatif étant donné la durée). En effet, les paquets émis par Toulouse à destination de Quimper ont été éliminés du réseau par les routeurs de Montpellier ou Marseille car leur durée de vie avait expiré. On peut en déduire qu'ils ont été "aspirés" dans la boucle entre ces deux routeurs jusqu'à leur expiration en terme de TTL. Afin de finement localiser la position des boucles, nos sondes sont envoyées avec des TTL initiaux variés pour pouvoir expirer en différents lieux sur le réseau. La période qui précède cette boucle (~100 ms) est liée au temps de détection et de signalisation de la panne. De manière générale, la figure 4 confirme la potentialité de boucle et les chemins pré-post évalués sur la figure 3 suite au retrait du lien Bordeaux-Nantes : on observe bien une augmentation des délais de bout en bout (one way delay estimé avec synchro NTP) et une augmentation du nombre de sauts qui indique que le chemin employé par nos sondes après la panne semble unique et est celui de taille 11 passant notamment par Monptellier-Marseille-Lyon-Paris-Rouen-Caen-Rennes.

---

https://www.renater.fr/

Participants

ICube : Pascal Mérindol (contact), J-J. Pansiot, P. David.

RENATER : GIP (support, assistance), RENALab

Autres : F. Clad (IMDEA-Cisco)

Publications

[1] Computing Minimal Update Sequences for Graceful Router-wide Reconfigurations F. Clad, S. Vissicchio, P. Mérindol, P. Francois and J.-J. Pansiot. IEEE/ACM Transactions on Networking, 2014.