Structures d'interconnexion : constructions et applications
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
This thesis deals with interconnection networks of logical circuits or processors, or communication networks. Several important properties are investigated. These networks can be modeled by graphs with given degree and diameter. An important problem is to build such graphs with a maximum of nodes. Several new constructions are given for simple or bipartite graphs: Some of these constructions are compounds of graphs such that the obtained graph has good diameter and degree. The problem is studied for an important family of graphs: The Cayley graphs of finite symmetric groups. For a given group we have to find a generating set of given cardinality yielding a diameter as small as possible. We exhibit a construction showing that the diameter can be about the logarithm of the order of the group, with logarithm basis the cardinality of the generating set. Some properties are related to the security of networks: E. G. , we look at a family of graphs where the secret key exchanges are easy and another family where it is possible to protect the traffic. Finally, the geometric regularity of interconnection structures are related to their universality, that is the possibility to represent all discrete functions of discrete variables. Such realizations are described for linear structures, called cascades, and rectangular structures.
Abstract FR:
Cette thèse concerne les réseaux d'interconnexion qui peuvent être des circuits logiques, des réseaux de processeurs ou des réseaux de télécommunications. Plusieurs de leurs propriétés importantes sont étudiées. Ces réseaux peuvent être modélisés par des graphes de degré et diamètre donnés. Un problème important est de construire de tels graphes avec un maximum de sommets. Plusieurs nouvelles constructions sont décrites pour des graphes simples ou bipartis: Certaines de ces constructions sont des composés de graphes tels que le graphe obtenu a les diamètres et degré demandés. Le problème est aussi étudié pour une famille importante de graphes: Les graphes de Cayley des groupes symétriques finis. Pour un groupe donné, il faut trouver un ensemble générateur de cardinalité donnée avec un diamètre résultant aussi petit que possible. Nous donnons une construction où le diamètre est environ le logarithme de l'ordre du groupe, la base du logarithme étant la cardinalité de l'ensemble générateur. Plusieurs propriétés sont reliées à la sécurité des réseaux: par exemple, nous étudions une famille de graphes où j'échange de clés est facile et une autre famille où il est possible de protéger le trafic. Enfin, la régularité géométrique des structures d'interconnexion est reliée à leur universalité, c'est-à-dire à la possibilité de représenter toutes les fonctions discrètes de variables discrètes. De telles réalisations sont décrites pour des structures linéaires, nommées cascades, et des structures rectangulaires.