diff --git a/ex07/kn07.pdf b/ex07/kn07.pdf index a3c16dd..7c3cbb3 100644 --- a/ex07/kn07.pdf +++ b/ex07/kn07.pdf Binary files differ diff --git a/ex07/kn07.tex b/ex07/kn07.tex index 659a948..01efee8 100644 --- a/ex07/kn07.tex +++ b/ex07/kn07.tex @@ -7,6 +7,7 @@ \usepackage{hyperref} %Links \usepackage{ifthen} %ifthenelse \usepackage{enumerate} +\usepackage{stmaryrd} \usepackage{color} \usepackage{algpseudocode} %Pseudocode @@ -87,24 +88,17 @@ \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}\\ -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_ii$). For the ports $b_k$ we need $i$ ($k\geq N-i+1$). In sum that are $1+N-i+i=N+1>N\ \lightning$ + \item $a_i< N \wedge b_{N-i+1}< N$\\ + To assign numbers to all ports $a_k$ we need $i$ numbers $N\ \lightning$ \end{enumerate} -So the switch for $a_1,b_N$ is non-blocking.\\ -Similar we can handle the switches $a_i,b_{N-i+1}$:\\ -We know that $i-1\le a_i < N+i\forall 1\le i\le N$, same for $b_i$.\\ -For the current switch we show:\\ $x\geq N \oplus y\geq N$, where $i-1\le x < N+i,\ N-i< y \le 2N-i$\\ -We distinguish two cases: -\begin{enumerate}[c1:] - \item Assume $i-1\le x