DE102005040890B3

DE102005040890B3 - Iteratives Routing-Verfahren mit lastabhängiger Routing-Metrik

Info

Publication number: DE102005040890B3
Application number: DE200510040890
Authority: DE
Inventors: Martin Dr. Greiner; Wolfram Krause
Original assignee: Siemens Corp
Current assignee: Unify GmbH and Co KG
Priority date: 2005-08-29
Filing date: 2005-08-29
Publication date: 2007-03-22
Anticipated expiration: 2025-08-30
Also published as: WO2007025853A1

Abstract

Die Erfindung betrifft ein Verfahren zur Ermittlung von Pfaden in einem Kommunikationsnetz mit einer Mehrzahl von Knoten (Kl...6), die durch Links (L1...9) verbunden sind unter Verwendung einer Routing-Metrik. Die Routing-Metrik eines Pfades wird dabei bestimmt aus der Anzahl von über jeden Link des Pfades gehenden Pfaden zwischen den Knoten. Indem iterativ die Pfade aus der Routing-Metrik und die Routing-Metrik aus den Pfaden bestimmt werden, wird eine optimale Lastverteilung für ein kabelgebundenes Netzwerk erreicht.

Description

Die Erfindung betrifft ein Verfahren zur Ermittlung von Pfaden in einem eine Mehrzahl von Knoten umfassenden Kommunikationsnetz unter Verwendung einer Routing-Metrik. Weiterhin betrifft die Erfindung eine Vorrichtung und ein Computerprogrammprodukt zur Durchführung des Verfahrens.
In Kommunikationsnetzen werden Nachrichten vom jeweiligen Sender zu einem oder mehreren Empfängern übertragen. Hierbei umfasst das Kommunikationsnetz Knoten, welche Nachrichten versenden, empfangen und gegebenenfalls zu einem benachbarten Knoten weiterleiten. Die konkrete Ausgestaltung der Knoten sowie der Verbindungen zwischen benachbarten Knoten hängt vom betrachteten Netz ab. Im Internet beispielsweise sind Router über Leitungen miteinander verbunden, während in Funkkommunikationssystemen eine Funkschnittstelle benachbarte Funkstationen miteinander verbindet.
Sind Sender und Empfänger einer Nachricht nicht benachbart, so wird die Nachricht über einen Pfad, welcher über einen oder mehrere Knoten verläuft, übertragen. Um den Ablauf der Nachrichtenübertragung effizient zu gestalten, wird vor der Nachrichtenübertragung ein Pfad zwischen Sender und Empfänger ermittelt. Hierzu ist es bekannt, dass Knoten Routingtabellen speichern. Diese enthalten Informationen, welche die Entscheidungsgrundlage für die Festlegung der Wegewahl und Weiterleitung von Nachrichten im Netz bilden. Aufbau und Inhalt sowie die Aktualisierungsmechanismen von Routingtabellen sind im Wesentlichen vom eingesetzten Routing-Verfahren abhängig.
Bei der Ermittlung von Pfaden wird in der Regel eine Routing-Metrik verwendet. Mit dieser werden verschiedene Pfade bewertet und hierdurch die Entscheidung ermöglicht, welcher Pfad aus einer Mehrzahl an möglichen Pfaden verwendet werden soll.

Aus JP 07099490 A ist ein Routing-Verfahren bekannt, bei dem in die Routing-Metrik eine Größe, der sog. Routing-Vektor, eingeht, die Übertragungsgeschwindigkeit und Übertragungskosten für einen jeweiligen Link angibt. Aus der Summe der Routing-Vektoren der Links möglicher Pfade zwischen zwei Knoten kann der günstigste Pfad ermittelt werden.

Der Erfindung liegt die Aufgabe zugrunde, ein Verfahren zur Ermittlung von Pfaden in einem Kommunikationsnetz und eine Vorrichtung sowie ein Computerprogrammprodukt zum Durchführen dieses Verfahrens aufzuzeigen.

Diese Aufgabe wird durch ein Verfahren mit den Merkmalen des Anspruchs 1 und durch eine Vorrichtung mit Merkmalen von nebengeordneten Ansprüchen gelöst. Vorteilhafte Ausgestaltungen und Weiterbildungen sind Gegenstand von Unteransprüchen.

Bei dem erfindungsgemäßen Verfahren zur Ermittlung von Pfaden in einem eine Mehrzahl von Knoten umfassenden Kommunikationsnetz mit die Knoten verbindenden Links wird eine Routing-Metrik verwendet. In die Routing-Metrik geht eine Größe ein, welche aus der Anzahl an über einen Knoten verlaufenden Pfaden ermittelt wird.

Die Knoten des Kommunikationsnetzes sind durch Links verbunden. Diese Links können drahtlose Verbindungen sein. Alternativ können die Links auch tatsächlich vorhandene drahtgebundene Leitungen zwischen den Knoten sein.

Im Falle von drahtloser Kommunikation bestehen Links im Allgemeinen zwischen einem Knoten und jedem anderen Knoten, der in der Funkreichweite des Knotens ist.

Bei drahtgebundener Kommunikation bestehen Links nur dort, wo auch wirklich eine drahtgebundene Verbindung vorhanden ist.

Ein Pfad durch das Kommunikationsnetz verläuft von einem Start- oder Sendeknoten zu einem Ziel- oder Empfängerknoten.

Sind der Start- und der Zielknoten nicht benachbart, verläuft der Pfad über einen oder mehrerer weitere Knoten. Eine Routing-Metrik wird zur Bewertung von Pfaden eingesetzt, so dass unter Verwendung der Routing-Metrik zwischen alternativen Pfaden entschieden werden kann. So kann beispielsweise aus einer Mehrzahl an alternativen Pfaden zwischen einem bestimm ten Sender und einem bestimmten Empfänger derjenige Pfad verwendet werden, welcher den niedrigsten Wert der Routing-Metrik, d.h. die kürzeste Länge gemäß der Routing-Metrik, aufweist.

Die Größe, welche gemäß der Erfindung in die Routing-Metrik eingeht, wird aus der Anzahl von über einen Link verlaufenden Pfaden ermittelt.

Neben der beschriebenen Größe können auch weitere Größen in die Routing-Metrik eingehen. Insbesondere kann die beschriebene Größe in Bezug auf eine Mehrzahl von Links in die Routing-Metrik eingehen. So kann beispielsweise die Routing-Metrik gebildet werden, indem die beschriebene Größe aller Links, über welche der Pfad verläuft, addiert wird. Oder die Routing-Metrik kann gebildet werden, indem die beschriebene Größe aller Links, über welche der Pfad verläuft, und aller Links, welche zu den Links, über welche der Pfad verläuft, ein bestimmtes Verhältnis aufweisen, addiert wird.

In Weiterbildung der Erfindung wird für einen oder mehrere Knoten eine erste Summe aus der Anzahl von über den Link verlaufenden Pfaden bestimmt.

Vorzugsweise ergibt sich die Routing-Metrik eines Pfades aus der Summe der ersten Summen aller Links, über die der Pfad verläuft.

In Ausgestaltung der Erfindung handelt es sich um ein iteratives Verfahren, bei welchem abwechselnd die Pfade unter Verwendung der Routing-Metrik und die Routing-Metrik unter Verwendung der Pfade bestimmt wird. Dieses Vorgehen trägt der Tatsache Rechnung, dass bei der Bestimmung der Pfade die Routing-Metrik benötigt wird, während aber auch die Routing-Metrik von den bestimmten Pfaden abhängt.

Einer besonders vorteilhaften Ausgestaltung der Erfindung gemäß wird das iterative Verfahren durchgeführt, bis der Wert einer Größe konvergiert. Die iterativen Verfahrensschritte können so lange wiederholt werden, bis Konvergenz erreicht ist, d.h. sich z.B. der Ende-zu-Ende-Datendurchsatz und/oder die Ende-zu-Ende-Zeitverzögerung, oder die Pfade und/oder die Routing-Metrik von Berechnung zu Berechnung nicht mehr oder kaum mehr ändern.

Vorteilhaft ist es, wenn die Erfindung auf ein Kommunikationsnetz angewandt wird, bei welchem die Knoten drahtgebunden miteinander kommunizieren, wie z.B. im Internet oder einem Ethernet.

Die erfindungsgemäße Einrichtung weist Mittel auf zur Ermittlung von Pfaden in einem eine Mehrzahl von Knoten umfassenden Kommunikationsnetz mit die Knoten verbindenden Links unter Verwendung einer Routing-Metrik, wobei in die Routing-Metrik eine Größe eingeht, welche aus der Anzahl an über einen Link verlaufenden Pfaden ermittelt wird. Bei der erfindungsgemäßen Einrichtung kann es sich z.B. um einen Knoten des Kommunikationsnetzes handeln, oder auch um eine zentrale Einrichtung, welche für die Bestimmung von Pfaden verantwortlich ist und die Knoten über die ermittelten Pfade informiert.

Das erfindungsgemäße Computerprogrammprodukt weist Mittel auf zur Ermittlung von Pfaden in einem eine Mehrzahl von Knoten umfassenden Kommunikationsnetz mit die Knoten verbindenden Links unter Verwendung einer Routing-Metrik, wobei in die Routing-Metrik eine Größe eingeht, welche aus der Anzahl an über einen Link verlaufenden Pfaden ermittelt wird. Es kann z.B. auf einem Knoten des Kommunikationsnetzes zum Einsatz kommen.

Unter einem Computerprogrammprodukt wird im Zusammenhang mit der vorliegenden Erfindung neben dem eigentlichen Computerprogramm (mit seinem über das normale physikalische Zusammenspiel zwischen Programm und Recheneinheit hinausgehenden technischen Effekt) insbesondere ein Aufzeichnungsträger für das Computerprogramm, eine Dateisammlung, eine konfigurierte Recheneinheit, aber auch beispielsweise eine Speichervorrichtung oder ein Server, auf der bzw. dem zum Computerprogramm gehörende Dateien gespeichert sind, verstanden.

Sowohl die erfindungsgemäße Einrichtung als auch das erfindungsgemäße Computerprogrammprodukt eignen sich insbesondere zur Durchführung des erfindungsgemäßen Verfahrens, wobei dies auch auf die Ausgestaltungen und Weiterbildungen zutreffen kann. Hierzu können sie weitere geeignete Mittel umfassen.

Im Folgenden wird die Erfindung anhand eines Ausführungsbeispiels näher erläutert. Dabei zeigen:
1: ein Netzwerk bestehend aus sechs Knoten,
2a bis 2g: Schritte eines ersten erfindungsgemäßen Verfahrensablaufs,
3a und 3b: Schritte eines zweiten erfindungsgemäßen Verfahrensablaufs.
1 zeigt ein Netzwerk bestehend aus einem ersten bis sechsten Knoten K1...6. Die Knoten K1...6 des Netzwerkes kommunizieren miteinander über drahtgebundene Links L1...9 wie z.B. Ethernet-Verbindungen. Durch Linien sind diejenigen Knoten K1...6 miteinander verbunden, die direkt miteinander kommunizieren können. Die Linien repräsentieren also die in diesem Beispiel tatsächlich existierenden drahtgebundenen Verbindungen, also Kabel. Die Erfindung kommt vorzugsweise in größeren Netzwerken zum Einsatz, die Erläuterung des Vorgehens vereinfacht sich jedoch für kleinere Netzwerke wie das in 1 dargestellte.
Die folgenden neun Links L1...9 verbinden dabei die folgenden Knoten K1...6:

– der erste Link L1 den ersten und zweiten Knoten K1, K2
– der zweite Link L2 den ersten und vierten Knoten K1, K4
– der dritte Link L3 den ersten und sechsten Knoten K1, K6
– der vierte Link L4 den ersten und dritten Knoten K1, K3
– der fünfte Link L5 den fünften und sechsten Knoten K5, K6
– der sechste Link L6 den zweiten und sechsten Knoten K2, K6
– der siebte Link L7 den dritten und sechsten Knoten K3, K6
– der achte Link L8 den vierten und sechsten Knoten K4, K6
– der neunte Link L9 den dritten und vierten Knoten K3, K4

Ein Pfad in dem Netzwerk verläuft von einem Startknoten zu einem Zielknoten über keinen, einen oder mehrere weitere Knoten, und daher über einen oder mehrere Links. So kann beispielsweise ein Pfad zwischen dem ersten Knoten K1 und dem vierten Knoten K4 direkt über den zweiten Link L2 oder mit Weiterleitung durch den sechsten Knoten K6 über den dritten und den achten Link L3, L8 verlaufen.
Im Folgenden wird ein Verfahren vorgestellt, bei welchem Pfade durch das Netzwerk für alle Kombinationen von Start- und Zielknoten bestimmt werden. D.h. es wird eine vollständige Routing-Tabelle R für das Netzwerk ermittelt. Da in der Regel mehrere potentielle Pfade zwischen einem bestimmten Startknoten und einem bestimmten Zielknoten existieren, erfolgt eine Gewichtung bzw. Bewertung von Pfaden durch die Länge der Pfade, die wiederum durch eine Routing-Metrik festgelegt wird. Ein bekanntes Beispiel für eine Routing-Metrik ist die hopcount Metrik, bei der sich die Länge eines Pfades als die Anzahl der von dem Pfad benutzten Hops ergibt. In diesem Fall werden kurze Pfade gegenüber längeren bevorzugt.
Zur Berechnung der im Folgenden verwendeten Routing-Metrik wird für jeden Link L1...9 die Anzahl der Pfade bestimmt, die über den jeweiligen Link L1...9 verlaufen. Diese Größe wird im Folgenden als B_L bezeichnet, wobei L der Index des jeweiligen Links L1...9 ist. Die auf dieser Routing-Metrik basierende Länge eines Pfades ergibt sich als Summe aus den B_Ls der Links L1...9, entlang derer ein Pfad verläuft.
Diese Wahl der Routing-Metrik liegt darin begründet, dass bei einem drahtgebundenen Netz die Größe B_L am besten geeignet ist, die Belastung eines Links entlang eines Pfades zu beschreiben. Dies liegt daran, dass bei solchen Netzen die Knoten K1...6 des Netzwerks in den meisten Fällen Router sind, die zur Weiterleitung großer Datenmengen ausgelegt sind. Somit werden nicht die Knoten K1...6 an sich, sondern die Verbindungen zwischen den Knoten, also die Links L1...9, zur Engstelle der Übertragung.
Die auf der Routing-Metrik basierende Länge des Pfades zwischen dem dritten und vierten Knoten K3 und K4, der über den ersten Knoten K1, d.h. über den vierten und zweiten Link L4, L2 verläuft, lautet beispielsweise: L314 = B4 + B2
Die Pfade werden in eine Routing-Tabelle in Form einer Matrix eingegeben, wobei jede Spalte der Matrix einem bestimmten Zielknoten entspricht und jede Zeile der Matrix einem bestimmten Knoten K1...6, welcher eine Nachricht an diesen Zielknoten sendet oder weiterleitet. Ein Eintrag z für das Matrixelement mit der Position (x, y) bedeutet, dass der Knoten x eine Nachricht, welche für den Knoten y bestimmt ist, an den Knoten z zu versenden hat. Aus dem sendenden oder weiterleitenden Knoten x und dem jeweiligen direkten nächsten Knoten z ergibt sich der Link L1...9, der durch diese Sendung oder Weiterleitung belastet wird.
Zu Beginn des Verfahrens werden alle B_L auf den Wert 1 gesetzt. Dies entspricht der hop-count Metrik. Als Initialisierungs-Wert kann auch ein anderer Wert als 1 verwendet werden, das Ergebnis des Verfahrens ist weitgehend unabhängig von diesem Startwert. In die Routing-Tabelle wird ein Wert von (–1) eingetragen, wenn noch kein Pfad ermittelt wurde. Diese Situation zu Beginn entspricht der in der 2a dargestellten. B_L ist in 2a und in den folgenden Figuren als Vektor dargestellt, wobei B_L = (B₁; B₂: B₃: B₄: B₅: B₆: B₇; B₈; B₉) ist. In der Routing-Tabelle R sind zu Beginn alle Einträge mit dem Wert (–1) belegt.
Im ersten Schritt, in 2b dargestellt, werden alle Pfade betrachtet, die zum sechsten Knoten K6 führen, d.h. bei welchen der sechste Knoten K6 der Zielknoten ist. Da alle Knoten K1...6 mit dem sechsten Knoten K6 verbunden sind, senden sie eine Nachricht, die für den sechsten Knoten K6 bestimmt ist, direkt an diesen. Daher weist die letzte Spalte der Routing-Tabelle R für alle Zeilen eine 6 auf. Betrachtet man den dritten und vierten Knoten K3 und K4, so wäre es beispielsweise auch möglich, dass diese eine für den sechsten Knoten K6 bestimmte Nachricht an den ersten Knoten K1 senden, welcher die Nachricht dann an den sechsten Knoten K6 weiterleitet. Im Allgemeinen existieren zwischen zwei bestimmen Knoten K1...6 eine Mehrzahl an möglichen Pfaden. Dies bedeutet, dass bei der Erstellung der Routing-Tabelle R eine Auswahl zwischen den alternativen Pfaden getroffen werden muss. Diese Auswahl erfolgt unter Verwendung der oben erläuterten Routing-Metrik, d.h. es wird bei der Auswahl zwischen den Pfaden die Länge der Pfade berücksichtigt, welche gemäß der im vorhergehenden Schritt ermittelten Größe B_L bestimmt wird.
Für den Pfad zwischen dem dritten Knoten K3 und dem sechsten Knoten K6 ergibt sich folgende Betrachtung:
Direkter Pfadverlauf vom dritten Knoten K3 zum sechsten Knoten K6: die Länge für diesen Pfad ist B₇ = 1, da der Pfad nur über den siebten Link L7 verläuft.
Pfadverlauf zwischen dem dritten Knoten K3 und dem sechsten Knoten K6 über den ersten Knoten K1: die Länge für diesen Pfad ist B₄ + B₃ = 2, da der Pfad über den vierten und dritten Link L4, L3 verläuft, deren B_L gemäß 2a je den Wert 1 aufweist.
Pfadverlauf zwischen dem dritten Knoten K3 und dem sechsten Knoten K6 über den ersten und zweiten Knoten K1, K2: die Länge für diesen Pfad ist B₄ + B₁ + B₆ = 3, da der Pfad über die Knoten 1 und 2 verläuft, d.h. über den vierten, ersten und sechsten Link L4, L1, L6.
Es wird der Pfad mit der kleinsten Länge gemäß der Routing-Metrik ausgewählt. Dies entspricht dem direkten Pfad.
Für jeden Eintrag in der Routing-Tabelle R werden somit alle möglichen Pfade mit der Routing-Metrik bewertet und der Pfad mit dem niedrigsten Wert für die Länge gemäß der Routing-Metrik ausgewählt und in die Routing-Tabelle R eingetragen. Die Bewertung der verschiedenen Pfade erfolgt hierbei unter Verwendung der im letzten Schritt bestimmten Werte der Routing-Metrik.
Nach der Bestimmung der Routing-Tabelle R wird die Größe B_L berechnet. Zur Berechnung von B_L wird zuvor die Größe B_L,6 berechnet. Hierbei handelt es sich um den Anteil von B_L, bei welchem der sechste Knoten K6 der Zielknoten ist. Da gemäß der Routing-Tabelle R genau ein Pfad zum sechsten Knoten K6 vom ersten Knoten K1 ausgeht und kein Pfad existiert, welcher über den ersten Knoten K1 zum sechsten Knoten K6 verläuft, steht an dritter Stelle für den dritten Link L3 eine 1. Gleiches gilt auch für die weiteren Knoten K2...5, wodurch an den entsprechenden Stellen für den fünften bis achten Link L5...8 je eine 1 steht. Die restlichen Werte werden zu 0. Da bislang nur der sechste Knoten K6 als Zielknoten betrachtet wurde, ist B_L gleich B_L,6.
Im zweiten Schritt wird, in 2c dargestellt, der erste Knoten K1 als Zielknoten betrachtet. Wie oben beschrieben, werden die Einträge in die Routing-Tabelle R ermittelt, indem alle möglichen Pfade zum ersten Knoten K1 mit der Routing-Metrik bewertet werden und der gemäß der Routing-Metrik günstigste Pfad ausgewählt wird. Demgemäß sendet der sechste Knoten K6 eine für den ersten Knoten K1 bestimmte Nachricht direkt an diesen, daher steht an der Position (6,1) der Routing-Tabelle R eine 1. Entsprechendes gilt auch für die anderen dem ersten Knoten K1 benachbarten Knoten K2...4. Der fünfte Knoten K5 sendet eine für den ersten Knoten K1 bestimmte Nachricht an den sechsten Knoten K6, daher steht an der Position (5,1) der Routing-Tabelle R eine 6.
Nun wird zuerst B_L,1 berechnet. Hierbei handelt es sich um den Anteil von B_L, bei welchem der erste Knoten K1 der Zielknoten ist. Durch eine Sendung des ersten an den ersten Knoten K1 wird kein Link belastet. Eine Sendung des zweiten Knoten K2 an den ersten Knoten K1 nimmt den direkten ersten Link L1. Sendungen des dritten, vierten und sechsten Knotens K3, K4, K6 nehmen ebenfalls die direkten Links L4, L2, L3. Eine Sendung des fünften Knotens K5 muss gemäß Routing-Tabelle R über den fünften Link L5 an den sechsten Knoten K6 gehen und wird in Folge, ebenfalls gemäß der Routing-Tabelle R, den direkten Weg zum ersten Knoten K1 über den dritten Link L3 gehen. Der dritte Link L3 wird also doppelt belastet durch Sendungen, die vom sechsten und fünften Knoten K6, K5 ausgehen. Daher ergeben sich die folgenden Einträge: B1,1 = B2,1 = B4,1 = B5,1 = 1 B3,1 = 2
B_L wird berechnet, indem B_L,6 aus 2b, d.h. der Anteil von B_L, bei dem der sechste Knoten K6 der Zielknoten ist, und B_L,1 aus 2c, d.h. der Anteil von B_L, bei dem der erste Knoten K1 der Zielknoten ist, addiert werden.
In 2d ist der dritte Schritt dargestellt, bei dem der zweite Knoten K2 als Zielknoten betrachtet wird, in der 2e ist der vierte Schritt dargestellt, bei dem der dritte Knoten K3 als Zielknoten betrachtet wird, in der 2f ist der fünfte Schritt dargestellt, bei dem der vierte Knoten K4 als Zielknoten betrachtet wird, und in der 2g ist der sechste Schritt dargestellt, bei dem der fünfte Knoten K5 als Zielknoten betrachtet wird. Jeweils wird zuerst die Routing-Tabelle R weiter ausgefüllt, indem unter Verwendung der Routing-Metrik bestimmt wird, zu welchem Knoten eine Nachricht, die für den jeweiligen Zielknoten bestimmt ist, zu senden ist. Bei dieser Bestimmung wird das im Vorschritt bestimmte B_L verwendet, d.h. die Einträge werden unter Berücksichtigung der durch B_L vorgegebenen Routing-Metrik ausgewählt. Im An schluss wird basierend auf der neuen Routing-Tabelle R die Größe B_L berechnet.
Im Beispiel zeigt sich, dass durch die Belastung des sechsten Links L6, B₆ = 5 durch das Routing mit dem zweiten Knoten L2 als Zielknoten in 2d, später auf andere Routen ausgewichen wird, so in 2f für den vierten Knoten als Zielknoten.
Bei dem beschriebenen Vorgehen handelt es sich um ein iteratives Verfahren, da einerseits bei der Bestimmung der Pfade und somit bei Erstellung der Routing-Tabelle R die Routing-Metrik über die Größe B_L eingeht, und andererseits in die Routing-Metrik über die Größe B_L die bestimmten Pfade eingehen. Somit werden abwechselnd die Routing-Tabelle R und die Routing-Metrik aktualisiert.
In den 2b bis 2g wurde eine erste Berechnungsrunde zur Bestimmung der Pfade durch das Netzwerk aufgezeigt, wobei mit der Betrachtung des sechsten Knotens K6 als Zielknoten begonnen wird und über die weiteren Knoten K1...5 fortgefahren wird. Alternativ kann auch eine andere Reihenfolge verwendet werden. Im Anschluss an die erste Runde kann eine zweite Runde durchgeführt werden, wobei erneut mit dem sechsten Knoten K6 als Zielknoten begonnen wird. Somit wird im ersten Schritt der zweiten Runde die letzte Spalte der Routing-Tabelle R neu bestimmt, wobei die Routing-Metrik gemäß der Größe B_L aus dem letzten Schritt der ersten Runde zum Einsatz kommt. Im Anschluss wird B_L bestimmt. Entsprechend wird auch in Bezug auf die weiteren Knoten K1...5 als Zielknoten vorgegangen, wobei jeweils die Routing-Metrik dem jeweils vorhergehenden Schritt der zweiten Runde entnommen wird.
Bei Bedarf können weitere Berechnungsrunden folgen. Im Laufe der Runden konvergiert das Ergebnis, d.h. die Einträge der Routing-Tabelle R und die Größe B_L ändern sich nicht oder kaum mehr. Bereits nach zwei Runden ist in der Regel eine selbst-konsistente Routing-Tabelle R berechnet. Bei weiteren Iterationsrunden ändern sich zwar noch die Einträge der Routing-Tabelle R, jedoch findet keine wesentliche Erhöhung der Leistung des Netzwerkes mehr statt, gemessen z.B. an dem Ende-zu-Ende Datendurchsatz und der Ende-zu-Ende Zeitverzögerung. Die Anzahl der Runden, welche zum Erreichen der Konvergenz nötig sind, hängt von der Größe des betrachteten Netzwerks ab.
In den 3a und 3b sind die Schritte eines alternativen Berechnungsablaufs abgebildet. Der Initialisierungszustand entspricht dem der 2a. In der ersten Runde wird im ersten Schritt der sechste Knoten K6 als Zielknoten betrachtet und es wird die letzte Spalte der Routing-Tabelle R ausgefüllt. Zur Auswahl zwischen den verschiedenen möglichen Pfaden wird B_L aus der vorhergehenden Runde, d.h. B_L aus der Initialisierung verwendet. Im Anschluss wird B_L nicht neu berechnet. Vielmehr wird im zweiten Schritt der erste Knoten K1 als Zielknoten betrachtet und die erste Spalte der Routing-Tabelle R bestimmt, wobei wieder B_L aus der Initialisierung verwendet wird. Entsprechendes erfolgt auch in Bezug auf die weiteren Knoten K2...5 als Zielknoten. Für alle Einträge der Routing-Tabelle R der ersten Runde werden somit die Werte B_L der Initialisierung verwendet.
Nachdem die Routing-Tabelle R wie in 3a dargestellt im Rahmen der ersten Runde bestimmt wurde, erfolgt basierend auf dieser Routing-Tabelle R die Berechnung von B_L, wie in 3a dargestellt.
Manche Einträge der Routing-Tabelle R weisen nach der ersten Runde zwei Einträge auf. Dies tritt dann auf, wenn die Routing-Metrik für diese beiden Pfade gleich ist, d.h. die Pfade entartet sind. Diese Situation kann grundsätzlich auch bei dem anhand der 2a bis 2g geschilderten Verfahren auftreten. Diese Gleichwertigkeit mehrerer Routen zwischen zwei bestimmten Knoten verschwindet in der Regel bei den folgenden Berechnungsrunden.
In 3b ist das Ergebnis der zweiten Runde gezeigt. In der zweiten Runde werden zuerst für den sechsten Knoten K6, dann für den ersten Knoten K1, dann für den zweiten Knoten K2, dann für den dritten Knoten K3, dann für den vierten Knoten K4, und schließlich für den fünften Knoten K5 als Zielknoten die Einträge für die Routing-Tabelle R bestimmt, wobei jeweils die zum Abschluss der ersten Runde berechneten B_L zur Bewertung der Routen herangezogen werden. Nach Bestimmung der Routing-Tabelle R der zweiten Runde wird B_L, wie in 3b dargestellt, basierend auf dieser Routing-Tabelle R berechnet.
Die zweite in den 3a und 3b dargestellte Variante des erfindungsgemäßen Verfahrens weist den Vorteil auf, dass der Berechnungsaufwand niedriger ist, da lediglich einmal pro Runde B_L bestimmt werden muss, und nicht wie in der ersten Variante vorgesehen, nach jedem Schritt. Jedoch ist in der Regel bei der zweiten Variante eine größere Anzahl an Runden nötig, bevor Konvergenz erreicht wird.
Die berechneten Pfade der Routing-Tabelle R der 2 und 3 werden zur Versendung von Nachrichten zwischen den Knoten K1...6 verwendet. Eine Neuberechnung der Pfade ist dann nötig, wenn sich die Topologie des Netzwerkes ändert, d.h. wenn sich die Nachbarschaftsbeziehungen zwischen den Knoten ändern oder wenn Knoten neu zu dem Netzwerk hinzukommen oder wenn Knoten das Netzwerk verlassen.
Zur Bestimmung der Pfade wird davon ausgegangen, dass die Einrichtung, die die Berechnung durchführt, die vollständige Topologie des Netzwerkes kennt. Dies kann z.B. dadurch realisiert werden, dass jeder Knoten Informationen über seine Nachbarschaft sammelt und diese ihm bekannte „link state" Information an seine Nachbarn oder an eine zentrale Einrichtung weitergibt. Das Verfahren, nach dem Informationen über die Netzwerktopologie gesammelt und weitergegeben werden, hat keinen Einfluss auf das Verfahren zur Ermittlung der Pfade.
Die Berechnung der Pfade kann durch einen Knoten des Netzwerkes erfolgen, welcher das Ergebnis an die anderen Knoten weiterleitet. Auch eine zentrale Einrichtung, die die Topologie des Netzwerkes kennt, kann die Bestimmung der Pfade gemäß den vorgestellten Verfahren durchführen. Weiterhin ist es möglich, dass eine Mehrzahl von Knoten oder jeder Knoten des Netzwerkes die vorgestellten Berechnungen durchführen. Da die Knoten von der gleichen Netzwerktopologie ausgehen und den gleichen Algorithmus zur Berechnung der Pfade verwenden, ermitteln sie auch das gleiche Ergebnis.
Anstelle der berechneten Routing-Tabelle R kann auch die berechnete Größe B_L weitergegeben werden, so dass die Knoten auf Basis der empfangenen Größe B_L die Routing-Tabelle R bestimmen.
Die beschriebenen Verfahren, bei denen die Routing-Metrik bzw. die Länge der Pfade aus der Summe der B_Ls der sendenden Knoten eines Pfades ermittelt werden, resultieren in der Ermittlung von Pfaden, bei denen kritische Knoten, über die eine Vielzahl von Pfaden verlaufen und die dementsprechend stark ausgelastet sind, entlastet werden. So weichen z.B. gemäß dem erfindungsgemäßen Verfahren ermittelte Pfade auf Randknoten aus, wodurch die Pfade zwar gegebenenfalls länger sind, wenn man nur die Anzahl der verwendeten Links betrachtet, als bei Verwendung von Knoten in der Mitte des Netzwerkes, jedoch eine geringere Auslastung der Pfade eintritt, was sich in einer geringeren Länge gemäß der Routing-Metrik äußert. Die Verwendung der erfindungsgemäßen Routing-Metrik resultiert in einem erhöhten Ende-zu-Ende Datendurchsatz und einer verringerten Ende-zu-Ende Zeitverzögerung.
Das erfindungsgemäße Verfahren kann in beliebigen Netzwerken, in denen die Knoten miteinander kommunizieren, eingesetzt werden. Besonders vorteilhaft ist der Einsatz in drahtgebundenen Kommunikationssystemen wie z.B. dem Internet oder Ethernet-Netzwerken.

Claims

Verfahren zur Ermittlung von Pfaden in einem eine Mehrzahl von Knoten (K1...6) umfassenden Kommunikationsnetz mit die Knoten (K1...6) verbindenden Links (L1...9) unter Verwendung einer Routing-Metrik, in die eine Größe (B_L) eingeht, die aus der Anzahl von über einen Link (L1...9) verlaufenden Pfaden ermittelt wird.
Verfahren nach Anspruch 1, bei dem für einen oder mehrere Links (L1...9) eine erste Summe (B_L) aus der Anzahl an über den Link (L1...9) verlaufenden Pfaden bestimmt wird.
Verfahren nach Anspruch 2, bei dem sich die Routing-Metrik eines Pfades ergibt aus der Summe der ersten Summen (B_L) aller Links (L1...9), über die der Pfad verläuft.
Verfahren nach einem der vorangehenden Ansprüche, bei dem es sich um ein iteratives Verfahren handelt, bei welchem abwechselnd die Pfade unter Verwendung der Routing-Metrik und die Routing-Metrik unter Verwendung der Pfade bestimmt wird.
Verfahren nach Anspruch 4, bei dem das iterative Verfahren durchgeführt wird, bis der Wert einer Größe, insbesondere des Ende-zu-Ende-Datendurchsatzes und/oder der Ende-zu-Ende-Zeitverzögerung, konvergiert.
Verfahren nach einem der vorangehenden Ansprüche, bei dem die Knoten (K1...6) des Kommunikationsnetzes drahtgebunden miteinander kommunizieren.
Einrichtung mit Mitteln zur Ermittlung von Pfaden in einem eine Mehrzahl von Knoten (K1...6) umfassenden Kommunikationsnetz mit die Knoten (K1...6) verbindenden Links (L1...9) unter Verwendung einer Routing-Metrik, wobei in die Routing-Metrik eine Größe (B_L) eingeht, welche aus der Anzahl an über einen Link (L1...9) verlaufenden Pfaden ermittelt wird.
Computerprogrammprodukt mit Mitteln zur Ermittlung von Pfaden in einem eine Mehrzahl von Knoten (K1...6) umfassenden Kommunikationsnetz mit die Knoten (K1...6) verbindenden Links (L1...9) unter Verwendung einer Routing-Metrik, wobei in die Routing-Metrik eine Größe eingeht, welche aus der Anzahl an über einen Link (L1...9) verlaufenden Pfaden ermittelt wird.