\documentclass{uebungsblatt}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}

\usepackage{tikz}

\author{Marek Kubica kubica@in.tum.de, Michael Kerscher kerschem@in.tum.de}
\fach{Rechnernetze und Verteilte Systeme}
\blatt{4}
\gruppe{G}

\usepackage{ulem}

\begin{document}

\aufgabe[10]

\teilaufgabe

Die empfangende Schicht erhält zu Beginn die gesendeten Daten doppelt, weil die
zwei Pakete bestätigt und angenommen wurden, diese Bestätigung jedoch nicht beim
Sender ankommt. Der Sender versucht die Daten mit denselben Sequenznummern
nochmal zu senden, wobei der Empfänger denkt, dass die Daten neu sind, da die
erwartete Sequenznummer gepasst hat.

Das Sendefenster darf kein Vielfaches der Größe des Sequenznummernraums sein.

\teilaufgabe

Man braucht 3 Sequenznummern. Da der Sender 2 unbestätigte Pakete haben darf,
stellt die dritte Sequenznummer sicher, dass das wiederholte Paket nicht für
ein neues Paket gehalten wird.

\teilaufgabe

Der Sender darf maximal $2^4-1=15$ unbestätigte Pakete schicken, da das
16-te Paket dasselbe Problem wie in Teilaufgabe 1 verursacht.

\begin{enumerate}
\item

Bei \emph{Go-Back-N} werden so viele Pakete gesendet, wie der
Sequenznummernraum ($-1$) groß ist. Danach wird auf die entsprechenden ACK-Pakete
gewartet und ab dem ersten nicht bestätigten Paket wird die Übertragung
wiederholt.

Wir schicken $2^4-1$ Pakete beginnend mit Sequenznummer 0. Das Paket mit der
Sequenznummer 1 wird vom Empfänger nicht bestätigt, daher werden alle folgenden
($2^4-2$) Pakete neu versendet und können vom Empfänger als Duplikate erkannt
werden.
 
\item 

Bei \emph{Selective Repeat} werden ebenfalls $2^4-1$ Pakete gesendet beginnend
mit Sequenznummer 0. Nur das Paket mit der Sequenznummer 1 wird vom Empfänger
nicht bestätigt, daher wird bei diesem Verfahren auch nur das Paket mit der
Sequenznummer 1 neu gesendet, da der Rest bereits vom Empfänger
zwischengespeichert und bestätigt wurde. Ein nicht-erkennen von Duplikaten ist
hierbei ausgeschlossen, da die Sequenznummer $2^4-1=15$ noch nicht verwendet
wurde. Der Empfänger ist daher in der Lage, das wiederholte Paket richtig in die
Übertragungssequenz einzuordnen
\end{enumerate}

\teilaufgabe

Bei \emph{Go-Back-N} wird das empfangende Paket sofort an die nächsthöhere
Schicht weitergegeben. Daher ist ein Puffer nicht notwendig bzw. für maximal 1
Paket ausgelegt, da ab dem ersten "`verlorenem"' Paket neu übertragen wird. Ein
Zwischenspeichern wäre unnötig.

Bei \emph{Selective Repeat} muss der Puffer für mind. $2^4-1$ Pakete ausgelegt
sein. Da im \emph{worst-case} das erste Paket der Sequenz verloren geht, müssen
alle zu dieser Sequenz gehörenden Pakete im Empfangspuffer zwischengespeichert
werden, bis das erste fehlende Paket wiederholt wurde.

\aufgabe

\teilaufgabe
$X$ = Genau eine Insel sendet im Zeitslot

\begin{align*}
\Pr[X] = {n \choose 1} p^1 \cdot (1-p)^{n-1}
\end{align*}

\teilaufgabe

\begin{align*}
\max \left \{{n \choose 1} p^1 \cdot (1-p)^{n-1} \right \} \Rightarrow p =
\frac{1}{n}
\end{align*}

\teilaufgabe

\begin{align*}
\Pr[X] &= {n \choose 1} p^1 \cdot (1-p)^{n-1} \\
\Pr[X] &= {n \choose 1} \frac{1}{n} \cdot \left( 1-\frac{1}{n} \right)^{n-1} \\
\Pr[X] &= \left( 1-\frac{1}{n} \right)^{n-1} \\
\lim_{n \to \infty} \left( 1-\frac{1}{n} \right)^{n-1} & = \frac{1}{e}
\end{align*}

\teilaufgabe

Jeder Teilnehmer sendet höchstens wenn ein freies Medium erkannt wird. Wenn nun
ein Teilnehmer zu senden beginnt, muss sich das Signal erst auf dem Medium
ausbreiten. Da andere Teilnehmer das Signal erst später erkennen können, kann
es passieren, dass der Teilnehmer ein freies Medium erkennt und beginnt nun auch
zu senden. Eine Kollision ist daher erst ausgeschlossen, wenn der letzte
potentielle Sender das vom ursprünglichen Sender gesandte Signal empfangen hat.

Die Zeit dafür beträgt $t=\frac{s}{v}$.

\teilaufgabe

Ja, man weiß nun, dass es ein Zeitfenster in dem Zeitslot gibt, in dem das
Signal gestört werden kann. Die Übertragungszeit die nach diesem Zeitfenster
genutzt wird, ist garantiert störungsfrei. Man kann nun die Auslastung des
Kanals erhöhen, indem man den Zeitslot an sich vergrößert oder man vergrößert
die Signalausbreitungsgeschwindigkeit (nur möglich, wenn man Doctor Manhattan
ist!).

\aufgabe

\teilaufgabe

\begin{tikzpicture}[yscale=-1]
  \draw[help lines] (0,0) grid (5,11);
  \draw[->,very thick] (0,0) -- (5.3,0) node[above right] {l in m}; % Wegpfeil
  \foreach \x/\y in {2.5/B,5/C} 
    \draw[thick] (\x,0) node[above] {\y} -- (\x,11); % Zeitpfeile
  \draw[->,very thick] (0,0) node[above] {A} -- (0,11.3) node[left] {t in $\mu$s}; % Zeitpfeile
  \draw (1,0) node[above] {\footnotesize 100m};

  \foreach \x in {2,4,6,8,10}
    \draw (0,\x) node[left] {\footnotesize $\x\mu$s};

  \fill[color=blue!50,opacity=0.6] (0,1) -- (5,3.5) -- (5,5.9) -- (0,3.4);
  \draw (0,1) node[left] {Begin A} -- (5,3.5);
  \draw (0,3.4) node[left] {End A} -- (5,5.9);
 
%  \fill[color=red!50,opacity=0.4] (2.5,3) -- (0,4.25) -- (0,6.65) -- (2.5,5.4) --
%(5,6.65) -- (5,4.25);
%  \draw (2.5,3) node[above,right] {Begin B} -- (0,4.25);
   \draw (2.5,3) node[above,right] {Begin B};
%  \draw (2.5,3) -- (5,4.25);
%  \draw (2.5,5.4) node[below,right] {End B} -- (0,6.65);
%  \draw (2.5,5.4) -- (5,6.65);


  \fill[color=green!50,opacity=0.2] (5,3) -- (5,3.5) -- (0,6) -- (0,5.5);
  \draw (5,3) node[right] {Begin C} -- (0,5.5);
  \draw (5,3.5) node[right] {End C} -- (0,6);

  \fill[color=red!50,opacity=0.4] (5,3.5) -- (5,8.3) -- (0,10.8) -- (0,6);
  \draw (5,3.5) -- (0,6);
  \draw (5,4) node[right] {Begin Jam-Signal, 48 Bit};
  \draw (5,8.3) node[right] {End Jam-Signal, 48 bit} -- (0,10.8);
\end{tikzpicture}

Ja, es gibt mehrere Probleme. Während B versucht zu senden, stellt B fest, dass
ein Signal von A angekommen ist und stellt den Übertragungsversuch sofort ein.

Währenddessen fängt Teilnehmer C ebenfalls an einen Datenrahmen zu senden.
Jedoch kommt 0.5$\mu$s später das Signal von A bei C an. C erkennt diese
Kollision, bricht seine Übertragung daraufhin ab.

C sendet, um die Kollision zu signalisieren, ein 48 Bit = 6 Byte langes
Jamming"=Signal. A und B können so feststellen dass eine Kollision
stattgefunden hat.

\teilaufgabe

100 Mbit/s = $10^8$ Bit/s = 15000000 Byte/s. Es sollen 64 Byte übertragen
werden. Dies dauert $\frac{64
\textrm{Byte}}{12500000\frac{\textrm{Byte}}{\textrm{s}}} = 5.12 \cdot 10^{-6} =
5.12 \mu \textrm{s}$.

Die maximale Länge beträgt also: $l = c \cdot 5.12 \cdot 10^{-6} \textrm{s} =
1024 \textrm{m} = 1 \textrm{ Kibimeter}$.


\teilaufgabe

Switches und Brücken trennt die Kollisionsdomäne in mehrere Kollisionsdomänen,
da diese am Knotenpunkt das Medium auftrennen. Dies führt dann dazu, dass jeder
Ausgang der Geräte zu einer eigenen Kollisionsdomäne wird. Die Pakete werden
dazu von den Geräten zwischengespeichert und können gesendet werden, sobald das
Medium frei ist. Ein Switch hat im Vergleich zur Bridge mehr Ports. Man könnte
einen Switch sozusagen als \emph{multiport-bridge} bezeichnen.

Ein simpler Hub dagegen vergrößert die Kollisionsdomäne, da es im Prinzip einen
\emph{multiport repeater} darstellt und nur das Signal auf der Leitung liest
und wieder verbessert auf das Kabel gibt. Das Signal wird dabei im Gegensatz
zum Switch auf allen Ports ausgegeben. Falls hier zwei Rechner gleichzeitig
senden wollen, kommt es zur Kollision. Der Hub dient hierbei meist auch als
Kollisionsdetektor, der bei zwei gleichzeitigen Signalen das Jamming-Signal auf
die Leitung legt.
\end{document}
