Cette thèse propose un schéma entièrement distribué de routage résilient pour les réseaux de switches. Dans cette approche une panne est traitée localement ; ainsi les autres nœuds du réseau n’ont pas besoin de prendre des mesures spécifiques. Contrairement aux systèmes classiques de routage IP qui se base uniquement sur la destination, le routage est fait en se basant sur l’arc de l’entrée et la destination. La contrainte qui en résulte est que les deux flux à la même destination entrant dans un nœud par un arc commun doivent fusionner après cet arc. Nous montrons que sous des faibles hypothèses (en supposant que le réseau est symétrique et bi-connexes au sens des liens), il existe un schéma de routage résilient pour toutes les situations de pannes simples de liens. Nous modélisons le problème de dimensionnement par un programme linéaire en nombres entiers qui peut être résolu exactement pour des réseaux de taille modeste. Nous proposons également plusieurs heuristiques pour traiter des instances de grande taille. Notre méthode généralise les méthodes de la littérature, en particulier celles de Xi et al. et de Nelakuditi et al. qui ont proposé des approches similaires. Notre approche permet d’obtenir de meilleurs résultats sur de nombreuses instances de test. Nous avons également étudié l’existence d’un schéma de routage résilient pour situation de panne de nœud dans le réseau basée sur les switches. Nous montrons que dans le cas des pannes de plusieurs liens, la condition de connexité n’est pas suffisante. / This thesis presents a fully distributed resilient routing scheme for switch-based networks. A failure is treated locally, so other nodes in the network do not need to undertakespecial actions. In contrast to conventional IP routing schemes, each node routesthe traffic on the basis of the entering arc and of the destination. The resulting constraintis that two flows to the same destination entering in a node by a common archave to merge after this arc. We show that this is sufficient for dealing with all singlelink failure situations, assuming that the network is symmetric and two-link connected.We model the dimensioning problem with an Integer Linear Program which can besolved exactly for small networks. We also propose several heuristics for larger networks.Our method generalizes the methods of Xi et Chao and Li and of Nelakuditiet al. who have proposed similar schemes in the context of IP. Our methods are moreefficient than previous ones. We have also studied the existence of a resilient routingscheme for single node failure situation in switch-based network. We study also thecase of multi-link failure situations and show that requiring the network to be connectedafter any failure does not guarantee the existence of a resilent routing schemeas described above.

Dans cette thèse, nous analysons les réseaux des systèmes temps-réel distribués et plus particulièrement ceux des domaines de l’avionique et de l’automobile. Nous nous sommes focalisés sur deux protocoles : « Avionic Full DupleX Switched Ethernet » (AFDX), « Audio Vidéo Bridging Ethernet » (AVB). Dans ces domaines critiques, le déterminisme du réseau doit être garanti. Il consiste, notamment, en la détermination d’une borne garantie du délai de bout en bout de traversée du réseau pour chaque trame ; et un dimensionnement des files d’attente des trames suffisamment grand pour garantir qu’aucune d’entre elle ne débordera et ainsi, éviter toute perte de trame.Il existe plusieurs méthodes pour l’évaluation des délais et nous avons, principalement, travaillé sur la méthode « Forward end-to-end delay Analysis » (FA). FA avait déjà été définie avec la politique d’ordonnancement « First-In-First-Out » dans le contexte de l’AFDX. Nous sommes repartis de cette approche, nous l’avons reformulé et généralisé à n’importe quel réseau Ethernet commuté. Nous l’avons aussi étendu aux priorités statiques et au protocole AVB et sa politique de service « Credit Based Shaper ». Pour chaque contribution, des démonstrations formelles ont été présentées et une expérimentation incluant une comparaison de FA avec les principales approches d’évaluation sur un exemple industriel. Finalement, nous avons développé et démontré formellement une approche pour le dimensionnement des files d’attente en termes de nombre de trames. Cette approche a été expérimentée également sur une configuration industrielle. / In this thesis, we analyze networks in the context of distributed real-time systems, especially in the fields of avionics, with “Avionics Full DupleX Switched Ethernet” (AFDX), and automobile, with “Audio Video Bridging Ethernet” (AVB). For such applications, network determinism needs to be guaranteed. It involves, in particular, assessing a guaranteed bound on the end-to-end traversal time across the network fr each frame; and dimensioning the buffers in order to avoid any loss of frame because of a buffer overflow.There are several methods for worst-case delay analysis, and we have mainly worked on the “Forward end-to-end Delay Analysis” (FA) method. FA had already been developed for “First-In-First-Out” scheduling policy in the AFDX context, so we generalized it to any Switched Ethernet network. We have also extended it to handle static priorities and the AVB protocol, shaping policy named “Credit Based Shaper” (CBS). Each contribution has been formaly proved and experiments have been led on industrial configurations. For our experimentations, we have compared our results with the results of competing approaches. Finally, we have developed and formally demonstrated an approach for buffer dimensioning in terms of number of frames. This approach has also been tested on an industrial configuration and has produced tight bounds.