DE10127880A1

DE10127880A1 - Dynamisches Netzwerk und Routing-Verfahren für ein dynamisches Netzwerk

Info

Publication number: DE10127880A1
Application number: DE10127880A
Authority: DE
Inventors: Joerg Habetha
Original assignee: Philips Corporate Intellectual Property GmbH
Current assignee: Philips Intellectual Property and Standards GmbH
Priority date: 2001-06-11
Filing date: 2001-06-11
Publication date: 2002-12-12
Also published as: ATE341139T1; EP1400071A2; WO2002102000A3; DE60215005D1; EP1400071B1; US20040170151A1; US7031321B2; DE60215005T2; JP2004521561A; WO2002102000A2

Abstract

Die Erfindung bezieht sich auf ein dynamisches Netzwerk mit mehreren Knoten, wobei vorgesehen ist, DOLLAR A - in Knoten des Netzwerks Routing-Informationen in lokalen Routing-Tabellen zu speichern, DOLLAR A - daß die Knoten zum Aktualisieren der lokalen Routing-Tabellen eine Aktualisierungsanfrage an benachbarte Knoten senden, DOLLAR A - daß die angefragten Knoten eine Aktualisierungsantwort mit aktualisierten Routing-Informationen an den anfragenden Knoten senden.

Description

Die Erfindung bezieht sich auf ein dynamisches Netzwerk sowie auf ein Routing- Verfahren für ein dynamisches Netzwerk.

Unter einem dynamischen Netzwerk wird ein Netzwerk verstanden, dessen Topologie sich während des Betriebs dynamisch verändern kann. Hierunter fallen insbesondere Ad-Hoc- Netzwerke. Unter einem Ad-Hoc-Netzwerk wird ein selbstorganisierendes Netzwerk verstanden, bei dem die Struktur und die Anzahl von Teilnehmern innerhalb vorgegebener Grenzwerte nicht festgelegt ist. Beispielsweise kann eine Kommunikationsvorrichtung eines Teilnehmers aus dem Netzwerk genommen oder eingebunden werden. Im Gegensatz zu traditionellen Mobilfunknetzen ist ein Adhoc-Netzwerk nicht auf eine fest installierte Infrastruktur angewiesen.

Dynamische Netzwerke können aber auch z. B. Internet-Netze sein, deren Topologie sich während des Betriebes verändert.

Ein derartiges Ad Hoc Netzwerk ist aus dem Buch Ad Hoc-Networking, C. E. Perkins, Addison Wesley, Seiten 53-62 bekannt. Um das Routing an Änderungen der Netzwerktopologie anzupassen, sendet bei diesem bekannten Netzwerk jeder Knoten in regelmäßigen Abständen Updates der Routing-Informationen an benachbarte Knoten.

Es ist eine Aufgabe der Erfindung, ein Netzwerk der eingangs genannten Art zu schaffen, welches ein verbessertes Routing bei Änderungen der Netzwerktopologie ermöglicht. Es ist eine weitere Aufgabe der Erfindung, ein diesbezügliches Routing-Verfahren anzugeben.

Die Aufgabe wird für das Netzwerk gelöst durch ein dynamisches Netzwerk mit mehreren Knoten, wobei vorgesehen ist,

- in Knoten des Netzwerks Routing-Informationen in lokalen Routing-Tabellen zu speichern,
- daß die Knoten zum Aktualisieren der lokalen Routing-Tabellen eine Aktualisierungsanfrage an andere Knoten senden,
- daß die angefragten Knoten eine Aktualisierungsantwort mit aktualisierten Routing- Informationen an den anfragenden Knoten senden.

Bei dem erfindungsgemäßen Netzwerk werden in Knoten des Netzwerks Routing- Informationen gespeichert. Bei dezentralen Netzen werden vorzugsweise in jedem Knoten Routing-Informationen gespeichert. Bei Cluster-Netzen mit zentralen Controllern werden vorzugsweise nur in den zentralen Knoten Routing-Informationen gespeichert.

Die Routing-Informationen sind in Form von Routing-Tabellen abgespeichert. Die Routing-Tabelle eines Knotens weist vorzugsweise für alle anderen Knoten des Netzwerks oder für diejenigen Knoten, die von dem jeweiligen Knoten erreichbar sind, Felder auf. Die Knoten, die von einem Knoten erreichbar sind, d. h. zu denen eine Übertragung möglich bzw. gewünscht ist, werden als Zielknoten bezeichnet.

Als Routing-Informationen können in den Feldern z. B. der nächste Knoten, über den eine Datenübertragung zu dem jeweiligen Zielknoten erfolgen soll (next hop), die Pfadlänge zu dem Zielknoten und die maximale Übertragungskapazität zu dem Zielknoten gespeichert werden.

Um die lokalen Routing-Tabellen aktuell zu halten, senden die Knoten, die eine Routing- Tabelle aufweisen, in vorzugsweise regelmäßigen Abständen eine Aktualisierungsanfrage an andere Knoten. Diese anderen Knoten sind insbesondere benachbarte Knoten. Bei Cluster-Netzen mit zentralen Controllern sind dies insbesondere benachbarte Controller.

Die Aktualisierungsanfrage signalisiert den Knoten, die diese Anfrage erhalten, daß diese aktualisierte Routing-Informationen an den anfragenden Knoten schicken sollen.

Der Vorteil des Abfragemechanismus liegt insbesondere darin, daß der Abfragemechanismus eine gebündelte Übertragung der Routing-Informationen ermöglicht. Die einzelnen Knoten übertragen geänderte Routing-Informationen nur auf Anfrage. Bei der Anfrage können dann mehrere Topologieänderungen bzw. die in der Zeit zwischen zwei Anfragen aufgetretenen Topologieänderungen gebündelt an den anfragenden Knoten gesendet werden. In einer einzigen Protokolldateneinheit (engl. Protocol Data Unit PDU) können daher mehrere Änderungen der Netzwerktopologie an den anfragenden Knoten gesendet werden. Dies führt zu einer Verringerung der Anzahl der PDUs (Pakete), die für das Routing verschickt werden müssen.

Der Erfindung liegt die Idee zugrunde, die Menge an Informationen, die zur Aktualisierung der lokalen Routing-Tabellen übertragen werden, dadurch zu verringern, daß die einzelnen Knoten Routing-Informationen bei anderen Knoten abfragen.

Der vorteilhaften Ausgestaltung der Erfindung gemäß Anspruch 2 liegt die Idee zugrunde, den angefragten Knoten mitzuteilen, wie aktuell die Routing-Informationen des anfragenden Knotens sind. Dies ermöglicht den abgefragten Knoten somit eine Selektion der an den anfragenden Knoten zu sendenden Routing-Informationen.

Es werden jeweils nur die Routing-Informationen an den anfragenden Knoten übermittelt, welche aktueller sind als die bisherigen Routing-Informationen des anfragenden Knotens.

Hierzu weisen die lokalen Routing-Tabellen eine Tabellen-Update-Information und eine Feld-Update-Information auf. Die Tabellen-Update-Information enthält eine Information darüber, wie aktuell die lokale Routing-Tabelle ist, d. h. wann die letzte Änderung in der Routing-Tabelle vorgenommen wurde. Dies kann z. B. eine Zeitangabe oder eine Sequenznummer sein. Die Feld-Update-Information enthält eine Information darüber, wie aktuell die einzelnen Felder der Routing-Tabelle sind, d. h. wann die letzte Änderung in dem jeweiligen Feld der Routing-Tabelle vorgenommen wurde. Die Feld-Update- Information kann z. B. ebenfalls eine Zeitangabe oder eine Sequenznummer sein. Die Tabellen-Update-Information entspricht somit der aktuellsten Feld-Update- Information der jeweiligen Routing-Tabelle.

Die Aktualisierungsanfrage beinhaltet die Tabellen-Update-Information des anfragenden Knotens. Dies ermöglicht den angefragten Knoten, eine Selektion der Routing- Informationen, die an den anfragenden Knoten geschickt werden. Durch die Tabellen- Update-Information des anfragenden Knotens wissen die angefragten Knoten, wie aktuell die Routing-Tabelle des angefragten Knotens ist, d. h. wann in der Routing-Tabelle des angefragten Knotens die letzte Änderung aufgetreten ist. Die angefragten Knoten schicken an den anfragenden Knoten eine Aktualisierungsantwort, welche nur diejenigen lokalen Routing-Informationen aufweist, die aktueller als Tabellen-Update-Information sind. Ist die Tabellen-Update-Information eine Zeitangabe, so werden nur Routing-Informationen verschickt, die zeitlich jünger sind. Die Selektion der Routing-Informationen kann durch Vergleich der Tabellen-Update-Information des anfragenden Knotens mit den einzelnen Feld-Update-Informationen der Felder der Routing-Tabellen der angefragten Knoten erfolgen. Eine derartige selektive Auswahl der gesendeten Routing-Informationen reduziert die Datenmenge, die für das Routing zwischen den einzelnen Knoten übertragen werden muß. Damit lassen sich effiziente Routing-Verfahren implementieren.

Das Senden der Tabellen-Update-Information zu den angefragten Knoten hat den Vorteil, daß die Tabellen-Update-Information nur wenig Übertragungskapazität benötigt und pro Routing-Tabelle bzw. Knoten nur eine Tabellen-Update-Information übertragen werden muß. Dadurch benötigt die Aktualisierungsanfrage nur wenig Übertragungskapazität. Dies ist insbesondere bei drahtlosen Netzen vorteilhaft.

Bei der vorteilhaften Ausgestaltung der Erfindung gemäß Anspruch 3 weisen die lokalen Routing-Tabellen eine Topologie-Änderungs-Information auf. Mittels der Topologie- Änderungs-Information kann die Aktualität einer Änderung der Netzwerktopologie gekennzeichnet werden und somit angegeben werden, wann in dem Netzwerk eine Änderung der Netzwerktopologie aufgetreten ist. Vorzugsweise enthält jedes Feld der lokalen Routing-Tabellen eine Topologie-Änderungs-Information. Dies kann z. B. eine Zeitangabe oder eine Sequenznummer sein. Da es eine gewisse Zeit dauert, bis sich die Information bezüglich einer Änderung der Netzwerktopologie über die einzelnen Knoten des Netzwerks ausgebreitet hat, kann in jedem Knoten, der diese Information zeitlich später erhält, unterschieden werden, ob diese Information für ihn neu ist, ob er diese Information bereits gespeichert hat oder ob diese Information für ihn bereits veraltet ist, z. B. weil er von einem anderen Knoten bereits eine neuere bzw. aktuellere Information erhalten hat. Mittels der Topologie-Änderungs-Information ist es somit möglich, effiziente Updates der lokalen Routing-Tabellen durchzuführen.

Dies erfolgt bei der vorteilhaften Ausgestaltung der Erfindung nach Anspruch 4 dadurch, daß die Aktualisierungsantwort die Topologie-Änderungs-Information aufweist und daß eine Aktualisierung der einzelnen Felder der lokalen Routing-Tabellen vorgenommen wird, wenn die Topologie-Änderungs-Information des angefragten Knotens aktueller als die Topologie-Änderungs-Information des anfragenden Knotens ist. Der Knoten, der eine Aktualisierungsanfrage an benachbarte Knoten geschickt hat, kann somit nach Erhalt der Antworten eine selektive Aktualisierung durchführen. Eine Aktualisierung der einzelnen Felder des anfragenden Knotens wird durchgeführt, wenn dadurch eine aktuellere bzw. neuere Information bezüglich der Netzwerktopologie gewonnen wird.

Wenn die Topologie-Änderungs-Information des angefragten Knotens genauso aktuell ist wie die Topologie-Änderungs-Information des anfragenden Knotens, wird gemäß der vorteilhaften Ausgestaltung der Erfindung nach Anspruch 7 eine Aktualisierung durchgeführt, wenn die Pfadlänge zu dem jeweiligen Zielknoten durch die Aktualisierung kürzer wird.

Bei der vorteilhaften Ausgestaltung der Erfindung nach Anspruch 8 wird eine Aktualisierung durchgeführt, wenn die Topologie-Änderungs-Information des angefragten Knotens genauso aktuell ist wie die Topologie-Änderungs-Information des anfragenden Knotens und die maximale Datenübertragungsrate zu dem jeweiligen Zielknoten durch die Aktualisierung größer wird.

Die vorteilhaften Ausgestaltungen der Erfindung nach Anspruch 7 und 8 lassen sich auch kombinieren, wobei je nach Applikation dem Kriterium gemäß Anspruch 7 oder dem Kriterium gemäß Anspruch 8 eine höhere Priorität zugewiesen werden kann.

Die Ausführungsform gemäß Anspruch 5 hat den Vorteil, daß Zeitinformationen einen unabhängigen Vergleich der Aktualität der einzelnen Routing-Informationen ermöglichen.

Die Ausführungsform mit den Sequenznummern gemäß Anspruch 6 läßt sich besonders einfach realisieren.

Bei zentralen Cluster-Netzwerken, welche einen zentralen Knoten (Controller) zur Steuerung der Cluster (Sub-Netzwerke) enthalten, ist es vorteilhaft, die Routing-Tabelle für das jeweilige Sub-Netzwerk zentralisiert in dem zentralen Knoten abzuspeichern. Die Übertragung von Informationen zwischen den einzelen Sub-Netzwerken erfolgt über Brücken-Knoten (Forwarder).

Für das Verfahren ist die Aufgabe gelöst durch ein Verfahren mit den Merkmalen des Anspruchs 10.

Einige Ausführungsbeispiele der Erfindung werden nachfolgend anhand der Zeichnung in den Fig. 1 bis 6 näher erläutert. Es zeigen:

Fig. 1 eine Routing-Tabelle mit Routing-Informationen,

Fig. 2 ein dynamisches Netzwerk mit 5 Sub-Netzwerken, welche jeweils mittels zentraler Controller gesteuert werden, zu einem ersten Zeitpunkt,

Fig. 3 das Netzwerk gemäß Fig. 2 zu einem zweiten Zeitpunkt, wobei ein Knoten des Netzwerks gegenüber Fig. 2 zu einem benachbarten Sub-Netzwerk verschoben ist,

Fig. 4 eine Tabelle, welche den zeitlichen Ablauf der Änderung der Routing-Tabellen der zentralen Controller infolge der Verschiebung des Netzwerkknotens aufzeigt,

Fig. 5 einen Ausschnitt eines Zeitregisters,

Fig. 6 ein Netzwerk mit 5 Sub-Netzwerken, welche jeweils mittels zentraler Controller gesteuert werden.

Fig. 1 zeigt eine Routing-Tabelle, die in den routenden Knoten bzw. Stationen eines Netzwerks gespeichert wird. Die Routing-Tabelle enthält Felder T1 bis TN für jede Station des gesamten Netzwerks sowie als Tabellen-Update-Information eine Zeit t_up, zu der die Routing-Tabelle das letzte Mal verändert wurde. Die Felder T1 bis TN für jede einzelne Station des Netzes enthalten 6 Sub-Felder 1 bis 6. Im ersten Sub-Feld 1 ist die Identifikationsnummer (ID) der jeweiligen Zielstation enthalten. Das zweite Sub-Feld 2 speichert die ID derjenigen Station, zu dem die Daten weitergereicht werden müssen, die an die Zielstation des ersten Sub-Feldes 1 gerichtet sind. Es wird somit für jede mögliche Zielstation immer der sog. nächste "Hop" auf dem Weg zu dieser Zielstation gespeichert. Wenn die Zielstation selbst der nächste "Hop" ist, wird die Zielstation selbst in das zweite Sub-Feld 2 eingetragen.

Das dritte Sub-Feld 3 speichert als Topologie-Änderungs-Information den Erzeugungszeitpunkt t_gen des Feldes. Der Erzeugungszeitpunkt t_gen gibt an, wann eine Änderung der Netzwerktopolgie für dieses Feld, d. h. für diese Zielstation aufgetreten ist. Er wird von derjenigen Station festgelegt, welche die Änderung der Netzwerktopologie erkennt und daraufhin eine inhaltliche Änderung des Feld in ihrer lokalen Routing- Tabelle durchführt. Im vierten Sub-Feld 4 wird die Zeit t_reg festgehalten. Sie gibt an, wann eine inhaltliche Änderung eines Feldes infolge einer Änderung der Netzwerktopologie von der jeweiligen Station in die Routing-Tabelle übernommen bzw. die von Nachbarstationen mitgeteilten Veränderungen übernommen wurden. Das fünfte Sub-Feld 5 jedes Feldes beinhaltet eine Metrik, wie beispielsweise die verbleibende Pfadlänge bis zur Zielstation. Es können weitere Metriken in zusätzlichen Sub-Feldern jedes Feldes gespeichert werden.

Das sechste Sub-Feld enthält die maximale Datenrate, mit der Daten zu der Zielstation übertragen werden können. Diese Datenrate entspricht der minimalen Datenrate aller Teilpfade von der betreffenden Station zur Zielstation.

Um die Routing-Tabellen immer aktuell zu halten, ist eine UPDATE-Prozedur zur Auffrischung der Routing-Tabellen vorgesehen. Diese UPDATE-Prozedur beruht auf einem Frage und Antwort (engl. Request-Response) Mechanismus.

Jede (routende) Station initiiert periodisch diese UPDATE-Prozedur. Die Station, im folgenden als UPDATING-Station (US) bezeichnet, verschickt im Rundsendemodus ("broadcast") eine UPDATE-REQUEST-Nachricht an ihre direkten (routenden) Nachbarstationen. Die UPDATE-REQUEST-Nachricht enthält die Zeit t_up, d. h. den Zeitpunkt des letzten Tabellenupdates der anfragenden Station.

Bei Empfang des UPDATE-REQUEST vergleichen die Nachbarstationen die empfangene Zeit t_up mit den Registrierungszeiten t_reg jedes einzelnen Eintrags ihrer eigenen Routing- Tabelle. Ist dieser Vergleich abgeschlossen, sendet jede Nachbarstation eine (eventuell segmentierte) UPDATE-RESPONSE-Nachricht an die anfragende Station US, in die sie all diejenigen Einträge ihrer Routing-Tabelle einfügt, die nach der Zeit t_up in die Tabelle übernommen wurden, für die also t_reg < t_up gilt. Es ist darauf hinzuweisen, daß vor dem Vergleich der Zeiten t_reg und t_up, die Zeit t_up im allgemeinen in das eigene Zeitnormal der jeweiligen Nachbarstation umgerechnet werden muß. Dieser Umstand und die dazu notwendigen Schritte werden im Anschluß an die Beschreibung der allgemeinen Routing- Prozedur erläutert. Für jeden der zu übertragenden Einträge werden alle Felder bis auf die Nächster-Hop-Terminal-ID und die Registrierungszeit t_reg übertragen, da diese für die anfragende Station US keine Bedeutung und keinen Nutzen haben.

Bei Empfang des UPDATE-RESPONSE vergleicht die US die Erzeugungszeitpunkte und Metriken der empfangenen Einträge mit den Erzeugungszeitpunkten und Metriken der bisherigen Einträge in der eigenen Routing-Tabelle.

Dabei sind die neu empfangenen Einträge bzw. Felder mit "new" und die bisherigen Einträge der anfragenden Station mit "US" gekennzeichnet. "PL" kennzeichnet, wie in Abb. 1 ersichtlich, die Pfadlänge und "MTR" die Maximale Datenrate (engl. Maximum Transmission Rate). MTR^US-NS bezeichnet die maximale Übertragungsrate zwischen der anfragenden und der antwortenden Nachbarstation. Analog gibt PL^US-NS die Anzahl der "hops" zwischen der anfragenden Station US und der Nachbarstation NS an. Es ist nämlich denkbar, daß nicht alle Stationen Routingaufgaben übernehmen. Somit könnte es vorkommen, daß zwei routende Stationen, die Nachbarn im Sinne des Routing-Verfahrens sind, über eine oder mehrere nicht-routende Stationen miteinander kommunizieren.

Es werden erfindungsgemäß von der US nur diejenigen Einträge übernommen, die folgende Kriterien erfüllen:

Sind die UPDATE-Kriterien für einen empfangenen Eintrag erfüllt, werden einige Felder des bisherigen Eintrags folgendermaßen ersetzt:

- Die "Nächster-hop-Terminal-ID" wird durch die ID der betreffenden Nachbarstation ersetzt.
- Der Generierungszeitpunkt des neuen Eintrags wird übernommen: t US|gen = t new|gen
- Die neue Pfadlänge lautet: PL^US = PL^new + PL^US-NS
- Die neue maximale Datenrate lautet: MTR^US = min(MTR^new, MTR^US-NS)

Auch in diesem Fall muß die Station die Zeit t new|gen in das eigene Zeitnormal umrechnen, bevor Zeitvergleiche und Ersetzungen durchgeführt werden (siehe Erläuterungen weiter unten).

Fig. 2 zeigt ein ein Netzwerk mit 5 Sub-Netzwerken 10 bis 14 zu einem ersten Zeitpunkt t0. Die Sub-Netzwerke 10 bis 14 werden jeweils mittels zentraler Controller CC1 bis CC5 gesteuert. Die einzelnen Sub-Netzwerke 10 bis 14 sind jeweils über Brücken-Knoten (Forwarder) F1 bis F5 verbindbar.

Der Brücken-Knoten F1 verbindet die Sub-Netzwerke 10 und 11, der Brücken-Knoten F2 die Sub-Netzwerke 11 und 12, der Brücken-Knoten F3 die Sub-Netzwerke 11 und 13, der Brücken-Knoten F4 die Sub-Netzwerke 12 und 14 und der Brücken-Knoten F5 die Sub-Netzwerke 13 und 14. In dem Sub-Netzwerk 11 befindet sich als Beispiel eine Station ST1. Die Sub-Netzwerke 10 bis 14 können in beliebiger Weise weitere nicht dargestellte Stationen bzw. Knoten enthalten. Zusätzlich ist in der Fig. 2 die Übertragungsrate der Verbindungen zwischen den einzelnen Sub-Netzwerken sowie zwischen dem CC2 und der Station ST1 angegeben. Die Übertragungsrate zwischen dem Sub-Netzwerk 10 und dem Sub-Netzwerk 11 über den Brücken-Knoten F1 beträgt 10 Mbit/s, die Übertragungsrate zwischen dem Sub-Netzwerk 11 und dem Sub-Netzwerk 12 über den Brücken-Knoten F2 beträgt 5 Mbit/s, die Übertragungsrate zwischen dem Sub-Netzwerk 11 und dem Sub-Netzwerk 13 über den Brücken-Knoten F3 beträgt 0,1 Mbit/s, die Übertragungsrate zwischen dem Sub-Netzwerk 12 und dem Sub-Netzwerk 14 über den Brücken-Knoten F4 beträgt 1 Mbit/s und die Übertragungsrate zwischen dem Sub-Netzwerk 13 und dem Sub-Netzwerk 14 über den Brücken-Knoten F5 beträgt 3 Mbit/s. Schließlich beträgt die Übertragungsrate zwischen dem Controller CC2 und der Station STI 5 Mbit/s. Die Verbindungen bei dem beispielhaften Netzwerk gemäß Fig. 2 verlaufen somit immer über die zentralen Controller CC1 bis CC5.

Fig. 3 zeigt das Netzwerk mit 5 Sub-Netzwerken gemäß Fig. 2 zu einem zweiten Zeitpunkt t1. Die Topologie des Netzwerks hat sich zu diesem zweiten Zeitpunkt dahingehend geändert, daß die Station ST1 von dem Sub-Netzwerk 11 zu dem benachbarten Sub- Netzwerk 10 verschoben worden ist. Die Übertragungsrate zwischen dem Controller CC1 des Sub-Netzwerks 10 und der Station ST1 beträgt nun 10 Mbit/s.

Fig. 4 veranschaulicht die zeitliche Veränderung der Routing-Tabellen der Controller CC1 bis CC5 infolge der Verschiebung der Station ST1 von dem Sub-Netzwerk 11 gemäß Fig. 2 zu dem Sub-Netzwerk 10 gemäß Fig. 3.

Die Tabelle gemäß Fig. 4 enthält jeweils eine Spalte für die Controller CC1 bis C5. Für die Controller CC1 bis CC5 sind in den Spalten zu 5 verschiedenen Zeitpunkten t0 bis t4 die Felder der Routing-Tabellen der einzelnen Controller für die Zielstation ST1 angegeben. Die Felder weisen in diesem Beispiel jeweils 5 Sub-Felder auf. Das gemäß Fig. 1 vorgesehene Sub-Feld mit der Identifikationsnummer (ID) der jeweiligen Zielstation ist in Fig. 4 nicht dargestellt, da Fig. 4 nur Routing-Informationen bezüglich der Zielstation ST1 zeigt.

Das oberste Sub-Feld der Felder gemäß Fig. 4 gibt jeweils den Brücken-Knoten an, zu dem die Daten weitergereicht werden müssen, die an die Station ST1 gerichtet sind. Es wird somit für die Zielstation ST1 immer nur der sog. nächste "Hop" auf dem Weg zu dieser Zielstation ST1 gespeichert. Das zweitoberste Sub-Feld 5 gibt die verbleibende Pfadlänge bis zur Zielstation an. Das mittlere Sub-Feld enthält die maximale Datenrate, mit der Daten zu der Zielstation ST1 übertragen werden können. Diese Datenrate entspricht der minimalen Datenrate aller Teilpfade von dem betreffenden Controller zur Zielstation ST1. Das zweitunterste Sub-Feld gibt als Topologie-Änderungs-Information den Erzeugungszeitpunkt t_gen des Feldes für die Zielstation ST1 an. Der Erzeugungszeitpunkt t_gen gibt an, wann eine Änderung der Netzwerktopolgie für die Zielstation ST1 aufgetreten ist. Er wird von derjenigen Station festgelegt, welche die Änderung der Netzwerktopologie erkennt und daraufhin eine inhaltliche Änderung des Feldes in der lokalen Routing- Tabelle durchführt. Dies ist vorliegend der Controller CC1 des Sub-Netzwerkes 10. Im untersten Sub-Feld wird die Zeit t_reg festgehalten. Sie gibt an, wann die Änderung der Netzwerktopologie von der jeweiligen Station, d. h. in diesem Beispiel von den jeweiligen Controllern, in die jeweilige Routing-Tabelle übernommen bzw. die von Nachbarstationen mitgeteilten Veränderungen übernommen wurden.

In dem vorliegenden Beispiel gibt die Spalte für den Zeitpunkt t0 die Felder der Routing- Tabellen der Controller CC1 bis CC5 für die Zielstation ST1 und das Netzwerk gemäß Fig. 2 an.

Zu dem Zeitpunkt t1 wird die Zielstation ST1 von dem Sub-Netzwerk 11 zu dem Sub- Netzwerk 10 verschoben. Dies entspricht der Netzwerktopologie gemäß Fig. 3. Dies wird von dem Controller CC1 des Sub-Netzwerks 10 erkannt und dementsprechend ändert der Controller CC1 zu dem Zeitpunkt t1 seine Routing-Tabelle. Die Topologie-Änderungs- Information ist somit zu dem Zeitpunkt t1 aufgetreten und dementsprechend wird t_gen = 1 gesetzt. Die aufgetretene Änderung der Netzwerktopologie wurde von dem Controller CC1 ebenfalls zu dem Zeitpunkt t1 in seiner Routing-Tabelle geändert und somit registriert. Dementsprechend wird t_reg auch gleich 1 gesetzt.

Zu dem Zeitpunkt t1 kennen die Controller CC2 bis CC5 die aufgetretene Änderung der Netzwerktopologie noch nicht. Die Information muß sich erst über das Netzwerk verbreiten. Dies geschieht mittels der Anfragen, welche die einzelnen Controller in regelmäßigen Abständen an die benachbarten Controller senden, und die diesbezüglichen Antworten der abgefragten Controller.

Zu dem Zeitpunkt t2 erhält der Controller CC2 von dem Controller CC1 eine Antwort auf seine Abfrage und die Änderung der Netzwerktopologie wird in der Routing-Tabelle des CC2 eingetragen. Da die Topologie-Änderung zu dem Zeitpunkt t1 aufgetreten ist, wird t_gen = 1 gesetzt. Die aufgetretene Änderung der Netzwerktopologie wurde von dem Controller CC2 zu dem Zeitpunkt t2 in seiner Routing-Tabelle geändert und somit registriert. Dementsprechend wird t_reg gleich 2 gesetzt.

Zu dem Zeitpunkt t3 erhalten die Controller CC3 und CC4 von dem Controller CC2 eine Antwort auf ihre Abfrage und die Änderung der Netzwerktopologie wird in den Routing-Tabellen des CC3 und des CC4 eingetragen. Da die Topologie-Änderung zu dem Zeitpunkt t1 aufgetreten ist, wird t_gen = 1 gesetzt. Die aufgetretene Änderung der Netzwerktopologie wurde von den Controllern CC3 und CC4 zu dem Zeitpunkt t3 in ihrer Routing-Tabelle geändert und somit registriert. Dementsprechend wird t_reg gleich 3 gesetzt.

Zu dem Zeitpunkt t4 erhält der Controller CC5 von dem Controller CC3 und/oder dem Controller CC4 eine Antwort auf seine Abfrage und die Änderung der Netzwerktopologie wird in der Routing-Tabelle des CC5 eingetragen. Da die Topologie-Änderung zu dem Zeitpunkt t1 aufgetreten ist, wird t_gen = 1 gesetzt. Die aufgetretene Änderung der Netzwerktopologie wurde von dem Controller CC5 zu dem Zeitpunkt t4 in seiner Routing-Tabelle geändert und somit registriert. Dementsprechend wird t_reg gleich 4 gesetzt.

Die weiteren Sub-Felder werden in entsprechender Weise ebenfalls zu den jeweiligen Zeitpunkten t1 bis t4 an die geänderte Netzwerktopologie angepaßt.

Bei Bedarf können zusätzliche Funktionen in dem Routing implementiert werden. Durch die konstante Periode der Auffrischung der Routing-Tabellen werden Topologieveränderungen, die zwischen zwei UPDATE-Zeitpunkten aufgetreten sind, den Nachbarstationen nicht unmittelbar, sondern erst zum nächsten UPDATE-Zeitpunkt mitgeteilt. Vorteilhaft können jedoch besonders wichtige Veränderungen, wie der Ausfall von Verbindungswegen, den Nachbarn auch ohne vorhergehende Anfrage mitgeteilt werden. Dies geschieht mittels einer UPDATE-TRIGGER-Nachricht, die die betroffenen Einträge mit den entsprechend veränderten Feldern enthält.

Um zu vermeiden, daß in der Zeit zwischen der Topologieveränderung und dem nächsten UPDATE-Zeitpunkt Daten von laufenden Verbindungen verloren gehen, kann außerdem von dem Knoten, der die Topologieveränderung detektiert eine ERROR-Meldung zu den Quellen bzw. Endpunkten der betroffenen Verbindungen geschickt werden, um die laufende Verbindung zu stoppen.

Die im Protokoll definierten Zeiten t_up, t_gen und t_reg können auf verschiedene Arten kodiert werden. Eine naheliegende Kodierung bezieht sich auf eine globale Systemzeit, die als Vielfaches einer Basiszeit modulo eines Maximalwertes in Form einer Bitfolge kodiert wird. Die Verwendung einer globalen Systemzeit würde allerdings eine Synchronisation aller Stationen des Netzes voraussetzen. Einige Kommunikationsstandards (wie beispielsweise der Standard 1394.1) bewerkstelligen bereits eine Synchronisation aller Geräte eines Netzes, jedoch kann von der Verfügbarkeit einer globalen Systemzeit nicht allgemein ausgegangen werden.

Aus diesem Grund wird die Verwendung einer globalen Systemzeit vermieden. In der Tat ist der Algorithmus bereits voll funktionsfähig, wenn benachbarte Stationen über die Differenz ihrer lokalen Zeit ("clock") informiert sind. Es ist daher vorgesehen, daß sich benachbarte Stationen periodisch über ihre aktuelle lokale Systemzeit informieren. Die Periode dieses Informationsaustausches kann in der Regel extrem groß gewählt werden, wie im weiteren Verlauf deutlich werden wird. Der Clock-Informationsaustausch stellt somit eine vernachlässigbare Benutzung von Übertragungsressourcen dar.

Jede Station speichert die Differenz ihrer lokalen Zeit und der lokalen Zeit jeder einzelnen Nachbarstation. Empfängt eine Station einen UPDATE-Request mit dem Parameter t_up, so addiert sie die bezüglich der betreffenden Nachbarstation gespeicherte Clock-differenz zu t_up hinzu, um den Zeitpunkt der letzten Änderung der Routing-Tabelle der Nachbarstation in das eigene Zeitnormal umzurechnen. Anschließend kann gemäß dem normalen Ablauf der Routingprozedur die umgerechnete Zeit t_up mit den Registrierungszeiten t_reg der eigenen Routingeinträge verglichen und eine UPDATE-Response generiert werden.

Empfängt eine Station eine UPDATE-Response auf einen vorhergehenden UPDATE- Request, wird völlig analog zum vorhergehenden Fall zunächst die Erzeugungszeit t_gen jedes empfangenen Eintrags in das eigene Zeitnormal umgerechnet, indem die Clock-differenz zur entsprechenden Nachbarstation zu der Zeit t_gen hinzuaddiert wird. Anschließend wird gemäß dem normalen Ablauf des Routing-Algorithmus entschieden, ob der empfangene Eintrag in die eigenen Routing-Tabelle übernommen wird oder nicht.

Es sei darauf hingewiesen, daß die von zwei benachbarten Stationen gespeicherte Clock- Differenz entgegengesetzte Vorzeichen hat, d. h. bei einem UPDATE-Request- UPDATE-Response Austausch zweier benachbarter Stationen entspricht die Addition eines positiven Zeitdifferenzwertes in einer Station det Subtraktion desselben positiven Wertes (bzw. der Addition eines negativen Wertes) in der anderen Station.

Heute gebräuchliche Zeitgeber haben in der Regel eine Genauigkeit in der Größenordnung von Micro- bzw. Nanosekunden. Eine derartige hohe Genauigkeit der Zeitangaben ist im betrachteten Routing-Verfahren nicht notwendig. Um die Anzahl zu übertragender bits zu minimieren, wird daher lediglich ein Ausschnitt der internen Uhr der Stationen für die Zeitangaben t_up, t_gen und t_reg verwendet.

Fig. 5 zeigt beispielhaft einen Ausschnitt eines kompletten Zeitregisters. In der Fig. 5 entsprechen die dargestellten Intervalle des Registers einzelnen bits. Der Zeitwert ist dual kodiert, wobei die Wertigkeit der bits von rechts nach links zunimmt, das höchstwertigste bit (engl. Most Significant Bit (MSB)) somit ganz links liegt.

Der für das Routingverfahren gewählte Ausschnitt des Registers, der in Abb. 1 schraffiert gekennzeichnet ist, ist durch die beiden Zeiten T_max und T_min bestimmt.

Die obere Grenze des gewählten Registerausschnitts bestimmt die maximale Zeit nach der ein Eintrag in einer Routing-Tabelle gelöscht werden muß. Dies ist auf die modulo- Definition des Zeitausschnitts innerhalb des Routingverfahrens zurückzuführen. Eine Station muß bei jedem (T_precision) Zeitschritt jeden bereits vorhandenen Eintrag der Routing-Tabelle überprüfen, ob der Erzeugungszeitpunkt t_gen des Eintrags mit der aktuellen lokalen Zeit (bzw. dem Ausschnitt des Zeitregisters) übereinstimmt. Ist dies der Fall, wird der Eintrag gelöscht. Der Grund hierfür ist, daß ein alter Eintrag ansonsten aufgrund der modulo-Definition nach einer modulo-Perdiode wieder als sehr aktuell erscheinen würde.

Die Größenordnung von T_min bestimmt die Genauigkeit der Zeitkodierung und orientiert sich an der minimalen Periode der Versendung der UPDATE-Request-Nachrichten. Der Grund hierfür liegt darin, daß alle seit dem letzten UPDATE der anfragenden Station in der antwortenden Station veränderten Einträge zu der anfragenden Station geschickt werden, unabhängig davon, ob die Änderungen kurz oder lange nach dem letzten UPDATE vorgenommen worden sind. Gleiches gilt für das Ersetzen von Einträgen in der anfragenden Station. Insofern bringt eine genauere Kodierung der Zeit keinen Vorteil sondern kostet lediglich Übertragungskapazität.

Vorteilhaft wird jedoch ein um einige bits nach unten vergrößerter Ausschnitt (in Abb. 1 bis zur Zeit T_precision) zur Übertragung und Speicherung der Zeiten t_up, t_gen und t_reg gewählt, obwohl nur die in Abb. 1 vollständig schraffierten bits tatsächlich im Routing-Algorithmus ausgewertet werden. Auf diese Weise können Fortpflanzungseffekte von Rundungsfehlern bei der Umrechnung der Zeiten eines Zeitnormals in ein anderes Zeitnormal vermieden werden.

Der Registerausschnitt wird einmalig festgelegt und kann während des Betriebs von einzelnen Stationen nicht verändert werden.

Gleiches gilt jedoch nicht für die Periode der Versendung der UPDATE-Request- Nachrichten. Das Routing-Verfahren setzt nicht voraus, daß alle Stationen dieselbe Periode verwenden. Dies wird dahingehend ausgenutzt, daß jede Station die eigene UPDATE-Periode während des Betriebs optimiert. Leere UPDATE-Response- Nachrichten können beispielsweise darauf hindeuten, daß die UPDATE-Perdiode vergrößert werden kann. Hohe Topologieveränderungsraten und daraus folgende Verbindungsabbrüche und Paketverluste sollten eine Verkleinerung der UPDATE- Perdiode nachsichziehen. Das Routing-Verfahren paßt sich somit automatisch an verschiedene Systemszenarien und Mobilitätsraten an.

Nach der Darstellung der Kodierungsvorschrift kann nun die zu Beginn gemachte Aussage begründet werden, daß der Informationsaustausch zur Ermittlung der Uhrdifferenzen benachbarter Stationen relativ selten erfolgen kann: Die Frequenz des Informationsaustausches richtet sich nach der sog. "Clock-Drift" der lokalen Zeitgeber der Stationen. In der Regel liegt die Clock-Drift in der Größenordnung oder sogar einige Zehnerpotenzen niedriger als die minimale Kodierungsstufe des Zeitregisters (Least Significant Bit (LSB) in Abb. 1). Die untere Grenze des ausgewerteten Ausschnitts, d. h. die Zeit T_min, wird jedoch wie in Abb. 1 angedeutet einige Zweier-Potenzen höher gewählt. Es muß spätestens dann ein Informationsaustausch über die Uhrdifferenzen erfolgen, wenn aufgrund der Clock-Drift eine Verschiebung in der Größenordnung von T_precision erreicht werden könnte.

Abschließend wird der Informationsaustausch über die Clock-Differenzen für ein in Form von Sub-Netzen bzw. Clustern organisiertes selbstorganisierendes Netz dargestellt. Ein Beispiel eines solchen Netzes ist in Fig. 6 dargestellt.

In dem cluster-basierten Netz gemäß Fig. 6 führt in jedem Cluster eine einzige Station, genannt Central Controller (CC), die Routing-Algorithmen für alle Stationen des eigenen Clusters aus. Das Netzwerk gemäß Fig. 6 weist fünf Cluster 20 bis 24 auf. Die Cluster 20 bis 24 weisen CCs 30 bis 34 auf. Nachbarn im Sinne des zuvor beschriebenen Routing- Verfahrens sind somit lediglich die CCs 30 bis 34. Die CCs können jedoch im allgemeinen nicht direkt miteinander kommunizieren, sondern müssen über im Überlappungsbereich der Cluster liegende sog. Forwarding Terminals (FT) Informationen austauschen. Die Cluster 20 und 22 sind über ein FT 40, die Cluster 21 und 22 über ein FT 41, die Cluster 22 und 23 über ein FT 42 und die Cluster 24 und 22 über ein FT 43 verbunden. Das Cluster 20 weist beispielhaft eine weitere Station 50, das Cluster 21 weitere Stationen 51 und 52, das Cluster 23 weitere Stationen 53 und 54 und das Cluster 24 weitere Stationen 55 bis 57 auf.

Die Zeitinformation wird auf folgende Weise zwischen den CCs 20 bis 24 ausgetauscht: Jedes FT 40 bis 43 und jeder CC 20 bis 24 speichert zu Beginn eines jeden MAC- Rahmens eine Kopie seines kompletten Clockregisters. Weiterhin versendet jeder CC periodisch (mit der Periode des Zeit-Informationsaustausches) eine Rundsende ("Broadcast") Nachricht innerhalb seines Clusters, in der als Parameter die Kopie des Clockregisters zum Zeitpunkt des Beginns des akutellen MAC-Rahmens enthalten ist. Die FTs, die die Nachricht empfangen, bilden die Differenz aus der Kopie des eigenen Clock- Registers und der empfangenen Kopie des Clock-Registers des CC. Auf diese Weise ermitteln sie den Versatz der Uhren zwischen dem CC und sich selbst und speichern diesen. Hat ein FT gemäß der gleichen Prozedur den Versatz zu einem weiteren CC ermittelt, kann es per Subtraktion der beiden Versatzwerte die Clock-Differenz der beiden CCs bestimmen. Die Clock-Differenz wird daraufhin den beiden CCs in einer eigens dafür vorgesehenen Signalisierungsnachricht mitgeteilt.

Claims

1. Dynamisches Netzwerk mit mehreren Knoten, wobei vorgesehen ist,
in Knoten des Netzwerks Routing-Informationen in lokalen Routing-Tabellen zu speichern,
daß die Knoten zum Aktualisieren der lokalen Routing-Tabellen eine Aktualisierungsanfrage an andere Knoten senden,
daß die angefragten Knoten eine Aktualisierungsantwort mit aktualisierten Routing- Informationen an den anfragenden Knoten senden.

2. Netzwerk nach Anspruch 1, dadurch gekennzeichnet, dass die Tabellen Feldern für die Zielknoten aufweisen, daß die lokalen Routing-Tabellen eine Tabellen-Update-Information hinsichtlich der letzten Aktualisierung der lokalen Routing-Tabelle und eine Feld-Update-Information hinsichtlich der letzten Aktualisierung der einzelnen Felder aufweisen, daß die Aktualisierungsanfrage die Tabellen-Update-Information aufweist und daß daß die Aktualisierungsantwort die lokalen Routing-Informationen aufweist, für die die Feld-Update-Information des angefragten Knotens aktueller als die Tabellen-Update- Information des anfragenden Knotens ist.

3. Netzwerk nach Anspruch 1, dadurch gekennzeichnet, dass die lokalen Routing-Tabellen Felder für die Zielknoten aufweisen und daß die Felder eine Topologie-Änderungs-Information zur Kennzeichnung der Aktualität einer Änderung der Netzwerktopologie aufweisen.

4. Netzwerk nach Anspruch 3, dadurch gekennzeichnet, dass vorgesehen ist, daß die Aktualisierungsantwort die Topologie-Änderungs-Information aufweist und daß der anfragende Knoten nach Erhalt der Aktualisierungsantworten der angefragten Knoten eine Aktualisierung seiner lokalen Routing-Tabelle vornimmt, wenn die Topologie-Änderungs- Information des angefragten Knotens aktueller als die Topologie-Änderungs-Information des anfragenden Knotens ist.

5. Netzwerk nach Anspruch 1, dadurch gekennzeichnet, dass die Tabellen-Update-Information und/oder die Feld-Update-Information und/oder die Topologie-Änderungs-Information Zeitinformationen sind.

6. Netzwerk nach Anspruch 1, dadurch gekennzeichnet, dass die Tabellen-Update-Information und/oder die Feld-Update-Information und/oder die Topologie-Änderungs-Information Sequenznummern sind.

7. Netzwerk nach Anspruch 1, dadurch gekennzeichnet, dass daß der anfragende Knoten nach Erhalt der Aktualisierungsantworten der angefragten Knoten eine Aktualisierung seiner lokalen Routing-Tabelle vornimmt, wenn die Topologie-Änderungs-Information des angefragten Knotens genauso aktuell ist wie die Topologie-Änderungs-Information des anfragenden Knotens und wenn die Pfadlänge zu dem jeweiligen Zielknoten durch die Aktualisierung kürzer wird.

8. Netzwerk nach Anspruch 1, dadurch gekennzeichnet, dass daß der anfragende Knoten nach Erhalt der Aktualisierungsantworten der angefragten Knoten eine Aktualisierung seiner lokalen Routing-Tabelle vornimmt, wenn die Topologie-Änderungs-Information des angefragten Knotens genauso aktuell ist wie die Topologie-Änderungs-Information des anfragenden Knotens und wenn die maximale Datenübertragungsrate zu dem jeweiligen Zielknoten durch die Aktualisierung größer wird.

9. Netzwerk nach Anspruch 1, dadurch gekennzeichnet, dass das Netzwerk in mehrere Sub-Netzwerke gruppierbar ist, die jeweils einen Controller zur Steuerung der Sub-Netzwerke enthalten, daß die Sub-Netzwerke jeweils über Brücken-Knoten verbindbar sind und daß der jeweilige Controller zur Speicherung und Verwaltung einer zentralen Routing- Tabelle für das jeweilige Sub-Netzwerk vorgesehen ist.

10. Routing-Verfahren für ein dynamisches Netzwerk, welches mehrere Knoten aufweist, wobei vorgesehen ist,
in Knoten des Netzwerks Routing-Informationen in lokalen Routing-Tabellen mit Feldern für die Zielknoten zu speichern,
daß die Knoten zum Aktualisieren der lokalen Routing-Tabellen eine Aktualisierungsanfrage an andere Knoten senden,
daß die angefragten Knoten eine Aktualisierungsantwort mit aktualisierten Routing- Informationen an den anfragenden Knoten senden.