Technische Universität Braunschweig, Fachbereich Informatik, Institut für Betriebssysteme und Rechnerverbund
Betreuung: Prof. Dr. Martina Zitterbart, Dipl. Inform. Till Harbaum

Inhalt

1 Einleitung
1.1 Was ist Routing?
1.2 Strukturmodell eines Routers

2 Die Routingtabelle
2.1 Longest Matching Prefix
2.2 Hashtabellen
2.3 Content Addressable Memories
2.4 Binärbäume
2.5 Tries

3 Datenstrukturen für Routingtabellen
3.1 PC-Erweiterungskarte
3.2 Dynamic Prefix Trie
3.3 Binary Tree with Chunks
3.4 Hashing with Binary Search

4 Zusammenfassung

5 Literaturverzeichnis

Einleitung

Was ist Routing?

Große Netzwerke wie das Internet bestehen aus vielen kleineren Teilnetzwerken (siehe Abbildung 1). Die Verbindung der verschiedenen Netze wird durch spezielle Rechner hergestellt. Das sind, neben Bridges, Switches und Gateways, im Internet vor allem Router. Diese haben die Aufgabe, Daten zwischen Rechnern in verschiedenen Netzen auf möglichst günstigen Wegen weiterzuleiten. Zum Beispiel wenn Rechner 1 im Netz B Daten an Rechner 2 im Netz C schicken möchte.

Diese Datenvermittlung im Internet geschieht auf Basis des Internet-Protokolls (IP). Es kann in der Vermittlungsschicht (Schicht 3) des OSI-Schichtenmodells angesiedelt werden. Jeder Rechner im Internet besitzt eine global eindeutige Internet-Protokoll-Adresse, kurz IP-Adresse. Das Verschicken der Daten im Netz geschieht in Form von IP-Paketen. Größere Datenmengen müssen dazu auf mehrere Pakete verteilt werden. Jedes IP-Paket besteht aus einem Datenteil und einem Paketkopf. Im Paketkopf befindet sich unter anderem die IP-Adresse des Zielrechners, auf deren Basis ein Router das Paket im Netz weiterleiten kann.

Bevor ein Router ein Paket mit einer bestimmten IP-Adresse weiterleiten kann, muß er für diese Adresse zunächst den Weg durch das Netz zum Zielrechner bestimmen. Das geschieht mit Hilfe spezieller Protokolle wie ARP, RIP, OSPF, EGP/BGP (siehe [KoBu94]). Auf diese Protokolle wird hier jedoch nicht weiter eingegangen. Dieser Vortrag befaßt sich mit einer Datenstruktur innerhalb eines Routers, in der die Ergebnisse der oben erwähnten Wegesuche eingetragen werden, der sog. Routingtabelle.

In der Routingtabelle ist aber nicht der gesamte Weg zu einem Rechner mit einer bestimmten IP-Adresse gespeichert. Vielmehr kennt der einzelne Router nur die nächste Zwischenstation (engl. next hop) auf dem Weg zum Ziel. Das kann ein weiterer Router oder der Zielrechner sein.

Strukturmodell eines Routers

Wie funktioniert das Weiterleiten (engl. forwarding) von Paketen nun im Detail? Dazu ist es sinnvoll, zunächst den groben Aufbau eines Routers zu betrachten (sieheAbbildung 2). Dieser besteht aus mehreren Netzwerkadaptern, die eine Verbindung zu den jeweiligen Netzen, die mit dem Router verbundenen sind, herstellen. Die Adapter sind meist über einen Systembus mit der CPU des Routers verbunden. Die CPU wiederum hält im Hauptspeicher des Rechners die Routingtabelle vor.

Wenn einer der Netzwerkadapter ein Datenpaket erhält, so verarbeitet er zunächst die Schicht-2-Protokolldaten, extrahiert dann das IP-Paket und reicht es zur weiteren Verarbeitung an die CPU weiter. Diese entnimmt dem Paketkopf die IP-Adresse des Zielrechn ers. Wenn nicht der Router selber adressiert ist, muß das Paket weitergeleitet werden. Dazu sucht die CPU in der Routingtabelle nach der passenden Next-Hop-Information. Die Next-Hop-Information beinhaltet zum einen die Nummer des Netzwerkadapters über den das Paket ausgegeben werden soll und zweitens die IP-Adresse des Next-Hop. Diese Adresse übergibt die CPU nun zusammen mit dem IP-Paket an den entsprechenden Netzwerkadapter. Dieser generiert daraus ein Schicht-2-Paket und sendet es ab.

Bei Hochgeschwindigkeitsnetzen im Gigabitbereich ist die oben beschriebene Struktur eines Routers nicht mehr adäquat. Die CPU und der Systembus müßten dabei die Summe der Übertragungsraten aller angeschlossenen Netzwerke verarbeiten können. Bei 2 GBit/s Datenübertragungsgeschwindigkeit entspricht das bei einer angenommenen Paketgröße von 1000 Bits bis zu zwei Millionen IP-Paketen pro Sekunde und Netzwerkanschluß (siehe [DBCP97]). Bei solchen Hochleistungsroutern geht man dazu über, die Aufgabe des Weiterleitens von IP-Paketen den einzelnen Netzwerkadaptern zu übertragen. Die Netzwerkadapter erhalten zu diesem Zweck eine eigene CPU und Speicher, in dem sich eine Kopie der zentralen Routingtabelle des Routers befindet. Trifft bei diesem Routermodell ein IP-Paket bei einem der Adapter ein, bestimmt dieser den Next-Hop und gibt das Paket direkt an den entsprechenden Ausgangsadapter weiter. Die CPU des Routers ist nur noch für die Ausführung der Routingprotokolle und die Verwaltung der zentralen Routingtabelle sowie anderer administrativer Aufgaben zuständig. Die zentrale Routingtabelle wird im Fall einer Änderung anschließend in die Speicher der einzelnen Netzwerkadapter kopiert [DBCP97].

Die Routingtabelle

Es wird nun erklärt werden, mit welchen Datenstrukturen eine Routingtabelle realisiert werden kann. Eine einfache Tabelle über alle 2³² (bei IPv4) bzw. 2¹²⁸ (bei IPv6) möglichen IP-Adressen wäre zwar für IPv4 machbar aber wirtschaftlich unsinnig. Schließlich kann ein Router über die direkt mit ihm verbundenen Netze nur maximal einige tausend Rechner erreichen. In der Regel sind es sogar weniger als hundert (laut [DBCP97]).

Longest Matching Prefix

Die IP-Adressen sind nicht einzeln wahllos auf Rechner in der ganzen Welt verstreut worden. Bei IPv4 ist der Adreßraum in fünf verschiedene Klassen A-E unterteilt worden. Jede IPv4-Adresse besteht aus einer Klassenkennung, einer Netzadresse, einer möglichen Subnetzadresse und einer Rechneradresse (siehe Abbildung 3). Jede Organisation im Internet bekommt eine Netzadresse aus einer bestimmten Klasse zugewiesen. Mit den Netzadressen der verschiedenen Klassen sind unterschiedliche Kontingente von Rechneradressen verbunden, je nachdem wie viele Adressen von einer Organisation benötigt werden. So sind die Netzadressen der Klasse B 14 Bit lang, und für die Adreßverteilung innerhalb einer Organisation stehen 16 Bit zur Verfügung. Für die mögliche Aufteilung in Subnetze und die Verteilung der Adressen an einzelne Rechner innerhalb der Organisationen sind diese selber zuständig.

Bei IPv6 gibt es die Unterteilung in Klassen nicht mehr. Statt dessen gibt es verschiedene Typen von Adressen. Innerhalb dieser Typen weisen die IPv6-Adressen eine ähnliche Struktur auf wie oben beschrieben mit dem Unterschied, daß eine feinere und flexiblere Abstufung vorgenommen wird als die starre Aufteilung in Netzadresse und Rechneradresse innerhalb der IPv4-Klassen.

Um in der Routingtabelle nicht einen Eintrag pro IP-Adresse zu benötigen, werden mehrere hintereinander liegende IP-Adressen, die eine identische Next-Hop-Information aufweisen, in einem Eintrag zusammengefaßt. Ein Eintrag enthält dann neben der Next-Hop-Information einen Adreßpräfix (Präfix - lat. Vorsilbe), der den Bereich der zusammengefaßten Adressen beschreibt. Zum Beispiel werden die (fiktiven) Adressen 1110 und 1111, wenn sie identische Next-Hop-Informationen besitzen, in einem Eintrag mit dem Präfix 111 zusammengefaßt. Auf diese Weise können allerdings nur Adressen zusammengefaßt werden, die durch einen gemeinsamen Präfix eindeutig beschreibbar sind. So weisen die Adressen 1101 und 1110 zwar das gemeinsame Präfix 11 auf, allerdings beschreibt dieses Präfix auch die Adressen 1100 und 1111. Die Zuordnung des Präfixes zu den beiden Adressen ist hier also nicht eindeutig. Trotzdem können auf diese Weise ganze Bereiche von Adressen in einem Eintrag zusammengefaßt werden.

So können in der Regel immer mindestens alle Rechneradressen der einzelnen Organisation zusammengefaßt werden. Das Adreßpräfix des Eintrags entspricht dann der Netzadresse dieser Organisation. Nur wenn ein Router sich innerhalb einer Organisation befindet, muß er eine genauere Zuordnung vornehmen.

Eine weitere Zusammenfassung von Einträgen ergibt sich aus der folgenden Überlegung. Angenommen alle IP-Adressen, die das gemeinsame Präfix P1 = 111 aufweisen, besitzen identische Next-Hop-Informationen und werden in einem einzigen Eintrag in der Routingtabelle zusammengefaßt. Dieser Eintrag deckt dann einen bestimmten Bereich (A) aus dem IP-Adreßraum ab (siehe Abbildung 4). In diesem Bereich A befindet sich nun ein kleinerer Teilbereich B von IP-Adressen, die eine von den übrigen Adressen im Bereich A abweichende Next-Hop-Information besitzen. Dieser Bereich B sei durch das Präfix P2 = 11101 repräsentiert. Auf diese Weise würde der Bereich A in drei Teilbereiche aufgespalten, die durch drei Einträge in der Routingtabelle mit den Präfixen P1a = 11100, P2 = 11101 und P 1b = 1111 beschrieben werden müßten, wobei die Einträge mit P1a und P1b identische Next-Hop-Informationen enthalten würden. Statt dessen speichert man nur zwei Einträge mit den Präfixen P1 und P2. Wird nun für eine Adresse nach einem Eintrag mit passendem Präfix gesucht, so wählt man den Eintrag mit dem längsten passenden Präfix (auf englisch: Longest Matching Prefix, im folgenden LMP genannt). Für Adressen aus dem Bereich B ist P2 der LMP und für Adressen aus den übrigen Teilbereichen von A ist es P1. Auf diese Weise ist eine eindeutige Zuordnung von Adressen zu einem bestimmten Tabelleneintrag sichergestellt.

Man könnte nun annehmen, eine Routingtabelle enthält zu jedem Next-Hop, den der Router kennt, nur genau ein Paar (Präfix, Next-Hop). Das wäre allerdings eine Idealsituation. Vielmehr ist es so, daß wie oben angedeutet bestimmte Adressen und Adreßbereiche m it identischer Next-Hop-Information nicht durch ein gemeinsames Präfix eindeutig beschrieben werden können und daher mehrere Einträge belegen. Auch können Adreßbereich mit identischer Next-Hop-Information nicht zusammenhängend sein. Das führt dazu, daß Tabellen größer werden als einige tausend Einträge. In [DBCP97] und [WVTP97] werden Tabellen mit 33.000 - 38.000 Einträgen als Beispiele verwendet. Dies und die Tatsache, daß bei schnellen Netzen nur wenig Zeit zum Weiterleiten eines Paketes bleibt, münden in der Forderung nach einer entsprechend schnellen Suchfunktion.

Aber auch die Verwaltungsfunktionen der Tabelle, wie Einfügen oder Löschen von Präfixen, dürfen nicht zu aufwendig realisiert werden, da mit Änderungen von Routinginformationen im Sekundenbereich oder häufiger zu rechnen ist. Auch spielt die Größe der Tabelle eine Rolle. Zum einen kostet Speicherplatz - wenn auch immer weniger - Geld. Zum zweiten kann die Ausführungsgeschwindigkeit der Operationen auf der Tabelle gesteigert werden, wenn diese klein genug ist, um in den Second-Level-Cache eines Prozessors zu passen. Dies ist zum Beispiel bei der in [DBCP97] vorgestellten Datenstruktur der Fall.

Eine andere wichtige Frage in diesem Zusammenhang ist, ob die Realisierung in Software oder in Hardware erfolgen soll. Denn bei hohen Datenübertragungsraten stellt sich die Frage, ob eine Realisierung in Software zur Zeit schnell genug ist. Andererseits ist eine Sofwarerealisierung einer Hardwarelösung vorzuziehen, da sie bei mögliche Änderungen einfacher angepaßt werden kann. Sei es, weil man eine bessere Datenstruktur für die Routingtabelle entwickelt hat, oder weil der Speicher erweitert werden muß, weil die Tabelle zu groß geworden ist. Die Erweiterung des Speichers kann bei einer Hardwarelösung schwierig sein, wenn die Anzahl der vorhandenen Adreßleitungen erschöpft ist.

In den folgenden Betrachtungen wird häufig von der Anzahl der Einträge in der Routingtabelle und von der Anzahl der Bits einer IP-Adresse die Rede sein. Für die Anzahl der Einträge in der Routingtabelle wird daher N und für die Anzahl der IP-Adreßbits W eingeführt. Dabei ist W = 32 bei IPv4 und W =128 bei IPv6. Zwischen N und W gibt es einen einfachen Zusammenhang: N < 2^W. Die Angaben O( W ) und O( log₂ N ) zur Beschreibung der Komplexität von Algorithmen sind daher scheinbar äquivalent. Da N in der Regel deutlich kleiner ist als die Obergrenze 2^W, verdeutlicht die Angabe O( log₂ N ) aber einen geringeren Aufwand als O( W ).

Hashtabellen

Wünschenswert wäre eine Realisierung der LMP-Suche mit konstanter Komplexität. Hierfür würde sich die Verwendung von Hashtabellen anbieten, da sie ein nahezu konstantes Suchverhalten aufweisen. Die Verwendung von Hashtabellen ist jedoch nicht möglich oder zumindest sehr schwierig, weil eine Hashfunktion bei mehreren passenden Präfixen immer das LMP liefern müßte. Dazu müßte die Hashfunktion jedoch den jeweils aktuellen Zustand der Routingtabelle berücksichtigen.

Content Addressable Memories

Eine andere Lösung mit konstantem Suchaufwand wäre die Verwendung von Content Addressable Memories (CAMs). Das sind spezielle Halbleiterspeicher, die, anders als normale Speicher, nicht nur in der Lage sind, auf das Anlegen einer Speicheradresse, deren Inhalt zurück zu liefern, sondern bei denen man ein Datum anlegen kann, und daraufhin die Adresse der Speicherzelle, die dieses Datum als Inhalt besitzt, zurückbekommt. Freilich führen diese Bausteine nur einen Vergleich mit der kompletten Adresse durch. Für die Such nach dem LMP müßte man eine spezielle Art der CAMs, sog. ternäre CAMs, benutzen. Diese speichern zusätzlich zum Datum eine Maske, mit der sich dann ein Präfix beschreiben ließe. Bei Anlegen einer IP-Adresse würden diese dann tatsächlich die Adresse des LMP zurückliefern. Allerdings sind CAMs sehr teuer und ternäre CAMs sind zudem sehr schwer zu beschaffen [Harb97].

Binärbäume

Die Kenntnis der allgemeinen Struktur eines Binärbaums wird vorausgesetzt. Jeder Baumknoten entspricht einem Eintrag der Routingtabelle. Er ist folglich ein Paar aus (Präfix, Next-Hop). In der Wurzel befindet sich ein Defaulteintrag mit einem Präfix der Länge 0. Dieser Präfix paßt somit zu jeder beliebigen Adresse. Der Next-Hop-Eintrag der Wurzel enthält die Adresse des sog. Default-Routers. Zu diesem Router werden alle IP-Pakete mit Adressen weitergeleitet, die der Router (noch) nicht kennt.

Die Suche nach dem LMP beginnt bei der Wurzel. Wenn das Präfix des jeweils aktuellen Knotens zur IP-Adresse paßt, wird sich den Knoten als vorläufig bestes Ergebnis gemerkt. Paßt der Präfix zur Adresse wird die Suche im linken Teilbaum fortgesetzt, ansonsten im rechten. Die Suche ist beendet, sobald man ein Blatt erreicht hat. Der gemerkte Knoten enthält dann das LMP.

Der Aufwand für die Suche nach dem LMP ist demnach O( log₂ N ), wenn der Baum vollständig ausbalanciert ist. Hier liegt jedoch ein Nachteil des Binärbaums. Durch ungeschicktes Einfügen und Löschen von Einträgen kann ein Binärbaum aus der Balance geraten. Im schlimmsten Fall degeneriert er zu einer linearen Liste, die einen Suchaufwand O( N ) aufweist. Dies muß durch entsprechende Balancemaßnahmen bei den Einfüge- und Löschoperationen verhindert werden. Das Ausbalancieren eines Binärbaumes ist jedoch recht komplex, da dabei u. U. die Struktur des ganzen Baumes verändert werden muß. Wünschenswert sind deshalb Einfüge- und Löschoperationen, die ein Ungleichgewicht des Baumes von vornherein weitgehend vermeiden.

Tries

Tries sind eine besondere Form von Bäumen. Sie sind eine in der Praxis häufig benutzte Datenstruktur für Routingtabellen. Der prinzipielle Aufbau einer Routingtabelle auf Basis eines Tries zeigt Abbildung 5. Wie auch beim Binärbaum befindet sich an der Wurzel des Baumes meist ein Defaulteintrag. Jeder Knoten des Tries, der kein Blatt ist, ist immer die Wurzel eines Unterbaumes. In einem Trie ist der Präfix in einer Unterbaumwurzel ein Präfix aller übrigen in diesem Unterbaum enthaltenen Präfixe.

Im Gegensatz zum Binärbaum liegt aufgrund dieser Struktur die Ausprägung eines Tries für eine Menge von konkreten Einträgen fest, d.h. sie hängt nicht von der Reihenfolge der Einfüge- und Löschoperationen ab. Deshalb ist auch ohne besondere Ausbalancierungsmaßnahmen bei diesen Operationen eine maximale Tiefe W des Tries garantiert.

Für die Suche nach dem LMP gibt es zwei denkbare Algorithmen:

1. Die Suche beginnt mit der Wurzel. Wenn das Präfix des aktuellen Knotens zur IP-Adresse paßt, wird sich den Knoten als vorläufig bestes Ergebnis gemerkt. Der Zustand desjenigen Bits der IP-Adresse, dessen Nummer der aktuellen Ebene im Baum entspricht, entscheidet darüber, ob die Suche mit dem linken oder rechten Unterbaum fortgesetzt wird. Ist der betreffende Unterbaum leer, ist die Suche an dieser Stelle beendet. Der gemerkte Knoten enthält dann das LMP. Der Aufwand für die Suche beträgt demnach O( W ).
2. Die Suche beginnt mit der Wurzel. Zunächst wird im Baum an einem Ast bis zu einem Blatt hinabgewandert. Der Ast wird aufgrund der Bits in der IP-Adresse bestimmt, wie beim ersten Algorithmus beschrieben. Bei einem leeren Unterbaum angekommen, wandert man denselben Ast wieder nach oben und vergleicht dabei die Präfixe mit der Adresse. Das erste passende Präfix ist das LMP und die Suche ist beendet. Der Suchaufwand beträgt hier O( 2W ).

Der zweite Algorithmus benötigt also im Extremfall doppelt so viele Schritte wie der erste. Präfixvergleiche sind aber bei einer Realisierung in Software relativ aufwendig. Der Vorteil des zweiten Algorithmus ist, daß beim Hinabwandern im Baum zunächst keine Vergleiche stattfinden. Beim Rückweg werden dann im Durchschnitt nur halb so viele Präfixvergleiche benötigt wie beim ersten Algorithmus. Nachteilig ist, daß die Knoten beim zweiten Algorithmus, um ein Zurückwandern im Baum zu ermöglichen, zusätzlich einen Verweis auf den Vorgängerknoten enthalten müssen.

Datenstrukturen für Routingtabellen

Im folgenden werden nun kurz vier verschiedene Datenstrukturen für Routingtabellen vorgestellt und deren Vor- und Nachteile erläutert.

Hardware Routingtabelle

Grundlegende Idee dieser Lösung [Harb97] war es, die Routingtabelle und Suchoperation aus Geschwindigkeitsgründen in Hardware zu realisieren. Ergebnis des Projektes ist ein Prototyp in Form einer Erweiterungskarte für den Systembus (ISA-Bus) eines normalen PCs (siehe Abbildung 6).

Als Basis der Datenstruktur dient dabei ein Binärbaum. Um nicht für jeden Knoten Speicher für die bei IPv6 maximal mögliche Präfixlänge von 128 Bit zu verschwenden, wird die gesuchte IP-Adresse in kleinere, gleich lange Stücke geteilt. In jedem Baumknoten befindet sich ein entsprechend langes Teilstück eines Präfix. Von der Wurzel beginnend wird nun zunächst das erste Stück der IP-Adresse mit dem ersten Stück eines Präfix verglichen (sehr kurze Präfixe passen dabei in ein Teilstück). Ist der Vergleich des ersten Teilstücks abgeschlossen, wird durch ein spezielles Flag in der Datenstruktur angezeigt, daß der Vergleich mit dem nächsten Teilstück von IP-Adresse und Präfixen fortgesetzt werden soll. Auf diese Weise benötigen kurze Präfixe weniger Speicher und längere Präfixe mit identischem vorderen Teil teilen sich für den vorderen Teil einen Eintrag.

Unter der Voraussetzung, daß der Baum ausbalanciert ist, beträgt die Komplexität der Suche demnach O( log₂ N ), das entspricht maximal 128 Suchschritte für IPv6. Der Prototyp wird mit einer Taktfrequenz von 8 MHz betrieben. In jedem Taktzyklus wird ein Suc hschritt ausgeführt. D.h. für die gesamte Suche werden ca. 16µs benötigt. Bei Verwendung eines FPGA (Field Programmable Gate Array) (Xilinx 3020LCA mit 120 MHz) für die Steuerlogik und schnellerem Speicher, ließe sich die Suchzeit bei 128 Schritten auf ca . 1µs senken.

Um die Balance des Baumes zu waren, müßte dieser bei Einfüge- und Löschoperationen entsprechend ausbalanciert werden. Alternativ könnte man, wie oben beschrieben, im Hauptspeicher eine zweite Routingtabelle vorhalten, die als Vorlage für die in der Erweiterungskarte dient. In diesem Fall kann man nach jeweils mehreren Einfüge- oder Löschoperationen an der Hardwaretabelle, diese zunächst im Hauptspeicher neu erzeugen und dann auf die Erweiterungskarte herunterladen.

Dynamic Prefix Trie

Dieser Ansatz (siehe [DKN96]) beruht auf einem Trie. Der Aufbau eines Baumknotens ist in Abbildung 7 dargestellt. Er enthält drei Zeiger, die auf den übergeordneten Knoten und auf den linken und rechten Unterbaum verweisen. Weiterhin enthält ein Knoten Zei ger auf zwei Prä fixe (hier Keys genannt). Das Indexfeld enthält die Nummer der Bitstelle, ab der die beiden Präfixe des Knotens einen Unterschied aufweisen. Dabei bildet das Präfix, der an dieser Stelle eine Null enthält, immer den LeftKey und das Präfix mit einer Eins an dieser Position den RightKey. Der Index erhöht sich mit jeder Baumebene um mindestens Eins.

Da die Datenstruktur auf einem Trie beruht ist eine maximale Tiefe des Baumes garantiert. Das sind bei IPv4 maximal 32 und bei IPv6 maximal 128 Ebenen.

Die Präfixsuche beruht auf dem zweiten der für Tries beschriebenen Suchalgorithmen. D.h. man wandert erst an einem Ast hinab bis zu einem Blatt. Dabei entscheidet das Adreßbit mit der Nummer, die durch das Indexfeld des jeweiligen Knoten beschrieben wird, ob mit dem linken oder rechten Unterbaum fortgefahren wird. Auf dem Rückweg ist dann das erste passende Präfix das gesuchte LMP. Der Aufwand für die Suche ist demnach O( 2W ). Da der Algorithmus sehr einfach ist, ist ein Beschleunigung der Suche durch eine Realisierung in Hardware möglich.

Die Einfüge- und Löschoperationen haben lediglich lokal begrenzte Auswirkungen auf die Struktur des Baumes, weil aufgrund der garantierten maximalen Tiefe des Baumes keine Ausgleichsoperationen benötigt werden. Für das Einfügen von Präfixen beträgt der Auf wand O( 2W ) und für das Löschen O( W ).

Binary Tree with Chunks

Die in [DBCP97] beschriebene Datenstruktur ist als Softwarelösung für die Anwendung in Hochleistungsroutern auf Basis von IPv4 entwickelt worden. Sie ist deshalb auf eine möglichst schnelle Präfixsuche optimiert. Eine Realisierung in Hardware ist jedoch möglich. Im folgenden wird zunächst der Aufbau der Struktur für IPv4 erklärt. Die sich im Zusammenhang mit IPv6 ergebenden Änderungen werden weiter unten besprochen.

Der Ansatz beruht ebenfalls auf einem binären Trie. In der Vorstellung kann man sich zunächst einen Baum mit 32 Ebenen, der eine statische Struktur aufweist, vorstellen. An der Wurzel befindet sich der Defaulteintrag mit der Präfixlänge Null. Ebene 1 enthält die Präfixe der Länge 1, Ebene 2 die Präfixe der Länge 2, usw. In der untersten (32.) Ebene befinden sich dann 2³² Blätter, die die Gesamtzahl der möglichen IP-Adressen repräsentieren.

Diese Struktur wäre bei direkter Umsetzung natürlich viel zu groß. Zur Realisierung wird der Baum deshalb in drei Stufen unterteilt. Die erste Stufe umfaßt die Ebenen 0 bis 16 des Baumes, die zweite Stufe die Ebenen 17 bis 24 und die dritte Stufe die Ebenen 25 bis 32 (Abbildung 8).

Die erste Stufe wird im wesentlichen durch ein Bitfeld mit 2¹⁶ Einträgen realisiert. Diese entsprechen den möglichen Blättern der ersten Stufe. Jeder nicht leere Eintrag repräsentiert entweder ein Präfix oder einen Verweis auf jeweils einen Unterbaum in der nächsten Stufe. Die zweite und dritte Stufe bestehen dem entsprechend aus einer Anzahl Unterbäumen, die der Anzahl der Verweise in der jeweils nächst höheren Stufe entspricht. Die Unterbäume heißen in [DBCP97] Chunks und besitzen die gleiche Struktur, wie die erste Ebene mit dem Unterschied, daß das Bitfeld lediglich 2⁸ = 256 Einträge umfaßt.

Da jede der unteren Ebenen 8 Bit einer IP-Adresse umfaßt, muß für IPv6 die Anzahl der Ebenen um 12 weitere auf insgesamt 15 erhöht werden.

Da die Suche nach dem LMP in den einzelnen Stufen konstanten Aufwand aufweist, werden demnach für die Suche in der gesamten Tabelle maximal 3 Schritte (IPv4) bzw. 15 Schritte (IPv6) benötigt. Der Aufwand beträgt also O( W/8 ) (genauer O( W/8 - 1 )). Pro Stufe müssen dabei nur wenig Befehle ausgeführt werden.

Ein weitere Beschleunigung der Suche entsteht durch die Kompaktheit der Datenstruktur. Bei einem Umfang der Tabelle (IPv4) von 30.000 - 40.000 Einträgen beträgt die Größe der Tabelle nur ca. 150 - 170 kBytes. Sie paßt deshalb vollständig in den 2nd-Level-Cache einer Intelmaschine. Die maximale Suchzeit auf einem Pentium Pro mit 200 Mhz betrug bei Testmessungen 505 ns. Das entspricht einem Durchsatz von mindestens 2 Millionen IP-Paketen pro Sekunde.

Einfüge- und Löschoperationen sind von den Autoren nicht vorgesehen worden. Die Idee ist vielmehr, daß die Datenstruktur als reine Suchtabelle dient. Daneben befindet sich eine zweite Tabelle im Router, die zum Einfügen und Löschen von Präfixen besser geeignet ist. Wenn sich diese Tabelle geändert hat, wird aus ihr eine neue Suchtabelle generiert und gegen die alte ausgetauscht.

Hashing with Binary Search

Dieser Vorschlag (siehe [WVTP97]) für Routingtabellen basiert auf Hashtabellen und ist, wie der vorherige Ansatz, als Softwarelösung für Hochleistungsrouter konzipiert. Auch bei dieser Lösung ist eine Realisierung in Hardware möglich.

Die oben erwähnten Probleme bei der Suche des LMP in Hashtabellen wird bei dieser Datenstruktur vermieden, indem für jede Präfixlänge eine eigene Hashtabelle angelegt wird (siehe Abbildung 9). Die Tabellen befinden sich der Präfixlänge nach sortiert in einem Feld mit 32 bzw. 128 Einträgen.

Um das LMP zu finden wird eine binäre Suche (Intervallhalbierung) über dieses Feld von Hashtabellen durchgeführt. Für eine binäre Suche werden maximal log₂ <#Hashtabellen> Schritte benötigt. D.h. die Suche ist nach maximal 5 Schritten (IPv4) bzw. 7 Schritten (IPv6) abgeschlossen. Der Aufwand für die LMP-Suche beträgt also O( log₂ W). Dies trifft jedoch nur zu, wenn der Aufwand für die Suche in den einzelnen Hashtabellen nahezu konstant (O( 1 )) ist. Die Schwierigkeit bei diesem Ansatz liegt also im Auffinden einer möglichst optimalen Hashfunktion. Über die in [WVTP97] verwendete Hashfunktion wird in dem Artikel nichts gesagt.

Nachteilig ist der aufwendige innere Aufbau dieser Datenstruktur. Denn die binäre Suche über die Hashtabellen ist so einfach, wie sie oben in der gebotenen Kürze beschrieben wurde, gar nicht möglich. Damit sie trotzdem funktioniert, mußten viele Tricks und Kniffe angewendet werden, die die Datenstruktur verkomplizieren. Das Einfügen und Löschen von Präfixen ist deshalb sehr komplex. Ähnlich wie bei der Hardware-Routingtabelle kann diese Komplexität noch etwas verringert werden, wenn man in Kauf nimmt, daß die Datenstruktur nach mehreren Änderungen mit Hilfe einer Referenztabelle neu aufgebaut wird.

Für IPv4 und einer optimierten Datenstruktur wird für eine reale Routingtabelle mit ca. 33.000 Einträgen eine maximale Suchzeit von 450 ns angegeben.

Die aufwendige Struktur schlägt sich auch in einem höheren Speicherverbrauch nieder. Bei 33.000 Einträgen (IPv4) verbraucht die Tabelle 1,2 bis 1,4 Mbyte. Das ist knapp das zehnfache des Verbrauchs der vorigen Lösung.

Zusammenfassung

In Tabelle 1 sind noch einmal kurz die wichtigsten Eigenschaften der vorgestellten Datenstrukturen zusammengefaßt. Die Angaben zum Speicherverbrauch dienen nur dem Vergleich der hier vorgestellten Datenstrukturen miteinander. Auch die Angaben zum Aufwand beim Einf ügen und Löschen von Einträgen dienen nur der groben Orientierung, da ein direkter Vergleich der Ansätze nicht möglich war. Die tatsächliche Effizienz dieser Funktionen hängt auch von der konkreten Implementierung ab.

* Falls auf ein Ausbalancieren des Baumes verzichtet wird.
Tabelle 1: Übersicht über die wichtigsten Eigenschaften der vorgestellten Datenstrukturen

Der DP-Trie ist eine ausgewogene Lösung. Er bietet eine Suchfunktion mit garantierter maximaler Laufzeit und ebenso effiziente Einfüge- und Löschoperationen. Da die Suche aber bis zu 128 Schritte benötigt, eignet er sich eher für Router in Umgebungen mit niedrigeren Datenübertragungsraten oder als zentrale Routingtabelle in Hochleistungsroutern, wie sie im Abschnitt 1.2 beschrieben wurden.

Die PC-Erweiterungskarte besitzt eine etwas geringere Suchkomplexität als der DP-Trie. Durch die Realisierung in Hardware wird die Suche zudem erheblich beschleunigt. Durch Zusammenfassung der diskret aufgebauten Steuerlogik auf einem FPGA und der Verwendung von schnelleren Speicherhalbleitern wäre eine weitere Steigerung der Geschwindigkeit zu erreichen.

Die beiden anderen Verfahren (Binary Tree with Chunks und Hashing with Binary Search) bieten aufgrund ihrer Auslegung als »Hochleistungstabellen« die schnellsten Suchfunktionen. Diese kompromißlose Auslegung als Suchtabelle macht jedoch das Einfügen und Löschen von einzelnen Einträge sehr aufwendig. Sie setzen deshalb eine zentrale Routingtabelle voraus, aus der bei Bedarf eine neue Suchtabelle erzeugt werden kann. Der Binary Tree with Chunks scheint mir für IPv4 die sinnvollere Alternative zu sein, da er bei ungefähr gleicher Suchgeschwindigkeit eine einfachere Struktur aufweist und weniger Speicher verbraucht. Bei IPv6 steigt bei dieser Lösung die Suchdauer linear mit der Zahl der Adreßbits an. Das Hashing with Binary Search weist dabei nur einen logarithmischer Anstieg auf, so daß die Geschwindigkeit der Suche bei IPv6 hierbei dann höher liegen dürfte als beim Binary Tree with Chunks.

Welcher der vorgestellten Lösungen der Vorzug zu geben ist, hängt also stark vom geplanten Einsatzgebiet ab.

Literaturverzeichnis

[BrZi96] T. Braun, M. Zitterbart: Hochleistungskommunikation, Band 2: Trans­portdienste und -protokolle, R. Oldenbourg Verlag, 1996, ISBN 3-486-23088-3

[DBCP97] M. Degermark, A. Brodnik, S. Carlsson, S. Pink: Small Forwarding Tables for Fast Routing Lookups, Communications of the ACM, No. 9/1997, S. 3-14

[DKN96] W. Doeringer, G. Karjoth, M. Nassehi: Routing on Longest-Matching Prefixes, IEEE/ACM Transactions on Networking, Vol. 4, No. 1, Febr. 1996, S. 86-97

[Harb97] T. Harbaum: Entwurf und Realisation einer Routingtabelle für einen IPv6-Router, Studienarbeit, Institut f. Betriebssysteme u. Rechnerverbund, Technische Universität Braunschweig, 1997, http://www.ibr.cs.tu-bs.de/~harbaum/

[KoBu94] W. P. Kowalk, M. Burke: Rechnernetze - Konzepte und Techniken der Datenübertragung in Rechnernetzen, B. G. Teubner Stuttgart, 1994, ISBN 3-519-02141-2

[WVTP97] M. Waldvogel, G. Varghese, J. Turner, B. Plattner: Scalable High Speed IP Routing Lookups, Communications of the ACM, No. 9/1997, S. 25-35