-
Hintergrund
der Erfindung
-
Gebiet der
Erfindung
-
Diese
Erfindung betrifft allgemein Datenpaketroutingprozeduren in Multiknotennetzen
und insbesondere ein adaptives Pfaderkennungs- und Rekonfigurationsverfahren
für verteilte
Netze.
-
Beschreibung
des Stands der Technik
-
Ein
Netz umfaßt
eine Mehrzahl von Datenpaketschaltern (sog. „Router"), die mit einer geeigneten Technologie,
wie beispielsweise Punkt-zu-Punkt-Verbindungen, Datenpaketrepeatern
(transparente Brücken)
oder Lokalbereichsnetzen (LANs) verbunden sind. Der Zweck eines
Netzes besteht darin, Nutzer, die ihre Geräte (die als „Endknoten" bezeichnet werden)
an das Netz anschließen,
in die Lage zu versetzen, Daten zu Entknotengeräten anderer Nutzer zu übertragen
oder davon zu empfangen. Wie in 1 bezüglich des
Endknotens 20 gezeigt ist, handelt es sich bei dem Netz 22 lediglich
um eine große „Wolke", an die der Endknoten
angeschlossen ist, wodurch er in die Lage versetzt wird, mit anderen
Endknoten, wie beispielsweise den Endknoten 24 und 26,
die ebenfalls an die Wolke 22 angeschlossen sind, über die
Mehrzahl von Verbindungen zu kommunizieren, die die Netztopologie
bilden, die durch die einen Teil des Weges 32 zwischen
dem Endknoten 20 (Quelle) und dem Endknoten 26 (Ziel)
in 1 darstellenden Verbindungen 28 und 30 veranschaulicht
ist. Endknoten, Brücken
und Router werden hierin ebenfalls im allgemeinen als „Knoten" bezeichnet.
-
Im
Open Systems Interconnection (OSI)-Referenzmodel sind sieben Netzprotokollebenen
definiert. Gemäß dem OSI-Referenzmodel
kommuniziert jede Ebene in einem Knoten mit ihren Teilnehmerebenen
in fremden Knoten durch Austausch von Protokolldateneinheiten (PDUs) über das
Netz. Um derartige PDU-Transfers zu bewirken, verwendet jede Ebene
die von der niedrigeren Ebene in ihrem Knoten zur Verfügung gestellten
Dienste durch den Austausch von Dienstdateneinheiten (SDUs) mit
ihrer lokalen benachbarten Ebene.
-
Die
physische Ebene (Ebene 1) überträgt Informationsbits über einen
Verbindung und setzt sich mit Problemen wie der Steckergröße und Form,
der Zuteilung von Steckerpinfunktionen, der Umwandlung von Bits
in elektrische oder optische Signale und der Bitebenensynchronisation
auseinander. In einem Netz kann es mehrere verschiedene Arten physischer
Ebenen geben und es kann sogar mehrere verschiedene Arten physischer
Ebenen in einem einzigen Knoten geben, da jede physikalische Technologie
(z. B. CMOS, Infrarot, Faseroptik, usw.) ihre eigene physische Ebene
erfordert.
-
Die
Datenverbindungsebene (Ebene 2) überträgt Informationseinheiten über eine
Verbindung. Verschiedene Verbindungen können verschiedene Datenverbindungsebenen
implementieren und ein einzelner Knoten kann verschiedene Datenverbindungsebenenprotokolle
unterstützen.
Die Datenverbindungsebene verwendet die Dienste der physischen Ebene,
um Verbindungs-PDUs
(LPDUs) zu ihrer Teilnehmerdatenverbindungsebene in einem anderen
Knoten des Netzes zu übertragen.
Die „transparente
Brücke" arbeitet auf der
Datenverbindungsebene.
-
Die
Netzebene (Ebene 3) ermöglicht
die Kommunikation innerhalb jedes beliebigen Knotenpaares in einem
Netz. Ein „vollkommen
verbundenes" Netz
ist ein Netz, bei dem jedes Knotenpaar durch eine Direktverbindung
verbunden ist. Eine derartige Topologie geht aufgrund des exponentiellen Anstiegs
der Zahl der Verbindungen jedoch nicht über mehr als ein paar wenige
Knoten hinaus. Typischerweise muß in einem verteilten Netz
mit mehreren Knoten die Netzebene einen Weg durch eine Reihe von
miteinander verbundenen Knoten finden, von welchen jeder Datenpakete
in der richtigen Richtung weiterbefördern muß. Die Netzebene beschäftigt sich mit
Problemen wie der Berechnung des Pfades, der Paketfragmentierung
und -wiederzusammensetzung (um eine Änderung der maximalen Paketgröße von einer
Verbindung zur nächsten
zu bewältigen)
und der Überbelastungssteuerung.
Die Netzebene verwendet die Dienste der Datenverbindungsebene, um Netz-PDUs
(NPDUs) zu ihrer Teilnehmernetzebene in einem anderen Knoten des
Netzes zu übertragen. Der
Datenpaketschalter (Router) arbeitet auf der Netzebene.
-
Wenn
Daten von einem Endknoten zu einem entfernten Knoten über das
Netz gesendet werden sollen, müssen
dem sendenden Endknoten (Quelle) die Adresse des Zielknotens und
zumindest die erste Verbindung im Pfad (Route) zwischen Ursprung
und Ziel bekannt sein. Im Stand der Technik sind viele Routingstrategien
bekannt, jedoch ist nach allen Gütemaßstäben keine
dieser Strategien besser als alle anderen. Im Stand der Technik
ist das „Sourcerouting"- Protokoll gut bekannt. Die grundlegende
Idee hinter dem Ursprungs-Routing (source routing) besteht darin,
daß jeder
Paketheader eine Spezifizierung des Pfades enthält, die vom Ursprungsknoten selbst
in das Paket eingefügt
wurde. Damit der Ursprungsknoten einen Pfad zum Zielknoten in ein
Paket einfügen
kann, muß er
zunächst
mit einem bestimmten Mittel den Pfad auffinden. Der Ursprungsroutingstandard
umfaßt
zahlreiche Verfahren, die zur Errichtung und Aufrechterhaltung von
Pfaden von einem Ursprungsknoten verwendet werden können. Bei
einem strikten Ursprungsrouting wird eine Liste aller dazwischen
liegenden Knoten in einer Paketpfadliste spezifiziert. Bei einem
lockeren Ursprungsrouting könnten
durch die Paketpfadliste gegebenenfalls lediglich einige wenige
dazwischen liegende Adressen längs
des Pfades festgelegt sein, die das Paket in einer bestimmten Reihenfolge
bei seiner Reise durch das Netz nicht versäumen darf. Die grundlegende
Idee, die sich hinter dem strikten Ursprungsrouting verbirgt, ist,
daß ein
Ursprungsendknoten einen Zwischenspeicher mit Pfaden zu Zielknoten
enthält,
mit welchen er momentan kommuniziert. Falls sich für ein bestimmtes
Ziel kein Pfad im Zwischenspeicher befindet, kann vom Knoten ein „Pfaderkundungs" -Protokoll verwendet
werden, um einen Pfad oder eine Gruppe von Pfaden zu ermitteln.
Falls festgestellt wird, daß ein
Pfad im Zwischenspeicher nicht länger
praktikabel ist, kann der Ursprung entweder versuchen, einen anderen
neuen Pfad zu ermitteln oder einen der alternativen Pfade zu verwenden,
die er für
das Ziel gespeichert hat.
-
In
Netzen, in welchen Brücken
verwendet werden, kann der Ursprungsknoten einen Pfad durch Übertragung
einer bestimmten An von Datenpaket (eines „Erkundungs"-Pakets) ermitteln,
das sich selbst repliziert, wenn es auf Verzweigungen oder Pfadwahlmöglichkeiten
trifft, wobei gegebenenfalls eine Kopie des Erkundungspaketes über jeden
möglichen
Pfad im Netz gesendet wird. Jede Kopie des Erkundungspaketes führt Buch über seine
Fortbewegung, so daß ein
Pfad aus der Vielzahl von Kopien des Erkundungspaketes, die den
Bestimmungsknoten erreichen, ausgewählt und in einer Nachricht
zum Ursprungsknoten zurückgegeben
werden kann. Immer wenn ein Ursprungsknoten einen Pfad zu einem anderen
Knoten auffindet, speichert er den Pfad, so daß er für nachfolgende Pakete mit demselben
Ziel verwendet werden kann. Das Problem der exponentiellen Zunahme
von Erkundungspaketen kann durch Verwendung des im Stand der Technik
bekannten Spanning-Tree-Erkundungspaketprozesses verhindert werden.
Jedoch müssen
alle Ursprungsroutingbrücken
einen Spanning-Tree-Algorithmus
ausführen,
um den Spanning-Tree-Erkundungspaketprozeß zu unterstützen, was
aufwendig sein kann. Wenn mehrere Erkundungspakete an einem Zielknoten
ankommen, muß einer
der mehreren verfügbaren
Pfade gemäß einer
bestimmten Strategie ausgewählt werden.
Beispielhafte Strategien umfassen das Auswählen des ersten empfangenen
Pakets (basierend auf der Theorie, daß es sich auf dem schnellsten Pfad
bewegt hat); das Auswählen
des Pfads, der die maximale Paketgröße angibt; das Auswählen des Pfads
mit der geringsten Zahl von Sprüngen;
das Auswählen
des zuletzt empfangenen Pfads; oder das Auswählen einer bestimmten Kombination
der vorhergehenden Möglichkeiten.
-
Im
Stand der Technik bekannte Netzebenenroutingprotokolle basieren
entweder auf den verteilten „Distanzvektor"- oder den verteilten „Verbindungszustand"- Routingprozeduren.
Das Distanzvektorrouting erfordert, daß jeder Knoten die Distanz (ein
Maß für den Übertragungsaufwand)
zwischen sich und jedem möglichen
Ziel aufrecht erhält.
Die einen lokalen Distanzvektor bestimmenden Distanzen werden im
lokalen Knoten rekursiv durch Zusammensetzen und Verwenden der Informationen
der Distanzvektoren, die bei benachbarten Knoten vorgefunden wurden,
berechnet. Das Hauptproblem beim Distanzvektorrouting besteht in
der langsamen Konvergenz der Distanzvektoren über das Netz. Wenn sich eine
Routinginformation nur teilweise über das Netz ausgebreitet hat,
kann die Routing-Leistung ernsthaft gestört sein. Da die Änderung
einer einzigen Verbindung viele Pfade beeinflussen kann, ist es wichtig,
nach einer topologischen Änderung
im Netz das Routing so schnell wie möglich wiederherzustellen. Nach
einer derartigen topologischen Änderung kann
das Distanzvektorrouting eine sehr lange Zeit für eine Konvergenz benötigen. Von
Praktikern wurden zahlreiche Lösungen
für das
Problem der langsamen Konvergenz beim Distanzvektorrouting vorgeschlagen,
einschließlich
des Diffusing-Update-Algorithmus (DUAL), der „Split Horizon" -Technik, der „Full Path
Reporting" -Technik,
der „Poison
Reverse" -Technik,
der „Triggered-Update" – Technik und verschiedenen „Hold-Down" -Techniken. Nachteiligerweise
konnten die grundlegenden Nachteile der Distanzvektorroutingprozeduren
mit keinem dieser Vorschläge
beseitigt werden. Der primäre
Vorteil besteht darin, daß weniger
Knotenspeicher erforderlich sind als bei Verbindungszustandroutingprozeduren.
-
Die
Verbindungszustandroutingprozedur beinhaltet die grundlegende Idee,
daß jeder
Router für das
Zusammenfinden mit seinen Nachbarn und das Erfassen ihrer Namen
verantwortlich ist. Jeder Router konstruiert ein spezielles Paket
(ein Verbindungszustandspaket oder LSP), das eine Liste der Namen seiner
Nachbarn und des Aufwands bzw. der Kosten (Distanz) zu jedem seiner
sich nebenan befindenden Nachbarknoten enthält. Das LSP wird auf eine beliebige
Weise zu allen anderen Knoten übertragen
und jeder Knoten speichert das am kürzlichsten erzeugte LSP von
jedem anderen Knoten im Netz. Jeder Knoten kann dann Pfade zu ir gendeinem
Ziel basierend auf der vollständigen
Karte der aus der akkumulierten LSP-Information abgeleiteten Netztopologie
berechnen. Das Verbindungszustandrouting unterliegt vielen gut bekannten
bedeutenden Problemen, wie beispielsweise der „kanzerogenen" LSP-Verteilung und der
LSP-Inkompatibilität
zwischen den Knoten; Zustände,
die sich aus der ineffizienten Übertragung
eines neuen LSP zu allen anderen Knoten im Netz ergeben, wenn sich
die Zustände
der lokalen Verbindungen ändern.
Andere im Stand der Technik bekannte Nachteile umfassen drastische
Schwierigkeiten, die aus dem Fehlschlagen der Zeitstempel-Synchronisation (time-stamp)
und dem Herumkreisen (wrap around) der Sequenznummer resultieren.
Darüber
hinaus können
sowohl die Verbindungszustandsroutingprozedur als auch die Distanzvektorroutingprozedur
vollkommen durch einen einzigen fehlerhaften Router gesperrt sein
(dies wird als ein „byzantinischer" Fehler bezeichnet),
obwohl sich im Stand der Technik zumindest ein Verbindungszustandsroutingprotokoll
als immun gegen byzantinische Fehler erwiesen hat (von Radia Perlman).
Trotz des großen
betriebstechnischen Aufwands wird im Stand der Technik das Verbindungszustandsrouting hauptsächlich aufgrund
der schnelleren Netzkonvergenz bei Topologieänderungen bevorzugt.
-
Im
Stand der Technik gibt es eine große Zahl von Vorschlägen zur
Verbesserung der Pfaderkennung und für Instandhaltungsprozeduren
bei Multiknotennetzen. So schlägt
beispielsweise Shin et al. [Kang G. Shin et al., „Distributed
Route Selection for Establishing Real-Time Channels", IEEE Trans. Parallel
and Distributed Systems, Vol. 11, Nr. 2, S. 318 – 335, März 2000] eine verbesserte Verbindungszustandsroutingprozedur
vor, mit der der zentralisierte Flaschenhals bei der Pfadauswahl
entschärft
wird, während
die Effizienz durch schnelles Ausschließen von nicht ausführbaren
Pfaden aus der parallelen Pfadsuche verbessert wird. Shin et al.
beschäftigt sich
in erster Linie mit der „Vollständigkeit" (d. h. der Sicherstellung
der Erkennung eines geeigneten Pfades, falls ein solcher existiert)
und verwendet einen modifizierten Bellman-Ford-Algorithmus, der
weniger effizient ist als der ursprüngliche, zieht jedoch weder Lösungen für das Problem
eines adaptiven Erkennens eines Pfades zwischen Netzendknoten in
einer dynamischen Netztopologie in Betracht noch schlägt solche
vor. Ein weiterer Vorschlag zur Verbesserung der Effizienz des Verbindungszustandsrouting
in auf dem Private Network to Network Interface (PNNI) basierenden
Asynchronous Transfer Mode (ATM) – Netzen ist der modifizierte
Dijkstra-Pfadoptimierungsalgorithmus, der von Rochberger et al.
im US-Patent 6,147,971 vorgeschlagen wird. Bei der Dijkstra-Prozedur
handelt es sich um ein Verbindungszustandsroutingprotokoll, bei
dem eine intensive Knotenverarbeitung verwendet wird, um die „Kosten" eines Pfades zu
minimieren. Beim Vorschlag von Rochberger et al. wird die Konvergenzzeit
des Dijkstra-Protokolls lediglich für die Hop-Count-Minimierung verbessert.
-
Im
US-Patent 6,047,330 von Stracke, Jr. wird ein virtuelles Routererkundungssystem
zum Aufbau eines virtuellen Multicastnetzes über eine bestehende Topologie
und zur dynamischen Anpassung des Routingsystems in Reaktion auf
unvorhergesagte Änderungen
der zugrunde liegenden Netzkonnetivität vorgeschlagen. Stracke, Jr.
verwendet virtuelle Router, die „Herzschläge" über
das Internetprotokoll (IP)-Netz aussenden, wobei jeder mit einem
Time-To-Live (TTL)-Wert
markiert ist. Jeder Router gibt ein Antwortpaket auf den Empfang
des Herzschlagpakets zurück
und der Ursprungsrouter erhält
eine Abschätzung
für die
Distanz (Kosten) zum antwortenden Router beim Empfang des Antwortpakets. Durch
Auswählen
von nähergelegenen
Routern für die
Verbindung, paßt
sich das System automatisch und dynamisch an Netzänderungen
an, indem ineffiziente Verbindungen gegenüber effizienteren fallen gelassen
werden. Jedoch werden von Stracke, Jr. weder Lösungen für das Problem der Erkennung
eines Pfades zwischen den Endknoten eines Netzes in einer dynamischen
Netztopologie in Betracht gezogen noch vorgeschlagen.
-
Im
US-Patent 6,023,733 offenbart Periasamy et al. ein wirkungsvolles
Verfahren zur Darstellung einer Verbindungszustandstabelle in einem Knoten,
womit die Speicherung einer Darstellung des gesamten Netzes an jedem
Knoten mit einem geringen Speicheraufwand ermöglicht wird. Es werden jedoch
weder Lösungen
für das
Problem der dynamischen Pfaderkennung in Betracht gezogen noch vorgeschlagen.
-
Im
US-Patent 6,201,794 offenbart Stewart et al. eine dynamische Technik
zur Pfaderkennung, die zur Bestimmung des effizientesten Pfades
zur Übertragung
einer Nachricht von einem Ursprungsknoten zu vielen anderen Zielknoten
vorgeschlagen wird, wobei die Bedingungen des vorhenschenden Netzverkehrs
berücksichtigt
werden. Pilotnachrichten werden zwischen kommunizierenden Knoten
entweder periodisch oder kontinuierlich übertragen, um die „Kosten" jedes verfügbaren Pfades
zu überwachen. Die
verschiedenen von Pilotnachrichten durchlaufenen Pfade werden zum
Ursprungsknoten zurückgegeben
und zur Verwendung bei der Auswahl des effizientesten Pfades (mit
den niedrigsten Kosten) gespeichert. Ein operierender Masterknoten
kann die Sequenzierung von Pilotnachrichten in Reaktion auf Netzverkehrsbedingungen
verändern,
um die Pfadanalyse für
verkehrsreiche Routen häufiger
zu ak tualisieren. Als ein Nachteil neigt diese Technik zu einem Anstieg
des Netznachrichtenverkehrs auf den verkehrsreicheren Routen.
-
Es
besteht der bekannte Bedarf für
ein Pfadauswahlsystem weiter fort, das sich dynamisch an Änderungen
der Netzkonnektivität
und Verkehrsbedingungen anpassen kann, ohne daß eine bedeutende Netzverkehrsüberlastung
und ein zusätzlicher
Betriebsaufwand für
den Knoten entsteht. Die damit verbundenen ungelösten Probleme und Nachteile
sind im Stand der Technik deutlich spürbar und werden durch diese
Erfindung in der im Nachfolgenden beschriebenen Weise gelöst.
-
Abriß der Erfindung
-
Durch
diese Erfindung wird das Problem der dynamischen Pfaderkennung durch
Anwenden von „Kollisionen" von sich zufällig vorwärts bewegenden „Fühler" -Paketen sowohl
von den Ursprungsknoten als auch den Bestimmungsknoten zur Erkundung
eines Wegs mit dem die Ursprungs- und Bestimmungsknoten in einem
Mehrknotennetz verbunden sind, gelöst. Die erkannten Wege können im
Ursprungsknoten gespeichert werden und in Reaktion auf Berichte über neue
Kollisionen von Fühlerpaketen
aktualisiert werden. Gemäß dieser
Erfindung erkannte Wege können
am Ursprungsknoten analysiert werden, um Schleifen zu beseitigen.
-
Eine
Aufgabe dieser Erfindung besteht darin, einen gültigen Weg von einem Ursprungs-
zu einem Bestimmungsknoten mit verringerten Betriebsverkehraufwandseffekten
zu erkennen. Es ist ein Merkmal des erfindungsgemäßen Verfahrens,
daß sich die
Fühlerpakete
zufällig
durch die Netztopologie ausbreiten, wodurch im Netz relativ gleichförmige Verkehrseffekte
bewirkt werden. Ein Vorteil des erfindungsgemäßen Verfahrens besteht darin,
daß das Erkennen
eines Weges immer die momentane Netztopologie und die Verkehrsbedingungen
zu dem Zeitpunkt, zu dem sie zum Ursprungsknoten zurückgegeben
werden, reflektiert. Eine weitere Eigenschaft des erfindungsgemäßen Verfahrens
besteht darin, daß die
Generierungsrate der Fühlerpakete
durch die kommunizierenden Knoten in Reaktion auf Nachfrageänderungen,
Kosten oder andere Parameter angepaßt werden kann.
-
Gemäß einem
Gesichtspunkt handelt es sich bei der Erfindung um einen maschinenimplementierten
Prozeß zum
Erkennen eines Weges zum Übertragen
zumindest eines Datenpakets von einem Ursprungsknoten zu einem Bestimmungsknoten über eine
Mehrzahl von Knoten, die zur Bildung eines Netzes miteinander verbunden
sind, wobei das Verfahren die Schritte aufweist: Senden eines Fühlerpakets,
das Fühlerdaten,
die den Bestimmungsknoten identifizieren und Knotenübertragungsprotokolldaten umfaßt, die
den Ursprungsknoten identifizieren, vom Ursprungsknoten zu zumindest
einen ersten der Mehrzahl von Netzknoten, Senden eines Fühlerpakets,
das Knotenübertragungsprotokolldaten
umfaßt, die
den Bestimmungsknoten identifizieren, vom Bestimmungsknoten zu zumindest
einem zweiten der Mehrzahl von Netzknoten, in Antwort auf den Empfang
eines ersten Fühlerpakets
an einem ersten der Mehrzahl von Netzknoten, Erweitern des Knotenübertragungsprotokolls
im ersten empfangenen Fühlerpaket
mit Daten, die den ersten empfangenden Knoten identifizieren, um
ein erstes erweitertes Fühlerpaket
zu bilden, Identifizieren eines zweiten empfangenen Fühlerpakets
mit Knotenübertragungsprotokolldaten,
die den Bestimmungsknoten identifizieren, im ersten empfangenden
Knoten, und wenn das zweite empfangene Fühlerpaket gefunden wurde, Kombinieren
der Knotenübertragungsprotokolldaten vom
ersten und zweiten empfangenen Fühlerpaket zur
Darstellung eines erkannten Weges zur Übertragung zumindest eines
Datenpakets vom Ursprungsknoten zum Bestimmungsknoten über das
Netz, ansonsten Senden einer Kopie des ersten erweiterten Fühlerpakets
zu einem zweiten der Mehrzahl von Netzknoten.
-
Gemäß einem
weiteren Gesichtspunkt handelt es sich bei der Erfindung um eine
Netzvorrichtung zum Erkennen eines Weges zur Übertragung zumindest eines
Datenpaketes von einem Ursprungsknoten zu einem Bestimmungsknoten über eine
Mehrzahl von Knoten, die miteinander zur Bildung eines Netzes verbunden
sind, wobei die Vorrichtung Mittel zum Senden eines Fühlerpakets,
das Fühlerdaten,
die den Bestimmungsknoten identifizieren und Knotenübertragungsprotokolldaten,
die den Ursprungsknoten identifizieren, von einem Ursprungsknoten
zu zumindest einer Mehrzahl von Netzknoten; Mittel zum Senden eines
Fühlerpakets, das
Knotenübertragungsprotokolldaten
umfaßt,
die den Bestimmungsknoten identifizieren, vom Bestimmungsknoten
zu zumindest einem zweiten der Mehrzahl von Netzknoten; Mittel zum
Erweitern des Knotenübertragungsprotokolls
in einem ersten empfangenen Fühlerpaket
mit Daten, die einen ersten empfangenden Knoten identifizieren,
um ein erstes erweitertes Fühlerpaket
zu bilden in Antwort auf den Empfang des ersten Fühlerpakets
am ersten empfangenden Knoten; Mittel zum Senden einer Kopie des
erweiterten Fühlerpakets
vom ersten empfangenden Knoten zu einem zweiten der Mehrzahl von
Netzknoten; Mittel zum Identifizieren im ersten empfangenden Knoten
eines zweiten empfangenden Fühlerpakets
mit Knotenübertragungsprotokolldaten,
die den Zielknoten identifizieren und Mittel zum Kombinie ren der
Knotenübertragungsprotokolldaten
vom ersten und zweiten empfangenen Fühlerpaket, in Reaktion auf
ein Auffinden des zweiten empfangen Fühlerpakets am ersten empfangenden
Knoten umfaßt,
um einen Weg wiederzugeben, der erkannt wurde, um zumindest ein
Datenpaket vom Ursprungsknoten zum Bestimmungsknoten über das
Netz zu übertragen.
-
Gemäß noch einem
weiteren Aspekt handelt es sich bei der Erfindung um ein Computerprogrammprodukt
zur Verwendung in einem Computersystem zum Erkennen eines Weges
zum Übertragen eines
oder mehrerer Datenpakete von einem Ursprungsknoten zu einem Bestimmungsknoten über eine
Mehrzahl von Knoten, die zur Bildung eines Netzes miteinander verbunden
sind, wobei das Computerprogrammprodukt ein Aufzeichnungsmedium,
ein auf dem Aufzeichnungsmedium aufgezeichnetes Mittel zur Steuerung
des Systems, um ein Fühlerpaket einschließlich von
Fühlerdaten,
welche den Bestimmungsknoten identifizieren, und von Knotenübertragungsprotokolldaten,
die den Ursprungsknoten identifizieren, vom Ursprungsknoten zu zumindest
einem der Mehrzahl von Netzknoten zu senden, auf dem Aufzeichnungsmedium
aufgezeichnete Mittel zur Steuerung des Systems, um ein Fühlerpaket
einschließlich
von Knotenübertragungsprotokolldaten, die
den Bestimmungsknoten identifizieren, vom Bestimmungsknoten zu zumindest
einem zweiten der Mehrzahl von Netzknoten zu senden, auf dem Aufzeichnungsmedium
aufgezeichnete Mittel zur Steuerung des Systems, um in Antwort auf
den Empfang eines ersten Fühlerpakets
am ersten empfangenden Knoten das Knotenübertragungsprotokoll im ersten empfangenen
Fühlerpaket
mit Daten, die den ersten empfangenden Knoten identifizieren, zu
erweitern, um ein erstes erweitertes Fühlerpaket zu bilden, auf dem
Aufzeichnungsmedium aufgezeichnete Mittel zur Steuerung des Systems,
um eine Kopie des erweiterten Fühlerpakets
vom ersten empfangenden Knoten zu einem zweiten der Mehrzahl von
Netzknoten zu senden, auf dem Aufzeichnungsmedium aufgezeichnete
Mittel zum Steuern des Systems, um im ersten empfangenden Knoten
ein zweites empfangenes Fühlerpaket
mit Knotenübertragungsprotokolldaten,
die den Bestimmungsknoten identifizieren, zu identifizieren, und
auf dem Aufzeichnungsmittel aufgezeichnete Mittel zum Steuern des
Systems, um in Antwort auf das Auffinden des zweiten empfangenen Fühlerpakets
am ersten empfangenden Knoten, die Knotenübertragungsprotokolldaten von
dem ersten und zweiten empfangenen Fühlerpaket zu kombinieren, so
daß sie
einen erkannten Weg zur Übertragung
von zumindest einem Datenpaket vom Ursprungsknoten zum Bestimmungsknoten über das Netz
wiedergeben.
-
Das
zuvor Beschriebene wird zusammen mit weiteren Gegenständen, Merkmalen
und Vorteilen dieser Erfindung mit Bezugnahme auf die folgende Beschreibung,
Ansprüche
und die begleitenden Zeichnungen besser verständlich.
-
Kurzbeschreibung
der Zeichnungen
-
Für ein umfassenderes
Verständnis
dieser Erfindung wird im Folgenden auf die folgende detaillierte
Beschreibung der in der begleitenden Zeichnung veranschaulichten
Ausführungsformen
Bezug genommen, in der gleiche Bezugszeichen gleiche Merkmale in
den Ansichten wiedergeben und wobei:
-
1 ein
schematisches Diagramm ist, das mehrere durch ein Netz mit mehreren
Knoten verbundene Endknoten zeigt;
-
2 ein
schematisches Diagramm ist, das ein beispielhaftes Internet zeigt,
das eine Haupttrasse und mehrere Domänen verbindet, von welchen jede
eines oder mehrere Lokal-bereichsnetze
aufweist, die eine Mehrzahl von Endknoten verbinden;
-
3 ein
Blockdiagramm ist, das die funktionelle Ausführungsform eines typischen
Endknotens aus 1 oder 2 veranschaulicht;
-
4 ein
Blockdiagramm ist, das die funktionelle Ausführungsform eines typischen
Zwischenknotens (Router) aus 2 zeigt;
-
5 eine
schematische Darstellung eines beispielhaften Ursprungs-gerouteten
Datenpakets ist, das für
eine Verwendung auf der Verbindungsebene (Ebene 2) geeignet ist;
-
6 eine
schematische Darstellung eines beispielhaften zufällig gerouteten
Fühlerpakets
gemäß dieser
Erfindung ist;
-
7 eine
schematische Darstellung eines beispielhaften Kollisions-gerouteten
Wegdatenpakets gemäß dieser
Erfindung ist;
-
8 ein
Blockdiagramm eines Ablaufdiagramms ist, das die Pfaderkennungsprozedur
dieser Erfindung an einem Ursprungsknoten veranschaulicht;
-
9 ein
Blockdiagramm eines Ablaufdiagramms ist, das die Pfaderkennungsprozedur
gemäß dieser
Erfindung an einem Kollisionserfassungsknoten veranschaulicht; und
-
10 ein
schematisches Diagram ist, das eine beispielhafte Ausführungsform
einer CDROM des Computerprogrammprodukts dieser Erfindung veranschaulicht.
-
Beschreibung
der bevorzugten Ausführungsform
-
2 ist
ein Blockdiagramm einer beispielhaften Ausführungsform eines Netzes 34,
das das Pfaderkennungssystem dieser Erfindung implementiert. Das
Netz 34 ist hierarchisch so organisiert, daß es eine
Gruppe von Domänen
umfaßt,
die beispielhaft durch die Domänen 36 – 38 dargestellt
sind, wovon jede eine Anzahl von lokalen Computernetzen (LCNs) enthält, die
beispielhaft durch die LCNs 40, 42, 44 und 46 dargestellt
sind, wovon jedes einen oder mehrere Endknoten umfaßt, die
beispielhaft durch den Endknoten 48 dargestellt sind. In
der hier verwendeten Form kann es sich bei dem LCNs beispielhaft
um Lokalbereichsnetze (LANs), Stadtbereichsnetze (MANs), weiträumige Netze
(WANs) etc. handeln. Bei den Endknoten handelt es sich typischerweise
um Computer (Work Stations und Server). Es kann sich dabei jedoch
um jede beliebige Art von Vorrichtung handeln, die eine Netzschnittstellenkarte
(NIC) beinhalten kann, wie beispielsweise ein Drucker oder ein Modem.
Die LCNs 40 – 46 sind
mit Zwischenknoten verbunden, wie beispielsweise den Intradomainroutern 50, 52 und 54 und
den Interdomainroutern 56, 58, 60, 52 und 64.
Die Haupttrasse (back bone) 66 stellt die höchste hierarchische
Ebene im Netz 34 dar und besteht aus einer großen Anzahl
von miteinander verbundenen Knoten (nicht gezeigt), einschließlich weiterer
Zwischendomainrouter (nicht gezeigt), die viele redundante Wege
zwischen den Domänen 36 – 38 und
vielen anderen Domänen (nicht
gezeigt) bereitstellen. Ein LCN ist in 2 als eine
Linie abgebildet, an die ein Endknoten angeschlossen sein kann,
um anzuzeigen, daß dieser
Datenpakete zu jedem anderen an dieselbe Leitung angeschlossenen
Endknoten übertragen
kann und Datenpakete davon empfangen kann. Um eine Domäne mit der
Haupttrasse zu verbinden, können
mehr als ein Zwischendomainrouter verwendet werden, was für eine Wegredundanz
häufig
förderlich
ist.
-
Die
durch den Router 54 beispielhaft angegebenen Router umfassen
typischerweise eine Zentralverarbeitungseinheit (CPU) 68,
eine Speichereinheit 70 und eine Datenspeichervorrichtung 72,
die durch einen Systembus 74 verbunden sind. Die Speichereinheit 70 kann
Direktzugriffsspeicher (RAM) -Vorrichtungen (nicht gezeigt) umfassen,
die durch die CPU 68 adressierbar sind und die sowohl Programmbefehle
als auch Daten speichern können.
Ein Betriebssystem, das Teile umfaßt, die sich typischerweise
im Speicher befinden und von der CPU 68 ausgeführt werden,
organisiert den Knoten funktional durch u. a. Abrufen von Netzoperationen
unterstützt von
in der CPU ablaufenden Prozessen.
-
Bisher
waren Intradomainrouter 50 und 54 zur Verwaltung
von Kommunikationen unter den LCNs 40 und 42 in
der Domäne 38 erforderlich
und diese kommunizieren miteinander unter Verwendung eines Intradomain-Routing-Protokols,
wie beispielsweise des Distanzvektorroutinginformationsprotokolls
(RIP) oder des Verbindungszustandszwischensystems für das Zwischensystemprotokoll
(IS–IS), die
im Stand der Technik bekannt sind. In ähnlicher Weise waren Zwischendomainrouter 56, 58, 60, 62 und 64,
die die Domänen 36 und 38 mit
der Haupttrasse 66 verbinden, zur Kommunikation miteinander unter
Verwendung eines Interdomainroutingprotokolls erforderlich, wie
beispielsweise des Interdomainroutingprotokolls (IDRP) für Konföderationen, des
Exterior-Gateway-Protokolls (EGP) oder des Border-Gateway-Protokolls
(BGP), die im Stand der Technik bekannt sind. Jedoch kann die Kommunikation
im Netz 34 auch entsprechend der Pfaderkennung und den
Ursprungsroutingverfahren dieser Erfindung verwaltet werden. Beispielsweise
können Datenpakete
von einem Ursprungsknoten 68 durch das Netz 34 zu
einem Bestimmungsknoten 70 erfindungsgemäß durch
zunächst
Erkennen des Pfades 72, der eine Mehrzahl von Zwischenknotenverbindungen
aufweist, die beispielhaft durch die Verbindung 74 dargestellt
sind, und dann einschließen
der Daten des erkannten Weges in das Routing Information (RI)-Feld
jedes Datenpakets (7), das vom Ursprungsknoten 68 zum
Bestimmungsknoten 70 gesandt wurde, in der nachfolgend
beschriebnen Weise geroutet werden.
-
In 3 ist
ein Blockdiagramm gezeigt, das eine beispielhafte Ausführungsform
des Endknoten 48 aus 2 zeigt,
der eine Zentralverarbeitungseinheit (CPU) 76, einen Direktzugriffsspeicher 78 und eine
Datenspeichervorrichtung 80 umfaßt, die miteinander durch einen
lokalen Datenbus 82 in der für einen Mehrzweckcomputer üblichen
Weise verbunden sind. Der Endknoten 48 kommuniziert mit
dem Netz 34 (2) mit Hilfe der Verbindung 84 (2, 3),
die mit dem Lokaldatenbus 82 mit Hilfe der Eingangs-/Ausgangs
(I/O)-Schaltung 86 verbunden ist. Der Endknoten 48 arbeitet
im allgemeinen durch Ausführen
einer Mehrzahl von im Speicher 78 und/oder im Speicher 80 gespeicherten
Softwarebefehlen. Beispielsweise können die Verarbeitungsschritte
der Wegerkennungsprozeduren gemäß dieser
Erfindung für
das Ursprungsknotenfühlerpaket
im Speicher 78 als die binären Softwaremodule 88 und 90 gespeichert
sein und ein für
den Bestimmungsknoten erkannter Pfad kann im Speicher 78 und
im Speicher 80 als die Datenstruktur 92 gespeichert sein.
-
In 4 ist
ein Blockdiagramm gezeigt, das eine beispielhafte Ausführungsform
des Routerknotens 50 aus 2 veranschaulicht,
der eine Zentralverarbeitungseinheit (CPU) 94, ei nen Direktzugriffsspeicher 96 und
eine Datenspeichervorrichtung 98 umfaßt, die miteinander durch einen
lokalen Datenbus 100 in der für einen Mehrzweckcomputer üblichen
Weise verbunden sind. Der Routerknoten 50 kann auch eine
separate Routingdatenbasis 102 umfassen, in der beispielsweise
die Identität
seiner unmittelbar benachbarten Knoten bestimmt ist. Der Routerknoten 50 kommuniziert
mit dem Netz 34 (2) mit Hilfe
der Mehrzahl von Verbindungen, die durch die Verbindung 104 (2, 3)
beispielhaft veranschaulicht sind, die mit dem lokalen Datenbus 100 mit
Hilfe des Eingangs-/Ausgangs (I/O)-Ports 106 verbunden
ist. Der Betrieb des Routerknotens 50 erfolgt im allgemeinen
durch eine Abarbeitung einer Mehrzahl von Softwarebefehlen in der
CPU 94, die im Speicher 96 und/oder im Speicher 98 oder
in einer anderen einem Speichermittel ähnlichen Datenbasis 102 gespeichert
sind. Beispielsweise können
die Verarbeitungsschritte für
die Fühlerpaketkollision
der Pfaderkennungsprozeduren gemäß dieser
Erfindung im Speicher 96 als die binären Softwaremodule 108 und 110 gespeichert
sein und ein temporäres
Fühlerpaket
kann als die Datenstruktur 112 im Speicher 96 und
im Speicher 98 gespeichert sein.
-
5 ist
eine schematische Darstellung eines beispielhaften Ursprungs-gerouteten
Datenpakets 114, das für
eine Verwendung zur Kommunikation zwischen beispielsweise den Knoten 68 und 70 in der
Verbindungsebene (Ebene 2) des Netzes 34 geeignet ist.
Das Datenpaket 114 umfaßt eine Mehrzahl von Datenfeldern
einschließlich
eines Quell- (oder Ursprungs-) Feldes 116, das Daten enthält, die
die Identität/Adresse
des Ursprungsknotens für
das Datenpaket 114 enthält.
Bei den Datenpaketen mit Ursprung am Knoten 68 umfaßt das Ursprungsfeld 116 die
Identität/Adresse
des Knotens 68. Das Bestimmungsfeld 118 enthält Daten,
die die Identität/Adresse
des Knotens, zu dem der Knoten 68 das Datenpaket 114 schicken
möchte,
umfassen. Bei den Datenpaketen mit Ursprung am Knoten 68 und
beabsichtigter Ankunft am Knoten 70 umfaßt das Bestimmungsfeld 118 die
Identität/Adresse
des Knotens 70. Da es sich dabei um ein „Ursprungs-geroutetes" Datenpaket handelt,
umfaßt
das Datenpaket 114 auch ein Routing-Information (RI)-Feld 120,
das eine komplette Bestimmung des Weges enthält, über den sich das Datenpaket 114 bewegen
muß, bevor
es am Bestimmungsknoten 70 ankommt. Dementsprechend muß die gesamte
Wegbestimmung am Ursprungsknoten 68 erkannt und gespeichert
werden, bevor das Datenpaket 114 generiert werden kann.
Gemäß dieser Erfindung
erhält
der Ursprungsknoten 68 den Weg zum Bestimmungsknoten 70 durch
Empfang eines Wegdatenpakets (PP) (7) von einem „Kollisions" -Knoten im Netz 34,
nachdem eines oder mehrere Fühlerdatenpakete
(FPs) (6) abgeschickt wurden.
-
6 ist
eine schematische Darstellung eines beispielhaften zufällig gerouteten
Fühlerdatenpakets
(FP) 122, das in einem Ursprungsknoten gemäß dem erfindungsgemäßen Verfahren
(8) generiert wurde. Das FP 122 umfaßt ein FP-Datenfeld 124,
das das FP 122 als ein „Fühlerdatenpaket" identifiziert, und
ein Fühlerdatenfeld 126,
das alle zur Spezifizierung der Erkundung eines Weges benötigten Informationen
enthält,
wie beispielsweise die Identität/Adresse
des gewünschten
Bestimmungsknotens, einen Ursprungszeitstempel, Hop-count-Grenzen und beliebige
andere notwendige, durch den Ursprungsknoten bestimmte, Daten. Schließlich umfaßt das FP 122 ein
Knotenübertragungs
(NT)-Protokollfeld 180, das von einem Knoten zum nächsten durch
Hinzufügen
der Identität/Adresse
jedes Knotens, der während
der Übertragung
vom Ursprungsknoten zu einer „Kollision" mit einem anderen
FP vom gewünschten
Bestimmungsknoten angelaufen wurde, inkrementell aktualisiert wird.
Somit umfaßt
das NT Protokoll 128, wenn das FP 122 im Ursprungsknoten,
beispielsweise im Ursprungsknoten 68 (2),
generiert wurde, nur einen einzigen Eintrag 130, der die
Identität/Adresse
des Ursprungsknotens 68 festlegt. Das FP 122 wird
dann zufällig
zu einem benachbarten Knoten abgesandt, wo es empfangen und gemäß dem erfindungsgemäßen Verfahren
(9) verarbeitet wird.
-
7 ist
eine schematische Darstellung eines beispielhaften Kollisions-gerouteten
Weg-Datenpakets
(PP) 132 gemäß dieser
Erfindung. Wenn das FP 122 mit einem zweiten FP (nicht
gezeigt) „kollidiert", das entweder seinen
Ursprung am gewünschten
Bestimmungsknoten hat oder diesen durchlaufen hat, erzeugt der eine
derartige Kollision erfassende Knoten (der Kollisionsknoten) das
PP 132 und sendet dieses zum Ursprungsknoten zurück, wie
in weiteren Einzelheiten in Verbindung mit 8 – 9 erläutert wird.
Das PP 132 kann ein PP-Datenfeld (nicht gezeigt) umfassen
(muß jedoch
nicht), das das PP 122 als ein „Wegdatenpaket" identifiziert, da
das PP 122 lediglich unter Verwendung der Bestimmung, des
Ursprungs, der Routing-Information und der Datenfelder des einfachen
Ursprungs-gerouteten Datenpakets 114 (5)
konfiguriert sein kann. Das Bestimmungsdatenfeld 134 spezifiziert
die Identität/Adresse
des „Ursprungs" -Knotens, an dem
das FP 122 seinen Ursprung hat. Das Ursprungsdatenfeld 136 spezifiziert
die Identität/Adresse
des „Kollisions" -Knotens, in dem
das FP 122 mit dem zweiten FP (nicht gezeigt) kollidierte,
wobei es sich dabei ebenfalls um den Ursprungsknoten handelt, von
dem das PP 132 abgesandt wurde. Das RI-Feld 138 spezifiziert
den Weg von dem Kollisionsknoten zurück zum Ursprungsknoten, der
durch Umkehren der Einträge
im NT Protokoll 128 des FP 122 erhalten werden
kann. Schließlich
umfaßt
das Da tenfeld 140 die aus der Kollision des FP 122 mit
dem zweiten FP (nicht gezeigt) in der durch das folgende Beispiel
dargestellten Weise erhaltene Weginformation:
-
Wieder
mit Bezugnahme auf den Weg 72 in 2 werde
ein erstes FP vom Ursprungsknoten 68 betrachtet, das mit
einem zweiten FP vom Bestimmungsknoten 70 am Kollisionsknoten 62 kollidiert. Das
erste FP wurde im Knoten 68 in Reaktion auf ein Begehren
des Knotens 68 generiert, mit dem Knoten 70 zu
kommunizieren, so daß der
Inhalt der Felder im ersten FP ist (die Übertragung durch die Haupttrasse 66 ist
gezeigt als „N1*2*3"):
- FP-Feld
ist das FP
- Fühlerdatenfeld
ist „gewünschte Bestimmung
= NODE 70"
- Knotenübertragungsprotokollfeld
(Node Transit Log Field) ist „NODE
68" „NODE 50" „NODE 58" „N1*2*3"
-
Das
zweite FP kann durch den Knoten 70 in Reaktion auf einen
Wunsch des Knotens 70 mit einem dritten Knoten, wie beispielsweise
dem Knoten 48 zu kommunizieren, erzeugt worden sein, so
daß der
Inhalt der Felder im zweiten FP ist:
- FP-Feld ist FP
- Fühlerdatenfeld
ist „gewünschte Bestimmung
= NODE 48"
- Knotenübertragungsprotokollfeld
(Node Transit Log Field) ist „NODE
70" „NODE 52"
-
Wenn
das erste FP am Knoten 62 ankommt, wird im Knoten 62 nach
anderen FPs gesucht und das zweite FP wird erkannt. Wenn das zweite
FP geprüft
ist, wird eine Übereinstimmung
der Einträge „NODE 70" im RI-Feld und „NODE 70" im Fühlerdatenfeld
des ersten FP festgestellt. Dadurch erkennt der Knoten 62 eine „Kollision" zwischen dem ersten und
zweiten FP und erstellt ein PP zur Übertragung zum Knoten 70.
Die Inhalte der Felder dieses PP sind:
- Das Ursprungsfeld
ist „NODE
68"
- Das Kollisionsfeld ist „NODE
62"
- Das RI-Feld ist „N3*2*1" „NODE 58" „NODE
50" „NODE 68"
- Das Datenfeld (erkannter Weg) ist „NODE 68" „NODE
50" „NODE 58" „N1*2*3" „NODE
62" „NODE 52" „NODE 70"
-
Da
für das
erste FP eine Kollision erkannt wurde, wird das erste FP nicht weiter
gesendet und erlischt im Knoten 62. Im Gegensatz dazu wiesen
bei diesem Beispiel die NT-Protokolle aller anderen am Knoten 62 vorhandenen
FPs nicht die gewünschte Bestimmung "NODE 48" auf, als das zweite
FP zum ersten Mal am Knoten 62 ankam. Da eine Kollision für das zweite
FP am Knoten 62 nicht erfaßt wurde, wird das zweite FP
dann durch Hinzufügen
von "NODE 62" zum NP-Protokoll
erweitert und auf zufällige Weise
zu einem benachbarten Knoten, der nicht der Ursprungsknoten 52 ist,
von dem es empfangen wurde, gesandt.
-
In 8 ist
ein Ablaufdiagramm dargestellt, das eine beispielhafte Ausführungsform
eines Teils der erfindungsgemäßen Prozedur
zeigt, die für
eine Durchführung
an einem Ursprungsknoten, wie beispielsweise dem Ursprungsknoten 68 (2)
geeignet ist. Diese Prozedur beginnt mit dem Schritt 142 in Reaktion
auf eine Anfrage am Knoten 68, (z. B.) mit dem Bestimmungsknoten 70 zu
kommunizieren. Zunächst
wird im Schritt 144 vom Knoten 68 bestimmt, ob
ein Weg zum Knoten 70 lokal verfügbar ist. Falls dieser lokal
gespeichert ist, wird er im Schritt 146 auf seine Aktualität überprüft und falls
er nicht ungültig ist,
fügt der
Knoten 68 den Weg in das RI-Feld jedes für den Knoten 70 bestimmten
Datenpakets im Schritt 148 ein und schickt die Pakete im
Schritt 150 auf ihre Reise durch das Netz 34.
Falls der lokal gespeicherte Weg zum Knoten 70 nicht mehr
gültig
ist, oder auf andere Weise nicht mehr verfügbar ist, beginnt der Knoten 68 im
Schritt 152 mit einer Wegerkennungsprozedur durch Generieren
und Abschicken eines zur Erkundung eines Wegs zum Knoten 70 bestimmten Fühlerpakets.
In den Schritten 154 und 156 wird im Schritt 158 während des
Abwartens der Rückkehr
eines PP von einem bestimmten Kollisionsknoten im Netz 34 ein
Zähler
abwärts
gezählt.
Wenn der Zähler nicht
mehr gültig
ist, wird der Schritt 152 durch Abschicken eines weiteren
zur Erkundung eines Weges zum Knoten 70 vorgesehenen Fühlerpakets
wiederholt und die Schritte 154 und 156 werden
während des
Abwartens eines PP im Schritt 158 wieder durchschleift.
Wenn im Schritt 158 ein PP ankommt, werden die Wegdaten
im Schritt 160 lokal im Knoten 58 gespeichert
und die Prozedur kehrt zu den oben beschriebenen Schritten 146, 148 und 150 zurück. Es ist
ohne Weiteres verständlich,
daß der
Schritt des Abschickens des FP 152 auch in Reaktion auf
zahlreiche andere geeignete Bedingungen, wie z. B. den Grad der
Datenaktualität,
beispielsweise in Reaktion auf den Grad der Nachfrage am Knoten 68 nach
einem Weg zum Knoten 70, oder in Reaktion auf die Höhe der Kosten
des durch die im Knoten 68 gespeicherten Wegdaten wiedergegebenen
Weges, wiederholt werden kann.
-
In 9 ist
ein Ablaufdiagramm gezeigt, das eine beispielhafte Ausführungsform
eines Teils der Wegerkennungsprozedur gemäß dieser Erfindung zeigt, die
zur Durchführung
an einem Kollisionserfassungsknoten, wie beispielsweise dem Knoten 62 (2)
geeignet ist. Diese Prozedur beginnt im Schritt 162 in
Reaktion auf den Empfang eines ersten Fühlerpakets (FP1) am Knoten 62.
Im Schritt 164 wird das FP1 geparst, um die gewünschte Bestimmung
zu erhalten (DEST1), nach der dann im Knoten 62 durch Abarbeiten
jedes anderen im Knoten 62 vorhandenen FP gesucht wird,
was beispielsweise alle nicht ungültig gewordenen FPs umfassen
kann, die vor dem FP1 erhalten wurden, und alle FPs, die während des
Aufenthalts (vor dem Ungültigwerden)
des FP1 am Knoten 62 ankommen. Im Schritt 166 wird die
Existenz früherer
Ankünfte
des FP getestet und im Schritt 168 wird das NT-Protokoll
für jedes
ermittelte FP auf das Vorhandensein von DEST1 überprüft. Falls im Schritt 170 DEST1
im NT-Protokoll
eines früher
angekommenen FP gefunden wird, wird im nächsten Schritt 172 eine
Detektion einer Kollision für
FP1 erklärt.
Das FP1 soll dann weiterhin im Knoten 62 bleiben, bis es
ungültig
wird, woraufhin es gelöscht
wird, ohne weitergeschickt zu werden. Im Schritt 174 werden
die Wegdaten aus den NT-Protokollen der kollidierenden FPs zusammengesetzt,
so daß der
vom Knoten 68 gesuchte Weg zum Knoten 70 gebildet
wird. Im Schritt 176, der statt dessen im Knoten 68 nach
dem Empfang der Wegdaten vom Knoten 62 ausgeführt werden
könnte,
werden alle Schleifen aus den Wegdaten entfernt, was im Prinzip durch
Löschen
von Einträgen
im NT-Protokoll zwischen zwei identischen Einträgen und Verbinden der identischen
Einträge
erreicht werden kann. Schließlich
wird im Schritt 178 ein PP erzeugt und zum Knoten 68 gesandt,
das die aus der FP-Kollision am Knoten 62 erhaltenen Wegdaten
enthält.
Bei einer alternativen Ausführungsform
(nicht gezeigt) für
vom Paketverkehr nicht betroffene Systeme kann das PP (das beispielsweise
in zweckmäßiger Weise
durch Umkehren der Wegdatenfeldsequenz modifiziert ist) ebenfalls
zum Knoten 70 zur unmittelbaren Verwendung beim Abschicken
von Paketen zurück
zum Knoten 68 weitergeschickt werden. Selbstverständlich kann
das Datenpaket RI-Feld für
denselben Zweck am Knoten 70 extrahiert werden (mit einem
geringeren Netzpaketverkehr), sobald das erste Datenpaket (5)
am Knoten 70 vom Knoten 68 in Antwort auf die
Ankunft des zum Knoten 68 gesendeten PP ankommt.
-
Wenn
der Schritt 166 endet, ohne daß eine Kollision für das FP1
am Knoten 62 erfaßt
wird, wird die Prozedur im Schritt 180 fortgesetzt, in
dem ein „Verweildauer
im Knoten" -Timer
für FP1
dekrementiert wird. Im Schritt 182 wird der Timer auf seinen
Ablauf geprüft und
sofern er nicht ungültig
geworden ist, wird im Schritt 184 der Knoten 62 auf
ein neu angekommenes FP überprüft, wobei
dessen NT-Protokoll im Schritt 168 auf einen DEST1-Eintrag überprüft wird.
Falls ein DEST1 im Schritt 188 ermittelt wird, verzweigt
sich die Prozedur zum oben erläuterten Schritt 172 und
das FP1 kann im Knoten 62 ungültig werden. Falls der Schritt 188 fehlschlägt, wird
der Schritt 184 noch einmal ausgeführt und falls der Schritt 184 fehlschlägt wird
die Timer-Dekrementierungsschleife im Schritt 180 neu gestartet.
Wenn die Zeit für
das FP1 im Knoten 62 ohne eine Kollision abgelaufen ist,
wird das FP1 im Schritt 190 durch Hinzufügen von „NODE 62" zum NT-Protokoll
von FP1 erweitert. Schließlich
wird im Schritt 192 eine willkürliche vom Knoten 62 ausgehende
Verbindung ausgewählt
und eine Kopie des erweiterten FP1 wird zum benachbarten Knoten
auf der ausgewählten
Verbindung ausgesandt, an dem die Prozedur in 9 wiederholt
werden kann.
-
In 10 ist
ein schematisches Diagramm eines CDROM 194 gezeigt, das
eine beispielhafte Ausführungsform
des Computerprogrammproduktes dieser Erfindung verkörpert. Der
CDROM 194 umfaßt ein
Aufzeichnungsmedium 196, in dem eine Mehrzahl von durch
die Softwareprogrammmodule 198, 200, 202 beispielhaft
verkörperten
Softwaremitteln gespeichert sind. Die Module 198, 200 und 202 können beispielsweise
Mittel zur Steuerung des Knotens 68, um das FP1 entsprechend
dem Schritt 190 (9) zu erweitern,
oder beispielsweise Mittel zur Steuerung des Knotens 68 zur
Kombination der Inhalte des NT-Protokolls aus zwei kollidierenden
FPs umfassen. Derartige Programmodule können vom CDROM 194 zu
den Speicherelementen jedes beliebigen Knotens oder von Knoten im
Netz 34 übertragen
werden, um das erfindungsgemäße Verfahren
zu erfüllen.
-
Offensichtlich
ergeben sich in Anbetracht dieser Lehre weitere Ausführungsformen
und Abwandlungen dieser Erfindung für den Fachmann ohne weiteres.
Daher ist die Erfindung lediglich durch die folgenden Ansprüche beschränkt, die
alle in Verbindung mit der obigen Beschreibung und der begleitenden
Zeichnung zu betrachtenden Ausführungsformen
und Abwandlungen umfaßen.