DE69716451T2

DE69716451T2 - Lastverteilung für redundante netze

Info

Publication number: DE69716451T2
Application number: DE69716451T
Authority: DE
Inventors: W. Carr; A. Edmondson; J. Fee
Original assignee: Cabletron Systems Inc
Current assignee: Cabletron Systems Inc
Priority date: 1996-08-14
Filing date: 1997-08-14
Publication date: 2003-06-12
Anticipated expiration: 2017-08-15
Also published as: EP0929955A1; CA2262590C; US6081511A; CA2262590A1; AU4150897A; EP0929955B1; AU708914B2; WO1998007259A1; DE69716451D1

Description

Erfindungsgebiet

Die vorliegende Erfindung betrifft Kommunikationsnetze und insbesondere eine Vorrichtung und ein Verfahren zur Lastteilung unter redundanten Verbindungsstrecken in einem Kommunikationsnetz.

Hintergrund der Erfindung

Mit der Realisation der wirtschaftlichen Vorteile für Geschäfte, teure Rechnerressourcen zu teilen, haben sich Verkabelungssysteme (einschließlich drahtlose Verkabelungssysteme) stark vermehrt, um das Teilen dieser Ressourcen über ein Rechnernetz zu ermöglichen. Ein Netz, das diese Kommunikation erlaubt, kann als Ortsnetz oder "LAN" (local area network) bezeichnet werden. LAN bezieht sich auf ein Verbund-Datennetz, das gewöhnlich auf ein geographisches Gebiet bescheidener Größe beschränkt ist, wie beispielsweise ein einzelnes Bürogebäude oder ein Hochschulgelände. Größere Netze werden häufig als Weitverkehrsnetze oder "WAN" (wide area networks) bezeichnet.
Netze lassen sich unter Verwendung verschiedener Verbindungselemente wie beispielsweise Kabeln mit einer unabgeschirmten verdrillten Doppelleitung, Kabeln mit einer abgeschirmten verdrillten Doppelleitung, Koaxialkabel, Glasfaserkabel oder sogar drahtlosen Verbindungselementen bilden. Die Konfiguration dieser Verkabelungselemente und der Schnittstellen für das Kommunikationsmittel kann einer (oder mehreren) von vielen Topologien folgen, wie beispielsweise Stern, Ring oder Bus. Darüber hinaus hat sich eine Anzahl unterschiedlicher Protokolle zum Zugreifen auf das Vernetzungsmittel entwickelt. Beispielsweise ist vom Institute of Electrical and Electronics Engineers, IEEE, eine Anzahl von Standards für Netze entwickelt worden, einschließlich des auf Ethernet-Busse bezogenen IEEE 802.3 mit Vielfachzugriff mit Trägerkennung und Kollisionserkennung, des auf Token-Busse bezogenen IEEE 802.4 mit Tokenübetgabe und des auf Token-Ring-Netze bezogenen IEEE 802.5 mit Tokenübergabe. Von ANSI ist auch ein Standard für Datenanschluß mit Signalverteilung über Glasfaser (FDDI - fiber distributed data interface) mit Mehrfach-Tokenübergabe entwickelt worden.
Mit zunehmendem Bedarf sind die Netze immer größer geworden. Irgendwann wird durch die Anzahl von Stationen an einem Netz die verfügbare Bandbreite für dieses Netz aufgebraucht oder die durch das verwendete physikalische Medium auferlegten Grenzen erreicht. Es sind infolgedessen Verfahren zum Verbinden von zwei getrennten Netzen entwickelt worden. Bei einem dieser Verfahren wird ein Koppelelement bzw. eine Brücke benutzt.
Im allgemeinen bezieht sich "Brücke" auf eine Verbindungsstrecke zwischen (mindestens) zwei Netzen. Wenn daher eine Brücke Informationen von einem Netz empfängt, kann sie diese Informationen zum zweiten Netz weiterleiten. Auf diese Weise kann erreicht werden, daß zwei getrennte Netze als ein größeres Netz fungieren.
Brücken können für verschiedene Zwecke benutzt werden. Sie können dazu benutzt werden, ein Netz über die physikalischen Begrenzungen einzelner Netze hinaus zu erweitern. Sie können dazu benutzt werden, Bandbreite einzelnen Netzen zuzuteilen, um Verkehr innerhalb einzelner Netze abzutrennen und damit die insgesamt verfügbare Bandbreite zu steigern. Auch können Brücken zum Abtrennen von Netzen für Sicherheitszwecke benutzt werden.
Fig. 1 zeigt ein Beispiel der Zusammenschaltung von Netzen. Mit der Wolke NW1 wird ein erstes Netz dargestellt. In der Figur befindet sich eine erste Endstelle ES1 innerhalb der Netzwolke NW1. Eine zweite Netzwolke NW2 ist ebenfalls dargestellt und innerhalb dieses Netzes NW2 befindet sich eine zweite Endstelle ES2. Auf ähnliche Weise ist ein drittes Netz NW3 dargestellt, in dem sich eine dritte Endstelle ES3 befindet.
Die drei Netze NW1, NW2, NW3 sind durch Koppelplatinen A, B und C zusammengeschaltet. Koppelplatine A enthält vier Anschlüsse A0, A1, A2 und A3. Die Koppelplatine B enthält drei Anschlüsse B0, B1 und B2. Die Koppelplatine C enthält zwei Anschlüsse C0 und C1. Jeder Anschluß weist einen zugehörigen Kommunikationskanal bzw. "Link" (Verbindungsstrecke) auf. Beispielsweise besitzt der Anschluß A1 einen Kommunikationskanal A-B1 mit Anschluß B0 der Koppelplatine B.
Eine Brücke ist ein Kommunikationsweg zwischen zwei Netzen. So definieren die Kommunikationsstrecken A-NW1, A-B1 und B-NW2, die die Koppelplatine A an Anschlüssen A0 und A1 und die Koppelplatine B an Anschlüssen B0 und B2 durchlaufen, eine Brücke zwischen NW1 und NW2. Der Kürze halber wird jedoch die Verbindungsstrecke A-B1 manchmal als die Brücke bezeichnet.
Brücken sind in der Technik wohlbekannt und sind der Gegenstand eines durch das IEEE verbreiteten Standards IEEE 802.1 bezüglich transparenter oder selbstlernender Brücken. Eine nützliche Hintergrundbesprechung von Brücken ist aus Radia Perlman, "Interconnections: Bridges and Routers" (Zusammenschaltungen: Brücken und Router), Addison Wellesley Professional Computing Series, Reading, MA 1992 ersichtlich. Um das Verständnis der vorliegenden Erfindung zu fördern, folgt eine Besprechung transparenter Brücken. Mit .dieser Besprechung ist nicht beabsichtigt, den Umfang oder die Anwendungsmöglichkeiten der vorliegenden Erfindung und Ansprüche zu begrenzen.
Eine mögliche Strategie zum Zusammenschalten von zwei Netzen mit einer Koppelplatine wäre, daß die Koppelplatine alle Kommunikationen (hier als "Pakete" oder "Datenpakete" bezeichnet, wobei beide Begriffe klassische Datenpakete und alle funktionellen Entsprechungen umfassen sollen, ganz gleich, ob sie in der Technik als "Zellen", "Datagramme" oder dergleichen bezeichnet werden) an alle anderen mit dieser Platine verbundenen Netze weiterleitet. Jedes Mal, wenn beispielsweise eine Kommunikation von der Endstelle ES1 empfangen wird, würde diese Kommunikation sowohl zum Netz NW2 als auch dem Netz NW3 weitergeleitet werden, ungeachtet dessen, wer der Empfänger sein soll. Auf diese Weise würde die Brücke dazu dienen, die Netze so zu kombinieren, als wären sie wirklich nur ein Netz. Leider würde durch die Verdopplung jeder auf einem Netz gesendeten Nachricht die verfügbare Bandbreite in jedem der Netze schnell verstopft werden.
Um dieses Problem anzugehen, wäre es möglich, jede Koppelplatine mit dem Ort jeder Station an jedem Netz zu programmieren. Auf diese Weise könnte jede Kommunikation zum richtigen Netz geleitet werden. Obwohl dies eine durchführbare Möglichkeit darstellt, erfordert es zusätzliche Hardware auf jeder Koppelplatine und zusätzlichen Systemaufwand.
Eine Alternative besteht darin, daß jede Koppelplatine den Verkehr über die Platine beobachtet, um bei der Durchführung von Kommunikationen über das Netz den Ort jeder Endstelle zu lernen. Auf diese Weise könnten Brücken einfach in Netze eingesteckt und allein gelassen werden, um die richtigen herzustellenden Verbindungen zu lernen. Diese Brückenart wird häufig als "transparente" Brücke oder "selbstlernende" Brücke bezeichnet.
Fig. 2A zeigt den Informationsfluß, wenn ein Datenpaket von der Endstelle ES1 zur Endstelle ES2 gesendet wird.
Jedes Informationspaket enthält eine eindeutige Kennzeichnung, die die Ursprungsstelle und die Zielstelle für das Paket anzeigt. Im vorliegenden Beispiel wäre die Ursprungsadresse eine eindeutige Adresse (wie beispielsweise eine MAC-(media access control)Adresse) für ES1 und die Zieladresse ist eine eindeutige Kennzeichnung für ES2.
In dem Beispiel der Fig. 2A empfängt die Platine A zuerst das Paket vom Netz NW1 am Anschluß A0. Aus diesem Paket lernt die Platine A, daß sich die Endstelle ES1 vor dem Anschluß A0 befindet, aufgrund der Tatsache, daß die am Anschluß A0 empfangene Ursprungsadresse ES1 entspricht. Die Platine A kann dann diese Informationen in einer Tabelle speichern. Bei manchen Ausführungsformen kann diese Tabelle als BAF-Tabelle, Brücken-ASIC-Filter-Tabelle oder Brücken- Adressenfilter-Tabelle bezeichnet werden. Obwohl sie hier als BAF-Tabelle bezeichnet wird, soll dies nicht auf irgendeine Weise als begrenzend aufgefaßt werden. Die Tabelle wird zum Nachschlagen der Zieladresse von Paketen bei ihrer Ankunft benutzt und, wenn der Ort der Zieladresse der Tabelle "bekannt" ist, zum Weiterleiten des Pakets nur zu dem Anschluß, der dem bekannten Weg zu diesem Ziel entspricht. Die Implementierungseinzelheiten und die Art und Weise, auf die die Informationen gespeichert werden, können unterschiedlich sein und sind für die vorliegende Erfindung nicht von wesentlicher Bedeutung.
Im Beispiel der Fig. 2A würde dass Paket eine Zieladresse ("DA" - destination address) entsprechend ES2 anzeigen. Bezug nehmend auf die BAF-Tabelle für die Platine A, ABAF ist ES2 eine "unbekannte" Verbindung, das heißt, diese Platine weiß nicht, welcher Anschluß zur Weiterleitung von Kommunikationen zu ES2 zu benutzen ist. Dementsprechend leitet die Platine A das Paket an jeden ihrer Anschlüsse außer dem Anschluß, an dem das Paket empfangen wurde, weiter (man nehme vorerst an, daß die Verbindungsstrecke A-32 nicht angeschlossen ist). So wird das Paket zur Koppelplatine B und Koppelplatine C weitergeleitet. Wie in Fig. 2A angezeigt aktualisiert die jeweilige Koppelplatine B und Koppelplatine C eine mit der Koppelplatine verbundene BAF-Tabelle, BBAF bzw. CBAF, und leitet das Paket zu ihrem einzigen anderen Anschluß weiter. Die Koppelplatine B leitet infolgedessen das Paket zum Netz NW2 weiter und das Paket wird schließlich durch die Endstelle ES2 empfangen.
In Fig. 2B ist dargestellt, was geschieht, wenn die Endstelle ES3 dann ein Kommunikationspaket zur Endstelle ES1 sendet. Das Paket wird zuerst durch die Koppelplatine C empfangen, die ihre BAF-Tabelle CBAF, wie in Fig. 2B angezeigt, aktualisiert. Danach wird das Paket über den Anschluß C0 zur Koppelplatine A weitergeleitet. Im vorliegenden Beispiel überprüft die Koppelplatine A die Zieladresse für das Paket (die der Endstelle ES1 entspricht) und stellt fest, daß die Verbindung zu ES1 eine bekannte Verbindung ist. Die Koppelplatine A leitet das Paket dementsprechend nur zum Anschluß A0 weiter. Natürlich aktualisiert die Koppelplatine A auch ihre BAF-Tabelle ABAF, um wiederzugeben, daß die Koppelplatine A nunmehr weiß, daß die Endstelle ES3 vor ihrem Anschluß A3 liegt.
In vielen Fällen ist es wünschenswert, eine zusätzliche Verbindung zwischen Netzen hinzuzufügen. In dem in Fig. 1 gezeigten Beispiel könnte eine Verbindungsstrecke A-B2 hinzugefügt werden. Dieser würde einen Kommunikationsweg bilden, der mit einem bereits gezeigten Kommunikationsweg (der durch die Verbindungsstrecke A-B1 läuft) redundant ist. Wie unten erläutert, würde dies jedoch bei Verwendung der bislang erläuterten Koppelanordnung zu bedeutenden Problemen führen.
Wiederum auf Fig. 2A Bezug nehmend, wo die Endstelle ES1 ein Kommunikationspaket zur Endstelle ES3 sendet, wird das Paket zuerst von der Koppelplatine A am Anschluß A0 empfangen. Da die der Endstelle ES3 entsprechende Zieladresse der BAF-Tabelle ABAF der Koppelplatine A unbekannt ist, würde die Koppelplatine A das Paket zu jedem der anderen Anschlüsse - Anschlüsse A1, A2 und A3 - weiterleiten. Wenn das Paket an der Koppelplatine B über Anschluß B0 empfangen wird, weist das Paket wiederum eine der Koppelplatine B in ihrer BAF-Tabelle BBAF unbekannte Zieladresse auf. Die Koppelplatine 8 würde dementsprechend das Paket zu ihren beiden anderen Anschlüssen B1 und B2 weiterleiten. Auf ähnliche Weise leitet die Koppelplatine B, wenn sie das Paket über den Anschluß B1 empfängt, das Paket auch an Anschlüsse B2 und B0 weiter. Das Paket würde infolgedessen unangemessen multipliziert werden und übermäßige Bandbreite verbrauchen.
Um dieses Problem anzugehen wurde ein Verfahren des aufspannenden Baums entwickelt, um sicherzustellen, daß im Netz-Netz-Aufbau keine redundanten Verbindungs- Verbindungsstrecken vorliegen. Ein "aufspannender Baum" läßt sich als eine Menge von Verbindungen in einer Netztopologie definieren, wo es genau einen Weg in jeder Brücke (bzw. jedem "Knoten" oder "Knotenpunkt") zu jedem anderen Knoten gibt. So würde im Netz der Fig. 1 durch den Algorithmus des aufspannenden Baums sichergestellt, daß entweder die Verbindungsstrecke A-B2 oder die Verbindungsstrecke A-B1 nicht in das Netz eingebaut ist und keine Pakete über diese Verbindungsstrecke laufen. Dies geschieht beispielsweise durch "Blockieren" des Anschlusses A2 auf der Koppelplatine A und des Anschlusses B1 auf der Koppelplatine B (bzw. der Kürze halber "Blockieren" der Verbindungsstrecke A-B2).
Implementierung des Algorithmus des aufspannenden Baums ist in der Technik wohlbekannt und eine Ausführungsform bildet den Gegenstand des IEEE-Standards 802.1D. Auch wird eine nützliche Zusammenfassung des Algorithmus des aufspannenden Baums in Perlman op. cit. geboten.
Verwendung des Verfahrens des aufspannende Baums weist jedoch mehrere Nachteile auf. Beispielsweise wird die Blockierung einer verfügbaren Verbindungsstrecke in den Verlust von Bandbreite umgesetzt. So würde die Blockierung der Verbindungsstrecke A-B2 in der Fig. 1 die Informationsmenge verringern, die sonst zwischen dem Netz NW1 und dem Netz NW2 in einer gegebenen Zeitperiode fließen könnte. Zusätzlich kann die Hinzufügung oder der Verlust einer Verbindungsstrecke eine langwierige Umkonfigurierungszeit bewirken, da der Algorithmus des aufspannenden Baums aufgrund der Zustandsänderung bestehender Verbindungsstrecken versucht, einen neuen aufspannenden Baum zu konstruieren.
In US 5,018,137 ist ein Verfahren mit den Schritten des Identifizierens von mindestens einer Gruppe einer Mehrzahl von Verbindungsstrecken in einem Netz offenbart, die Teil eines redundanten Kommunikationsweges bilden, und des Weiterleitens eines Teils des Verkehrs zu dieser Gruppe. Es wird nur erkannt, ob irgendwo im Netz eine Redundanz vorliegt, die bewirkt, daß dasselbe Paket mehr als einmal ankommt. Im Fall einer derartigen Redundanz wird in US 5,018,137 ein festes Schema vorgeschlagen, nach dem jedes an einem bestimmten Anschluß empfangene Paket zur selben Verbindungsstrecke weitergeleitet würde.
Eine Aufgabe einer Ausführungsform der vorliegenden Erfindung besteht darin, Lastteilung im Zusammenhang mit redundanten Verbindungsstrecken zu erlauben, ohne zur Vermehrung und Verdopplung von über redundante Verbindungsstrecken gesendeten Paketen zu führen.
Erfindungsgemäß ist ein Verfahren zum Teilen einer Kommunikationslast in einem redundanten Kommunikationsnetz mit einer Mehrzahl von Verbindungsstrecken vorgesehen, wobei das Verfahren die folgenden Schritte umfaßt: Identifizieren von mindestens einer Gruppe einer Mehrzahl von Verbindungsstrecken im Netz, die einen Teil eines einen Anschluß an einer Brücke im Netz durchlaufenden redundanten Kommunikationsweges bilden, wobei jede Verbindungsstrecke in der Gruppe dazu ausreicht, Kommunikation im Netz ohne irgendeine der anderen Verbindungsstrecken in der Gruppe zu unterstützen; Übertragen einer Kommunikationslast über den Anschluß; und Teilen der Kommunikationslast unter den Verbindungsstrecken in der Gruppe.
In einer Ausführungsform der vorliegenden Erfindung wird ein Verfahren zum Teilen einer Kommunikationslast in einem redundanten Kommunikationsnetz bereitgestellt. Nach dem Verfahren wird mindestens eine Gruppe von Verbindungsstrecken im Netz identifiziert, die einen redundanten Kommunikationsweg bilden. Die Kommunikationslast unter diesen Verbindungsstrecken kann dann geteilt werden.
In der folgenden Beschreibung werden andere zugehörige Verfahren beschrieben, die unten allgemein zusammengefaßt sind.
Nach einem Verfahren wird ein Verfahren zum Weiterleiten eines an einer Koppelplatine empfangenen Datenpakets bereitgestellt, wobei sich die Koppelplatine in einem redundanten Netz befindet. Nach diesem Verfahren wird ein Anschluß zur Übertragung des Pakets ausgewählt. Anschlüsse mit Verbindungsstrecken, die mit einem ausgewählten Anschluß redundant sind, werden identifiziert. Das Paket wird zu dem ausgewählten Anschluß übertragen und nicht zu als redundant identifizierten Anschlüssen.
Nach einem anderen Verfahren wird ein Verfahren zum Weiterleiten eines durch eine Koppelplatine in einer redundanten Netztopologie empfangenen Datenpakets bereitgestellt. Nach dem Verfahren werden Informationen über die Topologie des Netzes gesendet und empfangen. Bei dieser Ausführungsform wird mindestens ein Anschluß der Koppelplatine identifiziert, der einer Verbindungsstrecke in einer ersten Menge von redundanten Verbindungsstrecken in der Netztopologie entspricht. Jedem identifizierten Anschluß wird ein Etikett zugewiesen. Einem empfangenen Datenpaket wird ein Vorwärtswert zugewiesen. Das Datenpaket wird nur dann zu jedem identifizierten Anschluß weitergeleitet, wenn das Etikett für diesen Anschluß dem Vorwärtswert entspricht.
Nach einem weiteren Verfahren wird ein Verfahren zum Fortführen der Kommunikation in einem Netz nach Ausfall einer ersten Verbindungsstrecke im Netz bereitgestellt. Nach diesem Verfahren wird vor dem Ausfall der ersten Verbindungsstrecke eine zweite Verbindungsstrecke im Netz, die redundant mit der ersten Verbindungsstrecke ist, identifiziert. Nach Ausfall der ersten Verbindungsstrecke wird die Kommunikationslast auf der zweiten Verbindungsstrecke gesteigert (entweder von einer Nullast oder einem bestehenden Betrag zu einem höheren Betrag).
Nach einem weiteren Verfahren ist eine selbstlernende Koppelplatine für ein Kommunikationsnetz offenbart. Die Koppelplatine enthält eine Mehrzahl von Kommunikationsanschlüssen, Mittel zum Erkennen einer Redundanz in der Netztopologie, wobei die Redundanz mindestens eine an einen der Anschlüsse dieser Koppelplatine angekoppelte Verbindungsstrecke umfaßt, und Mittel zum gezielten Weiterleiten von Datenpaketen mit einer unbekannten Zieladresse zum Anschluß der Koppelplatine, der der erkannten Redundanz entspricht.

Kurze Beschreibung der Zeichnungen

Fig. 1 zeigt ein Beispiel von drei zusammengeschalteten Netzen.
Fig. 2A zeigt einen Kommunikationsweg für ein in den zusammengeschalteten Netzen der Fig. 1 gesendetes Datenpaket.
Fig. 2B zeigt ein zweites Beispiel eines Kommunikationsweges für ein in den drei zusammengeschalteten Netzen der Fig. 1 gesendetes Datenpaket.
Fig. 3 zeigt ein Verfahren nach der vorliegenden Erfindung zum Teilen der Kommunikationslast in einem redundanten Kommunikationsnetz.
Fig. 4 zeigt eine Muster-Netztopologie mit mehreren redundanten Kommunikationswegen.
Fig. 4A zeigt eine beispielhafte wirkungsvolle Netztopologie für ein im Netz der Fig. 4 gesendetes Datenpaket.
Fig. 4B zeigt ein zweites Beispiel einer wirkungsvollen Netztopologie für ein im Netz der Fig. 4 gesendetes Datenpaket.
Fig. 5 zeigt eine Ausführungsform eines Verfahrens zum Teilen der Kommunikationslast in einem redundanten Kommunikationsnetz.
Fig. 6A zeigt ein Format für ein lastteilendes Paket.
Fig. 6B zeigt ein Beispiel einer Netztopologie und ein entsprechendes lastteilendes Paket bei dieser Topologie.
Fig. 7 zeigt eine Muster-Verbindungslisten-Datenstruktur.
Fig. 8 zeigt eine Ausführungsform eines Verfahrens zur Verarbeitung eines lastteilenden Pakets.
Fig. 9 zeigt ein Verfahren zur Rücksende einer Lastteilungsinstanzzählung und einer Lastteilungsinstanzliste.
Fig. 10 zeigt ein Verfahren zum Aufbauen einer Ordnungslistendatenstruktur, einer Knotenpunktlistendatenstruktur und zum Bestimmen einer Kantenzählung für eine Netztopologie.
Fig. 11A zeigt eine Muster-Netztopologie, die mehrere redundante Kommunikationswege enthält.
Fig. 11B zeigt eine Muster-Verbindungslistendatenstruktur für die Netztopologie der Fig. 11A.
Fig. 11C zeigt eine Muster-Netzlistendatenstruktur für die Netztopologie der Fig. 11A.
Fig. 11D zeigt eine Muster-Ordnungslistendatenstruktur für die Netztopologie der Fig. 11A.
Fig. 11E zeigt eine Muster-Knotenpunktlistendatenstruktur für die Netztopologie der Fig. 11A.
Fig. 12 zeigt ein Verfahren zum Verarbeiten von Lastteilungsinstanzen, wenn es möglicherweise mehr als eine Lastteilungsinstanz gibt.
Fig. 13 zeigt ein Verfahren zum Feststellen einer Lastteilungszählung für eine gegebene Knotenpunktliste.
Fig. 14 zeigt ein Verfahren zum Zuweisen von Vorwärtsmasken zu den Anschlüssen einer Koppelplatine.
Fig. 15A zeigt ein Beispiel von für die Netztopologie der Fig. 11A berechneten Lastteilungsinstanzen.
Fig. 15B zeigt eine erste wirkungsvolle Netztopologie für ein Datenpaket bei gegebenen Lastteilungsinstanzen und Vorwärtsmaskenzuweisungen der Fig. 15A.
Fig. 15C zeigt eine zweite wirkungsvolle Netztopologie bei gegebenen Lastteilungsinstanzen und Vorwärtsmasken der Fig. 15A.
Fig. 15D zeigt ein drittes Beispiel einer wirkungsvollen Netztopologie für die in Fig. 15A gezeigten Lastteilungsinstanzen und Vorwärtsmasken.
Fig. 16 zeigt ein Verfahren zum gezielten Bestimmen, an welche Anschlüsse einer Koppelplatine ein Datenpaket weiterzuleiten ist.
Fig. 17 zeigt eine Ausführungsform einer Koppelplatine nach der vorliegenden Erfindung.

Ausführliche Beschreibung

Durch die vorliegende Erfindung wird der Begriff der Lastteilung für redundante Verbindungsstrecken in einem Netz eingeführt. In Fig. 3 ist die Art und Weise dargestellt, auf die eine Koppelplatine Pakete gemäß einer Ausführungsform der vorliegenden Erfindung verarbeiten würde.
In der Fig. 3 beginnt die Verarbeitung mit einem Schritt 31, wenn eine Koppelplatine ein Paket an einem Anschluß empfängt. In einem Schritt 32 wird eine Bestimmung getroffen, ob die Koppelplatine den richtigen Weiterleitungsanschluß für die Zieladresse des Pakets kennt; d. h. ob dieses Paket für eine bekannte Verbindung bestimmt ist. Dies kann, wie unter Bezugnahme auf Fig. 2 erläutert, durch Zurateziehen einer BAF-Tabelle oder durch sonstige geeignete Mittel geschehen. Wenn der richtige Weiterleitungsanschluß bekannt (d. h. eine bekannte Zieladresse) ist, wird das Paket wie im Schritt 33 gezeigt nur an diesen Anschluß weitergeleitet. Wenn die Zieladresse nicht bekannt ist, tritt die Koppelplatine in eine Schleife 34 bis 37 ein, um das Paket an alle zutreffenden Ausgangsanschlüsse zu senden.
Die Schleife beginnt in einem Schritt 34, wo bestimmt wird, ob das Paket an alle zutreffenden Ausgangsanschlüsse gesendet worden ist. Wenn ja, dann ist die Verarbeitung für dieses Paket abgeschlossen und die Koppelplatine wartet auf den Empfang eines neuen Pakets zur Verarbeitung. Wenn nicht, dann kann die Koppelplatine einen Anschluß in einem Schritt 35 auswählen. In einem Schritt 36 würde die Koppelplatine dann alle redundanten Verbindungsstrecken für den gegebenen Anschluß identifizieren. Sobald die redundanten Verbindungsstrecken identifiziert worden sind, wählt die Koppelplatine in einem Schritt 37 nur eine der redundanten Verbindungsstrecken aus, auf der das Paket weiterzuleiten ist.
Wiederum Bezug nehmend auf Fig. 2A, und das Beispiel des Sendens eines Pakets zur Endstelle ES3 von der Endstelle ES1, und angenommen, daß die Verbindungsstrecke A-B2 ein Teil des Netzes ist, würde die Koppelplatine A ein Paket von der Endstelle ES1 empfangen, das zur Endstelle ES3 übertragen wird. Da die Endstelle ES3 keine bekannte Zieladresse ist, würde die Koppelplatine A in die Schleifenschritte 34 bis 37 eintreten. Da das Paket am Anschluß A0 empfangen wurde, wird das Paket nicht wieder am Anschluß A0 übertragen. Die Koppelplatine A kann dann im Schritt 35 den Anschluß A1 auswählen. Im Schritt 36 würde die Koppelplatine A feststellen, daß Verbindungsstrecke A- B1 und A-B2 redundante Verbindungsstrecken sind. Demnach würde die Koppelplatine A im Schritt 37 das Paket an einem der Anschlüsse A1 und A2 aber nicht am anderen übertragen. Die Koppelplatine A würde weiterhin im Schritt 34 beobachten, daß nicht alle Ausgangsanschlüsse abgedeckt worden sind. Im Schritt 35 würde die Koppelplatine A den Anschluß A3 auswählen. Da es keine redundanten Verbindungsstrecken gibt (Schritt 36), würde die Koppelplatine A das Paket im Schritt 37 zum Anschluß A3 weiterleiten.
Zum Implementieren des Verfahrens der Fig. 3 muß ein Mechanismus zum Identifizieren redundanter Verbindungsstrecken und zum Auswählen einer der redundanten Verbindungsstrecken für ein gegebenes Datenpaket bereitgestellt werden. Wie im Verfahren der Fig. 3 gezeigt, kann dies zum Zeitpunkt der Weiterleitung eines Pakets geschehen. Eine Alternative besteht in der Auflösung der Kennzeichnung redundanter Verbindungsstrecken und Art und Weise der Auswahl einer redundanten Verbindungsstrecke vor dem Empfangen und der Weiterleitung von Paketen, was das Verfahren einer ausführlicher unten beschriebenen bevorzugten Ausführungsform ist.
In beiden Fällen kann jedoch die Identifizierung redundanter Verbindungsstrecken aus zumindest zwei Gründen kompliziert werden. Als erstes kann die Netztopologie (und insbesondere die Zusammenschaltungen zwischen Koppelplatinen) kompliziert werden. Als zweites sollten die Brücken in einer bevorzugten Ausführungsform redundante Verbindungsstrecken selbsttätig identifizieren können - das heißt ohne Notwendigkeit der Koordinierung des Zusammenkoppelns von Netzen durch eine zentrale Steuerung.
Fig. 4 bietet ein Beispiel dafür, wie die Auswahl redundanter Verbindungsstrecken kompliziert werden kann. Man betrachte ein Paket mit einer unbekannten Zieladresse, das über die Verbindungsstrecke 41 an der Koppelplatine BA empfangen wird. Da die Zieladresse unbekannt ist, muß dieses Paket zu jeder der Koppelplatinen BB, BC, BD und BE gesendet werden. Wie leicht zu beobachten ist, gibt es viele mögliche Kombinationen von Verbindungsstrecken, die ein Paket durchlaufen könnte, um die Koppelplatine BE zu erreichen. Beispielsweise könnte das Paket die Verbindungsstrecken A-C, C-D und B-E durchlaufen. Als Alternative könnte das Paket die Verbindungsstrecken A- D, B-D und B-E durchlaufen. Zusammengefaßt ist die Auswahl davon, welche Verbindungsstrecke mit einer anderen Verbindungsstrecke redundant ist, unter Umständen nicht für jede Netztopologie einfach.
Das Problem kann unter Verwendung der Ideen von lastteilenden Mengen oder Instanzen und Vorwärtsmasken angegangen werden. Eine lastteilende Menge ist eine Menge von Verbindungsstrecken, die redundante Wege innerhalb eines Netzes darstellen.
Wiederum Bezug nehmend auf Fig. 4 könnten die Verbindungsstrecken A-C und A-D eine lastteilende Menge und die Verbindungsstrecken B-C, B-D und B-E eine zweite lastteilende Menge darstellen. Wie zu beobachten ist, bestehen keine redundanten Wege, wenn nur eine Verbindungsstrecke pro lastteilende Menge im Netz vorhanden ist (zusammen mit jeder der anderen Verbindungsstrecken im Netz). Fig. 4A und 4B zeigen zwei Beispiele des Netzes der Fig. 4, wobei aus jeder der obigen zwei lastteilenden Instanzen nur eine Verbindungsstrecke vorliegt. Da keine redundanten Wege verbleiben, besteht kein Erfordernis, irgendwelche anderen lastteilenden Mengen zu identifizieren. Das heißt, wenn nur eine Verbindungsstrecke aus jeder lastteilenden Instanz benutzt wird, gibt es keine Schleifen oder redundanten Kommunikationswege im Netz. Natürlich hätte für lastteilende Mengen eine Anzahl anderer Möglichkeiten ausgewählt werden können. Es ist in der Tat auch möglich, während der Durchführung von Lastteilung (d. h. Bestimmung von lastteilenden Instanzen oder Mengen) auf anderen Verbindungsstrecken einige Verbindungsstrecken zu "blockieren".
So werden durch die Auswahl lastteilender Instanzen redundante Kommunikationswege identifiziert. Ein Mechanismus zum Auswählen einer bestimmten einer redundanten Menge von Kommunikationsstrecken kann nunmehr beschrieben werden. Dies kann unter Verwendung der Idee von Vorwärtsmasken durchgeführt werden. Eine Vorwärtsmaske ist ein einmaliges Etikett, das einer Verbindungsstrecke in einer lastteilenden Instanz zugewiesen ist.
Wiederum Bezug nehmend auf Fig. 4 und unter Verwendung der oben identifizierten lastteilenden Instanzen {A-C, A-D} und {B-C, B-D, B-E} kann der Verbindungsstrecke B- C eine Vorwärtsmaske "X", der Verbindungsstrecke B-D eine Vorwärtsmaske "Y" und der Verbindungsstrecke B-E eine Vorwärtsmaske "Z" zugewiesen werden. Diese drei Verbindungsstrecken bilden eine lastteilende Instanz und jede weist eine einmalige Vorwärtsmaske auf. Auf ähnliche Weise kann der Verbindungsstrecke A-C eine lastteilende Maske 0 und der Verbindungsstrecke A-D eine Vorwärtsmaske 1 zugewiesen werden. Natürlich hätten anstelle von X, Y und Z 0, 1 und 2 benutzt werden können - das Erfordernis besteht darin, daß die Weiterleitungsmaske einmalig sei, nur innerhalb der lastteilenden Instanz.
Definieren eines Kommunikationsnetzes nach der Zuweisung von Vorwärtsmasken kann wie folgt erreicht werden. Wie oben unter Bezugnahme auf Fig. 2A erläutert, muß das Netz für zu einer unbekannten Zieladresse gesendete Pakete effektiv als ein aufspannender Baum aufgebaut werden. Weiterhin muß wie oben beschrieben bei Empfang eines Datenpakets dieses nur mit genau einer einmaligen Vorwärtsmaske aus jeder lastteilenden Instanz identifiziert werden und zu dieser weitergeleitet werden.
Die Idee der Vorwärtsmasken kann mit den in Fig. 4A und 4B gezeigten Beispielen aufgezeigt werden. In der Fig. 4A ist ein Datenpaket mit einer unbekannten Zieladresse mit der Vorwärtsmaske 1 Einer ersten lastteilenden Instanz und der Vorwärtsmaske X einer zweiten lastteilenden Instanz assoziiert. Da Verbindungsstrecken 1 und X ausgewählt worden sind, sind Verbindungsstrecken 0(A-C), Y(B-D) und Z(B-E) effektiv aus der Netztopologie entfernt (was dieses Datenpaket anbetrifft). Demnach würde die effektive Netztopologie für dieses Datenpaket der Darstellung in Fig. 4A entsprechen. Wie ersichtlich ist, ist die effektive Netztopologie eine ohne Schleifen, d. h. ein aufspannender Baum der fünf Koppelplatinen. Auf ähnliche Weise ist in Fig. 4B eine Vorwärtsmaske 0 für die erste lastteilende Instanz ausgewählt und eine Vorwärtsmaske Y für die zweite lastteilende Instanz ausgewählt. Wie ersichtlich ist, sind die Netzverbindungen unterschiedlich. Trotzdem ist die neue effektive Topologie immer noch ein aufspannender Baum.
Die Fig. 5 zeigt daher eine Ausführungsform der vorliegenden Erfindung zum Verteilen der Datenkommunikation über redundante Verbindungsstrecken in einem Netz. In einem Schritt 51 werden lastteilende Instanzen für das Netz identifiziert. In einem Schritt 53 wird jeder Verbindungsstrecke eine einmalige Vorwärtsmaske für jede lastteilende Instanz zugewiesen. In einem Schritt 55 wird bei Empfang eines Datenpakets mit unbekannter Zieladresse für jede lastteilende Instanz genau eine Vorwärtsmaske ausgewählt. Auf diese Weise, und wie in Verbindung mit Fig. 4, 4A und 4B erläutert, wird jedes Datenpaket über eine Topologie eines aufspannenden Baums rundgesendet, und die unerwünschten Auswirkungen der Paketverdopplung werden vermieden.
In einer bevorzugten Ausführungsform geschieht die Bestimmung der lastteilenden Instanzen und Zuweisung von Vorwärtsmasken auf verteilter Grundlage, d. h. jede Koppelplatine bestimmt selbst, an welchen lastteilenden Instanzen sie teilnimmt und was die Vorwärtsmaskenzuweisung für jeden der Anschlüsse der Platine sein wird (d. h. der den Verbindungsstrecken in der lastteilenden Menge entsprechenden Anschlüsse). Natürlich ist bevorzugt, daß jede Koppelplatine zu demselben Schluß kommt.
Die Bestimmung von lastteilenden Instanzen und Vorwärtsmasken kann auf verteilter Grundlage stattfinden, um die Notwendigkeit eines zentralen Managers und die bei Benutzung eines zentralen Managers aufkommenden, damit verbundenen Kosten und Aufwendungen zu vermeiden. Damit jede Koppelplatine eine Bestimmung über lastteilende Instanzen durchführt, muß die Koppelplatine Informationen hinsichtlich der Netztopologie an andere Koppelplatinen im Netz senden und von diesen empfangen.
In einer bevorzugten Ausführungsform werden zwischen Koppelplatinen nur Informationen betreffs der der Koppelplatine direkt benachbarten Koppelplatinen und der einen Schritt weiter liegenden ausgetauscht. So würde in dem in Fig. 4 dargestellten Netz die Koppelplatine BA Informationen über die Verbindungen der Koppelplatine BC (einschließlich der Verbindungsstrecke C-D) aber nicht der Koppelplatine B- E empfangen. Dadurch wird die Implementierung der Lastteilungsmethodik rationalisiert, mit dem möglichen Nachteil, daß nicht alle Schleifen in einer großen Netztopologie identifiziert werden können. Der Fachmann könnte natürlich ohne weiteres auf Grundlage der hier gebotenen Offenbarung Konstruktionen zum Einsammeln von mehr Informationen ausarbeiten.
Fig. 6A zeigt das Format eines Pakets, das zum Übermitteln von Informationen betreffs Netztopologie zwischen Koppelplatinen benutzt werden kann. Das Paketformat 60 enthält Felder 51a bis 61f. Das Feld 61a zeigt eine Formatart für das Paket an, wodurch es als ein Lastteilungsinformationspaket identifiziert wird. Das Feld 61b enthält Fehlererkennungsinformationen zur Unterstützung der Bestimmung, ob während der Paketübermittlung Fehler eingeführt wurden. Das Feld 61c ist eine MAC-(media access control)Adresse. Das Feld 61d kennzeichnet den Anschluß, auf dem das Paket übertragen wurde. Das Feld 61e gibt den Anschluß an, an dem ein Paket empfangen wurde. Das Feld 61f schließlich kennzeichnet die mit der Verbindungsstrecke zwischen dem Sendeanschluß (61d) und dem Empfangsanschluß (61e) verbundene Verbindungsart. Die Verbindungsart kennzeichnet, ob die bestimmte Verbindungsstrecke zur Lastteilung verfügbar ist. Wenn das Verbindungsart-Byte beispielsweise einen Wert 1 aufweist, wird die Verbindungsstrecke als "Netz"-Verbindungsstrecke identifiziert und steht zur Lastteilung zur Verfügung. Wenn der Wert des Verbindungsart-Bytes 2 ist, wird die zutreffende Verbindungsstrecke als eine "Nutz"- Verbindungsstrecke gekennzeichnet und verhindert, daß diese Verbindungsstrecke in einer lastteilenden Instanz enthalten ist. So kann ein Systembediener Lastteilung gezielt für einzelne, von einer Platine abgehende Verbindungsstrecken freigeben oder sperren. (In einer bevorzugten Ausführungsform kann der Systembediener auch die Lastteilung gezielt für eine gesamte Platine freigeben oder sperren).
In einer bevorzugten Ausführungsform werden Rückwandbusse in einem Netz stets als Nutzverbindungen gekennzeichnet. Dies geschieht deshalb, weil die Rückwand nicht für gezielte Lastteilung genutzt werden kann - die Rückwand überträgt Informationen an alle Platinen in dem zutreffenden Einschub. Aus ähnlichen Gründen sollten zwei Platinen (A und B) in einem Einschub nicht miteinander verbunden werden. Kommunikationen zu anderen Platinen im selben Einschub finden über die Rückwand statt - was bedeutet, daß die Kommunikationen stets von A zu B (und anderen Platinen) an der Rückwand gesendet werden; eine zusätzliche A-B-Verbindung ist nicht nützlich.
Zum Übermitteln von Netztopologieinformationen zwischen Koppelplatinen wird ein Paket des in Fig. 6A dargestellten allgemeinen Formats benutzt. Das Paket enthält nicht nur Informationen über die direkt verbundene Platine, sondern auch jede ihrer Nachbarn. So ist das Lastteilungsinformationspaket ein Paket veränderlicher Länge - die Paketlänge ist von der Anzahl von Nachbarn der zutreffenden Koppelplatine abhängig.
Fig. 6B zeigt ein Beispiel eines Lastteilungsinformationspakets 63 für von der Koppelplatine 66 zur Koppelplatine 65 übermittelte Informationen. Nach der Darstellung in 64a enthält das Paket eine Formatart, die angibt, daß dies ein Lastteilungsinformationspaket ist. In 64b ist eine Paket-Prüfsumme enthalten. In 64c hat die Koppelplatine 66 ihre Basis-MAC-Adresse identifiziert. Im Feld 64d identifiziert die Koppelplatine 66, daß dieses Lastteilungsinformationspaket von ihrem als 1 identifizierten Anschluß aus übertragen wird. Bei 64e zeigt die Koppelplatine 66 an, daß der Empfangsanschluß für diese Verbindung Anschluß Nr. 1 sein wird. (In der Tat weiß die Koppelplatine 66 u. U. nicht, daß die Koppelplatine 65 das Paket an ihrem Anschluß 1 empfangen wird; trotzdem kann dieses Feld als "Platzhalter" für den Aufbau einer unten beschriebenen Verbindungsliste eingeschlossen werden.) Die Koppelplatine 66 übermittelt weiterhin Informationen über jeden Nachbar der Koppelplatine 66 - wobei im vorliegenden Beispiel der einzige Nachbar die Koppelplatine 67 ist. So identifiziert die Koppelplatine 66 bei 62a die Basis-MAC-Adresse für die benachbarte Koppelplatine 67. Im Feld 62b kennzeichnet die Koppelplatine 66, daß der Anschluß 1 der Koppelplatine 67 ein Lastteilungsinformationspaket zur Koppelplatine 66 übertragen hat. Bei 62c kennzeichnet die Koppelplatine 66, daß dieses Paket von der Koppelplatine 67 am Anschluß 2 der Koppelplatine 66 empfangen wurde. Bei 62d schließlich kennzeichnet die Koppelplatine 66 diese Verbindungsart als eine Netzverbindungsart.
Diese Lastteilungsinformationspakete können zum Aufbauen einer Verbindungslistendatenstruktur benutzt werden, die die Verbindungen von der zutreffenden Koppelplatine und die Verbindungen von jedem der Nachbarn der Koppelplatine darstellt. Eine derartige Datenstruktur ist in der Fig. 7 dargestellt. Diese Datenstruktur kann als doppelt verkettete Liste gespeichert werden. Der Eintritt 71 in die Datenstruktur 70 ist eine Kennzeichnung für die Koppelplatine, die diese Datenstruktur speichert. Die Datenstruktur der Fig. 7 weist N Spalten auf, jeweils eine für jeden Anschluß auf dieser Platine. Jede Spalte besitzt eine Anzahl von Zeilen nach der ersten Zeile entsprechend der oben an der Spalte angezeigten Anzahl von aus der Platine austretenden Verbindungen. So beginnt die erste Spalte 72a mit einem Feld einer ersten Platine, die dieser Koppelplatine direkt benachbart ist (d. h. durch eine Verbindungsstrecke direkt mit dieser Koppelplatine von einem ersten Anschluß aus verbunden ist). Das erste Element der zweiten Spalte 72b enthält die Informationen, die auf eine zweite Platine anwendbar sind, die direkt mit dieser Koppelplatine verbunden ist (z. B. die vor einem zweiten Anschluß auf dieser Koppelplatine liegt). In einer bevorzugten Ausführungsform sind die Spalten in der Reihenfolge steigender MAC-Adresse organisiert. Jede Spalte enthält weiterhin alle Verbindungen, die vor der in der ersten Zeile gekennzeichneten Platine liegen. So gibt es für jede Verbindung vor der ersten Platine einen Eintrag in den Feldern 73a.
Die Verbindungslistendatenstruktur läßt sich leicht durch ein Beispiel verstehen. Fig. 11A zeigt eine Muster-Netztopologie mit Koppelplatinen A, B, C, D und E und Verbindungsstrecken A-C, A-D, B-C, B-D1, B-D2, C- D und D-E. Jede Verbindungsstrecke ist mit einem "N" für eine Netzverbindung oder einem "U" für eine Nutzverbindung bezeichnet. Es wird angenommen, daß den Koppelplatinen A-E MAC-Adressen in ansteigender Reihenfolge, d. h. A < B < C < D < E, zugewiesen sind.
Fig. 11B zeigt eine Verbindungsliste CL für die Netztopologie der Fig. 11A. Die Verbindungsliste wird wie bei 112 angezeigt aus der Perspektive der Koppelplatine D aufgebaut. Die Koppelplatine D besitzt wie bei 112a angezeigt einen mit der Koppelplatine A verbundenen Anschluß. Die Koppelplatine A selbst besitzt wie bei 112b angezeigt eine Verbindungsstrecke zur Koppelplatine C. Auf ähnliche Weise besitzt die Koppelplatine A wie bei 112c angezeigt eine Verbindungsstrecke zur Koppelplatine D (d. h. die Verbindungsstrecke A-D). In der Fig. 11B gibt es fünf Spalten in der Verbindungsliste - jeweils eine für jeden Anschluß auf der Koppelplatine D. Jede Spalte besitzt nach der ersten Zeile eine Anzahl von Zeilen entsprechend der oben an der Spalte angezeigten Anzahl von aus der Koppelplatine austretenden Verbindungen. Nach der Darstellung in Fig. 11B kann eine Koppelplatine als mehr als eine Spalte in der Verbindungsliste CL erscheinen - wenn mehr als eine Verbindungsstrecke zu dieser Koppelplatine läuft. Der obere Index "U" in der Verbindungsliste CL zeigt eine Nutzverbindung an. Beispielsweise bezieht sich B¹ auf die Verbindung zu B über die Verbindungsstrecke B-D1 und B² auf die Verbindung zu B über die Verbindungsstrecke B-D2.
Obwohl die Fig. 7 und die Fig. 11B kleine Felder für jedes Element der Verbindungsliste zeigen, kann an jedem Element eine vollständige Datenstruktur gespeichert werden. Diese Datenstruktur kann nicht nur die Identität der Koppelplatine (über die MAC-Adresse oder sonstwie) an dieser Verbindungsstelle enthalten, sondern auch den Sendeanschluß, den Empfangsanschluß und die Verbindungsart.
Fig. 8 zeigt die gegebenenfalls von einer Koppelplatine unternommenen Schritte bei Empfang eines Lastteilungsinformationspakets wie dem in Fig. 6B dargestellten. Nach Ankunft des Lastteilungspakets in einem Schritt 81 wird das Format in einem Schritt 82 überprüft, um sicherzustellen, daß es richtig ist. Wenn ja, dann wird in einem Schritt 83 das Prüfsummenfeld 61b untersucht, um sicherzustellen, daß keine Datenfehler im Paket vorliegen. Wenn das Paket entweder nicht das richtige Format besitzt oder eine ungültige Prüfsumme aufweist, wird die Verarbeitung in einem Schritt 88 abgeschlossen. Angenommen, das Paket besitzt das richtige Format und die Prüfsumme ist gültig, dann wird in einem Schritt 84 die Verbindungsliste für diese Koppelplatine untersucht, um zu bestimmen, ob ein Paket vor dem an diesem Anschluß empfangen worden ist. Wenn eine Verbindung in der ersten Zeile der Verbindungsliste steht, die am selben Anschluß empfangen wurde, dann ist schon ein Paket empfangen worden. Ansonsten ist noch kein Paket für diesen Anschluß empfangen worden. Wenn ein Paket noch nicht an diesem Anschluß empfangen worden ist, dann wird in einem Schritt 86 eine neue Spalte für die Verbindungsliste entsprechend der Struktur der Fig. 7 erstellt. Wenn im Schritt 84 bestimmt wird, daß das Paket einem Anschluß entspricht, der schon ein Paket empfangen hat, dann werden diese Verbindungen in einem Schritt 85 entfernt. Die Verarbeitung schreitet dann im Schritt 87 fort, wo die Verbindungsliste durch Einfügen der Informationen vom neuen Paket aktualisiert wird.
In der vorliegenden Ausführungsform werden jedes Mal, wenn ein Lastteilungspaket empfangen wird, die neuen Paketinformationen in die Verbindungsliste eingesetzt - selbst wenn alle Informationen in diesem Paket mit einem vorher empfangenen Paket identisch sind. Dementsprechend werden die ausführlicher unten beschriebenen Lastteilungsberechnungen periodisch durchgeführt - egal ob sich die Verbindungslisteninfdrmationen geändert haben oder nicht. Natürlich könnte eine Anzahl von Alternativen wie beispielsweise die Aktualisierung der Berechnungen nur dann, wenn eine substantive Änderung an der Verbindungsliste durchgeführt worden ist, implementiert werden.
Wiederum Bezug nehmend auf Fig. 5 ist ersichtlich, daß nach Aufbauen einer Verbindungsliste im Schritt 52a wie oben beschrieben die Verarbeitung fortgesetzt werden kann, indem die Anzahl von Lastteilungsinstanzen für das Netz im Schritt 52b bestimmt wird. Die Anzahl von Lastteilungsinstanzen (bzw. die "Lastteilungszählung") entspricht grob gesagt der Anzahl von Mengen von Verbindungsstrecken, auf denen die Last in der Menge von Verbindungsstrecken unabhängig auf dem Netz geteilt werden wird. In der unten beschriebenen besonderen Ausführungsform kann die im Schritt 52b wiedergegebene Zahl sogar größer als die Anzahl von Mengen von Verbindungsstrecken sein, auf denen Lastteilung im Netz durchgeführt wird. Im Schritt 52b identifizierte Lastteilungsinstanzen, die aber nicht eigentlich redundanten Verbindungsstrecken entsprechen, auf denen Lastteilung auftreten kann, werden im Schritt 53, wie ausführlicher unten beschrieben, ausgefiltert.
Fig. 9 zeigt ein Verfahren zur Bestimmung einer Lastteilungsinstanzenzählung und zum Rücksenden einer Lastteilungsinstanzenliste. Das Verfahren beginnt im Schritt 90, wo eine Kantenzählung bestimmt, eine Ordnungsliste aufgebaut und eine Knotenpunktliste aufgebaut wird.
Fig. 10 zeigt ein Verfahren zur Herstellung der Kantenzählung, Ordnungsliste und Knotenpunktliste. Die Verarbeitung beginnt in einem Schritt 100, wo die Ordnungsliste aufgebaut wird. Eine Ordnungsliste ist einfach eine Liste aller (durch MAC-Adressen identifizierten und in steigender Reihenfolge derselben sortierten) Koppelplatinen, über die die vorliegende Koppelplatine durch ihre Verbindungsliste Bescheid weiß. Wiederum auf die in Fig. 11A dargestellte Netztopologie Bezug nehmend ist in Fig. 11D eine Muster-Ordnungsliste O dargestellt. Die Ordnungsliste läßt sich aufbauen, indem einfach die in Fig. 11B dargestellte Verbindungsliste CL durchlaufen und jedes Mal, wenn eine neue Platine entdeckt wird, sie zu der Ordnungsliste hinzugefügt wird.
Nach Aufbauen der Ordnungsliste wird in Schritten 101 bis 107 mit der Verarbeitung fortgefahren, um eine Knotenpunktliste V herzustellen. Die Verarbeitung beginnt mit Schritt 101 durch Nehmen der ersten Spalte der Verbindungsliste. Bezug nehmend auf Fig. 11B wäre dies die Spalte bei 112a einschließlich der Elemente 112a, 112b und 112c. Im Schritt 102 wird die erste Zeile untersucht, um zu bestimmen, ob dies eine Netzverbindung ist. Wenn ja, dann wird diese Koppelplatine bzw. dieser "Knotenpunkt" zur Knotenpunktliste hinzugefügt. Wiederum auf Fig. 11B Bezug nehmend wird die Koppelplatine A über eine Netzverbindung mit der Koppelplatine D verbunden und demnach der Knotenpunkt A zur Knotenpunktliste hinzugefügt.
In Fig. 11E ist eine Muster-Knotenpunktliste V für die Netztopologie der Fig. 11A dargestellt. Wie aus der Knotenpunktliste V ersichtlich, enthält das erste Element der Liste einen Eintrag entsprechend der Koppelplatine A, die gemäß den direkt oben beschriebenen Schritten identifiziert wurde.
Das Verfahren schreitet in einem Schritt 103 fort, indem das nächste Element in der Spalte untersucht wird - im Beispiel der Fig. 11A wäre dies das Element 112b, das der Koppelplatine C entspricht.
In Schritten 104a bis 104e wird das Element untersucht, um zu bestimmen, ob es ebenfalls zur Knotenpunktliste hinzugefügt werden sollte (Schritt 104e). Wie aus Schritten 104a bis 104d ersichtlich, wird die Koppelplatine/das Element zur Knotenpunktliste hinzugefügt, wenn:
(a) die Koppelplatine über eine Netzverbindung angeschlossen ist;
(b) die Koppelplatine nicht die dieses Verfahren schrittweise durchlaufende Koppelplatine ist;
(c) die Koppelplatine nicht schon in der Knotenpunktliste steht; und
(d) entweder
(i) das erste Zeilenelement der Spalte für die Koppelplatine eine Netzverbindung ist, oder
(ii) die Koppelplatine auch direkt mit der dieses Verfahren schrittweise über eine Netzverbindung durchlaufenden Koppelplatine verbunden ist.
Im Schritt 106 wird jedes Element in einer Spalte solange untersucht, bis die Spalte aufgebraucht ist.
Zurückkehrend zum vorliegenden Beispiel wird das Element 112b beginnend im Schritt 104a untersucht. Die Verbindung A zu C ist eine Netzverbindung und die Koppelplatine (C) ist nicht die dieses Verfahren (D) schrittweise durchlaufende Platine - die Verarbeitung läuft infolgedessen im Schritt 104b fort. C erscheint noch nicht in der Knotenpunktliste und die Verarbeitung schreitet infolgedessen im Schritt 104d fort. Die Mutterverbindung für C (Element 112a) ist eine Netzverbindung. C wird infolgedessen zur Knotenpunktliste hinzugefügt. Dies ist in der Fig. 11E als das zweite Element (B) der Knotenpunktliste dargestellt.
Im Schritt 103 wird das nächste Element in der Spalte - das dem Element 112c entspricht, abgerufen. In einem Schritt 104a wird bestimmt, daß obwohl D durch eine Netzverbindung mit C verbunden ist, die zutreffende Koppelplatine (D) die dieses Verfahren (D) schrittweise durchlaufende Platine ist. Sie wird dementsprechend nicht zur Knotenpunktliste hinzugefügt.
Sobald eine Spalte vollständig ist, schreitet die Verarbeitung in einem Schritt 107 fort, bis alle Spalten untersucht worden sind.
Fig. 11E zeigt eine ursprüngliche vollständige Knotenpunktliste für die Netztopologie der Fig. 11A, die aus der Perspektive der Koppelplatine D berechnet wurde. Die in Fig. 11E dargestellte Reihenfolge von Elementen ist die Reihenfolge, in der die Elemente bei schrittweisem Durchlaufen des in Fig. 10 dargestellten Verfahrens zur Knotenpunktliste hinzugefügt werden würden. Eine abgeänderte Knotenpunktliste, die in diesem Verfahren später benutzt wird, wird jedoch in der Reihenfolge ansteigender MAC-Adresse sortiert, d. h. {A, B, B, C, C, E}.
In einem Schritt 108 wird die Kantenzählung, Ordnungsliste und Knotenpunktliste wiedergegeben. Die Kantenzählung stellt die Anzahl von Netzverbindungen in der Netztopologie (d. h. ausschließlich von Benutzerkanten) dar, über die D Bescheid weiß (z. B. die in der Verbindungsliste CL von D dargestellt sind). Die Kantenzählung ist gleich der Anzahl von Elementen in der zutreffenden Knotenpunktliste. So beträgt die Kantenzählung für die Koppelplatine D 6 - die Anzahl von Elementen in der Knotenpunktliste.
Wiederum Bezug nehmend auf Fig. 9 zeigen Schritte 91 bis 99C ein Verfahren zur Verwendung der Kantenzählung, Ordnungsliste, Knotenpunktliste und Verbindungsliste zur Bestimmung einer Lastteilungsinstanzenzählung und Instanzenliste.
In einem Schritt 91 wird eine Netzverbindungsliste bzw. "NW-Liste" aufgebaut. Die NW-Liste ist einfach eine Liste aller durch eine Netzverbindung direkt an diese Koppelplatine angeschalteten Koppelplatinen. In Fig. 11C ist eine Netzverbindungsliste für die Netztopologie der Fig. 11A dargestellt. Die Liste enthält einfach {A, B¹, B², E}. Wie in Fig. 11C dargestellt, kann jedes Element der Netzverbindungsliste einen Zeiger auf die verbleibenden Elemente der zutreffenden Verbindungslistenspalte, wie bei 113 gezeigt, enthalten.
Die Verarbeitung schreitet dann in einem Schritt 92 fort, der die Auswahl des nächsten Elements aus der NW- Liste betrifft. Der Zweckdienlichkeit halber wird das jeweilige im Schritt 92 ausgewählte Element als "X" bezeichnet. In einem Schritt 93a wird jedes andere (als "Y" bezeichnete) Element der Netzliste untersucht. Für jedes Element Y wird die diesem Element entsprechende Spalte in der Verbindungsliste im Schritt 93 daraufhin untersucht, ob die Koppelplatine X in der Spalte Y enthalten ist. Wenn sie nicht in der Spalte Y vorkommt, wird Y im Schritt 94 einer Liste "no_connect" hinzugefügt. Wenn X in der Spalte Y erscheint, wird Y zu einer Liste "connect_list" hinzugefügt und Y wird im Schritt 95 auch aus der NW-Liste entnommen.
Zurückkehrend zu den in Fig. 11A bis 11E dargestellten Beispielen wird das Element A zuerst im Schritt 92 aus der NW-Liste ausgewählt. Das nächste Element der NW-Liste ist eine Spalte mit der Koppelplatine B in der ersten Zeile. Da die Koppelplatine A nirgendwo in der Spalte der Platine B erscheint, wird B zu der Liste no_connect im Schritt 94 hinzugefügt. Dann wird die dritte Spalte untersucht. Da diese Spalte mit der zweiten Spalte identisch ist, wird B wieder zu der Liste no_connect hinzugefügt. Abschließend wird die mit der Koppelplatine E beginnende Spalte untersucht. Die Koppelplatine A erscheint wieder nicht in dieser Spalte und das Element E wird zu der Liste no_connect hinzugefügt. So wäre bei Abschluß des Schritts 93a die connect_list leer und die Liste no_connect würde {B, B, E} enthalten.
Im Schritt 96 wird das ursprüngliche Element einer Instanzenliste hinzugefügt - im obigen Beispiel würde nunmehr das Element A der Instanzenliste hinzugefügt werden.
Im Schritt 97 wird jedes Element in der connect_list untersucht. Für jedes Element in der connect_list und jedes Element in der Spalte dieses Elements in der Verbindungsliste wird jeder entsprechende Eintrag in der Liste no_connect oder in der Hetzliste aus der entsprechenden Liste entfernt. Im gegenwärtigen Beispiel ist die Verbindungsliste leer und aus der Liste no_connect oder der Netzverbindungsliste wurde im Schritt 97 nichts entfernt.
In einem Schritt 98 wird die Liste no_connect untersucht, und wenn die Liste no_connect nicht leer ist, wird die Instanzenzählung in einem Schritt 99 erhöht. Wenn die Liste no_connect leer ist, wird die Instanzenzählung nicht erhöht. Im obigen Beispiel würde die Instanzenzählung nunmehr auf 1 erhöht werden. In einem Schritt 99a beginnt das Verfahren, sich rückzusetzen, um das nächste Element in der Netzliste zu verarbeiten, indem es alle in der connect_list und Liste no_connect übrigen Elemente freimacht (das heißt löscht). In einem Schritt 99b ist, wenn die Netzliste leer ist, die Verarbeitung abgeschlossen und die Instanzenliste und Instanzenzählung werden in einem Schritt 99c wiedergegeben. Ansonsten schreitet die Verarbeitung durch Rückkehr zum Schritt 92 fort.
Um mit dem früheren Beispiel fortzufahren, ist das nächste Element der Netzverbindungsliste das erste Vorkommen der Koppelplatine B¹ in der Verbindungsliste. Wenn die Spalte B² in einem Schritt 93 untersucht wird, wird wieder die Koppelplatine B identifiziert. Dementsprechend wird die zweite Erscheinung von B aus der Netzverbindungsliste entfernt und B im Schritt 95 zur connect_list hinzugefügt. Wenn die mit der Koppelplatine E beginnende Spalte untersucht wird, wird die Koppelplatine B nicht gefunden und das Element E wird zu der Liste no_connect hinzugefügt (Schritt 94). So enthält die in Schritt 93a berechnete Connect-Liste {B}, und die Liste no_connect enthält {E}. Im Schritt 96 wird das Element B zur Instanzenliste hinzugefügt. Im Schritt 97 werden B (aus der connect_list) und die Verbindungen von B (C und D) nicht in der Spalte E (aus der Liste no_connect) oder in den übrigen Verbindungen der Netzverbindungsliste gefunden. Infolgedessen wird im Schritt 97 keine Handlung unternommen. Im Schritt 98 wird festgestellt, daß die Liste no_connect nicht leer ist (sie enthält das Element E). Infolgedessen wird die Lastteilungsinstanzenzählung im Schritt 99 erhöht (auf 2).
An dieser Stelle ist die Netzliste immer noch nicht leer (wobei das Element E das letzte in der Netzverbindungsliste verbleibende Element ist). Das Element E wird im Schritt 92 aus der Netzverbindungsliste abgerufen. Da es keine weiteren Spalten in der Netzverbindungsliste gibt, ist das Ergebnis der Schritte 93a bis 97 einfach, daß E in die Liste no_connect gesetzt wird. Die Liste no_connect ist nicht leer und die Instanzenzählung wird infolgedessen im Schritt 99 (auf 3) erhöht. Die Netzliste ist nunmehr leer. Im Schritt 99c wird dementsprechend die Instanzenliste (die Elemente {A, B, E} enthält) zusammen mit der Instanzenzählung von 3 wiedergegeben.
Wieder auf Fig. 5 Bezug nehmend müssen nach Identifizierung der Lastteilungsinstanzen die Vorwärtsmasken für jede Lastteilungsinstanz zugewiesen werden (Schritt 53).
Wenn es nur eine Lastteilungsinstanz gibt, kann dies direkt unter Verwendung der Knotenpunktliste und Ordnungsliste durchgeführt werden, wie ausführlicher unten in Verbindung mit Fig. 13-14 erläutert wird. Wenn jedoch die Lastteilungsinstanzenzählung größer als 1 ist, können die Vorwärtsmasken getrennt für jede einzelne Lastteilungsinstanz aufgesetzt werden.
Die Fig. 12 zeigt ein Verfahren zur Vorbereitung der Berechnung von Vorwärtsmasken für jede Lastteilungsinstanz, wenn es möglicherweise mehr als eine Instanz gibt. Das Verfahren beginnt mit einem Schritt 121, wo eine als "X" bezeichnete erste Verbindung in der Instanzenliste ausgewählt wird. Für diese Lastteilungsinstanz werden in einem Schritt 122 eine zeitweilige Ordnungsliste und eine zeitweilige Knotenpunktliste erstellt. Die zeitweilige Ordnungsliste und zeitweilige Knotenpunktliste sind an dieser Stelle mit der wie oben beschrieben bestimmten Ordnungsliste und Knotenpunktliste identisch. In einem Schritt 123 wird für jedes in der Instanzenliste aufgeführte verbleibende Element dieses Element aus der zeitweiligen Ordnungsliste und aus der zeitweiligen Knotenpunktliste entfernt, wenn dieses Element nicht gleich X ist.
Wiederum auf das Beispiel der Fig. 11A bis E Bezug nehmend und wiederum aus der Perspektive der Koppelplatine D ist wie oben erläutert die Instanzenliste {A, B, E}. Die erste aus der Instanzenliste ausgewählte Verbindung würde das Element A sein. Die zeitweilige Ordnungsliste würde wie in Fig. 11D gezeigt {A, B, C, D, E} enthalten. Die (sortiert e) zeitweilige Knotenpunktliste würde {A, B, B, C, C, E} enthalten. Im Schritt 123 wird jede der verbleibenden Verbindungen in der Instanzenliste {B, E} und jedes mit diesen verbundene Element (ein Auftritt von C und drei Auftritte von D (zwei von der B-Spalte und einer von der E-Spalte)) aus der zeitweiligen Ordnungsliste und der Knotenpunktliste entfernt. Die zeitweilige Ordnungsliste würde dementsprechend {A} sein. Die zeitweilige Knotenpunktliste würde {A, C} sein.
In einem Schritt 124 wird eine Anzahl von Lastteilungsanschlüssen unter Verwendung der im Schritt 123 bestimmten zeitweiligen Ordnungsliste und zeitweiligen Knotenpunktliste berechnet. Ein Verfahren zur Berechnung von Lastteilungsanschlüssen wird ausführlicher unten beschrieben. Wenn in einem Schritt 125 die Anzahl von Lastteilungsanschlüssen mehr als 1 beträgt, wird eine Lastteilungsinstanz gestartet (in diesem Zusammenhang bezieht sich Lastteilungsinstanz auf ein Programm, das Lastteilung über die Anschlüsse überwacht, die an Verbindungsstrecken in der zutreffenden Lastteilungsinstanz angekoppelt sind) und die Vorwärtsmasken werden den an dieser Lastteilungsinstanz teilnehmenden Anschlüssen zugewiesen. Wie in Schritten 126 und 127 angezeigt, schreitet die Verarbeitung fort, bis jedes Element der Instanzenliste untersucht worden ist.
Fig. 13 zeigt ein Verfahren zur Berechnung der Gesamtzahl von Lastteilungsanschlüssen in einer Lastteilungsinstanz. Die Anzahl von Lastteilungsanschlüssen bzw. die "Lastteilungszählung" ist gleich der Anzahl von Verbindungsstrecken bzw. "Kanten", an denen Lastteilung für diese bestimmte Lastteilungsinstanz vorkommt. So bezieht sich eine Lastteilungszählung von 2 auf Lastteilung über zwei Kanten in einem Netz.
Verarbeitung beginnt in einem Schritt 131a, wo ein Element einer Knotenpunktliste ("X") ausgewählt wird. Eine als die Verbindungszählung bzw. "CC" bezeichnete Variable wird dann gleich der Anzahl von. Malen gleichgesetzt, die die Koppelplatine am Element X in der Verbindungsliste erscheint, Schritt 132b. In dem Beispiel von Fig. 11A bis 11E und aus der Perspektive der Koppelplatine D ist das erste aus der Knotenpunktliste ausgewählte Element A. Der Knotenpunkt A erscheint genau zweimal in der Verbindungsliste für die Koppelplatine D. CC ist dementsprechend gleich 2. In einem Schritt 131C wird, wenn die Verbindungszählung gleich der Gesamtzahl von Anschlüssen für diese Koppelplatine ist (die Gesamtzahl von Anschlüssen beträgt 5 für die Koppelplatine D) und das Element bei X nur einen Abschnitt weit entfernt ist. (d. h. direkt mit der Koppelplatine verbunden ist) oder mindestens ein Anschluß mit einer Nutzverbindung vor der Koppelplatine D verbunden ist, das Element X aus der Knotenpunktliste entfernt und die Lastteilungszählung in einem Schritt 131d um 1 erhöht. Die Verarbeitung durchläuft die Schleife in Schritten 131a bis 131e, bis die gesamte Knotenpunktliste untersucht worden ist. Im vorliegenden Beispiel beträgt die Verbindungszählung für A 2 und die Verbindungszählung für C 4. Da keine von ihnen eine Verbindungszählung gleich der Anzahl von Anschlüssen an D (S) aufweist, wird kein Element der Knotenpunktliste entfernt und die Lastteilungszählung bleibt 0.
Wenn in einem Schritt 132 die Lastteilungszählung gleich der Gesamtzahl von Netzverbindungsstrecken in der Topologie (der auf die oben beschriebene Weise bestimmten Kantenzählung) ist, dann wird die Lastteilungszählung im Schritt 137 wiedergegeben. Im vorliegenden Beispiel beträgt die Lastteilungszählung immer noch 0 und die Anzahl von Verbindungsstrecken ist 6. Die Verarbeitung schreitet infolgedessen mit einem Schritt 133 fort.
Im Schritt 133 wird jedes der verbleibenden Elemente in der Knotenpunktliste untersucht. Wenn X direkt an die diesen Vorgang ausführende Koppelplatine über eine Netzverbindung angeschlossen ist, dann wird X aus der Knotenpunktliste entfernt und die Lastteilungszählung um 1 erhöht. Im vorliegenden Beispiel ist A direkt über eine Netzverbindung mit der Koppelplatine D verbunden. A wird dementsprechend aus der Knotenpunktliste entfernt und die Lastteilungszählung auf 1 erhöht. Das übrige Element. C in der Knotenpunktliste ist direkt an D angeschlossen, aber über eine Benutzerverbindung. C verbleibt dementsprechend in der Knotenpunktliste und die Verarbeitung schreitet in einem Schritt 134 fort. Da die Knotenpunktliste nicht leer ist, wird die Steuerung an einen Schritt 135 weitergegeben.
Im Schritt 135 wird C aus der Knotenpunktliste ausgewählt. In einem Schritt 136 wird die Verbindungsliste unter Bezugnahme auf das ausgewählte Element untersucht. Das Element X wird aus der Knotenpunktliste entfernt und die Lastteilungszählung erhöht, wenn mindestens eine Spalte der Verbindungsliste "Y" den folgenden Bedingungen genügt:
(a) die Spalte Y ist über eine Netzverbindung mit der Koppelplatine verbunden;
(b) das Element X ist mit der Spalte Y verbunden; und
(c) entweder
(i) das Element X erscheint in der Spalte Y als eine Benutzerverbindung, oder
(ii) das Element X ist direkt über eine Benutzerverbindung mit, der diesen Vorgang ausführenden Koppelplatine verbunden.
Zurückkehrend zum vorliegenden Beispiel wird die Koppelplatine C aus der Knotenpunktliste ausgewählt. Den obigen Bedingungen (a) bis (c) wird für jede der ersten drei Spalten in der Verbindungsliste genügt. Beispielsweise ist in der mit einer Verbindung von der Koppelplatine D zur Koppelplatine A beginnenden Spalte (a) A durch eine Netzverbindung mit D verbunden, (b) erscheint C in dieser Spalte und (c) (ii) ist C direkt durch eine Benutzerverbindung mit der Koppelplatine D verbunden. Dementsprechend wird C aus der Knotenpunktliste entfernt und die Lastteilungszählung auf 2 erhöht.
Die Steuerung kehrt dann zum Schritt 134 zurück. Da die Knotenpunktliste leer ist, wird die Lastteilungszählung (2) im Schritt 137 wiedergegeben.
Fortfahrend mit dem vorliegenden Beispiel wurde durch das obige Verfahren die Lastteilungszählung für die erste Lastteilungsinstanz bestimmt. Wie in der obigen Besprechung erwähnt, weist im gegenwärtigen Beispiel und aus der Perspektive der Koppelplatine D D drei mögliche Lastteilungsinstanzen entsprechend den drei Elementen der Instanzenliste {A, B, E} auf. Die mögliche Instanz A wurde wie oben verarbeitet und eine Lastteilungszählung 2 bestimmt. Die zweite mögliche Lastteilungsinstanz würde wie folgt verarbeitet werden.
Wiederum Bezug nehmend auf Fig. 12 wird im Schritt 121 das nächste Element der Instanzenliste ausgewählt - Element B. Im Schritt 122 wird dann eine zeitweilige Ordnungsliste und eine zeitweilige Knotenpunktliste erstellt. Wie durch schrittweises Durchlaufen der Schritte 123 bis 125 überprüft werden kann, würde die zeitweilige Ordnungsliste das einzige Element {B} umfassen. Die zeitweilige Knotenpunktliste würde {B, B, C} enthalten.
Die Steuerung wird dann dem in Fig. 13 aufgeführten Verfahren übergeben. Im Schritt 131a wird die erste Verbindung aus der Knotenpunktliste ausgewählt. Wie im vorhergehenden Beispiel wird die Schleife 131a bis 131e schrittweise durchlaufen, ohne daß irgendwelche Elemente aus der Knotenpunktliste entfernt werden und ohne daß die Lastteilungszählung erhöht wird. Im Schritt 133 bleibt dasselbe Element B oben in der Knotenpunktliste. Da es über eine Netzverbindung direkt mit der Koppelplatine B verbunden ist, wird dieses Element aus der Knotenpunktliste entfernt und die Lastteilungszählung auf 1 erhöht. Auf ähnliche Weise bewirkt das zweite Auftreten des Elements B in der Knotenpunktliste seine Entfernung und die Erhöhung der Lastteilungszählung auf 2. Da C mit einer Benutzerverbindung verbunden ist, läuft die Verarbeitung jedoch durch Schritt 134 zum Schritt 135 weiter. Wie in dem früheren Beispiel wird C als das einzige verbleibende Element der Knotenpunktliste ausgewählt. Im Schritt 136 wird aus denselben Gründen wie im früheren Beispiel C aus der Knotenpunktliste entfernt und die Lastteilungszählung auf 3 erhöht. Dementsprechend beträgt die Lastteilungszählung für die zweite Lastteilungsinstanz in der in Fig. 11A dargestellten Netztopologie und aus der Perspektive der Koppelplatine D 3.
Wieder zur Fig. 12 zurückkehrend gibt es ein verbleibendes Element in der Instanzenliste - E. Nach Verarbeitung in Schritten 122 bis 124 ist die Knotenpunktliste einfach {E}. Die Ordnungsliste ist ebenfalls {E}. In dem in Fig. 13 dargestellten Verfahren wird das Element E im Schritt. 131a aus der Knotenpunktliste abgerufen. Die Verbindungszählung beträgt 1, was nicht gleich der Anzahl von Anschlüssen vor der Koppelplatine D (5) ist. Das Verfahren schreitet dementsprechend durch Schritte 131e und 132 fort, um zum Schritt 133 zu gelangen. Im Schritt 133 wird bestimmt, daß das Element E direkt über eine Netzverbindung mit der Koppelplatine D verbunden ist. Das Element E wird dementsprechend aus der Knotenpunktliste entfernt und die Lastteilungszählung auf 1 erhöht. Im Schritt 134 wird festgestellt, daß die Knotenpunktliste leer ist. Infolgedessen wird die Lastteilungszählung 1 wiedergegeben.
Da die Lastteilungszählung nur 1 ist, würde jegliche Lastteilung nur über eine einzige Verbindung stattfinden. Das entspricht einer Verbindungsstrecke, für die es keine redundanten Verbindungen gibt - das heißt der gesamte Verkehr zum Element E durchläuft die Verbindungsstrecke D-E. Dementsprechend wird im Schritt 125 keine Lastteilungsinstanz für diese Verbindung begonnen. Da diese mögliche Lastteilungsinstanz keine wahre Gelegenheit zur Lastteilung bietet, besteht kein Erfordernis, eine Vorwärtsmaske für diese Verbindung zuzuweisen und kein Erfordernis, eine Lastteilungsinstanz zu beginnen.
Nach Bestimmung der Lastteilungszählung für jede Lastteilungsinstanz können Vorwärtsmasken für jeden Anschluß in einer gegebenen Lastteilungsinstanz zugewiesen werden. In Fig. 14 ist ein Verfahren zur Zuweisung von Vorwärtsmasken für eine Lastteilungsinstanz dargestellt.
Das Verfahren beginnt in einem Schritt 148a, wo das erste Element aus der Ordnungsliste für diese Instanz abgerufen wird. Angenommen, es gibt ein abzurufendes Element, schreitet die Verarbeitung im. Schritt 141 fort. In diesem Schritt holt die Verbindungsliste für die zutreffende Koppelplatine (die Koppelplatine, die die Vorwärtsmasken berechnet) die erste Verbindung aus der Verbindungsliste für das abgerufene Element aus der Ordnungsliste angenommen, es gibt eine. (Es wird eine Verbindung geben, wenn das aus der Ordnungsliste abgerufene Element direkt an die zutreffende Koppelplatine angeschlossen ist.) Wenn ja, dann wird im Schritt 147 die Verarbeitung zu einem Schritt 142 weitergegeben. Wenn das aus der Ordnungsliste abgerufene Element nicht direkt mit der zutreffenden Koppelplatine verbunden ist, dann gibt es keine aus dem zutreffenden Element abzurufende Anschlußverbindung. Dementsprechend wird das nächste Element aus der Ordnungsliste abgerufen und die Verarbeitung schreitet im Schritt 140 fort.
Angenommen, das aus der Ordnungsliste abgerufene Element "X" ist mit der Koppelplatine verbunden und eine Verbindung ("Y") ist abgerufen worden, dann schreitet die Verarbeitung in einem Schritt 142 fort. Wenn Y eine der dieses Verfahren ausführenden Koppelplatine entsprechende Adresse ist, wird der entsprechende Anschluß freigegeben und ihm die aktuelle Vorwärtsmaske im Schritt 143 zugewiesen (der bei 0 beginnt und im Verlauf des in Fig. 14 dargestellten Verfahrens erhöht wird). Wie im Schritt 144 gezeigt, ist die Verarbeitung abgeschlossen, wenn alle Anschlüsse eine Zuweisung erhielten. Ansonsten wird der nächste Anschluß, ein neuer "Y" aus der zutreffenden Spalte X abgerufen, und die Verarbeitung schreitet wie schon beschrieben im Schritt 147 fort. Wenn im Schritt 142 die abgerufene Verbindung nicht zu der dieses Verfahren anwendenden Koppelplatine ist, schreitet die Verarbeitung in einem Schritt 146a fort. Wie in Fig. 14 in Schritten 146a bis 146c gezeigt, wird der aktuelle Vorwärtsmaskenwert um 1 erhöht, wenn dieser Anschluß ein Netzanschluß ist und eine MAC-Adresse aufweist, die weniger als die MAC-Adresse für die dieses Verfahren anwendende Koppelplatine ist.
Die Anwendung des Verfahrens der Fig. 14 kann durch Fortfahren mit dem Beispiel der Fig. 11A bis 11E, wiederum aus der Perspektive der Koppelplatine D dargestellt werden. Man erinnere sich, daß zwei Lastteilungsinstanzen identifiziert wurden: eine mit einer Lastteilungszählung von 2 und eine mit einer Lastteilungszählung von 3.
Für die erste Instanz und wie oben beschrieben enthält die Ordnungsliste nur ein Element - {A}. Dieses wird im Schritt 148a aus der Ordnungsliste abgerufen. Da es ein Element gibt, schreitet die Verarbeitung im Schritt 141 fort. Im Schritt 141 wird festgestellt, daß A direkt mit der Koppelplatine D verbunden ist. Dementsprechend wird die erste Anschlußverbindung von der Koppelplatine A abgerufen - C in der Verbindungsliste der Fig. 11B. Da die Liste nicht aufgebraucht ist, wird im Schritt 147 die Verarbeitung zum Schritt 142 weitergegeben. Die Verbindung zu C geht nicht zur zutreffenden Platine D. Die Verarbeitung schreitet infolgedessen im Schritt 146a fort. Die Verbindung ist ein Netzanschluß (146a) und die MAC-Adresse für diese Verbindung (C) ist weniger als die MAC-Adresse für die zutreffende Platine (D). Die Vorwärtsmaske wird infolgedessen im Schritt 146c von 0 auf 1 erhöht. Im Schritt 145 wird die nächste Anschlußverbindung aus der Verbindungsliste für Element A abgerufen. Im Schritt 142 wird bestimmt, daß dieses Element durch eine Netzverbindung mit der Koppelplatine D verbunden ist. Infolgedessen wird der entsprechende Anschluß freigegeben und ihm eine Vorwärtsmaske von 1 zugewiesen. Der aktuelle Vorwärtsmaskenwert wird auf 2 erhöht. Nicht alle Anschlüsse der Koppelplatine D erhalten eine Zuweisung. Die Verarbeitung schreitet dementsprechend in einem Schritt 145 fort. Es sind alle vom Element A abgehenden Verbindungen untersucht worden. Im Schritt 147 wird dementsprechend die Steuerung zum Schritt 148b übergeben. Da A das einzige Element in der Ordnungsliste war, ist diese Liste gleichermaßen aufgebraucht. Die Zuweisung von Vorwärtsmasken für diese Lastteilungsinstanz ist dementsprechend abgeschlossen, Schritt 149a. So weist die Koppelplatine D für die erste Lastteilungsinstanz dem der Verbindungsstrecke A- D entsprechenden Anschluß eine Vorwärtsmaske von 1 zu.
Bezug nehmend auf die zweite Lastteilungsinstanz für das Beispiel der Fig. 11A bis 11E enthält die zeitweilige Ordnungsliste nur das Element B. Dies wird im Schritt 148a aus der Ordnungsliste abgerufen. Im Schritt 141 wird das erste Element C aus der Verbindungslistenspalte von B abgerufen. Im Schritt 142 wird festgestellt, daß es nicht mit der Koppelplatine D Verbunden ist. Im Schritt 146a wird festgestellt, daß dies ein Netzanschluß ist. Im Schritt 146b wird festgestellt, daß die MAC-Adresse C weniger als die MAC-Adresse von D ist. Im Schritt 146c wird infolgedessen die Vorwärtsmaske von 0 auf 1 erhöht. Die nächste, in Schritt 145 abgerufene Anschlußverbindung ist eine Verbindung zur Koppelplatine D. Diese ist mit der zutreffenden Koppelplatine verbunden. Im Schritt 143 wird dementsprechend dieser Anschluß freigegeben und ihm die aktuelle Vorwärtsmaske von 1 zugewiesen. Die Vorwärtsmaske wird auf einen Wert von 2 erhöht. Nicht alle Anschlüsse erhalten eine Zuweisung. Infolgedessen wird die nächste Anschlußverbindung aus der Liste abgerufen - die zweite Verbindung zu D. Die Verarbeitung schreitet wie zuvor fort und dieser Anschluß wird freigegeben und ihm die Vorwärtsmaske von 2 zugewiesen. Nachdem dies abgeschlossen ist, sind alle Verbindungen zum Element B untersucht worden und alle Elemente der Ordnungsliste (die nur diese eine Instanz war) untersucht worden. Die Verarbeitung ist infolgedessen abgeschlossen, und die Vorwärtsmasken sind zugewiesen worden - dem Anschluß für B-D1 ist eine Vorwärtsmaske von 1 und dem Anschluß für B-D2 ist eine Vorwärtsmaske von 2 zugewiesen worden. (Um sicherzustellen, daß die Koppelplatinen B und. D zum selben Schluß bezüglich der Zuweisung von Vorwärtsmasken zu den Anschlüssen für B-D1 und B-D2 kommen, kann jede Platine für die erste Zuweisung von Vorwärtsmasken die niedrigere Anschlußnummer der Stelle mit der niedrigeren MAC-Adresse auswählen).
In Fig. 15A ist die Netztopologie der Fig. 11A mit zugewiesenen Vorwärtsmasken dargestellt. Unter Verwendung der oben beschriebenen Verfahren kann jede Koppelplatine A, B, C, D und E das Verfahren unabhängig ausführen und hinsichtlich Vorwärtsmasken und Lastteilungsinstanzen zu denselben Schlüssen kommen.
In der Fig. 15A gibt es zwei Lastteilungsinstanzen. Die erste Lastteilungsinstanz LS1 weist Lastteilung unter Verbindungsstrecken A-C und A-D auf. Die zweite Lastteilungsinstanz LS2 erreicht Lastteilung unter Verbindungsstrecken B-C, B-D1 und B-D2. So weist die Koppelplatine A eine Lastteilungsinstanz auf, wobei ihre Anschlüsse Vorwärtsmasken 0 und 1 aufweisen. Die Koppelplatine B weist ebenfalls eine Lastteilungsinstanz auf und ihren Anschlüssen sind Vorwärtsmasken 0, 1 und 2 zugewiesen. Die Koppelplatine C weist zwei Lastteilungsinstanzen auf. Die erste Lastteilungsinstanz entspricht einer Lastteilung zwischen A-C und A-D und der A-C-Verbindungsstrecke ist eine Vorwärtsmaske 0 zugewiesen. Die zweite Lastteilungsinstanz ist Lastteilung zwischen Verbindungsstrecken B-C, B-D1 und B-D2 und dem B-C- Anschluß ist ebenfalls eine Vorwärtsmaske von 0 zugewiesen. Die Koppelplatine D weist ebenfalls zwei Lastteilungsinstanzen auf. Wie oben beschrieben ist dem Anschluß A-D eine Vorwärtsmaske von 1 für die erste Lastteilungsinstanz zugewiesen. Den Anschlüssen B-D1 und B-D2 sind Vorwärtsmasken von 1 bzw. 2 für die zweite Lastteilungsinstanz zugewiesen. Verbindungen C-D und D-E schließlich sind nicht an der Lastteilung beteiligt. Diese Verbindungsstrecken werden daher den gesamten Rundsendeverkehr im Netz tragen.
Wiederum Bezug nehmend auf Fig. 5 ist mit den obigen Verfahren eine Ausführungsform zur Implementierung des Schritts 51 - Identifizierung von Lastteilungsinteressen und Schritts 53 - Zuweisung von Vorwärtsmasken beschrieben worden. In der nachfolgenden Besprechung wird ein Verfahren zum Erreichen des Schritts 55, Assoziieren jedes Datenpakets mit einer eindeutigen Vorwärtsmaske aus jeder Lastteilungsinstanz dargelegt.
Eine Möglichkeit besteht in der Verwendung der Ursprungs-MAC-Adresse als Grundlage zur Zuweisung von Vorwärtsmasken. Dieses Verfahren ist in Fig. 16 dargestellt. Selbstverständlich kann eine Anzahl anderer Auswahlverfahren gewählt werden, solange jede Platine zu demselben Schluß hinsichtlich der Zuweisung einer Vorwärtsmaske kommt.
Das Verfahren beginnt in der Fig. 16 mit der Ankunft eines Pakets mit einer unbekannten Zieladresse in einem Schritt 161. (Das Verfahren kann auf ähnliche Weise für Rundsendeverkehr benutzt werden.) In einem Schritt 162 werden die Byte der Ursprungs-MAC-Adresse hinzugefügt. In einem Schritt 163 wird diese Summe MOD (bzw. "MODULO"), die Lastteilungszählung für die zutreffende Lastteilungsinstanz, berechnet. In Schritten 165 bis 169 wird das Datenpaket nur an einem Anschluß weitergeleitet, der eine Vorwärtsmaske gleich dem berechneten Betrag aufweist.
Zurückkehrend zum Beispiel der Fig. 15A betrachte man die Ankunft eines Pakets mit einer unbekannten Zieladresse, dessen Byte der Ursprungs-MAC-Adresse sich auf 2 belaufen. Für die erste Lastteilungsinstanz LS1 der Fig. 15A beträgt die Lastteilungszählung 2. 2 MOD 2 wird als 0 berechnet. Die Vorwärtsmaske für die erste Lastteilungsinstanz ist demnach 0. Die zweite Lastteilungsinstanz LS2 weist eine Lastteilungszählung von 3 auf. 2 MOD 3 ist immer noch 2. Die Vorwärtsmaske für die zweite Lastteilungsinstanz LS2 beträgt demnach 2. So zeigt die Fig. 15B das effektive Netz für dieses Paket. Für die Lastteilungsinstanz 1 wird nur die Vorwärtsmaske 0 benutzt. Für die zweite Lastteilungsinstanz LS2 wird nur die Verbindung mit der Vorwärtsmaske von 2 benutzt.
Ebenso betrachte man ein Paket, das mit einer unbekannten Zieladresse und einer sich auf 1 belaufenden Ursprungsadresse ankommt. Unter Verwendung des in Fig. 16 aufgeführten Verfahrens würde die Vorwärtsmaske für beide Lastteilungsinstanzen als 1 berechnet werden. Die effektive Netztopologie für dieses Paket wäre daher so wie sie in Fig. 15C dargestellt ist.
Abschließend betrachte man ein Paket mit einer unbekannten Zieladresse, das mit einer 6 ergebenden Ursprungsadresse ankommt. Für die erste Lastteilungsinstanz LS1 beträgt 6 MOD 2 0. Für die zweite Lastteilungsinstanz LS2 beträgt 6 MOD 3 0. Die Vorwärtsmaske für beide Lastteilungsinstanzen LS1 und LS2 ist dementsprechend 0. Die effektive Netztopologie für dieses Paket ist daher die in Fig. 15D dargestellte.
Nach der Beschreibung einer Ausführungsform der vorliegenden Erfindung kann nunmehr die Verwaltung von Zustandsänderungen im Netz beschrieben werden. Wenn ein Anschluß oder eine Verbindungsstrecke im Netz ausfällt, ist die Neukonfigurierung relativ einfach, wenn diese Verbindung einer Verbindungsstrecke in einer Lastteilungsinstanz entspricht. Die Lastteilungszählung wird um 1 erniedrigt, um widerzuspiegeln, daß eine Verbindungsstrecke weniger an der Lastteilung teilnimmt. Wenn die Lastteilungszählung nunmehr 1 beträgt, tritt keine eigentliche Lastteilung auf. Diese Lastteilungsinstanz kann demnach abgeschlossen werden. Ansonsten werden die Vorwärtsmasken einfach auf ähnlicher Grundlage wie die oben beschriebene neu zugewiesen.
Ebenso kann, wenn eine Koppelplatine ausfällt, dies als der Ausfall aller Verbindungsstrecken auf der Koppelplatine behandelt werden.
Der oben beschriebene Austausch von Lastteilungspaketen bietet eine Gelegenheit zur gleichzeitigen Feststellung einer Zustandsänderung im Netz. In einer bevorzugten Ausführungsform werden beispielsweise Lastteilungspakete alle zwei Sekunden an jedem der Anschlüsse einer Koppelplatine gesendet. Wenn ein Paket nicht innerhalb einer vorbestimmten Zeitdauer, beispielsweise sechs Sekunden, an einem Lastteilungsanschluß empfangen wird, kann die Koppelplatine annehmen, daß die an diesen Anschluß angeschlossene Kommunikationsstrecke ausgefallen ist. Ebenso kann, wenn eine Koppelplatine kein Lastteilungspaket von einer anderen Koppelplatine empfangen, hat, diese Platine mit Sicherheit annehmen, daß die andere Koppelplatine ausgefallen ist. Zufügung einer neuen Kommunikationsstrecke oder einer neuen Koppelplatine ist ebenfalls relativ einfach; wenn die neue Platine zugefügt wird, sendet sie neue Lastteilungspakete an jede benachbarte Koppelplatine. Die neuen Informationen werden automatisch in der Netztopologie für jede betroffene bestehende Koppelplatine unter Verwendung der oben beschriebenen Verfahren aufgenommen.
Die obigen Verfahren zur Reaktion auf Zustandsänderungen in einer Netztopologie bewirken eine bedeutende Verbesserung gegenüber einer einfachen Anwendung des aufspannenden Baums. Wenn eine Verbindungsstrecke im aufspannenden Baum verlorengeht, muß u. U. der gesamte Baum umstrukturiert werden. Im vorliegenden Fall kann die Kommunikation unbehindert an anderer Stelle im Netz und mit nur einer geringen örtlichen Verzögerung in der Nähe der ausgefallenen Verbindungsstrecke weiterlaufen.
Wenn ein neuer Anschluß oder eine neue Verbindung in die Netztopologie einkonfiguriert wird, wird der Anschluß entsprechend den oben beschriebenen Verfahren verarbeitet und ergibt möglicherweise die Berechnung neuer Lastteilungsinstanzen und neuer Vorwärtsmasken.
Die oben beschriebene bevorzugte Ausführungsform unterhält nur Informationen für direkt mit jeder Koppelplatine verbundene Koppelplatinen und einen Schritt weiter entfernte Platinen. Aus diesem Grund erkennt das Verfahren u. U. nicht Lastteilungsmöglichkeiten für Schleifen mit vier oder mehr Verbindungen. Zusätzlich können Schleifen von drei oder mehr Netzverbindungen Abnomalitäten in der Zuweisung von Vorwärtsmasken ergeben. Der Systembetreiber sollte dementsprechend sicherstellen, daß mindestens eine der Verbindungsstrecken in einer Schleife von drei als eine Benutzerverbindung zugewiesen wird. (Aus diesem Grund sollte bei jeweils drei Einschüben, die in der Form einer Dreischritt-Schleife zusammengeschaltet sind, mindestens eine dieser Verbindungen als eine Benutzerverbindung konfiguriert sein.)
Natürlich könnte die obige Ausführungsform erweitert werden und Schleifen von drei, vier oder mehr Verbindungen durch den Austausch von zusätzlichen Informationen über weiter von jeder Koppelplatine abgelegene Netztopologie und/oder geeignete Einstellungen an der obigen Ausführungsform richtig erkannt und bearbeitet werden. Man könnte beispielsweise genügend Topologieinformationen zum Aufbau der gesamten Netztopologie austauschen. Dann könnte einer aus einer Vielzahl unterschiedlicher Algorithmen zur Zuweisung von Lastteilungsinstanzen und Vorwärtsmasken gewählt werden - entweder optimal durch Iteration aller möglichen Konfigurationen oder unter Verwendung eines heuristischen Verfahrens zum Auswählen von Lastteilungsinstanzen und Zuweisen von Vorwärtsmasken. Ebenso kann eine Vielzahl unterschiedlicher Verfahren zur Zuweisung von Datenpaketen mit unbekannter Zieladresse zu einer Vorwärtsmaske innerhalb der Lastteilungsinstanz ausgewählt werden.
Das oben beschriebene Lastteilungsverfahren kann alleinstehend oder in Kombination mit dem Verfahren des aufspannenden Baums gefahren werden. Da die obige Ausführungsform u. U. einige Netzschleifen mit vier oder mehr Schritten nicht erkennt, wird empfehlen, daß die obige Ausführungsform in Kombination mit dem Verfahren des aufspannenden Baum benutzt werde.
Um das Lastteilungsverfahren in Kombination mit dem aufspannenden Baum zu benutzen, sitzen die Lastteilungsinstanzen "zwischen" der Implementierung des Verfahrens des aufspannenden Baums und der Koppelplatine. Das Lastteilungsverfahren wird wie oben beschrieben durchgeführt. Jede Verbindungsstrecke, die nicht ein Mitglied einer Lastteilungsmenge redundanter Verbindungsstrecken ist, wird für den Algorithmus des aufspannenden Baums identifiziert, so wie es im Stand der Technik durchgeführt wird und bekannt ist. Zusätzlich identifiziert jede Lastteilungsinstanz genau eine Verbindungsstrecke aus ihren Vorwärtsmasken (z. B. jede Vorwärtsmaske 0).
Fig. 17 zeigt eine Koppelplatine nach einer Ausführungsform der Erfindung. Die Koppelplatine 171 enthält Kommunikationsanschlüsse 172 und einen Befehlsanschluß 173. In der Koppelplatine ist eine Zentraleinheit 175 zur Steuerung der Funktionsweise der Platine enthalten. In einer bevorzugten Ausführungsform ist die Zentraleinheit eine 32-Bit-Verarbeitungseinheit Intel 960. Die Koppelplatine kann wahlweise zusätzliche Hardware 174 zur Durchführung spezifischer Funktionen wie beispielsweise der Implementierung einer BAF- Tabelle oder der automatischen Weiterleitung gewisser Kommunikationspakete ohne ein Programm auf der CPU 175 aufrufen zu müssen, enthalten. Softwareprogramme können zu der CPU über Anschluß 172 oder durch sonstige geeignete Mittel herabgeladen werden. Zusätzlich kann die Funktionsweise der CPU und die Konfiguration der Koppelplatine auch über den Befehlsanschluß 173 gesteuert werden. So kann beispielsweise Lastteilung für die Koppelplatine 171 unter Verwendung von über den Befehlsanschluß 173 an die CPU 175 erteilten Befehlen freigegeben oder gesperrt werden. Natürlich lassen sich viele Aspekte der oben definierten Erfindungen als Softwareobjekte, die in eingebetteten Vorrichtungen wie beispielsweise Firmware bestehen können; Softwareobjekte, die Teil einer Anwendung auf einem Universal- Rechnersystem sind; eine anwendungsspezifische integrierte Schaltung (ASIC) oder sonstige funktionell gleichwertige Mechanismen oder Hardwarebauteile aufbauen.
Nach dieser Beschreibung mindestens einer beispielhaften Ausführungsform der Erfindung werden dem Fachmann leicht verschiedene Abänderungen und Verbesserungen einfallen und sollen im Rahmen der Erfindung liegen. Die obige Beschreibung ist dementsprechend nur beispielhaft und soll nicht als begrenzend angesehen werden.

Claims

1. Verfahren zum Teilen der Kommunikationslast in einem redundanten Kommunikationsnetz mit einer Mehrzahl von Verbindungsstrecken, mit folgenden Schritten:

Identifizieren (Schritt 36) von mindestens einer Gruppe (A-C, A-D; B-C, B-D, B-E) einer Mehrzahl von Verbindungsstrecken im Netz, die Teil eines einen Anschluß (172) auf einer Brücke (171) im Netz durchlaufenden redundanten Kommunikationsweges sind, wobei eine jegliche Verbindungsstrecke in der Gruppe ohne irgendeine der anderen Verbindungsstrecken in der Gruppe zur Unterstützung Von Kommunikation im Netz genügt;

Übertragen einer Kommunikationslast über den Anschluß; und

Teilen der Kommunikationslast unter den Verbindungsstrecken in der Gruppe.

2. Verfahren nach Anspruch 1, weiterhin mit folgenden Schritten:

Bereitstellen eines Pakets (60) mit Informationen zur Übertragung im Netz;

Weiterleiten des Pakets über mindestens eine der Verbindungsstrecken im Netz, die nicht als Mitglied einer der Gruppen identifiziert wird; und

für jede der Gruppen Weiterleiten des Pakets über nur eine der Verbindungsstrecken in der Gruppe.

3. Verfahren nach Anspruch 1 oder 2, wobei der Schritt des Identifizierens den Schritt des Identifizierens einer Mehrzahl derartiger Gruppen (A-C) enthält.

4. Verfahren nach Anspruch 2, weiterhin mit folgenden Schritten:

für jede der Gruppen Zuweisen (Schritt 53) einer Kennzeichnung (0, 1, 2; XYZ) zu jeder der Verbindungsstrecken (B-C, B-D, B-E) in der Gruppe;

für das Paket Bestimmen eines Vorwärtswertes, der einer der zugewiesenen Kennzeichnungen entsprechen soll; und

wobei während des Schritts des Weiterleitens des Pakets über nur eine der Verbindungsstrecken in der Gruppe das Paket auf der Verbindungsstrecke mit einer dem Vorwärtswert entsprechenden zugewiesenen Kennzeichnung weitergeleitet wird.

5. Verfahren nach Anspruch 4, wobei der Schritt des Bestimmens eines Vorwärtswertes den Schritt des Bestimmens des Vorwärtswertes auf Grundlage von Informationen im Paket umfaßt.

6. Verfahren nach Anspruch 5, wobei der Schritt des Bestimmens eines Vorwärtswertes den Schritt des Bestimmens des Vorwärtswertes auf Grundlage einer Ursprungsadresse im Paket umfaßt.

7. Verfahren nach Anspruch 5, wobei der Schritt des Bestimmens eines Vorwärtswertes den Schritt des Bestimmens des Vorwärtswertes auf Grundlage der Anzahl von Verbindungsstrecken in der Gruppe und der Informationen im Paket umfaßt.

8. Verfahren nach Anspruch 3, weiterhin mit folgenden Schritten:

Bereitstellen einer ersten und einer zweiten Koppelplatine (66, 65);

Übertragen von Netztopologieinformationen (63) von der ersten Koppelplatine zur zweiten Koppelplatine;

Übertragen von Netztopologieinformationen von der zweiten Koppelplatine zur ersten Koppelplatine;

wobei jede der Koppelplatinen getrennt die mindestens eine Gruppe von Verbindungsstrecken im Netz identifiziert, die Teil des redundanten Kommunikationsweges im Netz sind; und

wobei jede der Koppelplatinen getrennt bestimmt, ob und auf welchen Verbindungsstrecken ein von dieser Koppelplatine empfangenes Paket weiterzuleiten ist.

9. Verfahren nach Anspruch 8, wobei für jede der Koppelplatinen der Schritt des getrennten Identifizierens vor dem Schritt des getrennten Bestimmens durchgeführt wird.

10. Verfahren nach Anspruch 2, weiterhin mit folgenden Schritten:

Berechnen eines aufspannenden Baums unter den Verbindungsstrecken, die nicht in den identifizierten Gruppen sind, und nur einer Verbindungsstrecke aus jeder identifizierten Gruppe;

Freigeben von Kommunikationen auf den. Verbindungsstrecken in den identifizierten Gruppen und auf den Verbindungsstrecken in einem aufspannenden Baum; und

Blockieren von Kommunikationen auf den verbleibenden Verbindungsstrecken im Netz.

11. Verfahren nach Anspruch 1, weiterhin mit einem Schritt des Bestimmens eines aufspannenden Baums im Kommunikationsnetz nach dem Schritt des Identifizierens.