Kurzfassung

Aktuelle Peer-to-Peer Systeme wie CAN realisieren eine verteilte Hash-Tabelle. Diese Tabelle besteht aus (Key, Value) Paaren und ermöglicht das Nachschlagen von jeweils einem Value zu einem Key. Während CAN sehr gut skalierbar ist, sich robust gegenüber einzelnen Ausfällen zeigt und das Nachschlagen von Keys sehr effizient möglich ist, so sind keine Mehrbereichsabfragen oder sonstige komplexe Abfragen möglich. In dieser Ausarbeitung werden zwei Erweiterungen vorgestellt, welche Mehrbereichsabfragen ermöglichen und gleichzeitig die genannten Vorteile von CAN weiterhin erhalten.
Die erste Technik verwendet so genannte Hilbertfunktionen, mit denen sich Abfragen nach ganzen Intervallen von Attributwerten realisieren lassen. Außerdem wird das Problem von regelmäßigen Updates von Attributwerten betrachtet und mit Hilfe von einem Expressway und Caches gelöst. Diese ermöglichen in den meisten Fällen den Versand von Updates direkt per IP-Routing, welches schneller als das CAN-Routing ist.
Bei der zweiten Technik werden drei verschieden Arten der Suche unterstützt: (1) Die Suche nach einzelnen Wörtern, (2) Die Suche nach einem Bereich von Attributwerten mit Hilfe von Bereichssuchbäumen, (3) Die Suche nach dem längsten passenden Präfix zu einem gegebenen Ausdruck mit der binären Suche. Außerdem ermöglichen Bloom-Filter eine effiziente Repräsentation von Ergebnissen einzelner Unterabfragen. Hiermit können diese Ergebnisse über Mengenoperationen zum Endergebnis kombiniert werden, ohne viele unnötige Informationen über das Netzwerk zu übertragen.
Die erste Technik richtet sich speziell an der Verwaltung von Computational Grids, während die zweite Technik am File Sharing orientiert ist.
Benjamin Schnaidt

Downloads

	Paper		Komplette Ausarbeitung zum Thema Mehrbereichsabfragen in CAN.	5 MB
	Folien		Folien zum Vortrag.	5 MB

Zurück zur Hauptseite

. . . . .