Effizientes Routing in verteilten skalierbaren Datenstrukturen

Abstract

Verteilte skalierbare Datenstrukturen (SDDS) besitzen große Bedeutung, insbesondere als Grundlage der Realisierung von innovativen Web-Diensten. Die Knoten einer SDDS verwalten (Schlüssel, Wert)-Paare sowie Kontaktinformation über andere Knoten. Diese Kontaktinformationen werden für das Routing von Nachrichten zwischen den SDDS-Knoten benötigt. Dieser Artikel untersucht, wie sich das Caching von Kontaktinformation und die Auswahl der Schlüsselabbildung, d.h. der Abbildung der Datenobjekte auf den Schlüsselraum der SDDS, auf das Routing auswirkt. Unser Hauptergebnis ist die Erkenntnis, dass Caching insbesondere in Verbindung mit einer nachbarschaftserhaltenden Schlüsselabbildung vorteilhaft ist.