Routage multichemins par interface d’entrée
Institution:
Université Louis Pasteur (Strasbourg) (1971-2008)Disciplines:
Directors:
Abstract EN:
The reliability of IP networks in terms of failures and congestions depends on the reaction time associated with the underlying routing protocol. Currently, link state routing protocols such as OSPF or IS-IS use only the best paths to forward the IP packets at a domain scale. The sub-optimality property of best paths ensures consistency of hop by hop routing although the paths calculated using Dijkstra’s algorithm are composed of close in close. According to the metric, the diversity of existing paths may be largely under estimated with a condition such as sub-optimality. Yet the diversity of alternatives paths is one of the key elements to ensure a limited reaction time. The main difficulty related to hop by hop multipath routing protocols is to ensure the absence of routing loops. Each node must verify that the traffic it carries is not switched on circuit where they belong. In this PhD report, we present two contributions whose the combination ensures that property. The first proposition, based on Dijkstra’s algorithm, is a multipath search algorithm called Dijkstra-Transverse (DT) which calculates a set of multiple paths between a root node and each other node in the graph modeling the network. The second contribution is a distributed validation procedure DT(p) whose the aim is to prune circuits potentially generated by hop by hop routing composition. To increase the diversity of validated paths, the forwarding mechanism is specific to each incoming interface. Furthermore, we have evaluated the impact of the path diversity to produce an effective coverage if link failure occurs. The coverage can be defined in two versions, local or global, depending on the possibility to notify upstream routers of the detected failure. We are also interested in traffic engineering issues related to load balancing in case of congestion. To estimate the importance of paths diversity to implement a efficient proportional routing, we have defined a reactive load balancing module. This module is based on a local analysis of residual bandwidth and highlight the performance of our proposed routing scheme. For the sake of credibility, our simulations are based on realistic topologies and traffic generation. The results underline the effectiveness of our algorithms to generate a greater diversity of paths compared to existing propositions. Paths diversity is necessary in order to obtain a sufficient forwarding capacity to circumvent outages and congestion as indicated by our results related to these two types of applications.
Abstract FR:
La fiabilité d’un réseau IP face aux pannes et aux congestions dépend du temps de réaction associé au protocole de routage sous-jacent. Actuellement, les protocoles de routage à états des liens tels que OSPF ou IS-IS n’utilisent que les meilleures routes de coût égal pour commuter les paquets IP à l’échelle d’un domaine. La propriété de sous-optimalité des meilleures routes garantit la cohérence du routage au saut par saut bien que les chemins calculés via l’algorithme de Dijkstra soient composés de proche en proche. Selon la métrique employée, la diversité des chemins existant peut être largement sous exploitée avec une condition telle que la sous-optimalité. Or la diversité des alternatives de routage est l’un des éléments clés pour assurer un temps de réaction limité. La difficulté inhérente aux protocoles de routage multichemins saut par saut est la vérification de l’absence de boucles de routage. Chaque noeud doit garantir que le trafic qu’il achemine ne soit pas commuté sur un circuit dont il fait partie. Dans ce rapport de thèse, après avoir mis en avant l’état de l’art existant dans la littérature, nous exposons deux contributions dont la combinaison assure cette propriété. La première proposition est basée sur l’algorithme de Dijkstra, il s’agit d’un algorithme de recherche opératoire nommé Dijkstra-Transverse qui calcule un ensemble de chemins transverses entre un noeud racine et chaque autre noeud du graphe modélisant le réseau. La seconde contribution est une procédure de validation distribuée dont le but est d’élaguer les circuits potentiellement générés par le routage saut par saut. Pour accroître la diversité des chemins validés, la procédure de commutation est spécifique à chaque interface entrante. Par ailleurs, nous avons évalué l’impact de la diversité des chemins pour mettre en oeuvre une couverture efficace en cas de panne de liens. La notion de couverture se décline en deux versions, locale ou globale, selon le type de protection envisagé, en d’autres termes, s’il est possible ou non de notifier les routeurs en amont de l’occurence d’une panne. Nous nous sommes également intéressés aux aspects ingénierie de trafic liés à l’équilibrage de la charge en cas de congestion. Afin d’estimer l’importance de la diversité des chemins pour mettre en oeuvre un routage proportionnel efficace, notre travail s’est focalisé sur la définition d’un module réactif de partage de charge. Celui-ci est simplement basé sur une analyse locale de la bande passante résiduelle et permet de mettre en relief les performances de nos propositions de routage par comparaison avec l’existant. De manière générale, dans un souci de crédibilité, nos évaluations par simulation sont basés sur des topologies et une génération de trafic réalistes. Les résultats obtenus mettent en avant l’efficacité de nos algorithmes pour déployer un routage multichemins générant une diversité accrue par rapport à l’existant. Celle-ci est en effet nécessaire pour obtenir une capacité de commutation suffisante pour contourner les pannes et les congestions comme l’indiquent nos résultats liés aux deux types d’applications évalués.