Direkt zum Inhalt | Direkt zur Navigation

Eingang zum Volltext

Lizenz

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bsz:25-opus-63718
URL: http://www.freidok.uni-freiburg.de/volltexte/6371/


Maindorfer, Christine

Algorithms and data structures for IP lookup, packet classification and conflict detection

Algorithmen und Datenstrukturen für IP Lookup, Paketklassifikation und Konflikterkennung

Dokument1.pdf (2.533 KB) (md5sum: 4d0ec8f814be4ec299f07c4ac15ca1d8)

Kurzfassung in Englisch

The major task of an Internet router is to forward packets towards their final
destination. When a router receives a packet from an input link interface, it uses its destination address to look up a routing database. The result of the lookup provides the next hop address to which the packet is forwarded. Routers only need to determine the next best hop toward a destination, not the complete path to the destination. Changes in network topologies due to physical link failures, link repairs or the addition of new routers and links lead to updates in the routing database. Since the performance of the lookup device plays a crucial role in the overall performance of the Internet, it is important that lookup and route update operations are performed as fast as possible. To accelerate lookup and update operations, routing tables must be implemented in a way that they can be queried and modified concurrently by several processes. Relaxed balancing has become a commonly used concept in the design of concurrent search tree algorithms.
The first part investigates the hypothesis that a relaxed balancing scheme is better suited for search-tree based dynamic IP router tables than a scheme that utilizes strict balancing. To this end we propose the relaxed balanced min-augmented range tree and benchmark it with the strictly balanced variant using real IPv4 routing data. Further, in order to carry out a plausibility consideration, which corroborates the correctness of the proposed locking schemes, we present an interactive visualization of the relaxed balanced min-augmented range tree.
Enhanced IP routers further provide policy-based routing (PBR) mechanisms,
complementing the existing destination-based routing scheme. PBR provides a
mechanism for implementing Quality of Service (QoS), i.e., certain kinds of traffic
receive differentiated, preferential service. Besides QoS, PBR further provides a mechanism to enforce network security policies. PBR requires network routers to examine multiple fields of the packet header in order to classify them into flows. Flow identification entails searching a table of predefined filters to identify the appropriate flow based on criteria including source and destination IP address, ports, and protocol type. Geometrically speaking, classifying an arriving packet is equivalent to finding the best matching hyperrectangle among all hyperrectangles that contain the point representing the packet.
The R-tree and its variants have not been experimentally evaluated and bench-
marked for their eligibility for the packet classification problem.
In the second part we investigate if the popular R*-tree is suited for packet classification. For this purpose we will benchmark the R*-tree with two representative
classification algorithms in a static environment. Most of the proposed classification algorithms do not support fast incremental updates. If the R*-tree shows to be
suitable in a static scenario, then the benchmark is a stepping stone
for benchmarking R*-trees in a dynamic environment.
If a packet matches multiple filters, a tiebreaker is used in order to determine
the best matching filter among all matching filters. However, not every policy can be enforced by assigning priorities. In these cases, MSTB should be used instead. Yet, the most specific tiebreaker is only
feasible if for each packet p the most specific filter that applies to p is well-defined.
If this is not the case, the filter set is said to be conflicting.
In the last part of the thesis we propose a conflict detection and resolution algorithm for static one-dimensional range tables, i.e., where each filter is specified by an arbitrary range. Further, we show that by making use of partial persistence, the structure can also be employed for IP lookup.


Kurzfassung in Deutsch

Die Hauptaufgabe eines Internet-Routers besteht in der Weiterleitung von Paketen.
Im Falle, dass mehrere Präfixe in der Routertabelle
mit der Zieladresse übereinstimmen, wird in der Regel eine Strategie gewählt, die als "Longest Prefix Matching" bekannt ist. Zur Lösung dieses sogenannten IP-Lookup-Problems sind
zahlreiche Algorithmen und Datenstrukturen vorgeschlagen worden.
Da die Performanz der IP-Lookup-Einheit einen entscheidenden Einfluss auf die Gesamtperformanz des Internets hat, ist
es entscheidend, dass IP-Lookup sowie Aktualisierungen so schnell wie möglich
durchgeführt werden. Um zu sichern, dass auf Suchbäumen basierte dynami-
sche Routertabellen nicht durch Updates degenerieren, unterlegt man diese mit
einer balancierten Suchbaumklasse. Relaxierte Balancierung ist ein gebräuchliches Konzept im Design von nebenläufig implementierten Suchbäumen.
Der erste Teil dieser Dissertation untersucht die Hypothese, dass ein relaxiert
balanciertes Schema für dynamische Routertabellen besser geeignet ist als ein
Schema, welches strikte Balancierung verwendet. Dazu schlagen wir den relax-
iert balancierten min-augmentierten Bereichssuchbaum vor und vergleichen diesen
mit der strikt balancierten Variante im Rahmen eines Benchmarks.
Des Weiteren stellen IP-Router "Policy basierte" Routing-Mechanismen (PBR) zur
Verfügung.
Um PBR zur Verfügung stellen zu können, müssen Router mehrere Paketfelder wie zum
Beispiel die Quell- und Zieladresse, Port und Protokoll inspizieren, um Pakete
in sogenannte "Flows" zu klassifizieren. Geometrisch gesprochen werden Filter durch d-dimensionale Hyperrechtecke und Pakete durch d-dimensionale
Punkte repräsentiert. Paketklassifikation bedeutet nun, für ein weiterzuleiten-
des Paket das am besten passende Hyperrechteck zu finden, welches den Punkt
enthält.
Im zweiten Teil werden wir eruieren, ob der weitverbreitete R*-Baum zur Lösung
dieses Problems geeignet ist. Dazu wird dieser mit zwei repräsentativen statischen Klassifizierungsalgorithmen im Rahmen eines Benchmark-Tests verglichen. Erweist sich der R*-Baum als geeignet, ist dieses Benchmark ein Sprungbrett fÄur eine Untersuchung im dynamischen Fall.

Falls mehrere Filter auf ein weiterzuleitendes Paket anwendbar sind, wird ein sogenannter Tiebreaker verwendet, um den am besten passenden Filter zu bestimmen.
Es wurde festgestellt, dass nicht jede Policy durch die Vergabe von Prioritäten durchgesetzt werden kann und
vorgeschlagen, in jenen FÄallen den "spezifischsten Filter" Tiebreaker anzuwenden.
Jedoch ist dieser Tiebreaker nur realisierbar, wenn für jedes Paket der spezifischste Filter wohldefiniert ist. Ist dies nicht der Fall, sagt man, die Filtermenge sei widersprüchlich.
Im letzten Teil dieser Dissertation schlagen wir einen Algorithmus zur Konflikt-
aufdeckung und Beseitigung für den statischen eindimensionalen Fall vor, wobei
jeder Filter durch ein beliebiges Intervall spezifiziert ist. Weiterhin zeigen wir, dass wenn zur Lösung dieses Problems eine partiell persistente Datenstruktur verwendet wird, diese Struktur auch IP-Lookup unterstützt.


SWD-Schlagwörter: Algorithmus
Freie Schlagwörter (deutsch): IP Lookup , Paketklassifikation , Konflikterkennung , relaxierte Balanzierung
Freie Schlagwörter (englisch): IP lookup , packet classification , conflict detection , relaxed balancing
Institut: Institut für Informatik
Fakultät: Technische Fakultät (bisher: Fak. f. Angew. Wiss.)
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Erstgutachter: Ottmann, Thomas (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 02.03.2009
Erstellungsjahr: 2009
Publikationsdatum: 10.03.2009
Indexliste