Feasibility study on distributed simulations of BGP

Description

The Autonomous System (AS)-level topology of the Internet that currently comprises 40k ASs, is growing at a rate of about 10% per year. In these conditions, Border Gateway Protocol (BGP), the inter-domain routing protocol of the Internet starts to show its limits, among others in terms of the number of routing table entries it can dynamically process and control. To overcome this challenging situation, the design but also the evaluation of alternative dynamic routing models and their comparison with BGP shall be performed by means of simulation. For this purpose, DRMSim, a Dynamic Routing Model Simulator, was developed that provides the means for large-scale simulations of various routing models including BGP. By means of this discrete-event simulator, execution of path-vector routing, e.g. BGP, and other compact routing models have been successfully performed on network topologies comprising more than ten thousand (abstract) nodes. However, to simulate dynamic routing schemes like BGP, DRMSim needs enhancements to support current Internet size (40k ASs) and even more by considering its evolution (up to 100k ASs). This paper proposes a feasibility study of the extension of DRMSim so as to support the Distributed Parallel Discrete Event paradigm. We first detail the possible distribution models and their associated communication overhead. Then, we analyze the communication overhead of such a distributed simulator by executing BGP on a partitioned topology according to different scenarios. Finally, we conclude on the feasibility of such a simulator by computing the expected additional time required by a distributed simulation of BGP compared to its sequential simulation.

Abstract (French)

La topologie d'Internet est constituée d'environ 40K systèmes autonomes (AS) et s'accroit de 10% par année. Dans ces conditions, BGP (Border Gateway Protocol), le protocole de routage inter-domaine utilisé dans Internet commence à atteindre ses limites, plus particulièrement en terme de nombre d'entrées dans les tables de routage qu'il peut traiter dynamiquement. Afin de surmonter ce problème, la conception et l'évaluation de modèles de routage alternatifs et leur comparaison avec BGP doivent s'appuyer sur la simulation. Dans ce but, DRMSim, un simulateur de modèles de routage dynamiques, a été développé afin de fournir les moyens nécessaires pour la simulation à grande échelle de divers modèles de routage, BGP inclus. Grâce à ce simulateur à événements discrets, BGP qui est basé sur le routage par vecteurs de chemins et d'autres modèles de routage ont été simulés avec succès sur des topologies composées de plus de 10 000 noeuds. Cependant, pour simuler des schémas de routage dynamiques comme BGP, DRMSim doit être amélioré afin de fonctionner sur la topologie actuelle d'Internet composée d'environ 40K ASs, voir plus si l'ont considère son évolution (jusqu'à 100K ASs). Dans ce papier nous proposons une étude de faisabilité pour étendre les fonctionnalités de DRMSim afin d'utiliser le concept de simulation parallèle et distribuée à événements discrets. Dans un premier temps, nous détaillons les divers modèles de distributions ainsi que le coût supplémentaire en terme de communication. Nous analysons ensuite ces coûts de communication pour un tel simulateur distribué lors de l'exécution de BGP sur une partition de la topologie suivant différents scénarios. Enfin, nous concluons notre étude sur la faisabilité d'un tel simulateur en relevant le temps supplémentaire nécessaire à une simulation séquentielle de BGP par rapport à celle distribuée.

Additional details