Feld der Erfindung
-
Die Erfindung betrifft allgemein ein Kommunikationssystem,
das durch Verbinden einer Vielzahl von unabhängigen
Netzwerken untereinander gebildet wird, und insbesondere eine
Methode und Anordnungen zum Bewirken der Verbindung
getrennter Netzwerke untereinander, ohne daß topologische
Beschränkungen gemacht werden.
Hintergrund der Erfindung
-
Es ist oft erforderlich, das Abdeckungsgebiet lokaler
Netzwerke (LAN = Local Area Network) durch Verbinden dieser
LANs untereinander auszudehnen, um ein geographisch weit
gestreutes Großstadtnetz zu erzeugen. Auch eine
Institution, wie z. B. eine Universität oder eine Firma, die mit
einem Satz unterschiedlicher LANs arbeitet, z. B. innerhalb
eines Gebäudekomplexes, kann es als notwendig betrachten,
diese LANs miteinander zu verbinden, um ein großes LAN zu
erzeugen, das den gesamten Komplex bedient.
-
Wenn eine Einrichtung (z. B. ein Computer, ein
Videoterminal, ein Telefongerät), die mit einem LAN verbunden ist,
nur einen Pfad zu einer Einrichtung eines anderen LANs nach
der gegenseitigen Verbindung hat, wodurch eine
schleifenfreie Topologie erzeugt wird, kann eine Verbindung erreicht
werden, indem Netzwerkpaare mit einem sog. Gateway
verbunden werden, das ein Speicher- und Sende-Protokoll ausführt.
Eine solche Verbindungsanordnung wird als transparente
Verbindung beschrieben, da das Vorhandensein eines Gateways
für keines der Geräte im verbundenen System sichtbar ist
und folglich sind keine Modifikationen der Geräte oder der
Nachrichten oder der Datenpakete, die von den Geräten
ausgehen, erforderlich.
-
Kürzlich hat eine Anzahl von bekannten Schriften die
Methode und die zugeordneten Schaltkreise einer transparenten
Verbindungseinrichtung diskutiert. Diese umfassen:
-
(1) "Local Area Network Applications", Telecommunications,
September 1984 von B. Hawe und B. Steward; (2) "An
Architecture for Transparently Interconnecting IEEE 802 Local Area
Networks", eine Digital Equipment Corporation technische
Schrift, die dem IEEE 802 Standardskommitee im Oktober 1984
vorgelegt wurde; und (3) "Transparent Interconnection of
Local Networks with Bridges", Journal of Telecommunications
Networks, Oktober 1984 von B. Hawe, A. Kirby und B.
Steward; (4) UK Patentanmeldung GB, A, 2149625, 12. Juni
1985; und (5) "On the Generation of Explicit Routing
Tables" von K. Maruyama et al, veröffentlicht in den
Proceedings of the Fifth International Conference on Computer
Communications, 27. Oktober 1980, Seiten 90 bis 95. Diese
Schriften stellen heraus, daß die Topologie der
untereinander verbundenen Netzwerke entweder die eines
Verzweigungsbaumes sein muß oder darin besteht, daß ein Satz von
Brückenbäumen für das Netzwerk ausgewählt werden muß, so
daß jeder Baum des Satzes schleifenfrei ist. Gateways
können LANs nicht transparent untereinander verbinden,
wobei sie alternative Pfade zwischen lokalen Netzwerken
unterstützen, was Schleifen ergibt. Tatsächlich wird in der
Schrift (1) eine Technik zum Transformieren einer
allgemeinen Maschentopologie in eine schleifenfreie Topologie
vorgeschlagen, so daß die Gateways verwendet werden können.
In der Schrift (5) werden Pakete über das Netzwerk
übertragen, indem ein Satz aus Brückenbäumen ausgewählt wird, ein
Baumidentifizierer mit jedem Paket zugeführt wird und das
Paket durch das geeignete Baumnetzwerk in Übereinstimmung
mit dem Identifizierer geschleust wird.
-
Das Erfordernis, daß die Systemtopologie schleifenfrei ist,
ist ganz allgemein schwerwiegend und begrenzt schließlich
die praktische Anwendung der herkömmlichen
Gateway-Anordnung. Um Kanalkapazitätsanforderungen zu erfüllen oder um
einen gewissen Zuverlässigkeitsgrad bereitzustellen, kann
ein verbundenes System einige Schleifen in einigen
Abschnitten der Topologie enthalten. Die herkömmlichen
Gateways detektieren und entfernen diese Schleifen immer,
wodurch eine verbesserte Redundanz oder Zuverlässigkeit
verhindert wird. Das Problem der verbindenden Schleife oder
der zyklischen Topologien in der physikalischen oder
Verbindungsschicht und das Abschwächen des "Überlaufens" des
Netzwerkes, wie es jedes Gateway aus dem Ort der
verschiedenen Netzwerke lernt, die durch die Gateways verbunden
werden, wurde von den bekannten Schriften nicht
angeschnitten.
Überblick über die Erfindung
-
Diese Einschränkung von erforderlichen schleifenfreien
Topologien für die transparente Verbindung lokaler Netzwerke
mit Speicher-und-Sende-Gateways wird gemäß der vorliegenden
Erfindung durch ein Verfahren gemäß Anspruch 1 vermieden,
das Wegsucheinformationen verwendet, die von den
Nachrichtenpaketen zugeführt werden.
-
Allgemein ausgedruckt wird die Gesamtsystemtopologie durch
einen ungerichteten, verbundenen Graphen wiedergegeben,
worin Netzwerke in Knoten und Gateways in Kanten umgesetzt
sind. Ein Satz von Brückenbäumen wird für den Graphen
definiert, um die erforderliche Kapazität und die notwendige
Redundanz zu erzeugen. Jeder Brückenbaum ist eindeutig
identifiziert. Jedes Nachrichtenpaket, das das Gesamtsystem
durchquert, wird einem spezifischen Brückebaum zugeordnet,
so daß das Paket zwischen Knoten entlang Kanten, die in
dem spezifizierten Brückenbaum enthalten sind, befördert
wird. Jedes Gateway mit einem entwickelten Speicher-und-
Sende-Protokoll analysiert das Paket, um den zugeordneten
Brückenbaum zu bestimmen und schickt die Nachricht
dementsprechend weiter. In einer Ausführungsform der vorliegenden
Erfindung spezifiziert das Gerät, von dem das Paket stammt,
den Brückenbaumidentifizierer und führt ihn entweder
explizit oder Implizit in dem Paket zu.
-
Um verschiedene potentiell unnötige Übertragungen über das
System durch ein Gerät zu reduzieren, das neu mit dem
Netzwerk verbunden wurde, bringt das Protokoll eine Verzögerung
ein, um den Gateways zu erlauben, den Ort des neuen Geräts
zu lernen. Das erweiterte Protokoll implementiert dann
einen Speicher-Verzögerung-Sende-Algorithmus.
-
Die Organisation und der Betrieb der vorliegenden Erfindung
sind besser aus einer Erläuterung einer genauen
Beschreibung der Erfindung zu verstehen, die nachfolgend in
Verbindung mit den beiliegenden Zeichnungen durchgeführt wird.
Kurzbeschreibung der Zeichnungen
-
Fig. 1 ist ein Blockdiagramm, das eine
Gatewaypaar-Anordnung zum untereinander Verbinden zweier lokaler
Netzwerke zeigt;
-
Fig. 2 ist ein exemplarisches, schleifenfreies und
hierarchisches System mit drei Ebenen, das die
Verbindung einer Vielzahl von LANs mit verschiedensten
Gatewaypaar-Anordnungen zeigt;
-
Fig. 3 zeigt die Art und Weise, mit der das erste Paket
von einem gegebenen LAN durch das System der Fig.
2 nach der Netzwerkinitialisierung fortschreitet
und zeigt die Fähigkeit des Netzwerks, den Ort
der Quelle des ersten Pakets zu lernen;
-
Fig. 4 zeigt das Fortschreiten eines Rückkehrpakets durch
das System der Fig. 2 und zeigt, daß das Netzwerk
den Quellenort des Antwortpakets "gelernt" hat;
-
Fig. 5 zeigt das Fortschreiten des zweiten Pakets von
dem gegebenen lokalen Netzwerk in der Fig. 2 und
demonstriert, daß die Gateways die Identifikation
der Paketquelle "gelernt" haben und nun optimal
alle zukünftigen Pakete von einem vorgegebenen
Geräte befördern;
-
Fig. 6 und 7 sind grafische Darstellungen des Systems nach
Fig. 2, die zwei unterschiedliche Brückenbäume
für das System zeigen;
-
Fig. 8 zeigt eine Erweiterung eines zyklischen Graphen
für einen Abschnitt des Systems der Fig. 2 und
zwei azyklische Graphen, die die Erweiterung
abdecken;
-
Fig. 9 ist ein Graph, der das System der Fig. 2
wiedergibt, wobei zwei Brückenbäume übereinander liegen,
um den Systemdurchsatz zu erhöhen;
-
Fig. 10 ist ein Graph eines Abschnitts der Fig. 9, der
einen kopierten Knoten zeigt, um die
Verkehrsüberlastung in einem einzelnen Knoten zu reduzieren;
und
-
Fig. 11 ist ein Flußdiagramm, das die Schritte für das
Ausbreiten eines Pakets durch ein im allgemeinen
zyklisches System zeigt.
Detaillierte Beschreibung
-
Zur Erläuterung ist es hilfreich anfangs eine bekannte
Gateway-Anordnung zu beschreiben, wobei der Schwerpunkt auf
der Methode liegen soll, um eine Basis für die
fundamentalen Konzepte der vorliegenden Erfindung bereitzustellen.
Diese Basis führt grundlegende Konzepte und eine
grundlegende Terminologie ein, die eine spätere Erläuterung der
Ausführungsformen der vorliegenden Erfindung erleichtern, um
die Abweichungen vom Stand der Technik zu erläutern.
1. Grundlegende Basis
-
Gemäß Fig. 1 sind zwei Netzwerke 101 und 201, die als
Netzwerk A bzw. Netzwerk B bezeichnet werden, durch ein Paar
von unidirektionalen Gateways 102 und 202 untereinander
verbunden, um ein Gesamtkommunikationssystem 100 zu bilden.
Die Gateways 102 und 202 sind in so einer Art und Weise
verbunden, daß das Gateway 202 eine Übertragung durch das
Gateway 102 zum Netzwerk B ignoriert. Das Gateway 102 ignoriert
eine Übertragung durch das Gateway 202 zum Netzwerk A.
-
Jedes separate Netzwerk bedient typischerweise eine
Vielzahl von Geräten und Hostrechnern. In Fig. 1 sind die
Hostrechner 111 und 112 und die Hostrechner 211 und 212 mit
dem Netzwerk 101 bzw. 201 verbunden und kommunizieren über
diese Netzwerke. Von jedem Hostrechner wird vorausgesetzt,
daß er eine eindeutige Adresse hat, und jedes Netzwerk hat
eine Übertragungsfähigkeit, d. h., wenn ein Hostrechner ein
Paket sendet, daß alle anderen Gateways des gemeinsamen
Netzwerks dieses Paket empfangen.
-
Jedes Paket, das über ein Netzwerk übertragen wird, enthält
eine Sendehostrechner-Adresse und eine
Ziel-Hostrechneradresse und die tatsächlichen Nachrichtendaten. Eines der
Gateways, die die zwei Netzwerke miteinander verbinden,
ist dazu ausgelegt, jedes Paket, das auf einem gegebenen
Netzwerk übertragen wird, zu empfangen. Zum Beispiel ist
in Fig. 1 das Gateway 102 der Empfänger für alle Pakete,
die auf dem Netzwerk 101 übertragen werden.
-
Ein Speicher- und -Sende-Protokoll, das von jedem Gateway
implementiert wird, ist wie folgt aufgebaut: ein Gateway
schickt jedes Paket, das über das ihm zugeordnete Netzwerk
übertragen wird, außer ein Paket, das für einen Hostrechner
bestimmt ist, der zuvor in der Sendeadresse eines anderes
Pakets erschienen ist. Somit, immer dann wenn ein
Hostrechner zum ersten Mal ein Paket sendet, lernt jedes Gateway,
durch das das Paket läuft, den Ort des Hostrechners. Wenn
ein zweiter Hostrechner später ein Paket an den ersten
Hostrechner schickt, läuft das Paket automatisch über den
optimalen Weg durch das System.
-
Um dieses Protokoll in einem gewissen Detail zu erläutern,
wird das System 300 der Fig. 2 betrachtet. Diese Anordnung
umfaßt verschiedene Netzwerke, die durch Paare von Gateways
verbunden sind, wobei jedes der Gateways den obenstehenden
Algorithmus ausführt.
-
Um das Protokoll genau zu definieren, wird die nachfolgende
Notation verwendet:
-
Ni: Netzwerk Nr. i (Elemente 30i), i = 1, . . ., 7
-
Gij: Gateway vom Netzwerk i zum Netzwerk j (Elemente 3ij)
-
A, B, C, D, E: Hostrechner (Elemente 381, 382, . .., 385)
Pxy: Paket, das vom Hostrechner X zum Hostrechner Y
geschickt wurde
:"ist wieder gesendet auf"
-
Dij: Satz aus Hostrechnern, gespeichert in Gij für den
die Übertragung durch Gij blockiert ist (Dij wird als
"Stoppfilter" bezeichnet).
-
Es wird angenommen, daß die Anordnung nach Fig. 2
initialisiert worden ist, d. h. daß Dij ist 0 (ein leerer Satz),
für alle i,j und daß nun eine Übertragung vom Hostrechner
E zum Hostrechner C (PEC) stattfindet:
-
1. PEC durchläuft N&sub7;
-
2. D&sub7;&sub3; = {E}, und PEC N&sub3; durch G&sub7;&sub3;
-
3. D&sub3;&sub6; = {E}, und PEC N&sub6; durch G&sub3;&sub6;
-
D&sub3;&sub1; = {E}, und PEC N&sub1; durch G&sub3;&sub1;
-
4. D&sub1;&sub2; = {E}, und PEC N&sub2; durch G&sub1;&sub2;
-
5. D&sub2;&sub4; = {E}, und PEC N&sub4; durch G&sub2;&sub4;
-
D&sub2;&sub5; = {E}, und PEC N&sub5; durch G&sub2;&sub5;
-
PEC erreicht den Zielort beim Schritt 3, aber es wird
weiter übertragen und überflutet das Netzwerk. Das wird durch
die gestrichelten Linien in Fig. 3 dargestellt.
-
Nun wird ein Rückkehrpaket PCE mit Bezug auf Fig. 4
betrachtet:
-
1. PCE durchläuft N&sub6;
-
2. D&sub6;&sub3; = {C}, und PCE N&sub3; durch G&sub6;&sub3;
-
3. D&sub3;&sub1; = {C, E}, und PCE wird von G&sub3;&sub1; gestoppt
-
D&sub3;&sub7; = {C}, und PCE N&sub7; (und Host E) durch G&sub3;&sub7;.
-
Da der Ort des Hosts E von der Übertragung von PEC
"bekannt" war, nahm das Rückkehrpaket den optimalen Weg durch
das Netzwerk.
-
Als letzte Betrachtung wird angenommen, daß ein zweites
Paket PEC über das Netzwerk übertragen werden soll, wie
es in der Fig. 5 gezeigt wird:
-
1. PEC durchläuft N&sub7;
-
2. D&sub7;&sub3; = {E}, und PEC N&sub3; durch G&sub7;&sub3;
-
3. D&sub3;&sub1; = {C, E}, und PEC wird von G&sub3;&sub1; gestoppt
-
D&sub3;&sub6; = {E}, und PEC N&sub6; (und Host C) durch G&sub3;&sub6;
-
Tatsächlich durchläuft PkE für alle k ≠ E nur die notwendigen
Netzwerke. Da PCE nur von G&sub6;&sub3;, G&sub3;&sub1; und G&sub3;&sub7; empfangen wurde,
weiß nur ein Teil des Gesamtnetzwerks den Ort des Hosts
C. Der Rest des Netzwerks wird jedoch den Ort des Hosts C
lernen, wenn er zu anderen Hosts überträgt. Wenn ein
Gleichgewichtszustand erreicht ist, hat jedes Gij eine sog.
"Sperr-" oder "Stopp-" Liste Dij, die eine optimale
Weggabe erzeugt und überflüssige Übertragungen unterbindet.
2. Erweiterungen der Protokollanordnung
-
Es kann aus der obenstehenden Beschreibung abgeleitet
werden, daß das System 300 nur einen Weg zwischen einem Paar
von Hosts haben muß, um ein Paket vom
"Schleifendurchlaufen" zwischen zwei Gateways für immer abzuhalten. Genauer,
wenn ein System auf einen ungerichteten Graphen abgebildet
ist, indem Netzwerke in Knoten und Gateway-Paare in Kanten
abgebildet werden, muß der entstehende Graph schleifenfrei
sein, damit er richtig funktioniert, d. h., die Topologie
des Systems 300 ist auf die eines nichtzyklischen Graphen
beschränkt. Fig. 6 ist eine Darstellung der Topologie des
Systems 300 In Graphenform. Paare aus Gateways von Fig.
2 sind gruppiert worden und mit den Indizes verbunden
worden, die nun in Fig. 6 verwendet werden, um die
Graphenkanten (durchgezogene Linien) zu definieren. Dieser Graph
ist azyklisch, da jedes Paar von Knoten mit nur einem Weg
verbunden ist. Wenn z. B. die Knoten 306 und 307 direkt
verbunden wären (gezeigt mit der gestrichelten Kante 375 der
Fig. 6), dann wäre der Graph zyklisch.
-
Systeme, die zyklisch sind, können nicht direkt das zuvor
erläuterte Speicher- und -Sende-Protokoll oder den
entsprechenden Algorithmus verwenden. Z.B. würde gemäß Fig. 6,
wo die Knoten 306 und 307 direkt verbunden sind, ein Paket,
das von einem Host auf dem Knoten 303 zu einem Host auf
den Knoten 306 gesendet wird, immer auf einem Weg 303-307-
306-303-307 . . . in einer Schleife laufen und das gleiche
Paket würde auf einem anderen Weg 303-306-307-303-306- . . .
in einer Schleife laufen. Die in einer Schleife laufenden
Pakete würden die Gateways und Netzwerke auf ihren
Schleifen auslasten und somit normale Kommunikationen blockieren.
-
Die Struktur gemäß durchgezogener Linie der Fig. 6 wird
als Brückenbaum bezeichnet, d. h., daß in einem Brückenbaum
jedes Paar von Knoten nur mit einem Weg verbunden ist. Der
Graph der Fig. 7 zeigt einen anderen Brückenbaum für die
Knotenanordnung der Fig. 6. Im allgemeinen hat ein
beliebiger Graph eine Vielzahl von Brückenbäumen.
-
Um die Verbesserung bezüglich der
Gateway-Protokoll-Anordnung in Übereinstimmung mit einem Aspekt der vorliegenden
Erfindung zu implementieren, wird ein Satz von
Brückenbäumen für den zyklischen Graphen gemäß den vorgegebenen
Richtlinien ausgewählt. Jeder Brückenbaum wird einem
einzigartigen Identifizierer oder einer Nummer zugeordnet und jede
Nachricht, die durch das System läuft, wird einem
einzigartigen Brückenbaum über ihren Identifizierer zugeordnet.
Jedes Gateway, das diese Nachricht empfängt, bestimmt die
Baumnummer und befördert die Nachricht über den
spezifizierten Brückenbaum und stoppt alle Pakete anderer
Brückenbäume. Typischerweise spezifiziert das Gerät, von dem die
Nachricht ausgeht, die Brückenbaumnummer, entweder explizit
oder implizit. Bei der expliziten Lösung kann z. B. eine
"Baumnummer" zu den Paketspezifikationen hinzugefügt
werden, z. B. als Extrabit im Kopf des Nachrichtenpakets. Bei
der impliziten Lösung kann eine Brückenbaumnummer aus
Feldern erzeugt werden, die normalerweise in dem Paket
untergebracht sind, wie z. B. die Quellen- und Zieladressen. Ein
geeignetes Funktionsbeispiel könnte z. B. sein
-
Brückenbaumnummer = (Quelle "exklusiv oder" Ziel) modulo N,
-
wobei N die Anzahl der Brückenbäume des Netzwerkes ist.
Dies hat den Vorteil, daß der gesamte Verkehr zwischen
einem Paar aus Hosts nur auf einem einzigen Brückenbaum
läuft, wodurch die besetzten Stopplisten im System
minimiert werden.
-
Der Graph in der Mitte der Fig. 8 ist eine Konstruktion
aus durchgezogenen und gestrichelten Linienabschnitten des
Graphen der Fig. 6, der die Knoten 303, 306 und 307 und
die Kanten 364, 374 und 375 aufweist. Der Graph nach Fig.
8 ist zyklisch. Um diese neue Konfiguration zu erlangen,
wird z. B. vorausgesetzt, daß das System 300 der Fig. 2
modifiziert wurde, um ein Gatewaypaar (Kante 375) zu
enthalten, das die Knoten 306 und 307 miteinander verbindet. Die
Kante 375 kann für einen erhöhten Nachrichtenverkehr vom
Knoten 306 zum Knoten 307 dienen, den die Kanten 364 und
374 nicht länger ohne Überlastung bewerkstelligen können.
-
Da der Graph der Fig. 8 zyklisch ist, wird ein Satz von
Brückenbäumen ausgewählt. Zwei Brückenbäume, die diesen
Graphen abdecken, werden in dem linken bzw. rechten
Diagramm der Fig. 3 als Graphen 401 bzw. 402 dargestellt.
Wenn die Notation M (S; D; T) verwendet wird, wobei S der
Quellenknoten, D der Satz aus Zielknoten und T die
Brückenbaumanzahl ist, dann ist ein möglicher
Nachrichtenweg-Zuordnungsalgorithmus für die Knoten 303, 306 und 307 gegeben
durch:
-
M (303; 306, 307, 301, . . .; 2),
-
M (306; 303, 307, 301, . . .; 1), und
-
M (307; 303, 306, 301, . . .; 2).
-
Diese spezielle Zuordnung verwendet die Kante 375 nur für
Nachrichten, die vom Knoten 306 stammen, und zwar
angenommenerweise zum Zwecke des Ausgleichens der Belastung. Wenn
die Kante 375 gesperrt wird, kann dies den Einrichtungen,
die mit dem Knoten 306 verbunden sind, mitgeteilt werden,
um die Zuordnung auf M (306; 303, 307, 301, . . .; 2) zu
ändern, wodurch die Kommunikation innerhalb des Systems
aufrechterhalten wird. Die Vielzahl der Brückenbäume in
einem zyklischen Netzwerk erzeugt eine Redundanz zwischen
gewissen Knoten. Es kann auch einen gewissen Verlust an
Geschwindigkeit während den Ausfällen entsprechender Gateways
geben.
-
Ganz allgemein müssen Gateways, die in unterschiedlichen
Brückenbäumen auftreten, eine Stoppliste für jeden
Brückenbaum aufrechterhalten. Z.B. gemäß Fig. 8, wenn
D(k)ij die Stoppliste für den k-ten Brückenbaum angibt,
dann treffen Pakete, die vom Host C zum Host E (PCE) auf
beiden Bäumen übertragen werden, beim Start für die Kante
374 auf:
-
D(1)&sub3;&sub6; = , D(2)&sub3;&sub7; = {C},
-
D(1)&sub7;&sub3; = {C} und D(2)&sub7;&sub3; = .
-
Die Notwendigkeit zum Aufrechterhalten mehrerer
Stopplisten kann bei einem beliebigen Graphen abgeschwächt
werden, indem die meisten Brückenbäume in einem Satz gesammelt
werden, so daß keine Kante in mehr als einem Brückenbaum
enthalten ist.
-
Auch wenn ein System nichtzyklisch ist, ist es oftmals
notwendig, schließlich doch mehrere Brückenbäume zu verwenden,
um eine ausreichende Kommunikationskapazität bereitstellen
zu können. Ein anderer Aspekt der vorliegenden Erfindung
umfaßt diese Situation. Erläuternd für diesen Fall ist ein
System in Baumform, wie z. B. eine öffentliche oder private
Telefonnetzwerkhierarchie, die ein großes geographisches
Gebiet abdeckt. Diese Systeme neigen zu einem Engpaß am
oder nahe am Ursprung. Anstatt der Verwendung von
getrennten Brückenbäumen, bei denen keine Kante in mehr als einem
Brückenbaum enthalten ist, erfordern Kapazitätsüberlegungen
im wesentlichen Identische Brückenbäume, die über dem
Graphen anzuordnen sind. Dies wird demonstriert mit Bezug auf
den Graphen der Fig. 9, der der neugezeichneten Fig. 6
entspricht, um zwei Brückenbäume (einer ist durchgezogen,
der andere hat eine gestrichelte Linie) für eine Hierarchie
mit drei Niveaus zu zeigen.
-
In diesem Fall implementiert nur ein Gatewaypaar die Kante
343 in jedem der zwei Brückenbäume. Die Kante 322 ist
jedoch mit zwei Gatewaypaaren implementiert, wobei eines für
jeden Brückenbaum vorgesehen ist. Ähnlich verwenden die
Kanten 353, 364 und 374 ein Gatewaypaar für beide Bäume,
wohingegen die Kante 332 zwei Gatewaypaare aufweist. Wegen
dieser strategischen Anordnung ist die Stoppliste für die
Kante 343 (auch für Kanten 353, 364 und 374) die gleiche
für jeden Brückenbaum, so daß nur eine Liste
aufrechterhalten werden muß. Ähnlich ist die Stoppliste der Kante 322
(auch Kante 332) die gleiche, aber dies ist weniger
signifikant, da zwei separate Gatewaypaare verwendet werden.
-
Das Netzwerk der Fig. 9 kopiert die Gateways zwischen den
Niveaus 1 und 2 (Kanten 322 und 332), um eine Überlastung
zu reduzieren. Eine Überlastung kann jedoch auch in den
Knoten auftreten. Fig. 10 zeigt einen Abschnitt des
Netzwerks nach Fig. 9, In dem der Knoten 301 kopiert (Knoten
303) Ist, um den Verkehr, der durch den Knoten 301 geht,
zu reduzieren. Dieses Netzwerk arbeitet so lange richtig,
so lange keine Hosts mit den Knoten 301 oder 303 verbunden
werden. Wenn Hosts mit den Knoten 301 und 303 verbunden
werden, müssen Gatewaypaare den Kanten 384 und 394
hinzugefügt werden, um eine komplette Verbindung zu erzeugen.
-
Die Strategie des Hinzufügens paralleler Kanten und Knoten
im gesamten System hat keine Begrenzung bezüglich der
Anzahl der Niveaus, die kopiert werden, oder bezüglich der
Anzahl paralleler Kanten und Knoten, die hinzugefügt
werden. Wegen dieser Eigenschaft können Netzwerke mit beliebig
großem Durchsatz aufgebaut werden. Diese Netzwerke haben
die gewünschte Eigenschaft, das nichtkopierte Kanten mit
nur einem einzigen Stoppfilter implementiert werden können,
und zwar unabhängig von der Anzahl der verwendeten
Brückenbäume.
-
Fig. 11 ist ein Flußdiagramm, das die Schritte des
Übertragens jedes Pakets durch ein System mit Brückenbäumen
erläutert. Der Block 401 gibt an, daß ein Satz aus
Brückenbäumen für das System vorausgewählt wird, um Kapazitäts-
und Zuverlässigkeitsüberlegungen zu erfüllen, worauf dann
jedem Baum ein eindeutiger Identifizierer zugeordnet wird.
Wie mit dem Block 411 angegeben wird, wird für jedes Paket,
das erzeugt wird und dann über das verbundene
Quellennetzwerk von einer Einrichtung übertragen wird, ein
vorausgewählter Brückenbaum-Identifizierer im Paket untergebracht.
Jedes Gateway, das das übertragene Paket empfängt, bestimmt
den Identifizierer, der im Paket untergebracht wird, aber
auch die Quellen- und Zieleinrichtungen, von denen das
Paket stammt bzw. empfangen wird. Dies wird durch den Block
421 gezeigt. Wie im Block 422 gezeigt wird, wird die
Quellenadresse des Pakets in der Stoppliste für den bestimmten
Brückenbaum-Identifizierer eingesetzt, wenn die Adresse
nicht bereits vorhanden ist. Wie mit dem Entscheidungsblock
423 angegeben wird, wird, wenn das Gateway nicht den
bestimmten Brückenbaum bearbeitet, der in dem Paket gefunden
wird, das Paket gestoppt. Zudem, wie im Entscheidungsblock
425 gezeigt wird, wird dann, wenn der Zielort des Pakets
in der Stoppliste für den Brückenbaum gefunden wird, das
Paket ebenfalls gestoppt. Ansonsten wird das Paket durch
das Gateway übertragen, wie beim Block 426 angegeben wird.
Bei der Zieleinrichtung wird das Pakte detektiert und ein
Anerkennungspaket wird im allgemeinen an die
Quelleneinrichtung zurückgegeben, wie es durch den Block 431 gezeigt
wird. Das Rückkehrpaket braucht nicht notwendigerweise den
gleichen Brückenbaum wie das Originalpaket zu durchlaufen,
aber aus Wirksamkeitsgründen sollte es den gleichen Baum
durchlaufen, wenn er gangbar ist.
-
In jedem System, aber insbesondere in einem großen System,
wenn ein neuer Host angebunden wird, können Nachrichten
für den Host von einem LAN das System überfluten, bis das
System den Ort des neuen Hosts gelernt hat. Um diesen Punkt
zu erläutern, der einen weiteren Aspekt der vorliegenden
Erfindung betrifft, werden der rechte Abschnitt der Fig.
2, nämlich die Netzwerke 303, 306, und 307 (N&sub3;, N&sub6; und N&sub7;)
die Gateways 337 und 373 (G&sub3;&sub7; und G&sub7;&sub3;) und die Hosts 384
(D) und 385(E) betrachtet. Es wird angenommen, daß der Host
384 angebunden ist und daß es ein Paket PED gibt, daß das
Netzwerk 307 durchläuft. Da das Gateway G&sub7;&sub3; den Host 384
noch nicht gelernt hat, d. h. der Stoppfilter hat den Host
D nicht in seiner Liste, würde normalerweise das Paket das
System überfluten. Wenn jedoch das Gateway G&sub7;&sub3; das
Wiederholen des Paktes PED für eine gewisse Zeitdauer (TD)
verzögert, die größer ist als die durchschnittliche
Bestätigungsantwortzeit des Hosts 384, dann fügt das Gateway G&sub7;&sub3; dem
Host 384 seine Stoppliste (D&sub7;&sub3; = {E, D, . . .}) hinzu. Auf
die erneute Betrachtung des Pakets PED durch das Gateway
G&sub7;&sub3; hin, wird eine erneute Übertragung zum Netzwerk 303
(N&sub3;) aber auch das Durchlaufen dieses Pakets durch das
System vermieden. Dies ist eine besonders wichtige
Eigenschaft, wenn der Host 384 generalisiert wird, so daß er
Irgendeine Kommunikationseinrichtung beschreibt, wie z. B.
ein Telefongerät oder ein Datengerät, und die Netzwerke
306, 307, . . . lokale Schaltnetzwerke sind.
-
Dieses Verzögerung-bevor-Senden-Protokoll kann auch mit
dem Brückenbaumprotokoll kombiniert werden, um eine weitere
Eigenschaft der vorliegenden Erfindung zu erzeugen. Mit
Bezug auf die Fig. 11 würde ein Speicher- und
-Verzögegerungs-Block, gefolgt von einem weiteren
Entscheidungsblock, zwischen den Blöcken 425 und 426 eingefügt werden.
Nach einer vorgegebenen Verzögerung in dem ersten neuen
Block würde der neue Entscheidungsblock nach der gleichen
Bedingung testen wie der Block 425. Wenn die Zieladresse
nun in der Stoppliste ist, wird das Paket gestoppt;
ansonsten wird das Paket vom Block 426 verarbeitet.
-
Eine weitere Eigenschaft der vorliegenden Erfindung zum
weiteren Reduzieren des Netzwerküberlastens und zum Reduzieren
von Verzögerungen besteht darin, daß die Gatewaypaare so
ausgelegt werden können, daß sie ihre Stopplisten
untereinander austauschen können. Dann, wenn der Host D in der
Stoppliste des Gateways G&sub3;&sub7; aufgeführt wird, was anzeigt,
daß der Host D nicht auf dem Netzwerk 307 (D&sub3;&sub7; {..., D,
...}) ist, sollte PED sofort wiederholt werden. Der
komplette Algorithmus für das Gatewaypaar G&sub7;&sub3; und G&sub3;&sub7; für das
Paket PED, der die Kommunikation und die Verzögerung
kombiniert, ist gegeben durch:
-
1. Wenn D in D&sub7;&sub3; enthalten ist, wird das Paket PED nicht
wiederholt;
-
2. Wenn D in D&sub3;&sub7; enthalten ist, wird das Paket PED N&sub3;;
-
3. Wenn D nicht in D&sub3;&sub7; enthalten ist und D nicht in D&sub7;&sub3;
enthalten ist, wird das Paket PED verzögert oder in G&sub7;&sub3;
für eine Zeit TD gespeichert, und dann wieder gesendet.
-
Für ein Gatewaypaar, das eine Zeitverzögerung aufweist,
kann der Block 425 der Fig. 11 erweitert werden, um einen
Test auszuführen, um zu entscheiden, ob die Zieleinrichtung
in der Stoppliste für den Baum in der umgekehrten
Fortpflanzungsrichtung ist, und zwar immer dann, wenn der Test in
der Vorwärtsrichtung erfolglos ist. Wenn dieser zusätzliche
Test erfolgreich ist, wird das Paket auf dem zugeordneten
Brückenbaum übertragen. Wenn der Test nicht erfolgreich
ist, wird das Paket für ein vorausgewähltes Intervall
gespeichert und dann dem Block 425 für eine abschließende
Disposition zugeführt.
-
Es wird darauf hingewiesen, daß die beschriebenen Verfahren
und zugeordneten Anordnungen nicht auf die hier
beschriebenen speziellen Ausführungsformen begrenzt sind, sondern
andere Ausführungsformen angenommen werden können, die nur
durch den Bereich der anhängenden Ansprüche begrenzt sind.