jeudi 10 février 2011
Routage inter-domaine

La soutenance aura lieu le Jeudi 10 Février 2011 à 10H30 en salle A001-A003

Composition du Jury:

– Timothy G. Griffin, Rapporteur, Université de Cambridge
– Patrick Sénac, Rapporteur, ISAE, LAAS/CNRS
– Khaldoun Al Agha, Examinateur, Université Paris-Sud
– Marcelo dias de Amorim, Examinateur, UPMC
– Ana Cavalli, Directrice de these, Telecom SudParis
– Stéphane Maag, Encadrant, Telecom SudParis

Abstract

Internet is the hugest network the humanity has ever known. It provides a large number of various services to more than two billion users. This complex and growing topology lacks stability, which we can notice when a voice call is dropped, when a web page needs to be refreshed, etc. The initiator of this instability is the frequent events around the Internet. This motivates us to unleash a profound study to tackle Internet stability and suggest solutions to overcome this concern.

Internet is divided into two obvious levels: AS (Autonomous System) level and router level. This distinction is reflected on the routing protocols that control the Internet traffic through two protocol
types: exterior (inter-AS) and interior (intra-AS). The unique used exterior routing protocol is the external mode of BGP (External Border Gateway Protocol), while there are several used internal routing protocols.

Therefore, stabilizing the Internet is correlated to the routing protocol stability, which directs such efforts to the investigation of routing protocol (BGP) behavior. Studying BGP behaviors results in that its external mode (eBGP) suffers from long convergence time which is behind the slow response to topology events and, in turn, the traffic loss. Those studies state also that BGP internal mode (iBGP) suffers from several types of routing anomalies that causes its divergence.

Therefore, we propose enhancements for both BGP modes: eBGP and iBGP and try to meet the following objectives: Scalability, safety, robustness, correctness, and backward compatibility with current version of BGP. Our eBGP proposal eliminates the transient disconnectivity caused by slow convergence by suggesting a backup strategy to be used upon the occurrence of a failure. IBGP proposal
(skeleton) gives an alternative to the existing internal configurations, that we prove its freeness of anomalies.

Validation methods are essential to prove that the suggested enhancements satisfies the attended objectives. Since we are tackling an interdomain subject, then it is not possible to do validation in the real Internet. We suggested several validation methods to show that our enhancements meet the above objectives. We used simulation environment to implement eBGP backup solution and observe the convergence time and the continuous connectivity. We relied on two
tools: brite and rocketfuel to provide us with inter and intra AS topologies respectively. And to prove the safety of our approaches we employed an algebraic framework and made use of its results.

Résumé

Internet est le réseau le plus gigantesque que l’humanité ne se soit pourvu. Il fournit un nombre important de services à plus de deux milliards d’utilisateurs. Cette topologie grandissante et complexe pêche en stabilité, ce qui peut notamment être constaté quand un appel voix est interrompu, quand une page web à besoin d?être rafraîchie, etc. L’initiateur de cette instabilité est l’ensemble des événements constatés dans l’Internet. Ceci nous motive à une Étude profonde de la stabilité d’Internet afin de suggère des solutions à cette problématique.

Internet est divisé en deux niveaux de base: le niveau AS (Autonomous
System) et le niveau de routage. Cette distinction se répercute dans les protocoles de routage qui contrôlent le trafic Internet à travers deux types de protocoles: extérieur (inter-AS) et intérieur (intra-AS). L’unique protocole de routage extérieur utilité est le mode externe de BGP (External Border Gateway Protocol) tandis qu’il en existe plusieurs de type intérieur.

De fait, la stabilisation de l’Internet est corrélée à la stabilité des protocoles de routage. Cela pousse les efforts de traitement de l?instabilité de l’Internet à Étudier le comportement du protocole de routage (BGP). Analyser les résultats des comportements de BGP dans son mode externe (eBGP) souffre d’un temps de convergence important menant notamment à des réponses lentes des évènements de topologie et, à terme, à la perte du trafic. Les études établissent également que le mode interne de BGP (iBGP) souffre de plusieurs types d’anomalies de routage causant la divergence.

Afin d’illustrer la stabilité de BGP, nous avons besoin d’un modèle de routage qui formule la procédure de décision et le flot de signalisation. De plus, les améliorations de BGP ne peuvent pas être aisément validées dans l’Internet, rendant ainsi les modèles de BGP indispensables à une validation formelle. De fait, la première étape dans l?étude du routage inter-domaine est de définir un modèle approprié permettant la formulation de ses opérations et de prouver sa correction.

Nous avons proposé deux modèles complémentaires: topologique et fonctionnel, avec lesquels nous avons formulé le processus de convergence du routage et démontré la sécurité et la robustesse de nos solutions d’inter/intra-AS. Notre proposition d’inter-AS élimine les déconnections transitoires causées par une faible convergence d’eBGP en suggérant une stratégie de backup lors d’une panne. Notre proposition d’intra-AS (skeleton) donne une alternative aux configurations internes existantes, pour laquelle nous avons montré l’absence d’anomalies.