Beschreibung

Verfahren zum Betreiben eines drahtlosen, vermaschten Datennetzes mit einer Mehrzahl an Netzknoten

Die Erfindung betrifft ein Verfahren zum Betreiben eines drahtlosen, vermaschten Datennetzes mit einer Mehrzahl an Netzknoten, bei dem Datenrahmen von einem Quellknoten über einen oder mehrere Zwischenknoten zu einem Zielknoten uber- tragen werden, wobei der Quellknoten, der eine oder die mehreren Zwischenknoten und der Zielknoten Netzknoten des Datennetzes darstellen.

Die übertragung von Datenrahmen zwischen dem Quellknoten und dem Zielknoten kann bei vermaschten Datennetzen prinzipiell über unterschiedliche Routen erfolgen. Unter einer Route wird eine Anzahl an Netzknoten verstanden, welche benachbart zueinander angeordnet sind und an ihren Enden eine Datenverbindung zu dem Quellknoten und dem Zielknoten aufweisen. Um die übertragung der Datenrahmen von dem Quellknoten zu dem Zielknoten nicht dem Zufall zu überlassen, wird von dem Quellknoten eine sog. Weg-Anfragenachricht (sog. route request) an alle benachbarten Netzknoten ausgesendet (sog. Broadcast) , welche die Weg-Anfragenachricht ebenfalls im Rahmen eines Broadcasts an die ihnen benachbarten Netzknoten weiterleiten, bis die Weg-Anfragenachricht schließlich den Zielknoten erreicht. Von dem Zielknoten wird eine Weg-Antwortnachricht (sog. route reply) initiiert. Bei der übertragung der Weg- Anfragenachricht und bei der zielgerichteten Ruckubertragung der Weg-Antwortnachricht (sog. Unicast) zu dem Quellknoten werden auf jedem Netzknoten Eintrage in sog. Wegewahl- Tabellen (sog. Routing-Tabellen) erstellt. Hierdurch ergibt sich ein definierter Pfad zur übertragung von Datenrahmen zwischen dem Quellknoten und dem Zielknoten.

Im Rahmen der vorliegenden Erfindung wird deshalb unter einem Pfad oder Datenpfad (englisch: route) die übertragung von Da-

tenrahmen über einen oder mehrere bestimmte Zwischenknoten zwischen dem Quellknoten und dem Zielknoten verstanden. Datenrahmen, die von dem Quellknoten zu dem Zielknoten entlang des Datenpfades übertragen werden, werden auf einer Vorwarts- route (sog. forward route) übertragen. Werden Datenrahmen von dem Zielknoten an den Quellknoten übertragen, so wird dies in der folgenden Beschreibung als Ruckwartsroute (sog. reverse route) bezeichnet.

Bei derartigen drahtlosen, vermaschten Datennetzen besteht das Problem, dass einzelne Datenrahmen auf einem Pfad zwischen dem Quellknoten und dem Zielknoten fehlgeleitet werden können, wodurch Schleifen oder Datenschleifen entstehen. Hierdurch wird die Datenkommunikation zwischen dem Quellkno- ten und dem Zielknoten beeinträchtigt. Das fehlerhafte übertragen von Datenrahmen kann bei allen bekannten Ubertragungs- protokollen (sog. routing protocols) auftreten. Die Bildung solcher unerwünschter Datenschleifen kann durch fehlerhafte Netzknoten oder zufallig oder böswillig bei der übertragung von Datenrahmen zu einem Netzknoten entstehen, der sich auf dem Pfad in Ubertragungsrichtung vor dem übertragenden Netzknoten befindet. Bei der Schleifenbildung werden der oder die Datenrahmen zu einem Netzknoten weitergeleitet, welcher sich in Vorwartsrichtung auf dem Pfad dichter am Quellknoten be- findet. Im Ergebnis kann hierdurch die zur Verfugung stehende Bandbreite des Netzwerks verringert werden.

Um den fortwahrenden Transport eines fehlgeleiteten Datenrahmens zu verhindern, ist es bekannt, in den Datenrahmen eine Lebensdauer-Information zu integrieren. Dies wird beispielsweise bei Datenpaketen nach dem Internetprotokoll (IP) und bei Datenpaketen gemäß der Spezifikation IEEE 802.11s umgesetzt. Die Lebensdauer-Information wird als Time to Live (ttl) bezeichnet. Dies ist ein Integer-Wert, der ublicherwei- se vom Sender des Datenrahmens auf 255 gesetzt wird. Bei jedem Weiterleiten des Datenrahmens zu einem neuen Netzknoten wird der Wert um 1 dekrementiert . Sobald der Lebensdauer-Wert

0 ist, wird der Datenrahmen verworfen und in dem Datennetz nicht mehr weiter transportiert.

Ein weiterer, bekannter Sicherheitsmechanismus ist das sog. „source routing". Der Empfanger eines Datenrahmens kann hierbei überprüfen, ob der Sender (Transmitter) des Datenrahmens die Erlaubnis besitzt, diesen Datenrahmen an den Empfanger weiterzuleiten. Die überprüfung basiert dabei auf einer Pfadinformation, welche in den Datenrahmen enthalten ist.

Weiterhin bekannt ist die Verwendung von eindeutigen Sequenznummern bei der übertragung von Datenrahmen. Hierdurch kann verifiziert werden, ob Datenrahmen bereits übertragen wurden. Anhand der Sequenznummern kann damit, wenn ein Datenrahmen bei einem Netzknoten zum zweiten oder wiederholten Male bei einem Netzknoten ankommt, auf eine Schleifenbildung geschlossen werden.

Von dem Algorithmus Ad-hoc On-demand Distance Vector Routing (AODV), wie dieser für IP MANET Routing in RFC 3561 beschrieben ist, ist die Verwendung sog. Precursor-Listen bekannt. Die Precursor-Listen werden für Fehlernotifikationen der Netzknoten verwendet. Hierbei wird eine Precursor-Liste sowohl für die Vorwartsrichtung als auch für die Ruckwartsrich- tung eines Datenpfades erstellt. Dies erfolgt wahrend des

Verarbeitens der Weg-Antwortnachricht, welche von dem Zielknoten ausgesendet wurde. Dieser Vorgehensweise liegt zu Grunde, dass beide Richtungen (Vorwartsrichtung und Ruck- wartsrichtung) demselben Pfad folgen. Die im Rahmen von AODV verwendeten Precursor-Listen können so jedoch das Auftreten von Schleifen nicht verhindern.

Es ist daher Aufgabe der Erfindung, ein Verfahren bereitzustellen, mit dem bei der übertragung von Datenrahmen in einem drahtlosen, vermaschten Datennetz Datenschleifen vermieden werden können.

Eine weitere Aufgabe der Erfindung ist es, ein Verfahren bereitzustellen, mit dem die übertragung von Datenrahmen in einem drahtlosen, vermaschten Datennetz eine möglichst effiziente Nutzung der von dem Datennetz zur Verfugung gestellten Ressourcen erlaubt.

Diese Aufgaben werden durch ein Verfahren mit den Merkmalen des Anspruchs 1 gelost. Vorteilhafte Ausfuhrungsformen sind in den abhangigen Ansprüchen wiedergegeben.

Bei dem erfindungsgemaßen Verfahren zum Betreiben eines drahtlosen, vermaschten Datennetzes mit einer Mehrzahl an Netzknoten, bei dem Datenrahmen von einem Quellknoten über einen oder mehrere Zwischenknoten zu einem Zielknoten uber- tragen werden, stellen der Quellknoten, der eine oder die mehreren Zwischenknoten und der Zielknoten Netzknoten des Datennetzes dar. Bei der übertragung eines Datenrahmens wird von zumindest manchen der Netzknoten, die den Datenrahmen empfangen, anhand einer dem Zielknoten des Datenrahmens zuge- ordneten Precursor-Liste überprüft, ob der den Datenrahmen sendende Netzknoten in der Precursor-Liste enthalten ist. Im positiven Fall wird der Datenrahmen zu einem weiteren Netzknoten übertragen. Im negativen Fall wird der Datenrahmen verworfen oder es wird eine Fehlerbehandlungsroutine durchge- fuhrt.

Die Erfindung schlagt vor, Precursor-Listen zu verwenden, um Datenrahmen aufzuspüren, die von Netzknoten stammen, die zur übertragung des betreffenden Datenrahmens nicht autorisiert oder vorgesehen sind. Precursor-Listen sind Listen mit einer Angabe über unmittelbare Nachbar-Netzknoten. Hierdurch können Datenschleifen in einem drahtlosen, vermaschten Datennetz vermieden werden. Durch die Vermeidung von Datenschleifen lasst sich die Verschwendung wertvoller Bandbreite in dem Da- tennetz vermeiden.

Damit Warteschleifen zuverlässig vermieden werden, müssen die Netzknoten überprüfen, ob der den Datenrahmen sendende Netzknoten in der Precursorliste enthalten ist. Die überprüfung wird zweckmaßigerweise von allen Netzknoten vorgenommen. Die überprüfung durch den Zielknoten ist nicht zwingend notwendig.

Denkbar ist auch eine Variante, in der die überprüfung von allen Netzknoten vorgenommen wird, mit Ausnahme des Zielkno- tens und des Zielknotens und des Zwischenknotens unmittelbar vor dem Zielknoten. In entsprechender Weise wurde die überprüfung dann auch nicht von dem Zwischenknoten unmittelbar vor dem Quellknoten vorgenommen werden, wenn der Quellknoten das Ziel einer Nachricht ist (sog. Ruckwartspfad) .

Gemäß einer Ausbildung werden für den Quellknoten, den Zielknoten und den oder die Zwischenkonten jeweils eine Wegewahl- Tabelle (eine sog. Routing-Tabelle) angelegt, wobei jede der Wegewahl-Tabellen zumindest einen Eintrag umfasst. Für jeden Eintrag der Wegewahl-Tabelle wird die Precursor-Liste angelegt, welche direkte Nachbarknoten umfasst, die einen Datenrahmen zu dem betreffenden Netzknoten übertragen können. Damit ist für jeden der Netzknoten festgelegt, von welchen benachbarten Netzknoten innerhalb eines Datenpfades Datenrahmen empfangen werden dürfen.

Die Erstellung der Wegewahl-Tabelle erfolgt im Rahmen der übertragung einer von dem Quellknoten initiierten Weg- Anfragenachricht und einer von dem Zielknoten initiierten Weg-Antwortnachricht. Eine Weg-Anfragenachricht wird auch als Route Request-Nachricht bezeichnet. Eine Weg-Antwortnachricht ist als Route Reply-Nachricht dem Fachmann gelaufig. Weg- Anfragenachrichten werden als Broadcast-Nachricht von dem Quellknoten ausgesandt. Im Gegensatz dazu erfolgt die von dem Zielknoten initiierte Wegantwortnachricht als Unicast-

Nachricht. In den Wegewahl-Tabellen werden Eintrage für die Vorwartsrichtung eines Datenpfades als auch für die Ruck-

wartsrichtung eines Datenpfades angelegt. Die Vorwartsrich- tung eines Datenpfades erstreckt sich von dem Quellknoten zu dem Zielknoten. Die Ruckwartsrichtung ist in entsprechender Weise von dem Zielknoten zu dem Quellknoten gerichtet.

Die Erstellung und/oder Aktualisierung der Precursor-Liste wird gemäß einer weiteren Ausbildung im Rahmen der von dem Zielknoten initiierten Weg-Antwortnachricht vorgenommen.

Gemäß einer weiteren Ausbildung umfasst ein Datenrahmen die Adresse des Quellknotens, die Adresse des Zielknotens, die Adresse des sendenden Netzknotens dieses Datenrahmens und die Adresse des diesen Datenrahmens empfangenden Netzknotens. Der den Datenrahmen empfangende Netzknoten überprüft, ob die ihm zugewiesene Adresse der Adresse des Zielknotens in dem Datenrahmen entspricht. Im positiven Fall der überprüfung wird der Datenrahmen einer weiteren Einheit zur Verarbeitung, insbesondere einer höheren Schicht im OSI-Referenzmodell, zugeführt. Dies bedeutet, dass der Datenrahmen den Zielknoten er- reicht hat.

Gemäß einer weiteren Ausbildung umfasst ein Eintrag in der Precursor-Liste eine Media Access Control-Adresse (Media Access Control = MAC) oder eine IP-Adresse und eine Lebensdauer des Eintrags. Eine Precursor-Liste ist damit eine Liste von MAC- oder IP-Adressen. Elemente einer Precursor-Liste sind direkte Nachbarn (Netzknoten) des Netzknotens, welche den Datenrahmen zu diesem Netzknoten übertragen dürfen. Dies resultiert daraus, dass der den Datenrahmen übertragende Netzkno- ten zu dem betreffenden Netzknoten auf dem Datenpfad zu dem

Zielknoten liegt. Hierbei wird eine Precursor-Liste pro Wegewahl-Tabelleneintrag erstellt. In vielen Routing-Protokollen ist dies gleichbedeutend mit einem Eintrag pro Zielknoten, da es pro Zielknoten lediglich einen einzigen Routing- Tabelleneintrag gibt. Im Ergebnis bedeutet dies, dass eine Precursor-Liste für einen Zielknoten n Eintrage haben kann,

wobei n <≡ [1, N] ist. N ist die Anzahl der Quellen, welche aktive Datenpfade über diesen Knoten (N ≥ 1) haben können.

Neben der Verwendung von Precursor-Listen zum Detektieren von fehlgeleiteten Datenrahmen schlägt die Erfindung eine Vorgehensweise vor, wie diese dafür verwendeten Precursor-Listen erstellt und gepflegt werden können.

Bei der Erfindung werden als Einträge in die Precursor-Listen Wertepaare einer MAC- oder IP-Adresse und einer Lebensdauer abgelegt. Die Lebensdauer des Eintrags ist vergleichbar mit dem Lebensdauer-Wert in dem AODV-Algorithmus . Das zu Grunde liegende Prinzip besteht darin, dass die Lebensdauer eines Eintrags der Precursor-Liste eines Netzknotens auf einen Aus- gangswert zurückgesetzt wird, wenn dieser Netzknoten einen Datenrahmen von dem Netzknoten erhält, dessen Adresse der MAC-Adresse in dem Eintrag entspricht. Die Lebensdauern werden für Einträge in Vorwärts- als auch in Rückwärtsrichtung aktualisiert, wenn auch die Lebensdauern der Routing- Tabelleneinträge sowohl in Vorwärts- als auch in Rückwärtsrichtung bei Erhalt eines entsprechenden Datenrahmens aktualisiert werden. Ferner wird ein Eintrag in der Precursor- Liste gelöscht, wenn die Lebensdauer des Eintrags abgelaufen ist. Hierdurch kann sichergestellt werden, dass die Gefahr einer Datenschleifenbildung minimiert ist.

Die Lebensdauer eines Eintrags in der Precursor-Liste ist maximal so lang wie ein Pfad-Lebensdauerwert von dem Quellknoten zu dem Zielknoten, wobei der Pfad-Lebensdauerwert als In- formation in dem Routing-Tabelleneintrag enthalten ist.

Eine Aktualisierung der Lebensdauer eines Eintrags in der Precursor-Liste und dem Pfad-Lebensdauerwert in dem betreffenden Routing-Tabelleneintrag erfolgt gemäß einer Ausbildung gleichzeitig. Eine Aktualisierung der Lebensdauer kann beispielsweise auch durch Weg-Antwortnachrichten (Route Reply- Nachrichten) erfolgen. Es ist hingegen nicht vorgesehen, dass

Weg-Anfragenachrichten (Route Request-Nachrichten) eine Aktualisierung der Precursor-Listen vornehmen.

Der Grund hierfür ist wie folgt: Die Precursor-Listen werden während einer sog. Route Discovery, mit welcher der Datenpfad zwischen dem Quellknoten und dem Zielknoten festgelegt werden soll, erstellt. Die grundsätzlichen Mechanismen stammen dabei aus der ursprünglichen Spezifikation zu AODV. Eine Veröffentlichung hierzu findet sich in [1] . Dabei wird das aus dem Stand der Technik bekannte Vorgehen durch das Hinzufügen von Lebensdauern zu den Einträgen der Precursor-Listen ergänzt. Die von dem Quellknoten ausgesendete Weg-Anfragenachricht an alle Netzknoten des Datennetzes erzeugt Rückwärtsrichtungen von allen Netzknoten zu dem Quellknoten. Nachdem diese Rück- wärtsrouten vom Ende her, d.h. von dem Zielknoten her, gebildet werden, sind die vorhergehenden Netzknoten noch unbekannt, so dass daher in die Precursor-Liste für den Wegewahl- Tabelleneintrag des Quellenknoten nichts eingetragen werden kann. Die Weg-Antwortnachricht, welche von dem Zielknoten zu dem Quellknoten unter Verwendung eines Unicast-Mechanismus übertragen wird, führt hingegen zur Erzeugung von Einträgen in die Precursor-Listen, sowohl für die Vorwärts- als auch für die Rückwärtsroute. Die Informationen „destination node" und „source_node" werden hierbei von korrespondierenden FeI- dern der Weg-Antwortnachricht entnommen.

Für die Population der Routing-Tabelle werden folgende Schritte vorgenommen:

• routingtable (destination_node) . create;

• routingtable (desitnation_node) . lifetime .update (RREP . lifetime) ;

• routingtable (destination_node) .precursor_list . add (routingtable (source_node) next_hop, RREP . lifetime) ; • routingtable (source_node) .precursor_list . add ( weg-antwortnachricht . transmitter, routingtable (source node) .lifetime) .

Die Erstellung einer Precursor-Liste für den entsprechenden Routing-Tabelleneintrag ist auf einem solchen Zwischenknoten nicht notwendig, wenn er bei einer Datenrahmenübertragungs- Route zwischen dem Zielknoten und dem Quellknoten dem Quellknoten benachbart ist beziehungsweise er bei einer Datenrah- menübertragungs-Route zwischen dem Quellknoten und dem Zielknoten dem Zielknoten benachbart ist. Die Erstellung einer Precursor-Liste auch in diesen Fällen vereinfacht und beschleungigt aber die Verfahren.

Sowohl AODV als auch HWMP (Hybrid Wireless Mesh Protocol) erlauben es den Zwischenknoten, auf eine Weg-Anfragenachricht mit einer Weg-Antwortnachricht zu antworten, wenn diese eine gültige Route zu dem Zielknoten kennen. In einem solchen Fall müssen die folgenden Aktualisierungen in den Wegewahl- Tabellen des Zwischenknotens, der die Weg-Anfragenachricht generiert, vorgenommen werden. Hierbei werden die Felder „destination_node" und „source_node" den korrespondierenden Feldern der Weg-Anfragenachricht entnommen:

routingtable (destination_node) .precursor_list . add(rou- tingtable (source_node) .next_hop, routingtable (destina- tion_node) . lifetime) - routingtable (source_node) .precursor_list . add(routing- table (destination_node) .next_hop, routingtable (source_ node) .lifetime)

Wenn ein weiterer Netzknoten, der nicht der Quellknoten, der Zielknoten oder einer der Zwischenknoten in einem Datenpfad zwischen dem Quellknoten und dem Zielknoten ist, nach Empfang einer Weg-Anfragenachricht des Quellknotens (aber keiner Weg- Antwortnachricht) einen Datenrahmen an den Quellknoten über einen weiteren Zwischenknoten überträgt, welcher weitere Zwi- schenknoten der nächste Netzknoten auf einem Rückwärtspfad zum Quellknoten ist, der nicht in der Precursor-Liste des Routing-Tabelleneintrags für den Quellknoten den weiteren

Netzknoten enthält, verwirft der weitere Zwischenknoten gemäß einer Ausführungsform die von dem weiteren Netzknoten empfangenen Datenrahmen.

Der zwischen dem weiteren Netzknoten und dem Quellknoten gebildete Datenpfad wird gemäß einer weiteren Ausführung in dem weiteren Netzknoten als ungültig gekennzeichnet. Um das unnötige Senden von Datenrahmen von dem weiteren Netzknoten zum Quellknoten zu vermeiden, wird ein solcher Pfad markiert, so dass der weitere Netzknoten eine Route Discovery zu dem

Quellknoten durchführen kann. Dies erfolgt anstatt der Verwendung des Rückwärtspfades, der im Rahmen der Route Discovery zwischen dem Quellknoten und dem weiteren Netzknoten gebildet wurde.

In einer alternativen Ausbildung werden die Precursor-Listen für den Pfad zwischen dem weiteren Netzknoten und dem Quellknoten gefüllt, bevor der Datenrahmen von dem weiteren Netzknoten zu dem Quellknoten übertragen wird. Dies kann bei- spielsweise durch das Senden einer Weg-Antwortnachricht vom weiteren Netzknoten an den Quellknoten erfolgen.

In einer weiteren alternativen Ausgestaltungsform werden bei Erhalt einer Weg-Anfragenachricht die Adressen aller zu einem Netzknoten benachbarten Netzknoten zusammen mit einem Ablaufwert bei Erhalt einer Weg-Anfragenachricht in die Precursor- Liste dieses Netzknotens als zeitweiliger Eintrag eingetragen.

Gemäß einer weiteren Ausgestaltung wird hierbei der zu dem Netzknoten benachbarte Netzknoten, der die Weg- Anfragenachricht ausgesendet hat, nicht in die Precursor- Liste dieses Netzknotens eingetragen.

Eine weitere Ausgestaltung sieht vor, dass der zeitweilige

Eintrag in der Precursor-Liste mit einem Ablaufwert (wie z.B. einem TTL (Time-to-Live-Wert) im Internet Protocol Header,

z.B. IPV4) versehen wird, welcher denselben Wert aufweist wie der Rückwärtspfad, der durch die Weg-Anfragenachricht aufgebaut wurde .

In einer weiteren optionalen Ausgestaltung können die zeitweiligen Einträge aus der Precursor-Liste gelöscht werden, wenn ein Eintrag in die Precursor-Liste im Rahmen der von dem Zielknoten initiierten Weg-Antwortnachricht erstellt wird.

Das gleiche Problem existiert auch mit pro-aktiven Weg- Anfragenachrichten bei einer pro-aktiven Erweiterung für das sog. Tree Routing in HWMP. Der undirektionale Baum von dem Ausgangsknoten (root tree) wird durch eine Weg- Anfragenachricht angestoßen, wobei die Weg-Anfragenachricht zu allen, mit dem Ausgangsknoten verbundenen Netzknoten übertragen wird. Dieses Vorgehen erzeugt den Rückwärtspfad zu dem Ausgangsnetzknoten, wobei jedoch die Precursor-Liste nicht erzeugt werden kann. HWMP bedient sich dabei einer ähnlichen Lösung wie von der Erfindung vorgeschlagen. Wenn ein pro- aktives Weg-Antwortnachricht-Flag gesetzt ist, wird eine Weg- Antwortnachricht in Reaktion auf eine Weg-Anfragenachricht ausgesendet. Hierdurch kann die Precursor-Liste wie üblich gefüllt werden. Wenn das pro-aktive Weg-Antwortnachricht-Flag nicht gesetzt ist, kann eine Weg-Antwortnachricht vor den Da- tenrahmen gesendet werden, so dass die Precursor-Liste „just in time" erstellt wird.

Die Erfindung stellt einen simplen Mechanismus zum Aufspüren von fehlgeleiteten Datenrahmen dar, um die Erzeugung von Da- tenschleifen aufgrund eines absichtlichen oder fehlerhaften Weiterleitens zu vermeiden. Dies wird durch die Verwendung von Precursor-Listen zum Aufspüren der fehlgeleiteten Datenrahmen bewerkstelligt. Dabei wird der Sender des Datenrahmens mit in der Precursor-Liste befindlichen erlaubten Vorgängern (= Sendern oder Transmittern) verglichen. Die Erfindung erweitert dabei den Mechanismus von Precursor-Listen, wie dieser für AODV spezifiziert ist. Einem Eintrag ist eine Lebens-

dauer in der Precursor-Liste zugeordnet, so dass der Inhalt der Precursor-Liste nun zu den aktiven Datenpfaden in dem drahtlosen, vermaschten Datennetz korrespondiert.

Die Erfindung wird nachfolgend weiter unter Bezugnahme auf die Figuren erläutert. Es zeigen:

Fig. 1 ein vermaschtes Datennetz mit einer Mehrzahl an

Netzknoten, anhand dem das der Erfindung zu Grunde liegende Verfahren erläutert wird,

Fig. 2 eine Darstellung, aus der in der Beschreibung verwendete Definitionen von Begriffen hervorgehen,

Fig. 3-8 jeweils Routing-Tabellen für die in Fig. 1 gezeigten Netzknoten, wobei die Population der Routing- Tabellen sowie darin enthaltener Precursor-Listen beim Aufbau eines Datenpfads zwischen zwei der Netzknoten des Datennetzes aus Fig. 1 erläutert wird, und

Fig. 9 eine Legende für die in den Fig. 3 bis 8 verwendeten Bezeichnungen.

Fig. 1 zeigt exemplarisch ein vermaschtes Datennetz mit einer Mehrzahl an Netzknoten MN. Die Netzknoten MN sind teilweise untereinander über Kommunikationsstrecken KS miteinander zum Datenaustausch verbunden. Die Kommunikationsstrecken KS sind drahtlos ausgebildet. Jedem der Netzknoten MN ist eine ein- deutige Adresse zugewiesen, anhand welcher eine übertragung von Datenrahmen von einem Quellknoten zu einem Zielknoten möglich ist. In der Fig. 1 sind die Adressen der Netzknoten MN mit den Bezugszeichen S, B, A, C, D, F und G gekennzeichnet. Die übertragung eines Datenrahmens von einem Netzknoten MN zu einem benachbarten Netzknoten MN über die Kommunikationsstrecke KS ist durch einen Pfeil gekennzeichnet. Die übertragung von Datenrahmen von einem Quellknoten des Datennetzes

zu einem Zielknoten des Datennetzes über einen oder mehrere Zwischenknoten, wobei Quellknoten, Zielknoten und Zwischenknoten durch Netzknoten des Datennetzes gebildet sind, erfolgt hop-by-hop, also von Netzknoten zu Netzknoten.

Sollen z.B. von dem Quellknoten S Datenrahmen zu dem Zielknoten D des Datennetzes aus Fig. 1 übertragen werden, so muss zunächst ein Datenpfad ermittelt werden, in welchem die zwischen dem Quellknoten S und dem Zielknoten D gelegenen Zwi- schenknoten (im Ausfuhrungsbeispiel die Netzknoten B, A und C) ermittelt werden, wobei dem jeweiligen Netzknoten Wegewahl-Tabellen zugeordnet sind. In der nachfolgenden Beschreibung werden die Wegewahl-Tabellen als Routing-Tabellen bezeichnet. Diese sind in Fig. 1 mit den Bezugszeichen RT ver- sehen. In dem dargestellten Ausfuhrungsbeispiel umfasst ein Eintrag einer Routing-Tabelle RT drei Werte. Der erste Wert gibt die Adresse des Zielknotens an. Der zweite Wert stellt eine Pfadmetrik dar, was gleichbedeutend ist mit der Anzahl der hops bis zu dem zu erreichenden Zielknoten. Der dritte Wert stellt die Adresse des Netzknotens dar, zu welchem der Datenrahmen als nächstes übertragen werden soll. Dies wird auch als „next hop" bezeichnet.

Die Ermittlung des Datenpfades erfolgt mittels einer sog. „route discovery", welche vom Betrieb eines drahtlosen, ver- maschten Datennetzes hinlänglich bekannt sind. Hierzu wird von dem Quellknoten S eine Weg-Anfragenachricht erzeugt und an samtliche, mit dem Quellknoten verbundene Netzknoten übertragen. Dieses als Broadcast bezeichnete Ubertragungsverfah- ren wird ebenfalls von den Zwischenknoten durchgeführt, welche eine derartige Weg-Anfragenachricht, nachfolgend Route Request-Nachricht oder Route Request, erhalten haben. Erhalt der Zielknoten D eine derartige Route Request-Nachricht, so antwortet er mit einer Weg-Antwortnachricht, nachfolgend als Route Reply oder Route Reply-Nachricht bezeichnet. Im Gegensatz zu der Route Request-Nachricht ist diese jedoch zielge-

richtet an den Quellknoten S übertragen. Dies wird auch als Unicast bezeichnet.

Im Rahmen der Route Discovery können die Routing-Tabellen je- weiliger Zwischenknoten in einem Datenpfad erstellt und gefüllt werden.

Fig. 2 zeigt eine bei der Beschreibung von vermaschten Datennetzen übliche Konvention. Der Einfachheit halber ist hierbei zu Grunde gelegt, dass der Quellknoten SN über lediglich einen Zwischenknoten IN mit dem Zielknoten DN verbunden ist. Zwischen dem Quellknoten SN und dem Zwischenknoten IN bzw. zwischen dem Zwischenknoten IN und dem Zielknoten DN ist jeweils eine drahtlose Kommunikationsstrecke KS ausgebildet. Die Netzknoten SN, IN und DN liegen in einem Datenpfad DP, über welchen die Datenrahmen übertragen werden. Der Datenpfad DP ist über das oben beschriebene Route Discovery-Verfahren ermittelt worden. Datenrahmen, die von dem Quellknoten SN an den Zielknoten DN übertragen werden, werden in Vorwärtsrich- tung bzw. auf einer Vorwärtsroute FR übertragen. Datenrahmen, die von dem Zielknoten DN an den Quellknoten SN übertragen werden, werden in Rückwärtsrichtung oder auf einer Rückwärtsroute RR übertragen. Nachfolgend wird auf diese Konvention Bezug genommen werden.

Bei der folgenden kurzen Beschreibung der Problemstellung anhand der Fig. 1 wird davon ausgegangen, dass der Datenpfad zwischen dem Netzknoten S als Quellknoten und dem Netzknoten D als Zielknoten wie folgt lautet: S-B-A-C-D. Ein weiterer Datenpfad soll zwischen dem Netzknoten G als Quellknoten und dem Netzknoten D als Zielknoten gebildet sein. Der Datenpfad hierfür lautet beispielsweise: G-F-B-A-C-D.

Der Netzknoten B, welcher einen Zwischenknoten darstellt, weist einen Routing-Tabelleneintrag auf, in welchem als Zielknoten der Netzknoten D enthalten ist. Bis zum Erreichen des Netzknotens D sind drei Hops notwendig, wobei ein von B er-

haltener Datenrahmen an den Netzknoten A (ebenfalls ein Zwischenknoten) übertragen werden muss. In entsprechender Weise weist der Netzknoten A einen Routing-Tabelleneintrag auf, in welchem der Netzknoten D als Zielknoten enthalten ist. Bis zum Erreichen des Zielknotens D sind zwei Hops notwendig, wobei ein von A erhaltener Datenrahmen an den Netzknoten C (ein Zwischenknoten) übertragen werden muss. In entsprechender Weise weist der Netzknoten C einen Routing-Tabelleneintrag auf, in welchem der Netzknoten D als Zielknoten enthalten ist. Bis zum Erreichen des Zielknotens D ist ein Hop notwendig, wobei ein von C erhaltener Datenrahmen an den Netzknoten D (den Zielknoten) übertragen werden muss. Erhält der Netzknoten F (ebenfalls ein Zwischenknoten) einen Datenrahmen für den Zielknoten D, so erhält dieser aus einem Routing- Tabelleneintrag die Information, dass bis zu dem Zielknoten vier Hops zu absolvieren sind. Von dem Netzknoten F erhaltene Datenrahmen müssen an den Netzknoten B weiter übertragen werden.

Bei einem Fehlverhalten des Netzknotens A, welches absichtlicher oder fehlerhafter Natur sein kann, kann es vorkommen, dass Datenrahmen nicht zu dem Netzknoten C, sondern zu dem Netzknoten F übertragen werden. Dies kann beispielsweise durch die Informationen aus der Weg-Anfragenachricht unter- stützt werden, die Netzknoten A von Netzknoten F erhalten hat. Hieraus ergibt sich die in Fig. 1 mit dem durchbrochenen Pfeil gekennzeichnete Datenschleife. Der Netzknoten F wird nämlich, aufgrund seines Routing-Tabelleneintrags den Datenrahmen an B weiterleiten, welcher seinerseits den Datenrahmen wiederum an A überträgt.

Da diese Schleifenbildung wertvolle Bandbreite in einem drahtlosen vermaschten Datennetz kostet, werden bei der Erfindung die Routing-Tabelleneinträge jeweils um eine Precur- sor-Liste ergänzt. Durch das Vorsehen der Precursor-Listen können Datenrahmen von solchen Netzknoten festgestellt werden, welche diese nicht zu dem, den Datenrahmen empfangenden

Netzknoten senden dürfen. Hierdurch lassen sich Datenschleifen vermeiden.

Jede Precursor-Liste, welche pro Routing-Tabelleneintrag er- stellt wird, stellt eine Liste von Media Access Control

(MAC) -Adressen dar. Elemente der Precursor-Liste sind direkte Nachbar-Netzknoten des eine Precursor-Liste aufweisenden Netzknotens, die entsprechend der durch das Routing-Protokoll ermittelten Routen Datenrahmen zu diesem Netzknoten ubertra- gen. Eine Precursor-Liste eines Routing-Tabelleneintrages eines Netzknotens kann damit n G [1, N] Eintrage aufweisen, wobei N die Anzahl der Quellknoten ist, die einen aktiven Datenpfad über den betreffenden Knoten haben.

In dem Standard IEEE 802.11s (WLAN Mesh Networking) ist ein Format für Datenrahmen definiert, welches sechs Adressen um- fasst. Der darin definierte Datenrahmen umfasst u.a. die Adresse des Netzknotens, der den Datenrahmen übertragt (trans- mitter address) . Dieser Netzknoten ist der vorhergehende Netzknoten (hop) in dem Datenpfad. Dieser stellt damit mit anderen Worten den Vorganger oder Precursor dar. Diese Adresse, d.h. die Transmitter-Adresse, wird mit der Adresse verglichen, welche in der Precursor-Liste auf dem Pfad zu dem gewünschten Zielknoten enthalten ist. Wenn der Empfangerkno- ten der Zielknoten ist, braucht der Vergleich nicht mehr durchgeführt zu werden, da das übertragen eines Datenrahmens zu dem Zielknoten zu keiner Datenschleife fuhren wird.

Zur Durchfuhrung des Verfahrens werden drei Adressen beno- tigt. Adresse des Zielknotens, Adresse des Netzknotens, der den Datenrahmen übertragt, sowie die Adresse des Netzknotens, der den Datenrahmen empfangt. Wie erläutert, findet ein Vergleich statt, ob die Zieladresse der Adresse des den Datenrahmen empfangenden Netzknotens entspricht. Ist dies der Fall, so wird der empfangene Datenrahmen einer höheren Verarbeitungsschicht zugeführt. Entspricht die Zieladresse nicht der Adresse des den Datenrahmen empfangenden Netzknotens, so

wird überprüft, ob die Adresse des sendenden Netzknotens (Transmitter) in der Precursor-Liste des Routing- Tabelleneintrages für den Zielknoten enthalten ist. Ist dies der Fall, so wurde der Datenrahmen korrekt übertragen. Der den Datenrahmen empfangende Netzknoten übertragt diesen daraufhin an den Netzknoten, welcher in dem entsprechenden Routing-Tabelleneintrag als Next Hop enthalten ist. Im Falle einer negativen überprüfung wird der Datenrahmen als fehlgeleitet betrachtet, da der Transmitter nicht der vorhergehende Netzknoten auf dem Datenpfad ist und deshalb den Datenrahmen nicht zu diesem Nachbar hatte übertragen dürfen. Der Datenrahmen wird deshalb entweder verworfen oder einer Fehlerbehandlungsroutine zugeführt.

Die Eintrage der Precursor-Listen sind ferner jeweils um einen Lebensdauer-Wert (life time) ergänzt. Ein Eintrag in einer Precursor-Liste enthalt damit das Wertepaar {MAC-Adresse, Lebensdauer}. Die Ergänzung um Lebensdauer-Werte ermöglicht eine Korrespondenz der Precursor-Listen zu den aktiven Daten- pfaden in dem Datennetz. Mit anderen Worten wird damit sichergestellt, dass die Eintrage in den Precursor-Listen auch nur für aktive Datenpfade vorgesehen sind.

Wenn die Lebensdauer eines Eintrags in der Precursor-Liste ablauft, wird der entsprechende Eintrag aus der Precursor- Liste geloscht. Die überprüfung bzw. Aktualisierung eines Lebensdauer-Werts erfolgt immer dann, wenn ein Datenrahmen von einem Netzknoten empfangen wird und ein entsprechender Pre- cursor-Listeneintrag vorhanden ist. Die Lebensdauer der Pre- cursor-Listeneintrage können hierbei in beiden Richtungen, d.h. in Vorwartsrichtung und in Ruckwartsrichtung des Datenpfades aktualisiert werden. Dies korrespondiert zu dem bei AODV/HWMP beschriebenen Vorgehen.

Der neue Wert eines Lebensdauereintrags ist der maximal mögliche Wert für die Lebensdauer. Zweckmaßigerweise ist kein Lebensdauer-Wert eines Precursor-Listeneintrages großer als

eine korrespondierende Lebensdauer des Datenpfades. Grundsätzlich erfolgt eine Aktualisierung eines Lebensdauer-Wertes in der Precursor-Liste zusammen mit der Aktualisierung des Lebensdauer-Werts eines Routing-Tabelleneintrages. Die Le- bensdauer-Werte der Precursor-Listeneinträge werden auch aktualisiert, wenn Route Reply-Nachrichten über den betreffenden Netzknoten laufen. Route Request-Nachrichten sorgen hingegen nicht für eine Aktualisierung des Precursor-Listen- Lebensdauereintrages .

Die den Routing-Tabelleneinträgen zugeordneten Precursor- Listen werden ebenfalls im Rahmen der Route Discovery erzeugt. Dabei kann ein besonderer Fall während des Route Discovery-Prozesses auftreten. Wenn der Quellknoten S mit dem Zielknoten D kommunizieren möchte, wird durch den Quellknoten S eine Route Discovery initiiert, wodurch eine Route Request- Nachricht zu allen Netzknoten in dem Datennetz übertragen wird. Die Route Request-Nachricht erzeugt Rückpfade von allen Netzknoten zu dem Quellknoten S. Wie eingangs erläutert, wird jedoch lediglich ein einziger Datenpfad zwischen dem Quellknoten S und dem Zielknoten D gebildet, auf welchem der Zielknoten D eine Route Reply zurücksendet. Diese Route Reply- Nachricht führt dazu, dass die Precursor-Listen in den Netzknoten erzeugt werden, wobei dies lediglich in solchen Netz- knoten erfolgt, die auf dem Datenpfad zwischen S und D liegen. Der Datenpfad ist, wie eingangs erläutert, S-B-A-C-D. In den anderen Netzknoten, im Ausführungsbeispiel die Netzknoten F und G, werden derartige Precursor-Listen in den zugehörigen Routing-Tabelleneinträgen jedoch nicht erzeugt. Nichtsdesto- trotz ist ein Rückpfad von dem Netzknoten G zu dem Quellknoten S tatsächlich gültig.

Wenn der Netzknoten G einen Datenrahmen zu dem Quellknoten S auf diesem Rückpfad überträgt, so sendet dieser einen Daten- rahmen zu dem nächsten Netzknoten, welcher im Ausführungsbeispiel der Netzknoten F ist. Allerdings weist der Netzknoten F, welcher benachbart zu dem Netzknoten G liegt, keinen Pre-

cursor-Listeneintrag für den Netzknoten G auf. Daher werden die von G übertragenen Datenrahmen auf dem Netzknoten F verworfen, obwohl diese auf einem an sich gültigen Pfad übertragen wurden.

Zur Lösung dieses Problems stehen drei Möglichkeiten zur Verfügung.

1. Der zwischen G und S gebildete Rückpfad wird als ungül- tiger Pfad betrachtet. Um das unnötige Senden von Datenrahmen zu vermeiden, muss dieser Pfad entsprechend markiert werden, so dass der Netzknoten G eine Route Discovery zum Netzknoten S initiieren kann, anstatt den Rückpfad zu S zu nutzen, der von der durch S initiierten Route Discovery initiiert wurde.

2. Es können Precursor-Listen erzeugt werden, indem eine Route Reply-Nachricht an S übertragen wird, bevor die eigentlichen Datenrahmen von G nach S übertragen werden.

3. Alternativ können die Adressen aller benachbarten Netzknoten in die Precursor-Liste für den Rückpfad eingefügt werden. Dies ist nicht notwendig für den Netzknoten, welcher die Route Request-Nachricht ausgesendet hat. Für den Netzknoten F wären dies die benachbarten Netzknoten A und G. Der benachbarte Netzknoten B braucht nicht in die Precursor-Liste aufgenommen werden, da er die Route Request-Nachricht ausgesendet hat. Diese Einträge werden mit einem Time out versehen, welcher denselben Wert auf- weist wie die Rückwärtsroute, die durch die Route Request-Nachricht aufgebaut wurde. Diese einfache Lösung hat jedoch den Nachteil, dass eine kurze Zeitdauer während der Route Discovery gegeben ist, während der kein Schutz gegen Datenschleifenbildung gegeben ist.

In den nachfolgenden Figuren 3 bis 8 wird nunmehr erläutert, auf welche Weise die Routing-Tabelleneinträge mit den zuge-

ordneten Precursor-Listen erzeugt werden, wobei dies unter Bezugnahme auf das in Fig. 1 dargestellte Datennetz erfolgt. Fig. 9 zeigt für das bessere Verständnis eine Legende für die in den Fig. 3 bis 8 gewählten Bezeichnungen.

Eine Routing-Tabelle RT umfasst fünf Einträge: die Adresse eines Zielknotens („destination") , die Anzahl der bis zu dem Zielknoten in dem Datenpfad liegenden Zwischenknoten („di- stance (hops)"), die Adresse des nächsten Netzknotens („next hop") , einen Lebensdauer-Wert für den Routing-Tabelleneintrag („time out (life time)") sowie eine Precursor-Liste, wobei jeder Eintrag der Precursor-Liste die Adresse eines Netzknotens sowie einen Lebensdauereintrag umfasst („precursor list (node, life time)")

Im Rahmen der Beschreibung werden zwei Arten von Nachrichten- Typen NT verwendet. Mit RREQ ist eine Route Request oder Weg- Anfragenachricht bezeichnet. Mit RREP ist eine Route Reply- Nachricht oder Weg-Antwortnachricht bezeichnet. Beide Rou- ting-Nachrichten RN umfassen folgende Werte: Zeitpunkt

(„time/at"), Adresse des sendenden Netzknotens („transmit- ter") , Adresse des Quellknotens („source"), Adresse des Zielknotens ( „destination") , Anzahl der Netzknoten bis zum Zielknoten („hop count") , Lebensdauer („life time").

In Fig. 3 wird in Schritten Sl bis S6 der Aufbau eines Datenpfades zwischen dem Netzknoten G als Quellknoten und dem Netzknoten D als Zielknoten dargestellt. Dabei wird insbesondere ersichtlich, wie nach Aussendung einer Route Request- Nachricht durch den Quellknoten G die Routing-Tabellen eines jeden der Netzkoten S, B, A, C, D, F und G erzeugt werden. Die hervorgehobenen Felder in den einzelnen Tabellen zeigen den Sender der Route Request-Nachricht und diejenigen Felder in einer Routing-Tabelle, die aufgrund einer Verarbeitung der Route Request-Nachricht eine Veränderung nach sich gezogen haben .

In Schritt Sl wird eine Route Request-Nachricht RREQ von dem Netzknoten G ausgesendet. Der Netzknoten G stellt damit den Transmitter der Nachricht dar. Gleichzeitig stellt G den Quellknoten des Datennetzes dar, so dass im Feld „source" e- benfalls G eingetragen ist. Als Ziel enthält die Route Request-Nachricht den Netzknoten D (destination) . Da Transmitter und Quelle der Nachricht identisch sind, wird für den Wert hop count 0 eingetragen. Als Lebensdauer-Wert wird willkürlich der Wert 8 gewählt. In den zugehörigen Routing- Tabellen der Netzknoten G und F ist ersichtlich, dass G der

Sender der Nachricht ist. In der Routing-Tabelle des Netzknotens F, welcher die Route Request-Nachricht RREQ von G erhält, werden Informationen bezüglich der Rückwärtsroute gespeichert. Als Ziel (destination) wird deshalb die Adresse des Netzknotes G erfasst, da dieser der Quellknoten der Route Request-Nachricht ist. Die Distanz zu diesem beträgt einen Hop. Um zu dem Ziel der Rückwärts-Route, der Source, zu gelangen, muss als nächster Knoten (next hop) der Knoten G erreicht werden. Als Lebenszeit für den Routing-Tabelleneintrag für die Rückwärts-Route zum Quellknoten G werden aus der Route Request-Nachricht die 8 Zeiteinheiten gewählt.

In Schritt S2 wird die Route Request-Nachricht RREQ an die mit Netzknoten F über Kommunikationsstrecken KS verbundenen Netzknoten gesandt. Dies sind im Ausführungsbeispiel nach

Fig. 1 die Netzknoten B, A und G. Die Route Request-Nachricht RREQ enthält folgende Informationen: Sender, d.h. Transmitter, der Nachricht ist der Netzknoten F. Die Route Request- Nachricht RREQ wurde durch den Quellknoten G initiiert, so dass dieser im Feld Source eingetragen ist. Ziel ist weiterhin der Zielknoten D, weshalb dieser im Feld Destination eingetragen ist. Die Netzknoten F und G sind einen hop count voneinander entfernt. Die Lebensdauer verbleibt bei dem festgesetzten Wert 8. In jedem der Netzknoten B, A und G, die die Route Request-Nachricht von F erhalten, werden jeweils Routing-Tabelleneinträge angelegt: in den Netzknoten B und A sowohl für den Transmitter-Netzknoten F als auch für den Quell-

knoten G, im Netzknoten G nur für den Transmitter-Netzknoten F. Die Distanz zu dem Ziel der Ruckwarts-Route (Source) wird auf den Wert 2 angepasst.

Auf diese Weise wird die Route Request-Nachricht RREQ weitertransportiert, bis diese schließlich in Schritt S6 den Zielknoten D erreicht. Der Netzknoten D weist zwei Routing- Tabelleneintrage auf, von denen einer für den Netzknoten C als Ziel und einer für den Netzknoten G als Ziel Informatio- nen enthalten.

In Fig. 4 sind in Schritten S7 bis Sil Route Reply- Nachrichten dargestellt, welche von dem Zielknoten D ausgesendet ist. Hierbei ist der Quellknoten G Empfanger der Route Reply-Nachricht . Hierbei ist den jeweiligen Routing-Tabellen zu entnehmen, dass für manche der Routing-Tabelleneintrage eine Precursor-Liste, umfassend die Adresse des vorhergehenden Netzknotens in dem Datenpfad und einen Lebensdauer-Wert, eingetragen sind.

Die Aussendung der Route Reply-Nachricht erfolgt durch den Netzknoten D. Die übertragung der Route Reply-Nachricht erfolgt an den benachbarten Netzknoten C. Im Feld „source" steht weiterhin der Quellknoten G, welcher die Route Request- Nachricht initiiert hat. Zielknoten ist weiterhin Netzknoten D, zu welchem der Quellknoten G einen Datenpfad etablieren mochte. Die hop counts werden aus Sicht des Senders der Route Reply-Nachricht gezahlt, weswegen der Wert 0 betragt. Die Lebensdauer ist entsprechend der Lebensdauer aus der Route Re- quest-Nachricht auf 8 gesetzt, kann jedoch prinzipiell willkürlich gewählt werden. Der Netzknoten C, der die Route Reply-Nachricht vom Netzknoten D empfangt, kann nun einerseits einen neuen Routing-Tabelleneintrag für den Netzknoten D anlegen. Andererseits kann für die Routing-Tabelleneintrage zu den Netzknoten G und D (jeweils destination) ein Precur- sor-Listeneintrag angelegt werden. Soll eine Nachricht von dem Netzknoten C zu dem Netzknoten G als Ziel gesendet wer-

den, so stellt Netzknoten D den Vorgänger im Datenpfad dar. Soll hingegen vom Netzknoten C ein Datenrahmen zu dem Netzknoten D als Empfänger gesendet werden, so stellt Netzknoten A den Vorgänger in dem Datenpfad dar. Diese Information kann dem Routing-Tabelleneintrag zum Netzknoten G als Empfänger entnommen werden, da hier A als next hop enthalten ist.

In entsprechender Weise wird die Route Reply-Nachricht von Netzknoten C an Netzknoten A und von diesem an Netzknoten B, schließlich an Netzknoten F und dann an Netzknoten G transportiert. Hierbei werden jeweils in der beschriebenen Weise Routing-Tabelleneinträge ergänzt und jeweilige Precursor- Listen erzeugt.

Eine den Fig. 3 und 4 entsprechende Vorgehensweise ist in

Fig. 5 in Verbindung mit Fig. 6 sowie in Fig. 7 beschrieben. Dabei wurde jedoch eine Route Request-Nachricht von dem Netzknoten S als Quellknoten ausgesendet, wobei Netzknoten D als Zielknoten bestimmt ist. Wie beispielsweise aus Fig. 5, Schritt S13 hervorgeht, ist der Zeitpunkt an dem die Lebensdauer der mit dieser Route Request-Nachricht erzeugten und aktualisierten Routing-Tabelleneinträge ein anderer (Zeitpunkt 11 anstelle von Zeitpunkt 8) . Bei der Betrachtung der Schritte S18 bis S21 wird ferner ersichtlich, dass manchen Routing-Tabelleneinträgen (vgl. z.B. Schritt S20, Routing- Tabelleneintrag für Netzknoten D) die Precursor-Liste ergänzt ist um einen weiteren Eintrag. Dabei zeigt Schritt S21 in Fig. 7 die endgültigen Routing-Tabellen sämtlicher Netzknoten des beispielhaften Datennetzes der Fig. 1. Falls nun, wie dies in Verbindung mit Fig. 1 beschrieben wurde, der Netzknoten A fehlerhafterweise Daten, die für den Netzknoten D bestimmt sind, an den Netzknoten F anstatt zum Netzknoten C sendet, so werden diese Datenrahmen verworfen, so dass das Auftreten von Datenschleifen verhindert ist.

Die Konsequenzen des erfindungsgemäßen Verfahrens werden nochmals anhand der folgenden Ausführung deutlich. Dabei werden folgende Abkürzungen verwendet:

RA Adresse eines empfangenden Netzknotens („receiver address") , TA Adresse des einen Datenrahmen sendenden Netzknotens

(„transmitter address") ,

DA Adresse des Zielknotens („destination address") , SA Adresse, von welcher der Datenrahmen ursprünglich gesendet wurde („source address") .

Betrachtung des Netzknotens A:

Schritt 1: Netzknoten A empfängt einen Datenrahmen mit RA

= A, TA = B, DA = D, SA = G oder S ;

Schritt 2: Der Netzknoten A ist nicht das Ziel des Datenrahmens (A ≠ D), d.h. die Adresse des Zielknotens entspricht nicht der Adresse des Netzkno- tens,

Schritt 3: Der Datenrahmen wurde korrekt empfangen, da der sendende Netzknoten B in der Precursor- Liste des Routing-Tabelleneintrags für den Zielknoten D ist ( [D-2-C-11- (B, 11) ] ) .

Es wird weiter angenommen, dass Netzknoten A den Datenrahmen an C weiterzuleiten hat (Routing-Tabelleneintrag für den Netzknoten D ist: [D-2-C-11- (B, 11) ] . Tatsächlich wird angenommen, dass Netzknoten A den Datenrahmen fälschlicherweise zu dem Netzknoten F überträgt.

Betrachtung des Netzknotens F:

Schritt 1: Netzknoten F empfängt einen Datenrahmen mit: RA = F, TA = A, DA = D, SA = G oder S,

Schritt 2: Der Netzknoten F ist nicht der Zielknoten des Datenrahmens (F ≠ D) ,

Schritt 3: Der Datenrahmen wurde fälschlicherweise empfangen, da der Sender (Transmitter) B nicht in der Precursor-Liste des Routing-

Tabelleneintrags für den Netzknoten D ist ( [D- 4-B-8- (G, 8) ) . Dies hat zur Folge, dass der Datenrahmen verworfen wird.

Die Erfindung unterbindet damit die Bildung von Datenschleifen, wenn ein fehlerhafter Netzknoten einen Datenrahmen zurück zu dem Netzknoten überträgt, von welchem er erhalten wird.

Es wird davon ausgegangen, dass der Netzknoten B in Fig. 1 Datenrahmen, die für den Netzknoten D bestimmt sind, zurück zum Netzknoten S oder F sendet. Sowohl S als auch F haben gültige Pfade zu dem Zielknoten D, wobei der Netzknoten B der nächste Zielknoten, d.h. der next hop, ist.

Betrachtung des Netzknotens B:

Schritt 1: Netzknoten B empfängt einen Datenrahmen mit RA

= B, TA = S oder F, DA = D, SA = S oder G, Schritt 2: Der Netzknoten B ist nicht das Ziel des Datenrahmens (B ≠ D) , Schritt 3: Der Datenrahmen wurde korrekt empfangen, da der Sender S oder F in der Precursor-Liste des Routing-Tabelleneintrages für den Netzknoten D ist: ( [D-3-A-11- (F, 8) (S, 11) ] ) .

Der Netzknoten B wäre dazu eingerichtet, den Datenrahmen zum Netzknoten A zu übertragen. Dies ergibt sich aus dem Routing- Tabelleneintrag für Netzknoten: [D-3-A-11- (F, 8) (S, 11) ] . Es wird im Ausführungsbeispiel jedoch davon ausgegangen, dass der Datenrahmen fälschlicherweise zum Netzknoten F oder S ü- bertragen wird.

Betrachtung des Netzknotens S:

Schritt 1: Netzknoten S empfängt einen Datenrahmen mit RA = S, TA = B, DA = D, SA = S oder G,

Schritt 2: Der Netzknoten S stellt nicht das Ziel für den Datenrahmen dar (S ≠ D) ,

Schritt 3: Der Datenrahmen wurde fälschlicherweise empfangen, da der Sender B nicht in der Precur- sor-Liste des Routing-Tabelleneintrages für den Netzknoten D ist: ( [D-4-B-11- ( )]). Dies hat zur Folge, dass der Datenrahmen verworfen wird.

Betrachtung des Netzknotens F:

Schritt 1: Netzknoten F empfängt einen Datenrahmen mit RA = F, TA = B, DA = D, SA = S oder G,

Schritt 2: Der Netzknoten F ist nicht Ziel des Datenrah- mens (F ≠ D) ,

Schritt 3: Der Datenrahmen wurde fälschlicherweise empfangen, da der Sender B nicht in der Precur- sor-Liste des Routing-Tabelleneintrags für den Netzknoten D ist: ( [D-4-B-8- (G, 8) ] ) .

Der Datenrahmen wird deshalb verworfen.

In Fig. 8 ist ferner das permanente Aktualisieren der Precur- sor-Listen von sich überlappenden Datenpfaden dargestellt. Es ist beispielsweise den Routing-Tabellen der Netzknoten S, B, A, C, D, F und G entnehmbar, dass aufgrund des Ablaufs der Lebensdauern von Routing-Tabelleneinträgen die zugehörigen Precurser-Listeneinträge gelöscht werden. Dies ist durch die hervorgehobenen, leeren Tabelleneinträge dargestellt. Beim Ablauf der Lebensdauer eines Routing-Tabelleneintrags wird somit sowohl der Routing-Tabelleneintrag als auch der Precur- sor-Listeneintrag selbst entfernt. Im Ausführungsbeispiel

wurde dabei davon ausgegangen, dass der Datenpfad zwischen den Netzknoten G und D abgelaufen ist. Der Datenpfad zu dem Zielknoten D in den Netzknoten B, A und C läuft jedoch nicht ab, da hier noch ein aktiver Datenpfad zwischen den Netzknoten S und D besteht. Den Netzknoten B weist Precursor für seinen Datenpfad zu D auf, nämlich einen für den Datenpfad zwischen G und D und einen für den Datenpfad zwischen S und D. Dabei läuft lediglich der erstgenannte ab und wird von der Precursor-Liste gelöscht.

Literaturliste :

[1] C.E. Perkins, E. M. Belding-Royer, S. R. Das: Ad hoc On- demand Distance Vector (AODV) Routing, IETF Experimental RFC 3561, JuIy 2003.