Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Evaluierung von Layer-2 Adress-Look-Up Techniken auf Multicore-Prozessoren

 
: Kraus, Daniel
: Knorr, Rudi; Strebelow, Ronald; Ungerer, Theo

Augsburg, 2012, 49 pp.
Augsburg, Univ., Bachelor Thesis, 2012
German
Bachelor Thesis
Fraunhofer ESK ()
multicore; Hash-Funktion; Hash-Tabelle; assoziative Datenstruktur; Map; Skip-List

Abstract
Durch den vermehrten Einsatz von Netzwerkprozessoren beim Aufbau von Netzwerkkomponenten werden immer mehr Aufgaben der Paketverarbeitung in Software realisiert. Um den immer wachsenden Anforderungen standhalten zu können, müssen effiziente Datenstrukturen und Algorithmen für die kritischen Komponenten verwendet werden. Ein wesentlicher und wichtiger Bestandteil einer Ethernet-Bridge ist die Filterdatenbank. Diese speichert MAC-Adressen und ordnet sie dem Port zu, über den das jeweilige Endgerät erreichbar ist. Empfängt die Bridge ein Paket, wird in der Filterdatenbank nach dessen Ziel-Adresse gesucht und das Paket auf dem gespeicherten Port weitergeleitet, falls ein Eintrag existiert. Da die Bridge für jedes eingehende Paket diesen Adress-Look-Up durchführen muss, beeinflusst die Zugriffszeit auf die Filterdatenbank auch maßgeblich die Verarbeitungsgeschwindigkeit der gesamten Bridge. Im Rahmen dieser Arbeit werden verschiedene Techniken zur Implementierung der Filterdatenbank hinsichtlich ihrer spezifischen Auswirkungen auf die Leistungsfähigkeit der Datenbank und der Weiterleitung von Nachrichten untersucht. Da für die Realisierung der Filterdatenbank durch eine Hash-Tabelle nicht nur eine effiziente Implementierung der Datenstruktur von Bedeutung ist, sondern auch die verwendete Hash-Funktion einen großen Einfluss hat, werden verschiedene Hash-Funktionen hinsichtlich vier Qualitätskriterien untersucht und verglichen. Weiter werden parallele Implementierungen für drei bekannte Datenstrukturen (Rot-Schwarz-Baum, B-Baum und Skip Liste) vorgestellt und bezüglich ihrer erwarteten Skalierbarkeit der Laufzeit bei Verwendung mehrerer Rechenkerne bewertet. Abschließend wird die Leistungsfähigkeit der besten Algorithmen und Datenstrukturen auf einer für die Paketverarbeitung spezialisierten Multicore-Plattform evaluiert.

: http://publica.fraunhofer.de/documents/N-273994.html