inria-00072871, version 1

## On Arbitrary Waksman Networks and their Vulnerability

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