s'authentifier
version française rss feed

inria-00072871, version 1

On Arbitrary Waksman Networks and their Vulnerability

Bruno Beauquier 1, Eric Darrot

N° RR-3788 (1999)

Résumé : Motivated by problems in telecommunication satellites, we investigate rearrangeable permutation networks made of binary switches. A simple counting argument shows that the number of switches necessary to build a $n \times n$ rearrangeable network (i.e. capable of realizing all one-to-one mappings of its $n$ inputs to its $n$ outputs) is at least $\psln! = n\log_2{n} - n\log_2{e} + o(n)$ as $n\rightarrow\infty$. For $n = 2^r$, the $r$-dimension- al Bene\vs network gives a solution using $n\log_2{n} - \frac{n}{2}$ switches. Waksman, and independently Goldstein and Leibholz, improved these networks using $n\log_2{n}-n+1$ switches. We provide an extension of this result to arbitrary values of~$n$, using $\slog{i}{n}$ switches. The routing algorithm used in Bene\v{s} networks is also generalized for arbitrary values of~$n$. Finally the fault-tolerance issue of these networks is discussed.

  • Domaine : Informatique/Autre
  • Mots-clés : SWITCHING NETWORKS / MULTISTAGE NETWORKS / REARRANGEABLE NETWORKS / PERMUTATION NETWORKS / FAULT TOLERANCE / VULNERABILITY
  • Référence interne : RR-3788
 
  • inria-00072871, version 1
  • oai:hal.inria.fr:inria-00072871
  • Contributeur : 
  • Soumis le : Mercredi 24 Mai 2006, 11:08:46
  • Dernière modification le : Mercredi 31 Mai 2006, 14:24:27
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...