On Arbitrary Waksman Networks and their Vulnerability - Archive ouverte HAL Access content directly
Reports Year : 1999

## On Arbitrary Waksman Networks and their Vulnerability

Bruno Beauquier
• Function : Author
Eric Darrot
• Function : Author

#### Abstract

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.

#### Domains

Computer Science [cs] Other [cs.OH]

### Dates and versions

inria-00072871 , version 1 (24-05-2006)

### Identifiers

• HAL Id : inria-00072871 , version 1

### Cite

Bruno Beauquier, Eric Darrot. On Arbitrary Waksman Networks and their Vulnerability. RR-3788, INRIA. 1999. ⟨inria-00072871⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

125 View