Universität Ulm
Abteilung Verteilte Systeme
Dynamische Verwaltung
globaler Namensräume
Dissertation zur
Erlangung des Doktorgrades Dr. rer. nat.
der Fakultät für Informatik
der Universität Ulm
vorgelegt von
Alfred Josef Lupper
aus Holzheim
Ulm, im Juni 1997
Meiner Familie
Amtierender Dekan: Prof. Dr. Friedrich von Henke
1. Berichterstatter: Prof. Dr. Peter Schulthess
2. Berichterstatter: Prof. Dr. Michael Weber
Tag der Kolloquiumsprüfung: 19. September 1997
Diese Arbeit entstand im Rahmen der Forschungsarbeiten, die an der Abteilung für Verteilte Systeme der Universität Ulm im Zusammenhang mit der Entwicklung des verteilten Betriebssystems PluriX geleistet wurden. Im Sommer 1991 wurden die Arbeiten an diesem universellen Betriebssystem auf der Basis eines IBM-kompatiblen Personal Computers, aufgenommen. Im Zuge der Arbeiten an diesem verteilten Betriebssystem wurden Konzepte zur Namensverwaltung für Rechnersysteme, die über gemeinsamen verteilten Speicher gekoppelt sind, entwickelt und implementiert. Zur Erweiterung des Systems über den speichergekoppelten Rechnerverbund hinaus wurden die in der vorliegenden Arbeit dargestellten Konzepte zur dynamischen Verwaltung globaler Namensräume entwickelt.
Das erste Kapitel der Arbeit motiviert globale Namensverwaltungen vor dem Hintergrund der zunehmenden globalen Vernetzung und definiert die an Namensverwaltungen gestellten Anforderungen. Gleichzeitig wird eine Abgrenzung der Aufgaben verteilter Datenbanken und Kommunikationsdienste von der Namensverwaltung vorgenommen. Im Anhang der Arbeit wird ein umfassender Überblick über bestehende Konzepte zur Namensverwaltung in verteilten Systemen gegeben. Hierbei zeigte sich, daß die vorhandenen Konzepte erhebliche Nachteile bei der Verwaltung globaler Namensräume aufweisen. Die Konkretisierung dieser Schwächen führt zu den Konzepten der dynamischen globalen Namensverwaltung, die im letzten Abschnitt des ersten Kapitels vorgestellt werden. Kapitel 2 behandelt die Charakteristika verschiedenartiger Namenskonzepte und die adäquate Strukturierung von Namensräumen. Das dritte Kapitel beschreibt die Architektur der dynamischen globalen Namensverwaltung und die anhand der Netzwerkeigenschaften gegebenen Konfigurationsoptionen. Zentraler Punkt ist hierbei die selbständige Konfigurierung des hierarchischen Verwalternetzes. In Kapitel 4 werden die Konzepte zur dynamischen Verwaltung globaler Namensräume vorgestellt und diskutiert. Kapitel 5 befaßt sich mit Fragen der Replikation und Konsistenz globaler Namenseinträge und diskutiert Verfahren zur Steigerung der Fehlertoleranz globaler Namensverwaltungen. Kapitel 6 schließlich faßt die Ergebnisse der Arbeit zusammen und zeigt Perspektiven für die künftige Entwicklung dynamischer globaler Namensverwaltungen auf.
Nicht vergessen möchte ich, mich an dieser Stelle ganz herzlich bei denjenigen zu bedanken, die mit ihrer kritischen Meinung zum Zustandekommen dieser Arbeit beitrugen. Mein besonderer Dank gilt Herrn Prof. Dr. Peter Schulthess, dem es gelang, mich mit zahlreichen Anregungen für diese Aufgabe zu begeistern. Bedanken möchte ich mich auch bei Herrn Prof. Dr. Michael Weber, Herrn Dr. Konrad Froitzheim, Herrn Dr. Gerhard Partsch, Herrn Dr. Stefan Traub, Herrn Jürgen Geßwein und Herrn Piotr Dudzik für die zahlreichen konstruktiven Diskussionen und wertvollen Anregungen.
Vor allen Dingen aber bin ich meiner Familie zu Dank verpflichtet. Sie hat oft mit Geduld meine wechselnden Stimmungen ertragen, die sich durch das Auf und Ab während der Erstellung dieser Arbeit ergaben. Oft mußte die Familie bei Gelegenheiten auf mich verzichten, bei denen gerade ein Vater gefordert ist. Schließlich gilt mein besonderer Dank meinen Eltern, die mich in all den Jahren auf meinem Weg wohlwollend unterstützt haben. Ihre optimistische Lebenseinstellung und ihr Aktivismus waren mir stets Vorbild und gaben mir nicht selten den Ansporn weiterzumachen.
Auszug aus der Titelseite der Computer Zeitung vom 31. Oktober 1996, Jahrgang 27, Nr. 44
Vorwort................ iii
Inhaltsverzeichnis.................. v
Zusammenfassung vii
1 Motivation und Abgrenzung............. 1
1.1 Anforderungen an die globale Namensverwaltung.............. 2
1.2 Abgrenzung zu anderen Systemdiensten................... 8
1.3 Schwächen existierender Namensverwaltungen......... 12
1.4 Konzepte der dynamischen globalen Namensverwaltung............ 19
2 Objekte, Namen und Namensräume........ 21
2.1 Kategorisierung von Namen und Namensräumen................. 22
2.2 Struktur und Eigenschaften von Benutzer-Namen...... 26
2.3 Integration attributierter und hierarchischer Namen...... 41
2.4 Beziehungen zwischen Namen und Objekten... 53
2.5 Operationen auf lokalen Namensräumen................. 58
3 Organisation einer dynamischen globalen Namensverwaltung................. 65
3.1 Strukturelle Komponenten globaler Namensverwaltungen......... 65
3.2 Funktionales Modell eines globalen Namensverwalters............. 71
3.3 Topologie und Organisation des Verwalternetzes................ 75
3.4 Konfigurierung hierarchischer Verwalternetze................. 88
4 Dynamische Verwaltung globaler Namensräume...... 101
4.1 Auflösung globaler Namen............... 101
4.2 Verteilung und Plazierung globaler Namen............... 109
4.3 Dynamische Verwaltung globaler Namensräume............... 120
4.4 Globale Verwaltung generischer, synonymer und attributierter Namen.... 134
4.5 Beurteilung der Plazierung von Namen im Verwalternetz............... 143
5 Replikation, Konsistenz und Fehlertoleranz. 145
5.1 Vorhalten von Namenseinträgen............ 145
5.2 Fehlertoleranz durch Replikation in globalen Namensverwaltungen....... 150
5.3 Konsistenz globaler Namenseinträge.............. 156
6 Zusammenfassung und Perspektiven....... 167
6.1 Zusammenfassung der Ergebnisse 167
6.2 Mögliche Erweiterungen und Perspektiven............... 169
Anhang A Literaturverzeichnis........... 171
Anhang B Übersicht über Namensverwaltungen und Verzeichnisdienste............... 191
Anhang B .1 Dynamische Namensverwaltungen....... 191
Anhang B .2 Verteilte Dateiverzeichnisse........... 201
Anhang B .2 ............... 201
Anhang B .3 Dynamisch verwaltete Objektverzeichnisse........ 207
Anhang B .4 Globale Namensverwaltungen....... 209
Anhang B .5 Globale Verzeichnisdienste........... 219
Anhang B .6 Namen in globalen Informationssystemen...... 239
Anhang C Datenstrukturen der dynamischen globalen Namensverwaltung............... 245
Anhang D Grundlegende lokale Namensoperationen............... 249
Anhang E Verzeichnis der Abbildungen......... 251
Anhang F Verzeichnis der Tabellen............... 255
Anhang G Lebenslauf............. 257
Im Rahmen dieser Arbeit werden neue Konzepte für die Verwaltung globaler Namensräume und Konfigurierung globaler Verwalternetze vorgeschlagen. Darüber hinaus wird gezeigt, wie eine effiziente globale Namensverwaltung strukturiert und implementiert werden kann.
Im Vordergrund stehen dynamische Konzepte zur Verwaltung globaler Namensräumen. Namen werden anhand ihrer Struktur und ihres Inhalts selbständig in einem verteilten hierarchischen Namensraum plaziert und Kontexte, wo erforderlich, generiert. Attributierte Namen finden hierbei in gleichem Maße Berücksichtigung wie Synonyme. Die Konfiguration des Verwalternetzes zur Namensverwaltung leitet sich aus den topologischen und semantischen Eigenschaften der zugrundeliegenden Kommunikationsinfrastruktur ab. Die erhöhten Konsistenzanforderungen, die sich aus der Dynamik und der Replikation von Namenseinträgen ergeben, werden durch optimistische Verfahren erfüllt. Die vorgestellten dynamischen Konzepte eröffnen ein weites Spektrum von Perspektiven für die künftige Entwicklung globaler Namensverwaltungen.
This thesis proposes
new concepts for dynamic management of global name spaces in distributed
systems. Further it shows, how to structure and implement a powerful global
naming system.
The focus is drawn to dynamic concepts for the global administration of name spaces by the user. Names are independently placed in a distributed hierarchical name space by their structure and content. Contexts are created on demand. Attributed names are addressed as well as synonyms. The configuration of name servers is deduced from the topology and semantics of the underlying communications network. The consistency requirements arising from the dynamic and replication of name entries will be fulfilled by optimistic methods. The concepts presented offer a wide spectrum of perspectives for the future development of global naming systems.