Netzwerk-Know-how (tecCHANNEL COMPACT) Kapitel 4: Vermittlung

Veröffentlicht: 22-06-2005

Von VON PROF. DR. STEPHAN EULER

Im Artikel „Ethernet & Co.“ haben wir gesehen, wie Stationen direkt miteinander kommunizieren können. Die direkte Verbindung stößt jedoch an Kapazitätsgrenzen, wenn es gilt, viele Stationen zu verbinden oder eine hohe Datenrate zu gewährleisten.

Allgemein gesehen handelt es sich um eine Reihe von Teilnetzen, die zusammengeschaltet werden sollen. Im Extremfall kann jedes Teilnetz aus nur einer einzelnen Station bestehen. Man kann die Teilnetze beispielsweise in Form eines Sterns über ein zentrales Koppelelement verbinden (Bild 1).

Bild 1: Netzwerk mit Sterntopologie und zentralem Koppelelement

Bei einem einfachen Ethernet-Hub werden alle Pakete über den gesamten Stern und damit an alle Knoten geschickt. Effizienter ist es, wenn das Koppelelement die Adresse auswertet und die Pakete nur an die betroffenen Teilnetze schickt. Ein Gerät mit entsprechender Funktionalität ist ein Vermittler oder Switch. Der grundsätzliche Aufbau ist in Bild 2 dargestellt.

Bild 2: Prinzip eines Switchs. Das Gerät wertet die Adressen aus und schickt die Pakete nur an die betroffenen Teilnetze

Ein Switch hat eine feste Anzahl von Ein- undAusgängen. An diesen Anschlüssen - auch als Ports bezeichnet - werden Teilnetze oder Knoten angeschlossen. Dabei können verschiedene Typen von Ports vorhanden sein. Zum Beispiel kann ein Switch eine Reihe von Ports mit lOBaseT zum direkten Anschluss von Stationen und breitbandige Anschlüsse zur Vernetzung mit weiteren Switches haben. Empfängt der Switch an einem Eingangsport ein Paket, so liest er die Adresse und entscheidet dann, auf welchen Ausgangsport er es schickt.

Bevor wir näher auf Switches eingehen, sind in der folgenden Auflistung die unterschiedlichen Geräte zur Verbindung von Netzen zusammengestellt. Im Wesentlichen unterscheiden sich die Gerät nach der Anzahl der Anschlüsse sowie in der eingebauten „Intelligenz".

Einfache Geräte arbeiten nur auf der Ebene des physikalischen Signals, während aufwendige Geräte eine komplette Analyse der Daten über alle Ebenen des ISO/ OSI-Referenzmodells durchführen.

• Repeater: Ein Repeater verbindet zwei gleichartige Netze. Er arbeitet auf Ebene 1 des ISO/OSI-Referenzmodells und behandelt nur das physikalische Signal. Ein Repeater kann beispielsweise dann verwendet werden, wenn ein Ethernet-Strang die maximale Länge erreicht hat. Über einen Repeater kann dann ein weiterer Strang angeschlossen werden. Der Repeater regeneriert das Signal, bevor er es in den zweiten Strang überträgt.
• Hub: Ein Hub entspricht im Prinzip einem Repeater, jedoch mit mehreren Ports (Multiport-Repeater).
• Bridge: Eine Bridge stellt eine Verbindung zweier Netze her, wobei Ebene 1 und 2 des ISO/OSI-Referenzmodells berücksichtigt werden müssen. Bei der Weiterleitung werden die Adressinformationen ausgewertet und fehlerhafte Rahmen blockiert
• Switch: Multiport-Bridge
• Router: Router verbinden Netzwerke unterschiedlicher Art. Falls erforderlich, können Sie Datenpakete in eine andere Form umsetzen. Sie arbeiten auf Schicht 3.
• Gateway: Als Schnittstelle zwischen unterschiedlichen Netzen (zum Beispiel TCP/IP mit einem herstellerspezifischen Protokoll wie DECnet) dienen Gateways. Sie arbeiten auf allen 7 Schichten

Bei der Entwicklung von Switches stellen sich zwei Herausforderungen. Das erste Problem ist die Realisierung der Vermittlungsfunktionalität.

• Woher weiß der Switch, an welchen Ausgangsport ein Paket mit der Adresse xyz geschickt werden soll?

Der zweite Themenkomplex ist die effiziente Realisierung eines Switches. Intern ist zunächst ein schneller Datentransfer zu gewährleisten. Weiterhin muss der Switch auf jeder angeschlossenen Leitung ein sicheres Protokoll realisieren und beispielsweise auch Verzögerungen durch Kollisionen handhaben können. Die Kernfrage lautet dann:

• Wie kann ein leistungsfähiger und trotzdem preisgünstiger Switch in Hardware realisiert werden?

Im Folgenden beschreiben wir zunächst die Grundprinzipien der Vermittlung. Anschließend werden einige anschauliche Beispiele für die Realisierung von Switches vorgestellt.

Zum Seitenanfang

Datagramme

In der Grundform der Paketvermittlung trägt jedes Datenpaket die Zieladresse. Anhand dieser Zieladresse wird das Paket durch das Netzwerk geleitet. Jeder Switch führt eine Tabelle mit der Information, aufweichen Port er Pakete mit gegebener Zieladresse weiterleitet (Weiterleitungstabelle oder Routing-Tabelle).

Bild 3: Netz mit neun Knoten A bis J und drei Switches.

Das Bild 3 zeigt ein Beispielnetz mit neun Knoten und Switches. Die Ports sind nummeriert. Der Einfachheit halber sind Ein- und Ausgänge zusammengelegt. Jeder Switch führt eine Tabelle, in der für jedes Ziel (Knoten) der richtige Port eingetragen ist. Entweder hängt der Knoten direkt an diesem Port oder der Port führt zum nächsten Switch in Richtung Ziel. Die Weiterleitung stabelle für Switch 2 ist in Tabelle 1 angegeben.

Zum Seitenanfang

Lernende Bridges

Lernende Bridges nutzen eine einfache Strategie zum Aufbau der Weiterleitung-stabellen. Bridges sind Geräte, die mehrere LANs verbinden, indem sie ankommenden Rahmen an die Ausgänge weitergeben. Wenn eine Bridge die Rahmen analysiert, kann sie feststellen, an welchem Port Rahmen von welchem Knoten ankommen. Dieser Port wird in die Weiterleitungstabelle für den Knoten eingetragen. Von da an werden Rahmen an diesen Knoten nur noch auf diesem Port ausgegeben. Durch diese Strategie wird für einen Knoten, sobald er Rahmen sendet, automatisch der richtige Eintrag in die Weiterleitung stabelle aufgenommen.

Am Anfang ist die Tabelle leer und wird erst im Laufe der Zeit gefüllt. Auch wenn die Tabelle das Netzwerk nicht vollständig erfasst, verbessert sich der Netzwerkverkehr. Fehlt für einen Zielknoten der Eintrag, so wird der Rahmen nach wie vor an alle Ports (außer dem Eingangsport) weitergeschickt. Um Änderungen im Netz zu erfassen, wird der Eintrag eines Knotens wieder gelöscht, sobald über eine gewisse Zeit keine Rahmen mehr von diesem Knoten gekommen sind.

Ein Problem entsteht bei der Verknüpfung von LANs über Bridges, wenn das Netz Schleifen enthält. Solche Schleifen entstehen entweder aus Versehen oder bewusst als Redundanz gegen Ausfall einer Bridge. Ohne Gegenmaßnahmen kann es dazu kommen, dass Rahmen ewig in den Schleifen kreisen. Eine Lösung dieses Problems stammt von R. Perlmann. Um Schleifen zu erkennen, tauschen die Bridges regelmäßig Informationen über den ihnen bekannten Teil des Netzes aus. Aus den Informationen berechnen sie dann einen Baum (Spanning Tree), der die jeweils kürzesten Verbindungen enthält. Eventuell vorhandene zusätzliche Verbindungen, die im vollständigen Netz zu Schleifen führen, werden im Baum nicht berücksichtigt. Während des Betriebs wird der Baum regelmäßig aktualisiert, um eventuelle Änderungen zu erfassen. Der Standard IEEE 802.1D „Media Access Control (MAC) Bridges" beschreibt das Protokoll.

Zum Seitenanfang

Virtuelle Verbindungen

Die Vor- und Nachteile der Nachrichtenübertragung mit Datagrammen wurden bereits diskutiert. Datagramme sind besonders geeignet, wenn nur kurze Nachrichten geschickt werden oder eine ausfallsichere Kommunikation wichtig ist. Andererseits wird häufig nicht nur eine einzelne Nachricht übermittelt, sondern die Kommunikation erfolgt über einen längeren Zeitraum (zum Beispiel Verbindung zwischen zwei Standorten einer Firma). In solchen Fällen ist die Datagramm-Übertragung nicht effizient, da für jedes Paket wieder der gesamte Ver-mittlungsprozess abläuft. Daher wickelt man die Kommunikation häufig über virtuelle Leitungen ab.

Virtuelle Leitungen (Virtual Circuit VC) simulieren mit Methoden der Paketvermittlung klassische Leitungsvermittlung. In einer Aufbauphase wird zunächst ein Weg vom Sender zum Empfänger festgelegt. Jeder dabei beteiligte Switch reserviert dann Kapazität für die Verbindung. Sobald die Verbindung steht, können Pakete über die Verbindung geschickt werden. Die Pakete benötigen nicht mehr die Zieladresse, sondern nur noch einen Bezeichner für die VC. Zum Ende der Verbindung sind die Switches zu informieren, so dass sie die VC wieder abbauen und die Ressourcen für neue Verbindungen frei machen.

Virtuelle Leitungen lassen sich entweder vom Netzadministrator dauerhaft anlegen (Permanent Virtual Circuit PVC) oder von einem Knoten bei Bedarf aufbauen (Switched Virtual Circuit SVC). Man kann sich den Netzaufbau ähnlich wie die Weiterleitung eines Datagramms vorstellen. Der Sender schickt ein Paket mit dem Wunsch zum Verbindungsaufbau. Das Paket wird durch das Netz zum Empfänger geleitet. Beim Passieren des Pakets reserviert ein Switch die Ressourcen für die Verbindung. An dieser Stelle lassen sich Vorgaben für die Qualität der Verbindung treffen, beispielsweise bezüglich Bandbreite oder Verzögerungszeit. So ist für die Verbindung eine definierte Dienstgüte (Quality of Service, QoS) garantiert.

Ist die VC aufgebaut, braucht jeder Switch sich nur noch die Verbindung zwischen Ein- und Ausgang zu merken. Da über einen Port mehrere VC kommen können, reicht nicht die Portnummer, sondern eine Kennzeichnung für die VC ist zusätzlich erforderlich. Diese Kennzeichnung gilt nicht global für den VC, sondern nur innerhalb jedes Switches und dort wieder für einen Port.

In Bild 4 ist ein Beispiel für einen Switch mit vier Ein- und vier Ausgangsports dargestellt. Eingetragen sind zwei virtuelle Verbindungen; eine von Port 2 nach Port 1 und die zweite ebenfalls von Port 2 aus nach Port 3.

Bild 4: VC innerhalb eines Switches

Um die Verbindungen zu kennzeichnen, vergeben die Switches eindeutige Identi-fikatoren. Das sind so genannte Virtual Circuit Identifier VCI. Für die Eingänge kann der Switch selbst die Nummerierung übernehmen. Sobald ein anderer Switch auf einem Port eine neue Verbindung anmeldet, vergibt der Switch eine freie VCI-Nummer. Diese meldet er dem Vorgänger-Switch, der sie dann als Ausgangs-VCI übernimmt. In Summe sind die Schritte für eine Verbindung steilstrecke von Switch N zu Switch M:

• Switch N sendet eine Anfrage an Switch M.
• Switch M entscheidet, ob er die Anfrage akzeptiert.
• Falls Switch M die Anfrage akzeptiert, wählt er einen freien VCI für seinen Eingangsport aus.
• Switch M meldet seinen Eingangs-VCI an Switch N.
• Switch N trägt den erhaltenen VCI dann als Ausgangs-VCI in seine eigene Tabelle ein.

Die Rückmeldung der VCI an den Vorgänger-Switch muss nicht unmittelbar erfolgen. Sie kann auf dem Weg einer Bestätigung vom Empfänger zurück zum Sender bei allen Switches nacheinander übergeben werden. Das Resultat trägt der Switch in eine Tabelle ein. Für das obige Beispiel könnte das Ergebnis folgendermaßen aussehen:

Techniken mit virtueller Leitungsvermittlung sind Frame-Relay und ATM. Fra-me-Relay ist bei der Übertragung in Weitbereichsnetzen im Einsatz. Eine wichtige Anwendung ist die Kopplung mehrerer LANs zu einem Virtual Private Network (VPN). Dazu werden vornehmlich PVC benutzt.

Zum Seitenanfang

Design von Switches

Wie oben beschrieben, besteht ein Switch aus einer Reihe von Ein- und Ausgängen - den Ports - sowie einer Einheit zur Verteilung der Pakete - dem Schaltnetzwerk (Switching Fabric). Die Herausforderung beim Design ist, Pakete von möglichst vielen Ports möglichst schnell zu verteilen. Dazu ist intern eine entsprechend hohe Verarbeitungsgeschwindigkeit bereitzustellen.

Die Eingangsports nehmen Pakete in Empfang und speisen sie in das Schaltnetzwerk ein. Ausgangsports erhalten Pakete vom Schaltnetzwerk und schicken sie auf die Leitung. Diese zunächst trivial erscheinenden Aufgaben erweisen sich jedoch bei genauerer Analyse als komplex. Das Grundproblem liegt nämlich in der ungleichen Verteilung des Verkehrs. In aller Regel kommuniziert nicht stets ein Eingang mit genau einem Ausgang. Beispielsweise schickt ein Server Pakete an viele Knoten. Damit werden an dem Port viele Pakete ankommen, an dem der Server angeschlossen ist. Diese Pakete sind auf mehrere Ausgänge zu verteilen. Ein Extremfall ist ein Broadcast-Paket, das an einem Eingang ankommt und an alle Ausgänge weitergereicht werden muss.

Entsprechend gilt für die Ausgänge, dass auch dort Pakete von vielen Eingängen „gleichzeitig" ankommen können und dann in eine Leitung einzuspeisen sind. Daher müssen Ports in der Lage sein, Pakete in einen Zwischenspeicher (Puffer) zu legen, bis sie weitergeschickt werden können. Bei dem Entwurf gilt es, einen guten Kompromiss zu finden: Die Puffer sollen möglichst selten überlaufen, aber andererseits auch nicht überdimensioniert sein.

Prinzipiell ist es möglich, die Puffer an den Eingängen oder an den Ausgängen zu platzieren. Zwischenspeicher an den Eingängen können allerdings schnell zu unnötigen Blockaden führen. Betrachten wir folgendes Beispiel von Paketfolgen an zwei Eingängen:

Die beiden nächsten Pakete an der Reihe kollidieren, da sie beide an Port 5 gerichtet sind. Bei Eingangspufferung würde eines der Pakete ausgewählt und die Ausgabe am zweiten Port verzögert. Damit werden auch weiter hinten liegende Pakete blockiert, obwohl ihr Ziel (4 oder 6) eventuell frei ist (Head-of-Line-Blocking). Daher erfolgt die Pufferung in der Regel an den Ausgängen.

Zum Seitenanfang

Weiterleitung

Eine weitere Frage ist, wann ein Paket weitergeleitet werden soll? Eine Möglichkeit hierfür: erst das Paket vollständig abwarten, dann die Integrität prüfen und es - sofern alles damit in Ordnung ist - anschließend weitergeben (Store-and-For-ward-Prinzip). So wird die weitere Verbreitung unvollständiger oder fehlerhafter Pakete verhindert. Daraus resultiert aber auch, dass die Verarbeitungszeit im Switch mindestens so groß ist wie die Übertragungsverzögerung für das Paket.

Die Alternative ist, ein Paket frühzeitig weiterzugeben. In der Regel steht die Zieladresse im vorderen Teil des Pakets. Sobald dieser Teil gelesen ist, kann schon die Weiterleitung aufgenommen werden (Cut-Through- oder On-the-fly-Prinzip). Allerdings nimmt man damit auch in Kauf, dass fehlerhafte Pakete in andere Netze übertragen werden.

Je nach Anwendungssituation kann eine der beiden Strategien besser sein. Bei einem lokalen Netz mit relativ geringer Auslastung lässt sich durch die beschleunigte Weiterleitung die Gesamtverzögerung reduzieren

Ist umgekehrt das Netz stark belastet, so dass es häufiger zu Kollisionen kommt, dann wird die Lage durch die ungehinderte Verbreitung von unvollständigen Paketen noch verschärft.

Einige Hersteller bieten deshalb Geräte an, die dynamisch zwischen den beiden Betriebsweisen hin und her schalten können. Abhängig von etwa der Anzahl der festgestellten fehlerhaften Pakete wird dann zwischen der schnelleren oder der sichereren Option gewählt.

Zum Seitenanfang

Knockout-Switch

Bei einem Knockout-Switch [1] werden alle ankommenden Pakete an alle Ausgangsports verteilt. An jedem Ausgangsport sind Paketfilter, die nur an den Port gerichtete Pakete passieren lassen. Die Pakete werden in eine Warteschlange eingereiht und von dort aus abgeschickt. Falls die Kapazität der Warteschlange nicht ausreicht, alle Pakete aufzunehmen, ist eine Auswahl zu treffen. Diese Aufgabe übernimmt ein Konzentrator, der aus L Paketen N<L Pakete auswählt. Die günstige Realisierung beruht auf einfachen Auswahlbausteinen mit nur zwei Eingängen. Ein Baustein wählt zufällig aus den beiden ankommenden Paketen eines als „Sieger" aus. Wie bei einem Turnier in K.-o.-Modus treten alle Pakete gegeneinander an, bis ein Sieger übrig bleibt. Die Verlierer kommen in eine zweite Runde, die nach dem gleichen Modus den zweiten Sieger ermittelt. Das Verfahren wird fortgesetzt, bis N Sieger feststehen. Die restlichen Pakete werden verworfen.

Zum Seitenanfang

Batcher- und Banyan-Netzwerke

Schaltnetzwerke lassen sich günstig als Verbund von gleichartigen kleinen, einfachen Elementen bauen. Solche Elemente haben zwei Eingänge sowie zwei Ausgänge und entscheiden nur zwischen zwei Möglichkeiten:

• Eingang 1 auf Ausgang 1 und Eingang 2 auf Ausgang 2
• Eingang 1 auf Ausgang 2 und Eingang 2 auf Ausgang 1

Das 2x2-Schaltelement trifft seine Entscheidung auf Grund von Informationen im Header des Pakets. Beispielsweise kann bei einer VC der Eingangsport aus der aktuellen Tabelle den Ausgangsport entnehmen und als internen Header an das Paket anfügen. Man spricht dann von eigenvermittelnden Schaltnetzwerken.

Der Entscheidungsprozess aus Sicht eines Pakets verläuft ähnlich wie die Suche in einem binären Baum. An jedem Knoten - Schaltelement - wird ein weiterführender Ast aus zwei Möglichkeiten ausgewählt. Bei einem Header mit n Bit erreicht ein Paket dann in n Schritten einen aus 2n Endknoten (Ausgangsports). Da es aber mehrere Eingänge gibt, sind mehrere Wurzeln notwendig. Alle Wurzeln führen aber zu den gemeinsamen Blättern, wobei die Pakete auf dem Weg nicht zusammenstoßen dürfen. Eine trickreiche Lösung dieses Problems sind Banyan-Netzwerke, bei denen diese Vergleichsbäume in geschickter Weise ineinander verflochten sind. Bei n Eingängen werden n/2 Schaltwerke pro Stufe und Iog2n Stufen benötigt. Banyan ist der englische Name eines Baumes (Ficus benghalen-sis), bei dem Ableger von den Ästen aus neue Wurzeln bilden.

Banyan-Netzwerke funktionieren allerdings nur gut, wenn die eingehenden Pakete in aufsteigender Reihenfolge sortiert sind. Daher wird ein nach seinem Erfinder benanntes Batcher-Netzwerk vorgeschaltet, das zunächst die Pakete in die richtige Reihenfolge bringt. Das nachgeschaltete Banyan-Netzwerk bringt die Pakete dann an die richtigen Ausgangsports.

Bild 5: Das Batcher-Netzwerk sortiert die Pakete für das Banyan-Netzwerk in aufsteigender Reihenfolge vor, damit dieses effizient arbeiten kann.

Das kombinierte Netzwerk befördert alle Pakete an den richtigen Ausgangsport. Es kann allerdings stets nur ein Paket zu jedem Ausgang leiten. Daher werden zusätzliche Komponenten benötigt, die durch Pufferung und eventuelle parallele Strukturen Zielkollisionen so weit wie möglich vermeiden.

Zum Seitenanfang

Literatur

© www.tecCHANNEL.de

[1] Y. Yey, M. G. Hluchj, and A. S. Acampora. The knockout switch: A simple, modular architecture for high-performance packet switching. IEEE J. Sel. Areas Commun., 5(8):1274-1283, October 1987

Zum Seitenanfang

| Home | Technische Artikel | Community