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.
- 1 : SLOOP (INRIA Sophia Antipolis / Laboratoire I3S)
- INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
- 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
- http://hal.inria.fr/inria-00072871
- oai:hal.inria.fr:inria-00072871
- Contributeur : Rapport De Recherche Inria
- Soumis le : Mercredi 24 Mai 2006, 11:08:46
- Dernière modification le : Mercredi 31 Mai 2006, 14:24:27






Documents associés

Exporter