thesis

Les réseaux d'interconnexion et leur vulnérabilité

Defense date:

Jan. 1, 1987

Edit

Institution:

Paris 11

Disciplines:

Computer sciences

Authors:

Directors:

Abstract EN:

This thesis contains several articles studying the vulnerability of interconnection networks. Such networks are modelled either as graphs (if the connections are made point to point) or as hypergraphs (if the connections are made via buses). We examine several vulnerability criteria for these networks. We give conditions on the degrees, the girth and the diameter which ensure that a graph has large connectivity, which, in turn, implies that the associated network will be insensitive to component failures. By calculating bounds for the maximum diameter of vertex-deleted or edge­ deleted graphs, we determine the worst possible effects resulting from fault-induced transmission delays. Finally, by determining their connectivities and vulnerabilities, we demonstrate that networks with interconnections modelled by Kautz graphs, de Bruijn graphs, and "double loop" graphs are highly reliable.

Abstract FR:

Cette thèse est constituée de plusieurs articles. La plupart d'entre eux porte sur les réseaux d'interconnexion et en particulier sur l'étude de leur vulnérabilité. Un tel réseau est modélisé soit par un graphe dans le cas de liaisons point à peint, toit par un hypergraphe dans le cas de liaisons par bus. Les sommets du graphe représentent les nœuds du réseau, et les arêtes les liaisons. Nous étudions ces réseaux fonction de divers critères de vulnérabilité. Nous donnons des conditions assurant qu'un graphe ait une bonne connexité, ce qui implique que le réseau associé peut continuer à fonctionner en cas de pannes. Nous étudions aussi l'influence des pannes sur le délai de transmission des messages dans le réseau résultant, en particulier en donnant des bornes sur la valeur maximale possible pour le diamètre du graphe résultant après les pannes. Nous considérons un certain nombre de bons réseaux connus, tels que les réseaux de Kautz, de de Bruijn ou les réseaux en double boucle, et déterminons leur connexité et leur vulnérabilité.