Rechnernetze
Home Nach oben

Ausfallsicherheit

Neben der Übertragungsleistung spielt die Ausfallsicherheit eines Systems eine große Rolle. In diesem Abschnitt soll untersucht werden, wie die Verfügbarkeit von Rechnernetzen durch die Bereitstellung alternativer Routen erhöht werden kann. Allerdings kann die Ausfallsicherheit in Netzen nur dann durch Umleitung von Daten erhöht werden, wenn der Routingalgorithmus dieses vorsieht.

Wir betrachten ein Netz mit N Knoten und untersuchen nur den Fall, daß zwischen zwei Knoten eine Verbindung existiert, wobei die Kapazität dieser Verbindung nicht berücksichtigt wird. Gesucht ist also die Wahrscheinlichkeit:

Zur Vereinfachung der Formeln nehmen wir im folgenden meist an, daß jede Leitung mit der gleichen Wahrscheinlichkeit p ausfällt; dieses läßt sich einfach auf den Fall erweitern, daß Leitungen unterschiedliche Ausfallwahrscheinlichkeiten haben. Darüber hinaus müssen die Ausfallwahrscheinlichkeiten als unabhängig angesehen werden, so daß die Gesamtwahrscheinlichkeit als Produkt der Einzelwahrscheinlichkeiten berechnet werden kann.

Besteht das Netz nur aus zwei Leitungen, die die Daten nacheinander übertragen, so erhält man die Ausfallwahrscheinlichkeit für die Fälle, daß eine oder beide Leitungen ausgefallen sind; einfacher bestimmt sich dieses aus der Formel 1–P[keine Leitung ausgefallen]. Es gilt also

.

Dieses läßt sich auf einen Pfad beliebiger Länge verallgemeinern.

Gibt es stattdessen r parallele Pfade der Länge 1 zwischen zwei Knoten A und B, so ist die Ausfallwahrscheinlichkeit gleich der Wahrscheinlichkeit, daß alle Pfade ausgefallen sind:

Gibt es r unabhängige Pfade zwischen zwei Knoten mit der Ausfallwahrscheinlichkeit so ist die gesamte Ausfallwahrscheinlichkeit das Produkt der einzelnen Wahrscheinlichkeiten, d.h.

Werden jedoch gleiche Leitungen von verschiedenen Wegen benutzt, so sind die Ausfallwahrscheinlichkeiten komplizierter zu berechnen. Man kann z.B. die Schnitte Sr zwischen zwei Knoten A und B verwenden, wobei die Anzahl der Schnitte zwischen A und B sein soll, die j Leitungen enthalten. N sei die Anzahl der Leitungen im Netz, so daß es Kombinationen von j Leitungen gibt, von denen jedoch nur die Knoten A und B trennen. Dann läßt sich offenbar berechnen:

Allerdings ist es i.allg. ein komplexes kombinatorisches Problem, sämtliche Schnitte eines Netzes zu finden. Sind die einzelnen Ausfallwahrscheinlichkeiten unterschiedlich, so kann dieses Verfahren bei größeren Netzen nicht mehr angewendet werden. Stattdessen läßt sich folgendes rekursive Verfahren anwenden, welches als Reduktion nach Hänseler bezeichnet wird.

Mit NA bezeichnen wir die Menge der Nachbarknoten von A, d.h. jener Knoten, die A über eine Verbindungsleitung direkt erreichen können. Man entferne den Knoten A aus dem Netz sowie sämtliche Verbindungen zu A. Kennt man jetzt die Ausfallwahrscheinlichkeiten zwischen den Nachbarknoten von A und dem Knoten B, so läßt sich die Ausfallwahrscheinlichkeit zwischen A und B rekursiv berechnen.

Dazu betrachten wir jede Teilmenge und berechnen zum einen die Wahrscheinlichkeit, daß die Verbindung zwischen A und allen Knoten in Kj ausgefallen ist, zum anderen die Wahrscheinlichkeit, daß die Verbindung zwischen allen Knoten in NA\Kj und B ausgefallen ist. Für die bedingte Wahrscheinlichkeit, daß die Verbindung zwischen A und B ausgefallen ist, falls die Verbindung zwischen NA\Kj und B ausgefallen ist, erhalten wir

.

Aufgrund des Satzes von der totalen Wahrscheinlichkeit erhält man dann:

Enthalten die Kj alle Kombinationen der Knoten aus NA, so gilt

Die erste Wahrscheinlichkeit in der Summe kann durch entsprechende Produktwahrscheinlichkeiten berechnet werden, da die Ausfallwahrscheinlichkeiten der einzelnen Leitungen als unabhängig angenommen werden. Im Falle gleicher Ausfallwahrscheinlichkeiten für alle Leitungen erhalten wir

Die zweite Wahrscheinlichkeit in der Summe ist für das um den Knoten A reduzierte Netz zu berechnen. Daher führt dieses auf ein etwas einfacheres Problem, wenngleich hier die Ausfallwahrscheinlichkeiten zwischen Knotenmengen zu bestimmen sind.