Fast Longest Prefix Matching: Algorithms, Analysis, and Applications

Kurzfassung

 This abstract is also available in English.

Viele aktuelle Probleme erfordern effiziente Algorithmen zur Bestimmung der besten Übereinstimmung zwischen einem Suchwort und einer vorgegebenen Datenbank von jokerbehafteten Mustern. Allein der Netzwerkbereich liefert bereits diverse Anwendungen dafür. Die Geräte müssen den längsten passenden Präfix bestimmen, um Pakete weiterzuleiten oder virtuelle Verbindungen zu erstellen. In dienstintegrierenden Paketnetzwerken müssen die Pakete darüberhinaus noch feiner klassiert werden. Dies wird erreicht, indem bestimmte Felder aus den Paketen mit einer grossen Menge von Vergleichsmustern verglichen wird, wovon jedes Joker an möglicherweise beliebigen Positionen beinhalten kann. Aus den passendsten Mustern wird das mit der grössten Übereinstimmung gewählt. Neben dem Netzwerkbereich werden solche Algorithmen auch in vielen anderen Bereichen benötigt, so fuer geografische Informationssysteme oder persistente Datenbanken.

In dieser Arbeit beschreiben wir eine Klasse von Algorithmen zur Bestimmung des längsten passenden Präfixes. Sie alle basieren auf demselben Algorithmus, der eine gegebene Musterdatenbank, senkrecht zur Orientierung der Vergleichsmuster, in parallele Schichten zerteilt. Über diese Schichten wird dann eine modifizierte binäre Suche durchgeführt. Danach führen wir Schemata ein, welche es dem Basisalgorithmus erlauben, aus der Struktur der Datenbank zu ``lernen'' und sich ihr anzupassen. Desweiteren zeigen wir, wie unsere Algorithmen effizient implementiert werden können, sowohl mittels Standardkomponenten in Hardware als auch in Software auf beliebten Personalcomputern und Workstations.

Die hier vorgestellte Arbeit wurde durch aktuellen Forderungen im Internet initiiert. Seit der Einführung des World Wide Web ist die Zahl der Benutzer, Rechner, Domänen und Netzwerken, welche am Internet angeschlossen sind, am Explodieren. Es überrascht deshalb nicht, dass der Netzwerkverkehr an den wichtigen Austauschknoten sich alle paar Monate verdoppelt. Das Internet ist ein Paketnetzwerk, in welchem jedes Datenpaket von Router zu Router weitergeleitet wird, bis es sein Ziel erreicht. Aus Gründen der Vielseitigkeit und effizienten Ausnützung der vorhandenen Übertragungsbandbreite leitet im Internet jeder Router jedes Paket möglichst unabhängig von den anderen Routern und anderen, auch gleich adressierten, Paketen weiter.

Damit das Internet weiterhin mit den steigenden Bedürfnissen Schritt halten kann, müssen fünf Punkte erfüllt werden:

1. höhere Geschwindigkeiten auf den Datenleitungen,
2. besserer Durchsatz innerhalb der Router,
3. schnellere Entscheidung über die Paketweiterleitung,
4. rasche Anpassung an Topologie- und Laständerungen und
5. die Unterstützung von Dienstgüte (QoS).

Die Anzahl Speicherzugriffe der besten bekannten Techniken zur Präfixbestimmung ist proportional zur Länge der verglichenen Adressen. Unser neues Verfahren benutzt eine binäre Suche über Hashtabellen, welche nach Länge der Präfixe aufgeteilt ist. Es skaliert sehr gut mit dem Wachstum der Adresslängen und Routingtabellen: unabhängig von der Tabellengrösse werden maximal log₂(Adressbits) Hashzugriffe benötigt. Dadurch werden beim aktuellen Internetprotokoll Version 4 (IPv4) mit 32 Bit langen Adressen nur 5 Hashzugriffe gebraucht, oder 7 für das bevorstehende IPv6 mit 128 Adressbits. Wir führen ebenso mutierende binäre Suche sowie weitere Optimierungen ein, welche es erlauben, den schlechtesten Fall auf 4 Zugriffe zu limitieren sowie die Mehrzahl der Adressen in maximal 2 Zugriffen zu finden. Wir erwarten ähnliche Verbesserungen für IPv6.

Wir erweitern diese Verfahren zur Suche nach den beste Übereinstimmung für Tupel von mehreren Felden des Paketkopfes, welche für QoS-Unterstützung benötigt wird. Darüberhinaus zeigen wir die Vielseitigkeit der resultierenden Algorithmen, indem wir sie für so unterschiedliche Anwendungen einsetzen wie geografische Informationssysteme, Speicherverwaltung, Garbage Collection, persistente objekt-orientierte Datenbanken, Synchronisation in verteilten Datenbanken und Zugriffskontrolle von Webservern.

Dokumente

• Buch und PDF
• PDF (lokale Kopie, Kopie an der ETH-Bibliothek)
• Verwandte Dokumente (CiteSeer/ResearchIndex)
• Teil des Forwarding-Projekts

BibTeX-Eintrag

@Book{waldvogel00fast,
  Author =    {Marcel Waldvogel},
  Title =     {Fast Longest Prefix Matching: Algorithms, Analysis, and Applications},
  Publisher = {Shaker Verlag},
  Address =   {Aachen, Germany},
  Month =     apr,
  Year =      2000
}

@PhdThesis{waldvogel00fast-thesis,
  Author =    {Marcel Waldvogel},
  Title =     {Fast Longest Prefix Matching: Algorithms, Analysis, and Applications},
  School =    {ETH {Z\"urich}},
  Year =      2000,
  Month =     apr,
  Number =    13266
}