\documentclass[a4paper,12pt]{scrartcl}
\usepackage[ngerman]{babel}
\usepackage{graphicx} %BIlder einbinden
\usepackage{amsmath} %erweiterte Mathe-Zeichen
\usepackage{amsfonts} %weitere fonts
\usepackage[utf8]{inputenc} %Umlaute & Co
\usepackage{hyperref} %Links
\usepackage{ifthen} %ifthenelse
\usepackage{enumerate}

\usepackage{color}
\usepackage{algpseudocode} %Pseudocode
\usepackage{dsfont} % schöne Zahlenräumezeichen
\usepackage{amssymb, amsthm} %noch stärker erweiterte Mathe-Zeichen
\usepackage{tikz} %TikZ ist kein Zeichenprogramm
\usetikzlibrary{trees,automata,arrows,shapes}
\usepackage{pgfplots}

\pagestyle{empty}


\topmargin-50pt


\newcounter{aufgabe}
\def\tand{&}

\newcommand{\makeTableLine}[2][0]{%
  \setcounter{aufgabe}{1}%
  \whiledo{\value{aufgabe} < #1}%
  {%
    #2\tand\stepcounter{aufgabe}%
  }
}

\newcommand{\aufgTable}[1]{
  \def\spalten{\numexpr #1 + 1 \relax}
  \begin{tabular}{|*{\spalten}{p{1cm}|}}
    \makeTableLine[\spalten]{E\theaufgabe}$\Sigma$~~\\ \hline
    \rule{0pt}{15pt}\makeTableLine[\spalten]{}\\
  \end{tabular}
}

\def\header#1#2#3#4#5#6#7{\pagestyle{empty}
\begin{minipage}[t]{0.47\textwidth}
\begin{flushleft}
{\bf #4}\\
#5
\end{flushleft}
\end{minipage}
\begin{minipage}[t]{0.5\textwidth}
\begin{flushright}
#6 \vspace{0.5cm}\\
%                 Number of Columns    Definition of Columns      second empty line
% \begin{tabular}{|*{5}{C{1cm}|}}\hline A1&A2&A3&A4&$\Sigma$\\\hline&&&&\\\hline\end{tabular}\\\vspace*{0.1cm}
\aufgTable{#7}
\end{flushright}
\end{minipage}
\vspace{1cm}
\begin{center}
{\Large\bf Sheet #1}

{(Hand in #3)}
\end{center}
}



%counts the exercisenumber
\newcounter{n}

%Kommando für Aufgaben
%\Aufgabe{AufgTitel}{Punktezahl}
\newcommand{\Aufgabe}[2]{\stepcounter{n}
    \textbf{Exercise \arabic{n}: #1} (#2 Points)}

\newcommand{\textcorr}[1]{\textcolor{red}{#1}}
\newenvironment{corr}{\color{red}}{\color{black}\newline}
\newcommand{\ok}{\begin{corr}
            $\checkmark$
        \end{corr}}

\newcommand{\enot}[2]{#1 \cdot 10^{#2}}

\begin{document}
%\header{BlattNr}{Tutor}{Abgabedatum}{Vorlesungsname}{Namen}{Semester}{Anzahl Aufgaben}
\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_i<b_{i+1}$ we know that $a_1\le N$ and $b_N\geq N-1$. We distinguish two cases:
\begin{enumerate}[c1:]
    \item Assume $a_1<N$\\
        $\Rightarrow b_N\geq N$ since it is the largest of the $b_i$ and there are no other addresses left.\checkmark
    \item Assume $a_1=N$\\
        $\Rightarrow b_N=N-1$ since $a_1$ has to be the smallest of the $a_i$\checkmark
\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<N$\\%TODO
    \item Assume $N\le x < N+i$\\
\end{enumerate}
\Aufgabe{Flow Control and ARQ Protocols}{22}
\begin{enumerate}
    \item Flow Control means the controlling of the transmission of data. This is necessary for example if the receiver is slower or has higher traffic than the sender and can't keep up. For flow control ACK message can be used to acknowledge received messages (used in the examples from he lecture).
    \item The specific package may be received anywhere in the window, i.e. newer packages may be received before older ones. However this does not directly lead to retransmission but only if the window for receiving is left. To implement this window a buffer is necessary.
    \item $n,m\in\mathds{N}$\\
        \begin{tabular}{c||c|c|c}
            &SAW&GBN&SR\\\hline
            sender window & 1 & n & n\\
            receiver window & 1 & 1 & m\\
            repetition & if necessary & all since last ACK & if necessary
        \end{tabular}\\[0.5cm]
        As we see in the table the main difference is the size of sending and receiving window. By this differences all the other differences can be explained (e.g. accepting only the matching frame or all in the window).\\
        Common for all protocols is that they use ACK messages to acknowledge receiving (implement flow control by this) and that they only have one sender and one receiver.
\end{enumerate}
\Aufgabe{Framing}{22}
\begin{enumerate}
    \item Byte-oriented protocols determine the size of flags to $8k$ bit for $k\in\mathds{N}_0$. For bit-oriented protocols they may have any size. Both protocols use the according stuffing technique to prevent a control pattern from occurring in the data. In opposite to character-oriented protocols both of them don't use a special encoding and are transparent by that.
    \item Bit stuffing means the preventing of the occurrence of control bit sequences (flags) in the data by adding 0-bits after sequences of 5 1s after a 0 (0111111 is the control sequence), by this it is broken and won't be interpreted. This added 0s have to be deleted in unstuffing process.\\
    Byte stuffing for the same purpose has an ESC-byte. The byte following this one won't be interpreted as control byte. Also these escape-bytes have to be removed in the unstuffing.
    \item PPP is byte-oriented and so uses byte stuffing.
\end{enumerate}
\Aufgabe{ALOHA and Slotted ALOHA}{36}
\begin{enumerate}
    \item $\frac{64kbit/s}{256bit/s}=25$ messages can be transmitted according to the bandwidth. The maximum of thoughput we reach at $G=0.5$, so the maximum number of terminals is $x^*=\left\lfloor\frac{25}{2}\right\rfloor=12$.
    \item For Slotted ALOHA the maximum is at $G=1$, so the best number of terminals is $x'^*=25$
    \item The formula is $x^*=\left\lfloor\frac{N}{2tm}\right\rfloor$, where $m$ is the message size, $t$ the messages per second. This leads to:
    \begin{enumerate}
        \item doubling $t$ halves $x^*$
        \item doubling $m$ halves $x^*$
        \item doubling $N$ doubles $x^*$
    \end{enumerate}
    All those with the limitation of the floor-function so only approximately.
\end{enumerate}
\end{document}