Rechnernetze

Leitungsbelastung

Wir haben bereits verschiedene Kenngrößen eines Rechnernetzes kennengelernt:

Kosten der Leitung (abhängig von Entfernung und Übertragungsleistung)

Datenfluß li zwischen zwei Stationen A->B

Voraussichtliche Wege W_i des Datenflußes l_i

Zulässige mittlere Verzögerung der Pakete bei der Übertragung

Aus diesen Parametern läßt sich in der Regel nicht geschlossen ein optimales Netz erzeugen. Um dennoch zu einem Ergebnis zu kommen, werden einige Heuristiken verwendet. So geht man von einem Netz mit offensichtlich vernünftiger Struktur aus und variiert einzelne Parameter, um Übertragungszeiten oder Kosten zu minimieren oder die Ausfallsicherheit zu maximieren.

Ist eine gegebene Verkehrsbeziehung (in e_ij) zwischen je zwei Knoten i und j gegeben, so läßt sich stets die Zulässigkeit dieses Verkehrs durch die Bedingung: e_k<1 für jede Leitung k ermitteln. Ist W_ik eine Indikatorfunktion für die Verbindung i und die Leitungen k, so läßt sich ebenfalls schreiben

Satz

Gilt für alle Leitungen k , so ist die i-te Verbindung zulässig.

Faßt man das Rechnernetz als einen Graphen auf, so müssen zwei Knoten A und B zusammenhängend sein, damit eine Verbindung zwischen beiden bestehen kann. Entfernt man einzelne Kanten (d.h. Verbindungsleitungen) so, daß A und B nicht mehr zusammenhängend sind, so wird die Menge dieser Kanten als Schnitt bezeichnet. In der Regel gibt es mehrere Schnitte, die zwei bestimmte Knoten A und B trennen. Sei Sr ein solcher Schnitt, und sei die gesamte Kapazität dieses Schnittes; würde man die Kanten irgendeines Schnitts Sr entfernen, so könnten die beiden Stationen A und B nicht mehr miteinander kommunizieren. Also ist das minimale Gr zugleich die maximale Datenkapazität (in Bit je Sekunde), die zwischen den Stationen A und B übertragen werden kann. Dieses wird in dem Satz von Ford-Fulkerson ausgedrückt.

Min-Cut-Max-Flow-Theorem

Werden A und B durch Schnitte S_r getrennt, und sei die gesamte Kapazität dieses Schnittes. Dann ist

die maximale Datenkapazität (in Bit je Sekunde), die zwischen den Stationen A und B übertragen werden kann.

ist eine Maßzahl, die die maximale Kapazität zwischen zwei Knoten A und B angibt. Wir hatten bereits andere Maßzahlen für Rechnernetze kennengelernt. So ist h die gesamte genutzte Kapazität aller Übertragungsleitungen in Paketen je Sekunde. Es gilt: l^.W=h, wobei W die mittlere Anzahl von Leitungen ist, über welche die Verbindungen geführt werden und l die gesamte Kapazität, die alle Verbindungen (in Paketen je Sekunde) übermitteln. Da m^.C_j die gesamte Kapazität der Übertragungsleitungen j (in Paketen je Sekunde) ist, ist die Summe

die gesamte Kapazität aller Übertragungsleitungen. Diese muß natürlich kleiner als die effektive Ausnutzung, also als h, sein.

Satz

Das Netz ist überlastet, wenn gilt

Dieses ist ein recht grobes Maß. Natürlich darf keine einzige Leitung überlastet sein, so daß folgt

Satz

Die Leitung j ist überlastet, wenn

Die hier entwickelten Kriterien sind eigentlich nur noch bei ‘klassischen‘ Rechnernetzen relevant. Moderne Netze verwenden in der Regel Hochleistungsverbindungen mit Übertragungsraten von mehreren hundert Gigabit je Sekunden. Hier stellt weniger die Kapazität der jeweiligen Leitungen als vielmehr die Verarbeitungsgeschwindigkeit von Paketen in den jeweiligen Knoten den Verkehrsengpaß dar.