75 lines
4.8 KiB
TeX
75 lines
4.8 KiB
TeX
\subsection{Topologien}
|
|
\begin{itemize}
|
|
\item Graph-Theorie als Grundlage:\begin{itemize}
|
|
\item Graph $G = (V, E)$ mit Knotenmenge $V$ und Kantenmenge $E$
|
|
\item Grad eines Knoten: Anzahl seiner direkten Nachbarknoten
|
|
\item Grad eines Netzes: höchster Grad eines seiner Knoten
|
|
\item Distanz eines Knotenpaares: Länge des kürzesten Pfad zwischen beiden Knoten
|
|
\item Durchmesser des Netzes: größte Distanz eines Knotenpaares im Netz
|
|
\item Kantenkonnektivität: minimale Anzahl an zu entfernenden Kanten, um das Netz in zwei disjunkte Teilnetze aufzuteilen
|
|
\item Bisektionsbreite: minimale Anzahl an zu entfernenden Kanten, um das Netz in zwei disjunkte, gleich große Teilnetze aufzuteilen
|
|
\end{itemize}
|
|
\item technische Eigenschaften eines Netzes:\begin{itemize}
|
|
\item Latenzzeit $L$: Zeit bis erstes Bit einer Nachricht beim Empfänger ankommt
|
|
\item Datenrate $B$: Maximale Datenmenge, die pro Zeiteinheit übertragen werden kann
|
|
\item Verzögerung $V(G)$: Übertragungsdauer einer Nachricht der Größe $G$
|
|
\begin{equation*}
|
|
V(G) = L + \frac{G - G_\text{min}}{B}
|
|
\end{equation*}
|
|
\item Durchsatz $D(G)$: Übertragungsrate bei Nachrichten der Größe $G$, charakterisiert \enquote{half-power point} als Paketgröße $G_\text{half}$, für die gilt:
|
|
\begin{equation*}
|
|
D(G_\text{half}) = \frac{B}{2}
|
|
\end{equation*}
|
|
\end{itemize}
|
|
\item Einteilung von Verbindungsnetzwerken:\begin{itemize}
|
|
\item statisch:\begin{itemize}
|
|
\item feste Verbindungen zwischen Knoten $k_i$
|
|
\item \begriff{Perfect Shuffle}: zyklischer Left-Shift
|
|
\item \begriff{Unshuffle}: zyklischer Right-Shift
|
|
\item \begriff{Butterfly}: $k_i \leftrightarrow k_{i,\text{reversed}}$ \item \begriff{Bus}: Grad 1, Durchmesser 1, Kantenkonnektivität 1, Bisektionsbreite 1
|
|
\item \begriff{voll-vermaschtes} Netz: Grad $n-1$, Durchmesser 1, Kantenkonnektivität $n-1$, Bisektionsbreite $\leq \frac{n^2}{4}$
|
|
\item \begriff{Ring}: Grad 2, Durchmesser $\lfloor\frac{n}{2}\rfloor$, Kantenkonnektivität 2, Bisektionsbreite 2
|
|
\item $d$-dimensionales \begriff{Gitter}: Grad $2d$, Durchmesser $d \cdot \left(\sqrt[d]{n}-1\right)$, Kantenkonnektivität $d$, Bisektionsbreite $\left(\sqrt[d]{n}\right)^{d-1}$
|
|
\end{itemize}
|
|
\item dynamisch (\begriff{Schaltnetzwerk}):\begin{itemize}
|
|
\item zusätzlich Schalter und dedizierte Schaltstufen
|
|
\item verschiedene Festlegung der Wegewahl: selbst-konfigurierend und nicht selbst-konfigurierend
|
|
\item \begriff{Kreuzschienenverteiler} (einstufig): $n$ Eingänge, $n$ Ausgänge, $n^2$ Schalter notwendig, Grad 2, Durchmesser 2, Kantenkonnektivität 2, Bisektionsbreite $\frac{n}{2}$
|
|
\item $d$-dimensionaler \begriff{Hyperwürfel}:\begin{itemize}
|
|
\item rekursive Konstruktion durch Spiegelung (Knoten als Binärzahlen nummeriert)
|
|
\item Routing: Ursprung $\oplus$ Ziel $\rightarrow$ Umschaltung wenn 1 an entsprechender Position
|
|
\item $n = 2^d$ Knoten, Grad $d$, Durchmesser $d$, Kantenkonnektivität $d$, Bisektionsbreite $\frac{n}{2}$
|
|
\end{itemize}
|
|
\item \begriff{Omega}-Netzwerk (mehrstufig, selbstkonfigurierend):\begin{itemize}
|
|
\item $\log_2$ Schichten an $2\times2$-Shuffles
|
|
\item Routing: Schicht $i$ vergleicht Bit $i$ von Ziel- und Quelladresse, bei Übereinstimmung unverändert, sonst schalten
|
|
\item Blockierung möglich
|
|
\item Grad 2 (für Knoten), Grad 4 (für Schalter), Durchmesser $\log_2 n$, Kantenkonnektivität 2, Bisektionsbreite $\frac{n}{2}$
|
|
\end{itemize}
|
|
\item \begriff{Baum}: Durchmesser $2 \log_2 n$, Bisektionsbreite 1
|
|
\item \begriff{Fat-Tree} ($n$ Knoten haben jeweils $k$ Eltern-Knoten):\begin{itemize}
|
|
\item $\log_k n$ Schichten, Schalter mit Grad $2k$, pro Schicht $\frac{n}{k}$ Schalter
|
|
\item Routing: direkter Weg über niedrigsten gemeinsamen Vorfahren, bei mehreren Alternativen zufällige Wahl
|
|
\item Durchmesser $2 \log_2 n$, Bisektionsbreite $\frac{n}{2}$
|
|
\end{itemize}
|
|
\item Benes-Netzwerk
|
|
\item Banyan-Netzwerk
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\item \begriff{Leitungsvermittlung}:\begin{itemize}
|
|
\item Senden der Adressdaten führt zum Aufbau eines festen Route
|
|
\item Senden der Nutzdaten folgt anschließend
|
|
\end{itemize}
|
|
\item \begriff{Paketvermittlung}: \begin{itemize}
|
|
\item Aufteilung der Nutzdaten in Pakete (mit jeweils einem Paketkopf für die Adressierung)
|
|
\item Paketverlust und Änderung der Reihenfolge möglich
|
|
\end{itemize}
|
|
\item \begriff{Routing}: \begin{itemize}
|
|
\item tabellenbasiert: statische Zuordnung von Zieladressen zu Ausgängen
|
|
\item quellenbestimmt: Paket führt Weiterleitungsinformationen mit sich
|
|
\end{itemize}
|
|
\item \begriff{Switching}: \begin{itemize}
|
|
\item \begriff{store/forward} puffert Pakete in Switch
|
|
\item \begriff{cut/through} dekodiert Paketkopf und leitet Nutzdaten direkt weiter, Blockierungsgefahr bei belegtem Ausgang (bei virtual cut/through durch Pufferung gelöst)
|
|
\end{itemize}
|
|
\end{itemize} |