Résistance aux pannes de grands réseaux d'interconnexion
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
This thesis deals with the fault-tolerance of several interconnection networks, namely the Kautz and de Bruijn networks, and their generalizations. A network is usually modeled by a graph or a digraph in which the vertices represent the nodes in the network and the arcs or edges represent the communication links. The fault tolerance properties are associated to different notions of connectivity. Among some other nice properties the results show that these networks are optimal for these different notions. For example their connectivity’s are almost always equal to their minimum degrees. Therefore those networks should be the model of the future multi processor architectures.
Abstract FR:
Cette thèse concerne l'étude de la vulnérabilité de certains grands réseaux d'interconnexion, en particulier les réseaux de Kautz et de Bruijn ainsi que leurs généralisations. Un réseau est modélisé par un graphe dans lequel les sommets correspondent aux nœuds du réseau et les arcs ou arêtes (suivant que le graphe est orienté ou non) représentent les liaisons de communication entre les nœuds. La vulnérabilité se traduit par diverses propriétés de connexité. On montre que ces réseaux sont souvent optimaux pour les diverses notions de vulnérabilité étudiées, en particulier que leur connexité est, dans presque tous les cas, égale au degré minimum du graphe associé. Ces réseaux devraient donc constituer le modèle des futures architectures multiprocesseurs.