diff --git a/ex07/kn07.pdf b/ex07/kn07.pdf index 4dd8ffb..a3c16dd 100644 --- a/ex07/kn07.pdf +++ b/ex07/kn07.pdf Binary files differ diff --git a/ex07/kn07.tex b/ex07/kn07.tex index e8883ac..659a948 100644 --- a/ex07/kn07.tex +++ b/ex07/kn07.tex @@ -87,7 +87,24 @@ \header{6}{}{2015-12-02}{Kommunikationsnetze}{\textit{Jonas Jaszkowic, 3592719}\\\textit{Jan-Peter Hohloch, 3908712}}{WS 15/16}{4} \vspace{1cm} \Aufgabe{Banyan Switches}{20}\\ -The first stage is non-blocking, because there are lines for each input and $2N$ outgoing ports.\\ %TODO: This is probably not the solution, however I have no clue how to involve ascending order here... +We assume $N=2^k,\ k\in\mathds{Z}$, otherwise it is possible to construct a blocking configuration.\\[0.2cm] +The lower half of the whole switch is non-blocking if the upper half isn't (symmetric, we can exchange the labels $a_i$ and $b_i$).\\We have to show $a_i\geq N \oplus b_{N-i+1}\geq N$ which means only one of them has $1$ as most significant bit, the other $0$.\\ +Given $a_i < a_{i+1},\ b_i