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 Computerpro ^¬ grammprodukt 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 Funkstati ^¬ onen miteinander verbindet .

Sind Sender und Empfänger einer Nachricht nicht benachbart , so wird die Nachricht über einen Pfad, welcher über einen o- der 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 Wei ^¬ terleitung 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 bewer-

tet und hierdurch die Entscheidung ermöglicht , welcher Pfad aus einer Mehrzahl an möglichen Pfaden verwendet werden soll .

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 wird eine Routing-Metrik verwendet . In die Routing- Metrik geht eine Größe ein, welche aus der Anzahl an über ei ^¬ nen Knoten verlaufenden Pfaden ermittelt wird .

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 bestimmten 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 an über einen Knoten verlaufen- den Pfaden ermittelt . Neben der Anzahl an über einen Knoten verlaufenden Pfaden können auch andere Werte oder Parameter in die Ermittlung der Größe einbezogen werden, so wie z . B .

zusätzlich die Anzahl an von dem Knoten ausgehenden Pfaden, d. h . zusätzlich die Anzahl der Pfade, bei welchen der jeweilige Knoten der Startknoten ist . Die Anzahl an über einen Knoten verlaufenden Pfaden und von dem Knoten ausgehenden Pfaden zu verwenden, entspricht der Betrachtung, wie oft ein bestimmter Knoten sendender Bestandteil eines Pfades ist und beschreibt somit eine Auslastung des Knotens .

Neben der beschriebenen Größe können auch weitere Größen in die Routing-Metrik eingehen . Insbesondere kann die beschrie ^¬ bene Größe in Bezug auf eine Mehrzahl von Knoten in die Rou ^¬ ting-Metrik eingehen . So kann beispielsweise die Routing- Metrik gebildet werden, indem die beschriebene Größe aller Knoten, über welche der Pfad verläuft , addiert wird . Oder die Routing-Metrik kann gebildet werden, indem die beschriebene Größe aller Knoten, über welche der Pfad verläuft , und aller Knoten, welche zu den Knoten, ü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 an über den Knoten verlaufenden Pfaden und von dem Knoten ausgehenden Pfaden bestimmt , für jeden Nachbarknoten des jeweiligen Knotens eine zweite Summe aus der Anzahl an über den jeweiligen Nachbarknoten verlaufenden Pfaden und von dem jeweiligen Nachbarknoten ausgehenden Pfaden bestimmt , und eine dritte Summe aus den zweiten Summen aller Nachbarknoten des Knotens und der ersten Summe bestimmt .

Vorzugsweise ergibt sich die Routing-Metrik eines Pfades aus der Summe der dritten Summe aller Knoten, über welche der Pfad verläuft , oder aus der Summe der dritten Summe aller Knoten, über welche der Pfad verläuft und der dritten Summe des Sendeknotens des Pfades . Im zweiten Fall werden die drit ^¬ ten Summen aller Knoten, welche entlang dem Pfad senden, summiert , d . h . die dritten Summen des ursprünglichen Senders und

der Zwischenknoten zwischen dem ursprünglichen Sender und dem Empfänger .

In Ausgestaltung der Erfindung handelt es sich um ein itera- tives Verfahren, bei welchem abwechselnd die Pfade unter Ver ^¬ wendung 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 Rou ^¬ ting-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 Kommunikati ^¬ onsnetz angewandt wird, bei welchem die Knoten per Funk miteinander kommunizieren, wie z . B . auf ein Multihop Adhoc- FunkkommunikationsSystem.

Die erfindungsgemäße Einrichtung weist Mittel auf zur Ermitt ^¬ lung von Pfaden in einem eine Mehrzahl von Knoten umfassenden Kommunikationsnetz unter Verwendung einer Routing-Metrik, wobei in die Routing-Metrik eine Größe eingeht , welche aus der Anzahl an über einen Knoten 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 unter Verwendung einer Routing-Metrik, wobei in die Routing-Metrik eine Größe eingeht , welche aus der Anzahl an über einen Knoten verlaufenden Pfaden ermittelt wird . Es kann z . B . auf einem Knoten des Kommu ^¬ nikationsnetzes zum Einsatz kommen .

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

Sowohl die erfindungsgemäße Einrichtung als auch das erfin- dungsgemäß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ührungsbei ^¬ spiels näher erläutert . Dabei zeigen :

Figur 1 : ein Netzwerk bestehend aus sechs Knoten,

Figuren 2a bis 2h : Schritte eines ersten erfindungsgemäßen

Verfahrensablaufs ,

Figuren 3a und 3b : Schritte eines zweiten erfindungsgemäßen

Verfahrensablaufs .

Figur 1 zeigt ein Netzwerk bestehend aus den Knoten 0 , 1 , 2 , 3, 4 und 5. Die Knoten des Netzwerkes kommunizieren miteinan-

der, wobei ein gemeinsames Übertragungsmedium verwendet wird, wie z . B . eine gemeinsame Funkfrequenz . Durch Linien sind benachbarte Knoten miteinander verbunden, d . h . diejenigen Knoten, welche direkt miteinander kommunizieren können . Der Kno- ten 0 ist benachbart zu den Knoten 1 , 2 , 3 , 4 und 5 , der Kno ^¬ ten 1 ist benachbart zu den Knoten 0 , 2 , 3 und 4 , der Knoten 2 ist benachbart zu den Knoten 0 und 1 , der Knoten 3 ist be ^¬ nachbart zu den Knoten 0 , 1 und 4 , der Knoten 4 ist benachbart zu den Knoten 0 , 1 und 3 , und der Knoten 5 ist benach- bart zu dem Knoten 0. 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 Figur 1 dargestellte .

Ein Pfad in dem Netzwerk verläuft von einem Startknoten zu einem Zielknoten über keinen, einen oder mehrere weitere Knoten . So kann beispielsweise ein Pfad zwischen dem Knoten 2 und dem Knoten 4 über den Knoten 0 oder über die Knoten 0 und 1 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 für das Netzwerk ermittelt . Da in der Regel mehrere potentielle Pfade zwischen einem bestimmten Startkno ^¬ ten und einem bestimmten Zielknoten existieren, erfolgt eine Wichtung bzw . Bewertung von Pfaden durch die Länge der Pfade, welche durch eine Routing-Metrik festgelegt wird . Ein bekanntes Beispiel für eine Routing-Metrik ist die hop-count Met- rik, 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 Knoten die Anzahl der Pfade bestimmt , welche von dem jeweiligen Knoten ausgehen, d . h . für welche der jeweilige Knoten der Startknoten ist , und die Anzahl der Pfade,

welche über den jeweiligen Knoten verlaufen . Diese Größe wird im folgenden als B _k bezeichnet , wobei k der Index des jewei ^¬ ligen Knotens ist . Jedem Koten wird die Summe aus seinem B _k und den B _k ' s der ihm benachbarten Knoten zugewiesen . Diese Größe wird im folgenden als B _k ^cum bezeichnet , wobei k der In ^¬ dex des jeweiligen Knotens ist . Die auf dieser Routing-Metrik basierende Länge eines Pfades ergibt sich als Summe aus den B _k ^cum s der Knoten, welche entlang des Pfades senden, d . h . des Sendeknotens und der Knoten, über welche der Pfad verläuft .

Diese Wahl der Routing-Metrik liegt darin begründet , dass die Größe B _k ^cum geeignet ist , die Mediums-Zugriffszeit eines Kno ^¬ tens auf das von den Knoten des Netzwerkes geteilte Übertra ^¬ gungsmedium zu beschreiben . Hierbei wird insbesondere berück- sichtigt , dass ein Knoten nicht auf das Übertragungsmedium zugreifen kann, wenn ein Nachbarknoten das Übertragungsmedium aktuell zur Versendung oder zum Empfang von Nachrichten verwendet . Dies bedeutet , dass ein Knoten und ein ihm benachbar ^¬ ter Knoten nicht gleichzeitig Nachrichten senden und/oder empfangen können . Je mehr Nachbarknoten ein Knoten aufweist , über welche eine Vielzahl von Pfaden verlaufen, desto länger dauert es in der Regel, bis dieser Knoten auf das Übertra ^¬ gungsmedium zugreifen kann .

Die auf der Routing-Metrik basierenden Länge des Pfades zwischen den Knoten 3 und 4 , welcher über den Knoten 1 verläuft , lautet beispielsweise :

Länge Pfad 314 = B"" ⁿ + B"" ⁿ , wobei B"" ⁿ = B ₃ + B ₀ + B _ι + B ₄ und B[ ^um = B _ι + B ₀ + B ₂ + B ₃ + B ₄ .

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 be- stimmten Knoten, 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 Nach-

rieht , welche für den Knoten y bestimmt ist , an den Knoten z zu versenden hat .

Zu Beginn des Verfahrens werden alle B _k und alle B _k ^cum auf den Wert 1 gesetzt . Dies entspricht der hop-count Metrik . Als I- nitialisierungs-Wert kann auch ein anderer Wert als 1 verwen ^¬ det werden, das Ergebnis des Verfahrens ist weitgehend unab ^¬ hängig von diesem Startwert . In die Routing-Tabelle wird ein Wert von (-1 ) eingetragen, wenn noch kein Pfad ermittelt wur- de . Diese Situation zu Beginn entspricht der in der Figur 2a dargestellten . B _k und B _k ^cum sind in Figur 2a und in den folgenden Figuren als Vektoren dargestellt , wobei [BΓ>BΓ>BΓ>BΓ>BΓ>BΓ] - ^{in der}

Routing-Tabelle ROUTES sind zu Beginn alle Einträge mit dem Wert (-1 ) belegt .

Im ersten Schritt , in Figur 2b dargestellt , werden alle Pfade betrachtet , die zu dem Knoten 0 führen, d . h . bei welchen der Knoten 0 der Zielknoten ist . Da alle Knoten 0 , 1 , 2 , 3 , 4 und 5 zu dem Knoten 0 benachbart sind, senden sie eine Nachricht , welche für den Koten 0 bestimmt ist , direkt an den Knoten 0. Daher weist die erste Spalte der Routing-Tabelle ROUTES für alle Zeilen eine 0 auf . Betrachtet man die Knoten 3 und 4 , so wäre es beispielsweise auch möglich, dass diese eine für den Knoten 0 bestimmte Nachricht an den Knoten 1 senden, welcher die Nachricht dann an den Knoten 0 weiterleitet . Im allgemei ^¬ nen existieren zwischen zwei bestimmen Knoten eine Mehrzahl an möglichen Pfaden . Dies bedeutet , dass bei der Erstellung der Routing-Tabelle ROUTES eine Auswahl zwischen den alterna- tiven 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 ermittelte Größe B _k ^cum bestimmt wird .

Für den Pfad zwischen dem Knoten 3 und dem Knoten 0 ergibt sich folgende Betrachtung :

Direkter Pfadverlauf von dem Knoten 3 zu dem Knoten 0 : die Länge für diesen Pfad ist B"" ⁿ = l , da der Knoten 3 , d . h . der

Sendeknoten, der einzige sendende Knoten entlang diesem Pfad ist und der Pfad über keinen weiteren Knoten verläuft . Pfadverlauf zwischen dem Knoten 3 und dem Knoten 0 über den Knoten 1 : die Länge für diesen Pfad ist B ^c " ^m + B[ ^um = 2 , da der

Pfad über den Knoten 1 verläuft , dessen B _k ^cum gemäß Figur 2a den Wert 1 aufweist .

Pfadverlauf zwischen dem Knoten 3 und dem Knoten 0 über die Knoten 1 und 2 : die Länge für diesen Pfad ist

B"" ⁿ + B[ ^wn + B ₂ ^c " ^m = 3 , da der Pfad über die Knoten 1 und 2 verläuft , deren B _k ^cum gemäß Figur 2a jeweils den Wert 1 aufweist . 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 ROUTES 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 Rou ^¬ ting-Metrik ausgewählt und in die Routing-Tabelle ROUTES ein- getragen . Die Bewertung der verschiedenen Pfade erfolgt hierbei unter Verwendung der im letzten Schritt bestimmten Werte der Routing-Metrik .

Nach der Bestimmung der Routing-Tabelle ROUTES wird die Größe B _k ^cum berechnet . Zur Berechnung von B _k ^cum wird zuvor die Größe B _k , ₀ berechnet . Hierbei handelt es sich um den Anteil von B _k , bei welchem der Knoten 0 der Zielknoten ist . Da der Knoten 0 an sich selber keine Nachricht sendet , steht an erster Stelle des Vektors B _k , ₀ eine 0. Da gemäß der Routing-Tabelle ROUTES genau ein Pfad zu dem Knoten 0 von dem Knoten 1 ausgeht und kein Pfad existiert , welcher über den Knoten 1 zu dem Knoten 0 verläuft , steht an zweiter Stelle eine 1. Gleiches gilt auch für die Knoten 2 , 3 , 4 und 5. Da bislang nur der Knoten 0 als Zielknoten betrachtet wurde, ist B _k gleich B _k , ₀ . Da B _k für alle Knoten bestimmt wurde, kann B _k ^cum berechnet werden :

Für den Knoten 0 gilt :

B _k ^c " ^m =B ₀ +B _ι +B ₂ +B ₃ +B ₄ +B ₅ =0 + 1 + 1 + 1 + 1 + 1 = 5.

Für den Knoten 1 gilt: B _k ^c " ^m = B ₀ + B ₁ + B ₂ + B ₃ + B ₄ =0 + 1 + 1 + 1 + 1 = 4.

Für den Knoten 2 gilt : B _k ^c " ^m = B ₀ + B ₁ + B ₂ = 0 + 1+ 1 = 2.

Für den Knoten 3 gilt : B _k ^c " ^m = B ₀ + B ₁ + B ₃ + B ₄ = 0+ 1 + 1+ 1 = 3.

Für den Knoten 4 gilt : B _k " ⁿ = B ₀ + B ₁ + B ₃ + B ₄ = 0+ 1+ 1+ 1 = 3.

Für den Knoten 5 gilt : B _k " ^m = B ₀ + B ₅ = 0+1 = 1.

Im zweiten Schritt wird, in Figur 2c dargestellt , der Knoten 1 als Zielknoten betrachtet . Wie oben beschrieben, werden die Einträge in die Routing-Tabelle ROUTES ermittelt , indem alle möglichen Pfade zu dem Knoten 1 mit der Routing-Metrik bewertet werden und der gemäß der Routing-Metrik günstigste Pfad ausgewählt wird . Demgemäß sendet der Knoten 0 eine für den Knoten 1 bestimmte Nachricht direkt an den Knoten 1 , daher steht an der Position ( 0 , 1 ) der Routing-Tabelle ROUTES eine 1. Entsprechendes gilt auch für die anderen dem Knoten 1 be ^¬ nachbarten Knoten 2 , 3 und 4. Der Knoten 5 sendet eine für den Knoten 1 bestimmte Nachricht an den Knoten 0 , daher steht an der Position ( 5 , 1 ) der Routing-Tabelle ROUTES eine 0.

Zur Bestimmung von B _k ^cum wird zuerst B _k , i berechnet . Hierbei handelt es sich um den Anteil von B _k , bei welchem der Knoten 1 der Zielknoten ist . Gemäß der Routing-Tabelle ROUTES geht von dem Knoten 0 ein Pfad zu dem Knoten 1 aus , und es verläuft ein Pfad zu dem Knoten 1 über den Knoten 0 , nämlich der Pfad von dem Knoten 5 zu dem Knoten 1. Daher steht an erster Stelle von B _k , i eine 2. Da der Knoten 1 an sich selber keine Nachricht sendet , steht an erster Stelle des Vektors B _k , i eine 0. Für die Knoten 2 bis 5 steht jeweils eine 1 in B _k , i, da von jedem dieser Knoten ein Pfad zu dem Knoten 1 ausgeht und kein Pfad über diese Knoten zu dem Knoten 1 verläuft .

B _k wird berechnet , indem B _k , ₀ aus Figur 2b, d . h . der Anteil von B _k , bei welchem der Knoten 0 der Zielknoten ist , und B _{k/ 1} aus Figur 2c, d . h . der Anteil von B _k , bei welchem der Knoten 1 der Zielknoten ist , addiert werden . Aus B _k kann dann wie oben beschrieben B _k ^cum berechnet werden . Für den Knoten 1 beispielsweise gilt : B _k ^cum = B ₀ + B ₁ + B ₂ + B ₃ + B ₄ = 2+ 1+ 2+ 2+ 2 = 9.

In der Figur 2d ist der dritte Schritt dargestellt , bei wel- ehern der Knoten 2 als Zielknoten betrachtet wird, in der Figur 2e ist der vierte Schritt dargestellt , bei welchem der Knoten 3 als Zielknoten betrachtet wird, in der Figur 2f ist der fünfte Schritt dargestellt , bei welchem der Knoten 4 als Zielknoten betrachtet wird, und in der Figur 2g ist der sechste Schritt dargestellt , bei welchem der Knoten 5 als

Zielknoten betrachtet wird . Jeweils wird zuerst die Routing- Tabelle ROUTES weiter ausgefüllt , indem unter Verwendung der Routing-Metrik bestimmt wird, zu welchem Knoten eine Nachricht , welche für den jeweiligen Zielknoten bestimmt ist , zu senden ist . Bei dieser Bestimmung wird das im Vorschritt be ^¬ stimmte B _k ^cum verwendet , d . h . die Einträge werden unter Be ^¬ rücksichtigung der durch B _k ^cum vorgegebenen Routing-Metrik ausgewählt . Im Anschluss wird basierend auf der neuen Rou ^¬ ting-Tabelle ROUTES die Größe B _k ^cum berechnet .

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 ROUTES die Rou ^¬ ting-Metrik über die Größe B _k ^cum eingeht , und andererseits in die Routing-Metrik über die Größe B _k ^cum die bestimmten Pfade eingehen . Somit werden abwechselnd die Routing-Tabelle ROUTES und die Routing-Metrik aktualisiert .

In den Figuren 2b bis 2g wurde eine erste Berechnungsrunde zur Bestimmung der Pfade durch das Netzwerk aufgezeigt , wobei mit der Betrachtung des Knotens 0 als Zielknoten begonnen wird und über die Knoten 1 , 2 , 3 , 4 bis zum Knoten 5 fortge-

fahren 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 Knoten 0 als Zielknoten begonnen wird . Somit wird im ersten Schritt der zweiten Runde die erste Spalte der Routing-Tabelle ROUTES neu bestimmt , wobei die Routing-Metrik gemäß der Größe B _k ^cum aus dem letzten Schritt der ersten Runde zum Einsatz kommt . Im Anschluss wird B _k und B _k ^cum bestimmt . Entsprechend wird auch in Bezug auf die Knoten 1 , 2 , 3 , 4 und 5 als Zielknoten vorgegangen, wobei jeweils die Routing-Metrik dem jeweils vorhergehenden Schritt der zweiten Runde entnommen wird . Zum Ende der zweiten Runde ergibt sich die Situation gemäß Figur 2h .

Bei Bedarf können weitere Berechnungsrunden folgen . Im Laufe der Runden konvergiert das Ergebnis , d . h . die Einträge der Routing-Tabelle ROUTES und die Größen B _k und B _k ^cum ändern sich nicht oder kaum mehr . Bereits nach zwei Runden ist in der Regel eine selbst-konsistente Routing-Tabelle ROUTES berechnet . Bei weiteren Iterationsrunden ändern sich zwar noch die Einträge der Routing-Tabelle ROUTES , jedoch findet keine wesent ^¬ liche Erhöhung der Leistung des Netzwerkes mehr statt , gemes ^¬ sen z . B . an dem Ende-zu-Ende Datendurchsatz und der Ende-zuEnde Zeitverzögerung . Die Anzahl der Runden, welche zum Er- reichen der Konvergenz nötig sind, hängt von der Größe des betrachteten Netzwerks ab .

In den Figuren 3a und 3b sind die Schritte eines alternativen Berechnungsablaufs abgebildet . Der Initialisierungszustand entspricht dem der Figur 2a . In der ersten Runde wird im ers ^¬ ten Schritt der Knoten 0 als Zielknoten betrachtet und es wird die erste Spalte der Routing-Tabelle ROUTES ausgefüllt . Zur Auswahl zwischen den verschiedenen möglichen Pfaden wird B _k ^cum aus der vorhergehenden Runde, d . h . B _k ^cum aus der Initia- lisierung verwendet . Im Anschluss werden B _k und B _k ^cum nicht neu berechnet . Vielmehr wird im zweiten Schritt der Knoten 1 als Zielknoten betrachtet und die zweite Spalte der Routing-

Tabelle ROUTES bestimmt , wobei wieder B _k ^cum aus der Initiali ^¬ sierung verwendet wird . Entsprechendes erfolgt auch in Bezug auf die Knoten 2 , 3 , 4 und 5 als Zielknoten . Für alle Einträ ^¬ ge der Routing-Tabelle ROUTES der ersten Runde werden somit die Werte B _k ^cum der Initialisierung verwendet .

Nachdem die Routing-Tabelle ROUTES wie in Figur 3a darge ^¬ stellt im Rahmen der ersten Runde bestimmt wurde, erfolgt ba ^¬ sierend auf dieser Routing-Tabelle ROUTES die Berechnung von B _k und B _k ^cum , wie in Figur 3a dargestellt .

Manche Einträge der Routing-Tabelle ROUTES 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 Figuren 2a bis 2h geschilderten Verfahren auftreten . Diese Gleichwertigkeit mehrerer Routen zwischen zwei bestimmten Knoten verschwindet in der Regel bei den fol ^¬ genden Berechnungsrunden .

In Figur 3b ist das Ergebnis der zweiten Runde gezeigt . In der zweiten Runde werden zuerst für den Knoten 0 , dann für den Knoten 1 , dann für den Knoten 2 , dann für den Knoten 3 , dann für den Knoten 4 , und schließlich für den Knoten 5 als Zielknoten die Einträge für die Routing-Tabelle ROUTES be ^¬ stimmt , wobei jeweils die zum Abschluss der ersten Runde be ^¬ rechneten B _k ^cum zur Bewertung der Routen herangezogen werden . Nach Bestimmung der Routing-Tabelle ROUTES der zweiten Runde werden B _k und B _k ^cum , wie in Figur 3b dargestellt , basierend auf dieser Routing-Tabelle ROUTES berechnet .

Die zweite in den Figuren 3a und 3b dargestellte Variante des erfindungsgemäßen Verfahrens weist den Vorteil auf, dass der Berechnungsaufwand niedriger ist , da lediglich einmal pro Runde B _k ^cum bestimmt werden muss , und nicht wie in der ersten Variante vorgesehen, nach jedem Schritt . Jedoch sind 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 ROUTES der Figuren 2 und Figur 3 werden zur Versendung von Nachrichten zwischen den Knoten 0 , 1 , 2 , 3 , 4 und 5 verwendet . Eine Neuberechnung der Pfade ist dann nötig, wenn sich die Topologie des Netz ^¬ werkes ändert , d . h . wenn sich die Nachbarschaftsbeziehungen zwischen den Knoten ändern oder wenn Knoten neu zu dem Netz- werk hinzukommen oder wenn Knoten das Netzwerk verlassen .

Zur Bestimmung der Pfade wird davon ausgegangen, dass die Einrichtung, welche 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" In ^¬ formation 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, welche die Topolo- gie 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 ROUTES kann auch die berechnete Größe B _k ^cum weitergegeben werden, so dass die Kno- ten auf Basis der empfangenen Größe B _k ^cum die Routing-Tabelle ROUTES bestimmen .

Die beschriebenen Verfahren, bei welchen die Routing-Metrik bzw . die Länge der Pfade aus der Summe der B _k ^cum s der senden ^¬ den Knoten eines Pfades ermittelt werden, resultieren in der Ermittlung von Pfaden, bei welchen kritische Knoten, über welche eine Vielzahl von Pfaden verlaufen und welche dement ^¬ sprechend stark ausgelastet sind, entlastet werden . So wei ^¬ chen z . B . gemäß dem erfindungsgemäßen Verfahren ermittelte Pfade auf Randknoten aus , wodurch die Pfade zwar gegebenenfalls länger sind als bei Verwendung von Knoten in der Mitte des Netzwerkes , jedoch eine geringere Auslastung der Pfade eintritt . 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 welchen die Knoten miteinander kommunizieren, eingesetzt werden . Besonders vorteilhaft ist der Einsatz in Funkkommunikationssystemen wie z . B . Multihop Adhoc-Systemen und Sensornetzwerken .