Ub7-Statische Verbindungsstrukturen

• In statischen Netzen existieren fest installierte Verbindungen zwischen Paaren von Netzknoten

• Steuerung des Verbindungsaufbaus ist Teil der Knoten

$K$-ärer $n$-Kubus (Cubes, Würfel)

• $n$: Dimension

• $K$: Anzahl der Knoten, die einen Zyklus in einer Dimension bilden (Rückwärtskanten)

• $\Rightarrow$ Insgesamt $N = K^n$ Knoten

• Adressierung der Knoten: n-stellige k-äre Zahl der Form $a_0, a_1, \dots, a_{n-1}$

  • Jede Stelle $0 \leq a_i < K$ stellt die Position des Knotens in der entsprechenden $i$-ten Dimension dar, mit $0 \leq i \leq n-1$

  • Ein Nachbarknoten in der $i$-ten Dimension zu einem Knoten mit Adresse $a_0, a_1, \dots, a_{n-1}$ kanan erreicht werden mit $$ a_0, a_1,\dots, a_(i \pm 1) \bmod k, \dots, a_{n-1} $$

• Knotengrad: $2n$

• Diameter: $n\left\lfloor\frac{k}{2}\right\rfloor$

Bsp 1

• $\color{orange}{n=3}$

• $\color{green}{K=2}$

  

• Adresse: $\color{orange}{3}$-stellige $\color{green}{2}$-näre Zahl $a_0, a_1, a_2$

  • $a_i \in (0, 2)$

Bsp 3

• $\color{orange}{n=3}$

• $\color{green}{K=3}$

• Ein Nachbarknoten in der $i$-ten Dimension zu einem Knoten mit Adresse $a_0, a_1, \dots, a_{n-1}$ kanan erreicht werden mit $$ a_0, a_1,\dots, a_(i \pm 1) \bmod k, \dots, a_{n-1} $$

  • Von 110 zu 100

    $a_1 = 1 \Rightarrow (a_1 - 1) \bmod 3 = 0$ 👏

  • Von 210 zu 010

    $a_{0}=2 \Rightarrow\left(a_{0}+1\right) \bmod 3=0$ 👏

Ring (Aufg. 2)

(a) Charakterisierung

• Verbindungsgrad: 4

  Jeder Knoten verbindet sich mit vier Nachbaren.

• Durchmesser: 2

  

• min. Bisektionsbreite: 6

  Die minimale Bisektionsbreite ist wie folgt definiert:

  Schneidet man einen Graphen in zwei gleich große in sich zusammenhängende Teile und betrachtet die Menge der Kanten, die diesen Schnitt kreuzen, so bezeichnet man die Kardinalität der kleinsten Kantenmenge – über alle möglichen Schnitte – als minimale Bisektionsbreite.

  

(b) Art des Verbindungsnetzwerkes

Chordaler Ring mit Knotengrad 4

(c) Redundanz

Liegt Redundanz vor? Wenn ja, wieviele Verbindungsleitungen können ausfallen, bevoreine Verbindung zwischen zwei beliebigen Knoten nicht mehr geschalten werden kann?

• Es liegt Redundanz vor.

• Verbindungsgrad jedes Knotens ist 4 und die bidirektionale Leitungen werden verwendet

  $\Rightarrow$ Bis zu drei Leitungen können sausfallen und dennoch jeder Knoten von einem anderen erreicht werden

  (Allerdings kann beim Ausfall einer Kante der Durchmesser steigen, das heißt es könnten längere Wege notwendig sein.)

Zusammenfassung von Charakterisierung der Netzwerktopologien

• $N$: #Knoten