Brevet FR2827102A1 — publié le 20030110

individuel ou un ordinateur de type agenda ou assitant. L: 1 2827102 Système de routage inter systèmes autonomes tolérant aux fautes La présente invention est relative à la continuité de service d'un système de routage au sein d'un réseau de type Internet. Plus précisément, I'invention concerne le routage inter systèmes autonomes conformément au protocole BGP (Border Gateway Protocol) tel que délini par le RFC (Requesf For Comments) 1771 de l'IETF (internet Engincering Task Force). Elle s'applique aussi aux versions antérieures de ce protocole telles EGP (Exterior Gateway Protocol) défini par le RFC 904 de l'IETF. Tel qu'illustré par la figure 1, un tel réseau est composé de systèmes autonomes (ou AS pour Autonomous system), AS1, AS2, AS3. Chaque système autonome possède un plan de routage cohérent et unique vis-à-vis des autres systèmes de routage. On distingue deux sortes de protocoles de routage: À Des protocoles intrasystème autonome qui visent à établir ces plans de routage au sein d'un système autonome. Un exemple d'un tel protocole de routage est OSPF (Open Shortest Path First) défini par le RFC 2328 de l'IETF. À Des protocoles inter systèmes autonomes qui visent à échanger ces plans de routage afin de permettre le routage entre systèmes autonomes. Sur la figure 1, les traits continus entre les routeurs représentent les communications selon le protocole OSPF. Les protocoles de routage inter systèmes autonomes, tels BGP, sont typiquement mis en _uvre par des routeurs de bord, BR,, BR2, BR3. Ces routeurs de bord peuvent communiquer entre eux et ainsi, s'échanger des informations de routage. Ils forment donc un sous-réscau. Le comportement 103789/SYC/NCID F:\Solle\F103789\PREMDEP\FllNprojelbr.doc i de ce protocole BGP dans le cas de communication entre routeurs de bord de systèmes autonomes différents est connu sous le nom de EBGP (Exterior Border Gatoway Protocol) et est représenté sur la figure 1, par des tirets discontinus. Accessoirement, ce sous-réseau peut aussi comprendre des routeurs intrasystème autonome mettant en _uvre le protocole de routage IBGP (Interior Gateway Protocol) qui est le comportement du protocole BGP pour les routeurs intra-système autonome. Les communications selon ce protocole sont représentés par des pointillés sur la figure 1. Typiquement, dans le cas des protocoles de type BGP (c'est-à-dire incluant IBGP,EBGP...), les informations de routage échangées sont des routes. Chaque autre routeur (notamment de bord) avec lequel un routeur de bord communique est appelé par la suite, routeur pair ou, plus simpiement 1 5 pair. Cela implique donc que ces routeurs de bord sont des éléments cruciaux du réseau. Si, à la suite d'une défaillance par exemple, ils sont amenés à ne plus pouvoir fournir leur service de routage, le fonctionnement du réseau est compromis, ou en tout état de cause, nécessite une réorganisation qui peut étre pénalisante. Aussi, il importe d'assurer ia continuité du service de routage, en particulier fourni par les routeurs de bord. Pour ce faire, I'invention a pour objet, un système de routage inter systèmes autonomes connecté à des routeurs pairs. Ce système se caractérise en ce qu'il comporte, pour chaque routeur pair, deux modules de routage permettant le routage inter systèmes autonomes, un seul étant dans un état actif à un instant donné, les autres étant dans un état de veille, et 1 03789/SYC/NCiD F:\S"lle\F1 03789\PREMDEP\FlI\projelEr.doc 3 2827102 À un moyen permettant de basculer un de ces autres modules de routage d'un état de veille à un état actif lors de l'arrêt du module de routage à l'état actif. Selon une mise en _uvre de l'invention, ces modules de routage sont conformes à un protocole de type BGP. Selon une mise en _uvre de l'invention, chaque module de routage comporte: À un moyen pour, à l'état actif, mémoriser des informations relatives à son état et au routeur pair associé, et un moyen pour récupérer ces informations lors d'un basculement de ce module de routage vers l'état actif. Ainsi, par ce macanisme de redondance et de mémorisations des informations possédées par les modules de routage actifs et en veille, ie service de routage sera constamment en fonctionnement. En cas de défa il la nce, le sous- résea u continuera de fonctionner norma lement, sa ns qu' il y a it de répercussion de cette défai l lance sur son com portement. L'invention et ses avantages appara^'tront de facon plus claire dans la description qui va suivre d'une mise en _uvre de l'invention, en liaison avec les figures jointes. La figure 1, déjà commentée, illustre l'architecture typique d'un réseau de type Internet. La figure 2 représente la machine à états correspondant au protocole BGP. 1 03789/SYC/NCID F:\Salle\F1 03789\PREN\DEP\FIT\projelbr.doc Classiquement, le système de routage inter systèmes autonomes selon l'invention est mis en _uvre au sein d'un routeur internet. Plus précisément encore, il peut être mis en _uvre au sein d'un routeur de bord. Toutefois, le système de routage inter systèmes autonomes peut aussi être mis en _uvre au sein d'un routeur intra-système autonome ou même au sein d'un équipement différent d'un routeur. Autrement dit, il s'applique aussi aux protocoles IBGP et EBGP. Le protocole BGP peut être représenté par une machine à états finis. Une telle machine à états finis peut être définie pour chaque pair auquel le système de routage inter systèmes autonomes est connecté. Ainsi sur la figure 1, le routeur de bord BR a deux ensembles de modules de routage pour chaque pair BR2 et BR3, chacun de ces modules de routage mettant en _uvre une machine à états finis BGP. La figure 2 illustre une telle machine à états finis. Le premier état est l'état . C'est l'état initial dans lequel démarre la machine à états finis. Dans cet état, le système de routage ne possède que des informations de base sur le pair. Selon une mise en _uvre de l'invention, ces informations de base sont mémorisées, afin de pouvoir être prises en compte lors d'un basculement vers un module de routage en veille. Ces informations de base peuvent comprendre L'adresse IP (Internet Protocol) du pair, 25. Son identifiant, L'état de sa machine à états (plus précisément, de la machine à états qui lui est associé) 1 03789/SYC/NCID F:\Salle\F1 03789\PREA4DEP\FIT\projelEr.doc 2827102 A la réception d'un événement "Start>>, la machines à états finis passe dans un état transport est alors initiée avec le routeur pair. Selon une mise en _uvre de l'invention, ce protocole de transport est un protocole TCP (Transport Control Profocol) tolérant aux fautes. Il existe de nombreux protocoles TCP tolérant aux fautes. On peut citer celui décrit dans l'article " Wrapping Server-S;de TCP to Mask Connection Failures " de Lorenzo Alvisi, Thomas C. Bressoud, A. El-Khashab, K. Marzullo, et D. ZagoroUnov), Technical Report, Department of Computer Sciences, The University of Texas, Austin, Juillet 2000. On peut aussi citer le protocole HydraNet-FT, décrit notamment dans l'article " Hydranet-FT: Network Support for Dependable Services >> de G. Shenoy, S. Satapati et Riccardo Bettati, paru dans le compte-rendu 1 5 Systems ", Mai 2000. En cas d'échec, la machine à états finis passe dans l'état " Active " qui consiste à attendre une connexion TCP de la part du pair. Au bout d'un certain temps, si aucune tentative de connexion TCP n'a aboutit, la machine à états finis repasse dans l'état " Connoct" afin de re-initier une tentative de connexion TCP. Lorsqu'une connexion TCP est finalement établie, le module de routage transmet un message " Open " et la machine à états finis passe dans I'état " OpenSent ". Dans cet état, le module de routage attend la réception d'un message passe dans l'état . Dans cet état, la machine à états finis attend la réception d'un message . Ces messages " KeepAlive " sont réqulièrement 1 03789/SYC/NCID F:\Salle\F1 03789\PREMDEP\FIT\projelbr.doc échangés par les modules de routage inter systèmes autonomes afin de s'informer mutuellement qu'ils sont toujours opérationnels. A la réception d'un message >. Ces messages " Update " contiennent des informations de routage, c'est-à-dire des nouvelles routes, ou des annulations de route. Selon l'invention, à chaque changement d'états, on mémorise ce nouvel état de sorte que le module de routage en veille puisse démarrer directement dans cet état. Ainsi, il n'est pas nécessaire de repasser par la succession d'états qui vient d'étre décrite, et le basculement d'un module de routage à un autre est transparent pour le pair. Selon une mise en _uvre de l'invention, outre les informations de base qui sont mémorisoes lorsque la machine à états finis est dans l'état " Idie ", on mémorise aussi les informations de routage recus du routeur pair (que ce soit des nouvelles routes ou des annulations de route). Cette mémorisation peut étre réclisoe au moyen d'une mémoire partagée par le module de routage actif et le ou les modules de routage en veille. D'autres modes de réclisation sont bien évidemment possibles et à la portée de l'homme du métier. Notamment, les modules de routage peuvent communiquer via un moyen de communication inter-processus. Ce moyen de communication inter-processus peut par exemple être un bus logiciel, tel le bus logiciel CORBA conforme aux spécifications de l'OMG (Object 1 03789/SYC/NCID F:\Salle\F1 03789\PREMDEP\FIT\projetUr.doc 7 2827102 Management Group). L'étape de mémorisation peut alors 8tre précédée d'une étape d'émission des informations vers le ou les modules de routage en veille, à charge pour eux de mémoriser ces informations de sorte qu'ils puissent les récupérer lors d'un basculement d'états. Lorsque le module de routage à l'état actif s'arrête (soit du fait d'un arrêt programmé, soit du fait d'une déTaillance), un des modules de routage en veil le devient actif. Il peut a lors prend re en com pte les i nformations mémorisées par le module de routage précédemment actif. D'une part, I'état de la machine à états finis associce au module de routage nouvellement actif peut étre forcé à l'état mémorisé (donc à l'état du module de routage précédemment actif avant son arrêt). D'autre part, le module de routage nouvellement actif peut prendre en compte les informations sur le routeur pair (comme évoqué précédemment, son adresse IP etc.), et les informations de routage reques de lui. 1 03789/SYC/NCID F:\Srlle\F1 03789\PREMDEP\FIT\projelEr.doc REVENDICATIONS 1. Système de routage inter systèmes autonomes connocté à des routeurs pairs, caractérisé en ce qu'il comporte, pour chaque routeur pair, deux modules de routage permettant le routage inter systèmes autonomes, un seul étant dans un état actif à un instant donné, les autres étant dans un état de veille, et un moyen permettant de basculer un desUits autres modules de routage d'un état de veille à un état actif lors de l'arrêt du module de routage à l'état actif. 2. Système de routage selon la revendication 1, dans lequel lesUits modules de routage sont conformes à un protocole de type BGP. 3. Système de routage selon l'une des revendications 1 ou 2, dans lequel chacun desUits modules de routage comporte un moyen pour, à l'état actif, mémoriser des informations relatives à son état et au routeur pair associé, et un moyen pour récupérer lesUites informations lors d'un bascu lement dud it modu le de routage vers l'état actif. 4. Système de routage selon la revendication précédente, dans lequel lesdites informations comprennent l'état de la machine à états finis associée audit module de routage, le module de routage basculant à l'état actif étant forcé dans cet état. 1;. Système de routage selon la revendication précédente, dans lequel lesdites informations comprennent de surcro^'t des informations sur le routeur pair associé et les informations de routage recus dudit routeur À, palr assocle. 1 03789/SYC/NCID F:\Salle\F1 03789\PREA4DEP\FIT\projelEr.doc - 9 2827102 6. Routeur comportant un système de routage selon l'une des revendications précédentes.