Breitbandige Netze

Optimierung von statischen Routingverfahren in speziellen Graphenklassen

Als Hauptunterscheidungsmerkmal der bisher publizierten Routingverfahren gilt die Adaptionseigenschaft des jeweiligen Verfahrens bezüglich des aktuellen Netzzustandes im laufenden Betrieb eines Kommunikationsnetzes. Während bei adaptiven Routingverfahren, sie werden in der Literatur auch dynamische Verfahren genannt, Veränderungen des Netzzustandes (z.B. Kantenausfälle) in den aktuellen Inhalt der Routingtabellen einfließen, wirken sich bei den nicht-adaptiven Routingverfahren Veränderungen des Netzzustandes nicht auf die Inhalte der Routingtabellen aus. Wegen den statischen Eigenschaften ihrer Routingtabellen werden sie deshalb auch statische Routingverfahren genannt. Obwohl in den letzten Jahren statische Routingverfahren häufig durch dynamische Verfahren substituiert wurden, präferieren Anwender bisher und in absehbarer Zukunft bei zeitkritischen Anwendungen die statischen Routingverfahren. Bei solchen Anwendungen, wie z.B. dem in der Telekommunikation eingesetzten Zeichengabesystem Nummer 7 (SS7), kann nämlich die zeitliche Verzögerung, bis auch weit entfernte Knoten den Ausfall einer Kante in ihrer Routingtabelle adaptieren, nicht akzeptiert werden.

Jedoch können auch sehr leistungsfähige Routingalgorithmen nur dann ihre Stärke voll entfalten, wenn ihnen die Anordnung der Netzknoten und der diese zu einem Netz verknüpfenden Netzkanten nicht kontraproduktiv entgegenwirkt. Deshalb wird eine andere Art der Optimierung bereits bei der Gestaltung der jeweiligen Netztopologie einsetzt. Dabei versucht man, durch eine "günstige" Anordnung der Verbindungen der Netzknoten die Voraussetzungen dafür zu schaffen, dass geeignete Algorithmen auch bei eventuellen Kantenausfällen immer einen kürzesten Weg vom Quell- zum Zielrechner bestimmen. Aber auch eine Beschränkung der Anzahl an "Zwischenknoten", die eine Nachricht vom Quell- zum Zielrechner passieren darf, setzen eine entsprechende Netztopologie voraus.

Für beliebige Graphen gibt es kein statisches Routingverfahren, das bezüglich Zyklenfreiheit (ZF) und kürzester Wege (SP) auch bei Kantenausfällen noch ZF-SP-optimal ist. Von dieser Erkenntnis ausgehend, wurden spezielle Graphenklassen erforscht, die bezüglich ausgewählter Kriterien ein optimales Routing ermöglichen. Ferner wurden praxis-bezogene Kriterien für suboptimale Graphenklassen definiert. Dabei wurde gleichzeitig versucht, die hohe Kantenkomplexität von vollvermaschten Graphen zu reduzieren, ohne sich dabei wesentlich von deren positiven Eigenschaften zu entfernen.

Für solche suboptimalen Graphen wurde auch die als "der prozentuale Anteil an allen Nachrichten-Routingvorgängen (q-...-z), für die die Routingtabellen eines Graphen auch nach einem Kantenausfall einen aktuellen kürzesten Weg enthalten" definierte Effizienz untersucht.

Ergänzend dazu wurde nach Verfahren geforscht, mit denen für einen beliebigen Graph G' festgestellt werden kann, ob er zu einem optimalen bzw. suboptimalen Graphen Go bzw. Gs isomorph ist. Für den Praxiseinsatz wurden Algorithmen entwickelt und implementiert, die für einen Teilgraphen Gt von Gs eine strukturerhaltende (d.h. kantenerhaltende) Abbildung liefern.


Prof. Firoz Kaderali Druckansicht