2          Objekte, Namen und Namensräume

 

 

Die Vielfalt der Begriffe und deren unterschiedliche Interpretationen in der Literatur erfordern es, der weiteren Diskussion der Eigenschaften von Namen und Objekten und deren Einfluß auf die dynamische globale Namens­verwaltung eine klärende Begriffsdefinition voranzustellen. Die hierbei verwen­dete Notation stützt sich teilweise auf die Arbeiten von Peterson und Comer [Comer, 89].

Die Beschäftigung mit Namen hat eine lange Tradition. Zahlreiche Versuche wurden unter­nommen, ein tieferes Verständnis im Umgang mit Namen zu gewinnen. Aus den Bestrebungen, Namen theoretisch zu ergründen, sind eine ganze Reihe interessanter Modelle hervorgegangen. Ein erster Versuch, das Wesen von Namen begrifflich zu bestimmen, war die vielzitierte Shochsche Sentenz [Shoch, 78]:

The name of an object specifies what a process seeks,

an address specifies where this object is,

a route specifies how to get there.

Die von Shoch aufgestellte Definition für Namen und Adressen war wenig erfolgreich. In der Literatur finden sich hierzu zahlreiche Kritiken [Saltzer, 82] [Hauzeur, 86]. Die Hauptgründe, warum die Shochsche Sentenz keine befriedigende Begriffsbildung darstellt, sind folgende:

•     Die Definition der Adresse läßt eine vieldeutige Interpretation zu. Zudem existieren Adres­sen, die nicht den Ort eines Objekts angeben (z.B. Ethernet-Adressen).

•     Die Shochsche Definition ignoriert ein weiteres Schlüsselkonzept der Namens- und Adreß-problematik, das Konzept der Abbildung.

Weitere Modelle zur Umsetzung und Auflösung von Namen wurden insbesondere von Saltzer [Saltzer, 78], Comer und Peterson [Comer, 89] und Younger [Younger, 92] aufgestellt. Saltzer schlägt eine breitere Definition des Begriffs „Name“ vor. Hierzu führt er als Beziehung zwi­schen Namen und Adressen den Begriff der Bindung ein. Die Adresse eines Objekts defi­niert er hierauf aufbauend als Name desjenigen Kommunikationsobjekts, an das das Objekt gebunden ist. Diese Beziehung von Namen und Adressen wird auch von Hauzeur [Hauzeur, 86] für das ISO/OSI-Schichten­modell aufgegriffen (vgl. Abschnitt 1.2.2).

An object’s address is the name of the object it is bound to.

In der vorliegenden Arbeit werden Benutzer-Namen und System-Namen unterschieden . Diese Kategorisierung von Namen ist zum einen durch die ursprüngliche Definition von Shoch, aber auch durch die Arbeiten von Terry [Terry, 85] motiviert:

•     Benutzer-Namen werden vom Anwender für Objekte vergeben.

•     System-Namen werden Objekten vom System oder vom Systemadministrator zugeteilt.

In diese einfache Kategorisierung fügen sich o.g. Namen als Benutzer-Namen ein, während Adressen der weitergefaßten Kategorie der System-Namen zuzuordnen sind. Eine nähere Charakterisierung von Benutzer- und System-Namen geben die folgenden Abschnitte.

Der Begriff „Name“ findet somit nicht nur für symbolische Namen der Anwen­dungsebene, sondern auch für system- und kommunikationsorientierte Bezeichner und Adressen Verwen­dung. Die unterschiedlichen Namen bilden dabei eigene Namens­räume, die zueinander in Beziehung stehen.

2.1         Kategorisierung von Namen und Namensräumen

Die Eigenschaften von Namen korrelieren mit den Eigenschaften benannter Objekte. Objekte treten in verteilten Systemen auf unterschiedlichen Systemebenen auf [AL1] , die zur Kategorisierung der zugehörigen Namensräume herangezogen werden können. Alternativ besteht die Möglich­keit zur Katego­risierung von Namen anhand ihrer Struktur und den Systemsichten, d.h. den Schnittstellen zum System, an denen Namen auftreten.

2.1.1          Objekte in verteilten Systemen

Verteilte Systeme ermöglichen nicht nur den Zugriff auf lokale, sondern über Kommu­nika­ti­onskanäle  auch auf entfernte Objekte im Netzwerk integrierter Knoten. Somit erhöht sich die Anzahl zu benennender Objekte im Gesamtsystem um ein Vielfaches. Aufgrund der Quantität der verwalteten Objekte kann in verteilten Systemen kein Anwender die gesamten, systemweit existierenden Informationen lokal verfügbar haben, sondern immer nur einen Teilausschnitt. Dabei besteht die Gefahr, daß ein Anwender wichtige Informationen nicht findet oder übersieht, da diese ungeeignet strukturiert sind oder durch die Namens­verwaltung nicht erfaßt werden.

Definition: Objekt

Ein Objekt o in einem Rechnersystem ist eine physische oder logische Ressource beste­hend aus Code, Daten oder Hardware, auf die Aktionen gerichtet sind. Objekte dienen der Abstraktion von den Implemen­­tierungsdetails. Die Gesamtheit der Objekte bildet die Menge O.

 

Wie Abbildung 2.1 verdeutlicht, treten zu den in konventionellen Systemen verwalteten Objek­ten in verteilten Systemen kommunikationsbezogene Objekte wie Kommunikationsports, Knoten, Cluster, Zonen, Netzwerke und Kommuni­kationswege (Routes) hinzu [Goscinsky, 91]. Diese tragen Bezeichner, wie Adressen und Port-Nummern. Zur systemübergreifenden Identifikation von Objekten werden global eindeutige System-Namen (Bezeichner) generiert. Anwender greifen auf Objekte knotenübergreifend über symbolische Benutzer-Namen zu, die dabei von der Namensverwaltung auf System-Namen abgebildet werden.

[AL2] 

Abbildung 2.1: Namen auf verschiedenen Ebenen eines verteilten Systems

Nicht immer ist die Transparenz soweit realisiert, daß für den Anwender im Gesamtsystem nur ein einziger globaler Namensraum sichtbar wird. Viele Systeme verwalten für Namen von Objekten verschiedener Eigenschaften und Systemebenen separate Namensräume.

2.1.2          Eigenschaften benannter Objekte

In verteilten Systemen findet sich eine Vielzahl adressier­barer Objekte unterschiedlichster Eigenschaften. Das Spektrum benannter Objekte reicht von globalen logischen Gruppie­rungen über Netzwerke bis zu einzel­nen Variablen:

Netzwerke, Zonen, Cluster, Knoten, Sockets, Ports, Server, Dienste, Devices, Ressourcen, Schnittstellen, Hauptspeicherbereiche, Datei­systemobjekte, Prozesse, Umgebungs­variablen, Benutzer und Benutzergruppen, Kommunik­a­t­ion­s­wege und ­-objekte, Mailboxen, Peripherie­geräte, Drucker, Tastatur, Maus, Grafikfenster, …

In diesem Spektrum existieren Objekte mit unterschiedlicher Lebensdauer, Zugriffseffizienz und Verfügbarkeit. Diese und weitere Objekt­eigenschaften beeinflussen das Verhalten der Namens­verwaltung wie folgt:

·      Lebensdauer von Objekten: Informationen über langlebige Objekte sollten im System einen höheren Replikations­grad aufweisen als Informationen über kurzlebige Objekte, die oft nur lokalen Charakter besitzen. Die Anforderungen an die Zugriffszeit über Namen sind um so höher, je kurz­lebiger die referenzierten Objekte sind.

·      Zugriffsfrequenz: Die Frequenz des Zugriffs über den Namen auf ein Objekt muß bei der Namensgebung und der Plazierung des Namens im Namensraum und in den Namens­ver­waltern Berücksichtigung finden. Je häufiger auf ein Objekt zugegriffen wird, desto effizi­enter[AL3]  muß die Abbildung des Namens auf die Ortsinformation sein.

·      Granularität von Objekten: Sie ist eng verbunden mit der Lebensdauer von Objekten. Große Objekte sind in der Regel langlebig, während kleinere Objekte oft nur temporär existieren.

·      Relative Entfernung: Objekte lassen sich in entfernte und nahe Objekte einordnen[1]. Die mitt­lere, relative Entfernung der Objekte zueinander bestimmt den Grad der Verteilung im System. Je näher Objekte zueinander plaziert sind, desto kürzer sollten die relativen Namen sein. Diese Forderung ist jedoch nur zu erfüllen, wenn Namen Ortsinfor­mationen enthalten.

·      Mobilität: Mit der physikalischen Lokation ändert sich auch die Adresse eines Objekts[AL4] . Eine Lokationsänderung von Objekten impliziert zwar nicht in jedem Fall eine Namens­änderung, je nach Art der Namensabbildung werden jedoch entweder Anpassungen der Namens- oder der Adreßtabellen erforderlich (vgl. Abschnitt 1.2.2 und Abschnitt 2.4.5).

·      Replikationsgrad: Zur Steigerung der Verfügbarkeit (Zugriffszeit, Ausfallsicherheit) werden in verteilten Systemen häufig Objekte repliziert. Sofern die Objektverwaltung nicht bereits Replika­tionstransparenz  bietet, muß die Namens­verwaltung Replikationen berücksichtigen.

2.1.3          Klassifizierung von Namen anhand der Systemebene

Objekte in verteilten Systemen können verschiedenen System­ebenen zugeordnet werden. Dabei werden die Objekte unterschiedlicher Systemebenen häufig in autonomen Namensräumen benannt. Eine Klassifi­zierung der Systemebenen [Autenrieth, 90] und der zugehörigen Namens­räume zeigt Abbildung 2.2.

Abbildung 2.2: Ebenen eines verteilten Systems

Innerhalb dieser Systemebenen können Aspekte der Zugriffseffizienz, des gesicherten Wachs­tums, der Zuverlässigkeit und der Sicherheit ihre individuelle Ausprägung finden:

·      Die verteilungsunabhängigen, objektinternen Namen (z.B. für Variablen, Datenstrukturen, Methoden, Instanzen) der Intraprogrammebene nehmen in der Namensverwaltung eine Son­der­stellung ein, da ihre Bindungen zu Objekten statischen Charakter haben und nur zum Zeitpunkt der Übersetzung, des Bindens oder des Ladens hergestellt werden. Diese Bin­dun­gen werden über programminterne oder allgemeine Vereinbarungen wie Header- bzw. Include-Dateien bereitgestellt.

·      Die Interprogrammebene mit systemspezifischen Identifi­kationen (z.B. für Ports, Prozesse, Dateien, Objekte) enthält die Umgebungsvariablen von Programmen. Namen dieser Ebene können gezielt zur Abstraktion eingesetzt werden. Dabei lassen sich die Vorzüge der indi­rekten Interprozeßkommuni­kation über Ports mit den Effizienzvorteilen der direkten Kom­munikation verbinden, indem logisch indirekt über Namen, physikalisch jedoch direkt über assoziierte Systemident­ifikationen kommuniziert wird.

·      Auf der Objektverwaltungsebene mit Namen objektverwaltender Dienste (z.B. Knoten, Server) sind Objekte zusammengefaßt, die unter der gemeinsamen Verwaltung sog. Objekt­manager stehen (z.B. Verzeich­nisse oder Dateien unter der Verwal­tung eines Dateiservers, Funk­tionen und Daten eines Gerätetreibers oder auch Verzeichnisse eines Namens­verwal­ters).

·      Objekte der Administrativebene mit administrativen Namen (z.B. für Zonen) gehören zum Einflußbereich organisatorischer Einheiten (z.B. Netzwerke, Firmen, Forschungsinstitute und Verwaltungen) und enthalten die Namen untergeordneter Abteilungen und Verwaltungs­strukturen. Einer solchen logischen Zuordnung unterliegt häufig gleichzeitig die Anbindung an ein gemeinsames Teilnetzwerk (Ethernet, Tokenring o.ä.). Administrative Verzeichnisse können hierarchisch angeordnet sein, wobei ihre Einträge auf Verzeichnisse der Objektver­waltungsebene oder untergeordneter Admi­nistrativebenen verweisen.

·      Die Globalebene mit globalen Namen, die den Verbund organisatorischer Einheiten und Gruppierungen angeben (Netzwerk), faßt Objekte zusammen, die unabhängige Organisa­tio­nen oder Organisations­gruppen repräsentieren. Namen für Objekte der Globalebene besitzen eine große Stabilität, d.h. die Bin­dungen zu Objekten unterliegen kaum Ände­rungen. Die Verfügbarkeit globaler Verzeichnisse ist wichtig, jedoch für den Betrieb eines verteilten Systems nicht elementar, da das System im administrativen Bereich weiter funktionsfähig bleibt und nur Funktionseinbußen in der globalen Kommunikation erleidet.

Unabhängig von Struktur und Eigenschaften können die Namen dieser Systemebenen anhand ihres Verteilungsgrads wie folgt lokalen oder globalen Namens­räumen zugeordnet werden:

·      Lokale Namensräume enthalten verteilungsunabhängige, objektinterne Namen für knoten­interne Objekte der Intraprogrammebene und Basisnamen für Objekte der Interprogramm­e­bene.

·      Globale Namensräume enthalten Namen für Objekte der Objektver­wal­tungsebene, der Administrativ­ebene  und der Globalebene, die den Verbund organisa­torischer Einheiten und Gruppierungen angeben.

Lokale und globale Namensverwaltungen enthalten Namen für Objekte unter­schiedlicher Granularität, Lebens­dauer und Mobilität. Hierin sind die differenzierten Anforde­rungen an die Skalierbar­keit und Effizienz begründet.

2.1.4          Namen unterschiedlicher Systemsichten

Betriebssysteme identifizieren Objekte durch eindeutige Bezeichner und Adressen. Diese sind für Protokolle wesentlich einfacher zu handhaben als Namen. Dem Anwender hingegen prägen sich Bezeichner und Adressen wegen der fehlenden Assoziation mit realen Gegen­stän­den und der schlechten Mnemonik nur schwer ein. Sie sollten daher an der Benutzer-Schnitt­stelle nicht in Erscheinung treten.

Protocols Use Addresses, People Prefer Names

Namen leisten für den Benutzer die Abstraktion vom Objekt. Der Anwender eines Systems arbeitet ausschließlich mit symbolischen Benutzer-Namen. Diese sind in der Regel syntaktische Namen, deren Struktur sich gut einprägt und ihm den Umgang mit dem System erleichtert.

In Betriebssystemen existieren verschiedene Sichten auf Objekte, die Systemsicht und die Benutzersicht. Je nach Sicht werden Objekte durch Benutzer-Namen oder System-Namen iden­tifiziert. Der Begriff „Name“ wird dabei nicht im engen Sinne nur für symbolische Benutzer-Namen verwendet, sondern auch für Identifi­kation von Objekten auf allen System­ebenen. Benutzer-Namen existieren an der Benutzerschnittstelle zum System (vgl. Abbildung 2.1) in Form beliebig langer Zeichenketten mit eigener Syntax und Semantik. Ein System-Name ist ein eindeutiger Bezeichner, der dem System die Handhabung von Objekten erleichtert und in Form von Zeichenketten, Bitstrings oder Integers auftritt. System-Namen treten für Benutzer eines Systems nicht in Erscheinung.

Definition: Objekt-Bezeichner, Objekt-Identifikation (OID)

Objekt-Bezeichner sind System-Namen, die Objekte eindeutig in Zeit und Raum identifi­zieren. Die Menge der erzeugten Objekt-Bezeichner I ist potentiell unendlich und stets gleich mächtig wie die Menge der existierenden Objekte O.

 

Auf der Ebene der System-Namen koexistieren u.U. mehrere Namensräume unterschiedlicher Ausprägung. System-Namen, die relativ zu einem physikalischen Namensraum aufgelöst wer­den, sind als physikalische Namen oder Adressen bekannt. Aus der Adresse eines Objekts wird eine konkrete Lokation und gegebenenfalls ein Pfad ( Route) zu dieser Lokation ermittelt.

 

Benannte Objekte treten in verteilten Systemen auf unterschiedlichen Systemebenen auf. Die hohe Mobilität, Dynamik und Diversität der benannten Objekte stellt erhebliche Anforderungen an die Verwaltung von Namen.

2.2         Struktur und Eigenschaften von Benutzer-Namen

Die vorliegende Arbeit beschäftigt sich mit der globalen Verwaltung von Benutzer-Namen. Diese wird maßgeblich beeinflußt von der syntaktischen Beschaffenheit und den Eigenschaften der verwalteten Namen. Der nachfolgende Abschnitt kategorisiert daher Benutzer-Namen anhand ihrer syntaktischen Struktur, beschreibt ihre Eigenschaften und diskutiert verschiedene Formen der Skalierung von Namensräumen.

2.2.1          Namenskonventionen und Namensräume

Namenskonventionen sind Regelungen zur Benennung von Objekten. Ein Namensraum ist als Menge von Namen definiert, die einer gegebenen Namenskonvention entsprechen [Terry, 86].

Definition: Namenskonvention

Eine Namenskonvention X bestimmt durch syntaktische und semantische Regeln, wie ein gültiger Name aufgebaut ist.

Definition: Namensraum  (Name Space)

Der Namensraum N ist die Menge aller gültigen Namen, die eine Namens­konvention erfüllen.

Namens­konventionen können strukurierte oder unstrukturierte Namen beinhalten:

Unstrukturierte Namen sind wahrscheinlich die einfachste Namenskonvention, da sie keine vorherrschende oder konsistente Struktur aufweisen. Gewöhnlich bilden unstrukturierte Namen einen flachen, homogenen Namensraum.

Strukturierte Namen andererseits weisen eine syntaktische Partitionierung in Teilnamen auf. Ein strukturierter Name muß nicht notwendigerweise syntaktisch erkennbar sein; die Struktur kann durchaus algorithmisch definiert werden. Namen, die nach syntaktischen Regeln aufgebaut sind, werden auch als syntaktische Namen bezeichnet. Besteht ein strukturierter Name aus einer Menge von Attributen, so wird er als attributierter Name bezeichnet, andernfalls als nicht-attribu­tierter Name. Die Reihenfolge, in der die Attribute angegeben sind, muß dabei jedoch nicht notwendigerweise eine Ordnung auf den Attributen definieren.

Abbildung 2.3: Arten von Benutzer-Namen

Die gebräuchlichste Organisationsform von Namen sind hierarchische, baumartige Namens­räume. Diese korrelieren vielfach mit der organisatorischen oder geogra­phi­schen Verteilung von Informationen. Derartige Namensräume unterstützen die dezentrale Namensverwaltung, da lokale Änderungen keinen Einfluß auf den gesamten Namensraum haben.

Abbildung 2.4: Arten von Namensräumen

Strukturierte Namen können auch Namensräume in Form zyklischer oder azyklischer gerichte­ter Graphen bilden. Im Gegensatz zu Bäumen besteht in azyklischen gerichteten Graphen die Möglichkeit, daß Knoten mehrere Namen besitzen. In der Praxis werden azyklische Namens­räume häufig durch das Einfügen sog. „soft links“ realisiert. In zyklischen gerichteten Graphen ist die Ordnung des Graphen nicht signifikant. Nicht alle Kanten müssen spezifiziert sein, um ein Objekt zu identifizieren. Diese Art von Namens­raum ist für attributierte und generische Namen gebräuchlich und bietet die Möglichkeit zur Suche mit unvollständigen Namensan­gaben. Eine derartige Suchmöglichkeit in einem zyklischen gerichteten Graphen erhöht die Benutzer­freundlichkeit des Systems [White, 84], ist allerdings sehr zeitaufwendig.

2.2.2          Syntaktische Struktur und Semantik von Benutzer-Namen

Benutzer-Namen existieren in Form von Zeichenketten mit eigener Syntax und Semantik. Anhand des Einflußes ihrer syntaktischen Struktur auf die Interpretation der Namen werden flache, partitionierte, hierarchische und attributierte Namen unterschieden.

2.2.2.1       Primitive oder flache Benutzer-Namen

Die einfachsten denkbaren Benutzer-Namen sind flache Namen[2]. Sie bestehen aus einer unstrukturierten Folge beliebiger Zeichen und entsprechen Wörtern einer Sprache N über einem endlichen Alphabet von Symbolen .

Der durch flache Namen erzeugte Namensraum  zeichnet sich durch seine Einfachheit aus. Ein flacher Namensraum enthält eine oder mehrere Namens­formen, wobei seine Elemente den von diesen Namens­formen erfaßten Symbolfolgen entsprechen.

Aus der Sicht der Namens­verwaltung werden flache Namen als syntaktische Atome betrachtet, da sie nicht weiter aufgelöst werden können. Das heißt nun aber nicht, daß flache Namen keine ausgeprägte syntaktische Struktur besitzen können. Die Strukturierungs­möglichkeiten flacher Namen sind vielfältig. Allerdings kommt den einzelnen Strukturelementen bei der Interpretation von Namen keine Bedeutung zu. In der Regel finden flache Namen als absolute Namen Ver­wendung. Da sie keinerlei Ortsinfor­mationen enthalten, erfordert die Migration gebun­dener Objekte keine Anpassung des Namens.

Für große verteilte Systeme sind flache Namensräume ungeeignet, da sie die verteilte Namens­verwaltung in keiner Weise unterstützen. Bei der Vergabe flacher Namen muß die Eindeutigkeit systemweit geprüft werden, indem sie gegen jeden existierenden Namen im flachen Namens­raum getestet werden. Da Ortsinformationen in flachen Namen fehlen, besitzt ein Namensver­walter keinerlei Hinweise, wo ein gegebener flacher Name letztendlich verwaltet wird[3]. Namens­­verwalter müs­sen daher entweder den gesamten Namensraum verwalten oder zumin­dest über Informa­tionen verfügen, welche Namensverwalter an der Verwal­­tung des Namens­raums beteiligt sind. Da beide Methoden einen hohen Kommuni­­kations- und Speicher­aufwand erfordern, sind flache Namensräume nicht beliebig skalierbar.

Weiter ist zu berücksichtigen, daß für Menschen flache Namen nur dann einpräg­sam sind, wenn sie Wörtern einer natürlichen Sprache entsprechen. In flachen Namensräumen wird es daher mit steigender Anzahl von Namen zunehmend schwieriger, eindeutige und gleichzeitig aussagekräf­tige Namen zu finden (vgl. hierzu auch Tabelle 1.1). Eine weitere Qualifizierung der Namen ist somit dringend erforderlich[AL5] .

2.2.2.2       Partitionierte Benutzer-Namen

Durch die Kombination flacher Namensräume entstehen partitionierte Namen. Sie können als Folge primitiver Namen betrachtet werden, die jeweils durch einen Separator getrennt sind. Der partitionierte Namensraum kann in disjunkte Bereiche zerlegt werden, die sogenannte Domains, Subdomains, Subsubdomains, usw. bilden.

Anhand der Partitionierung des Namensraums unterscheidet man:[V6] 

·      Physikalisch partitionierte Namensräume, die Ortsangaben enthalten, so daß aus dem Namen sofort auf die Lokation des benannten Objekts geschlossen werden kann. Physika­lisch partitionierte Namensräume erweisen sich jedoch besonders bei der Umorganisation als inflexibel. (z.B.: name@lokation)

·      Organisatorisch partitionierte Namensräume, die Namen nach der Zugehörigkeit zu organisato­rischen Einheiten gruppieren. Sie unterstüt­zen die dezentrale Namens­verwaltung unterhalb des die Organi­sation bezeichnenden Kontextes. Bei gegenseitigem Mißtrauen wird jedoch ein entsprechender Schutzmechanismus der eigenen Präfixes/Suffixes erforderlich. (z.B.: vs.informatik.uni-ulm.de)

·      Logisch partitionierte Namensräume, die anhand der Semantik der Namensteile oder des Typs der benannten Objekte partitioniert sind. Logische Namen besitzen keinen direkten Bezug zu einer physikali­schen Lokation oder organisatori­schen Ein­heit. (z.B.: aida.verdi.oper.music)

Enthalten Namen keine Abhängigkeiten von der darunterliegenden physikalischen Konfi­gura­tion, so wer­den sie auch als pure Namen bezeichnet. Unpure Namen enthalten Orts­infor­matio­nen und müssen daher bei der Relozierung von Objekten entsprechend aktuali­siert werden.

Partitionierte Namen sind immer an einen Kontext gebunden, der ihren Gültigkeitsbereich beschreibt. Kontexte können verschachtelt sein (nested context) und Namen können in mehre­ren Kontexten vorkommen.

Definition: Kontext

Ein Kontext Y ist eine Partition eines Namensraums, die durch die syntaktische Struktur der Namen oder durch eine Gruppierungs- oder Abbildungsvorschrift definiert wird.

Kontexte werden explizit durch die Struktur der Namen definiert oder implizit durch eine Abbildungsvorschrift, die kein Teil des Namens ist. Implizite Kontexte treten bei der Auflösung von Namen nicht in Erscheinung. Sie werden zuvor entweder durch den Prozeß der Namens­auflösung oder durch den Benutzer gesetzt.

2.2.2.3       Hierarchische Benutzer-Namen

Eine Teilmenge der partitionierten Namen[AL7]  sind die hierarchischen Namen, wie sie in vielen bekannten Systemen verwendet werden. Die Komponenten hierarchischer Namen besitzen im Gegensatz zu partitionierten Namen eine strenge Ordnung. Hierarchische Namen sind syntak­tisch strukturiert. Sie bestehen aus einer geordneten Folge primitiver Namen und werden anhand einer Interpretationsvorschrift bei der Namensauflösung wieder in eine solche zerlegt. Ein vollständiger hierarchischer Name eines Objekts kann sich dabei aus der Bezeichnung eines Kontextes, die sich selbst wieder aus primitiven Namen zusammen­setzt, und dem Objektnamen relativ zu diesem Kontext konkatenieren.

Hierarchische Namen aus Objekt- und Kontext­bezeichnung spannen einen hierarchischen Namens­raum  auf.

Hierarchische Namensräume lassen sich als gerichteter Graph darstellen. Die Knoten in diesem Graphen stellen benannte Objekte oder Kontexte dar. Namen werden an den Kanten des Graphen angetragen. Benannt werden also nicht die Objekte selbst, sondern die Beziehungen zwischen den einzelnen Kontexten und Objekten.

Abbildung 2.5: Die hierarchische Strukturierung eines Namensraums mit disjunkten Kontexten

Die Beschreibung eines hierarchischen Namensraums in Form eines gerichteten Graphen aus Abbildung 2.5 kann beispiels­weise als regulärer Ausdruck wie folgt dargestellt werden:

Wurzel = {(uni-ulm{(med), (math), (info{(dbis, vs)}) }), (daimler{(Mercedes), (AEG)})}

Die Baumstruktur eines hierarchischen Namensraums definiert eine Folge von Mengen­inklusio­nen. Alle Kontexte und Objekte eines Teilbaums sind in dem Kontext enthalten, aus dem der Teilbaum hervorgeht. Objekt-Eigenschaften, die mit dem Namen eines Kontexts assoziiert werden, vererben sich an alle im Teilbaum enthaltenen Objekte. Dieser Umstand motiviert die Darstel­lung hier­archi­scher Namensräume als Mengendiagramme. Verschachtelte Kontexte wer­den hierbei als Inklusionen von Mengen dargestellt. Disjunkte Mengen repäsentieren Kon­texte derselben Hierarchiestufe (vgl. Abbildung 2.6).

Abbildung 2.6: Darstellung eines hierarchischen Namensraums als Mengendiagramm

Hierarchische Namensräume unterstützen die Untergliederung der Namensverwaltung zur Bewältigung der unterschiedlichen Erfordernisse, wobei die Lebens­dauer von Objekten ein wesentliches Strukturierungsmerkmal vorgibt. Ebenen mit Namen langlebiger Objekte liegen dabei in der Hierarchie typischerweise höher als die kurzlebiger Objekte. Die Quantität der Objekte einer bestimmten Eigenschaft korreliert ebenfalls mit der Hierarchie­stufe im Namens­raum. Je weiter oben im hierarchischen Namensraum eine Eigenschaft repräsentiert ist, desto mehr Objekte erben diese Eigenschaft.

Hierarchische Namen haben sich als fundamentales und nützliches Prinzip zur Strukturierung von Informationen erwiesen. Für Anwender, die vor die Aufgabe gestellt sind, eine große Menge diverser Objekte zu organi­sieren, ist es nichts ungewöhnliches, diese in eine hierarchi­sche Struktur einzuordnen. Hierarchische Anordnungen sind schließlich u.a. die Basis zahl­rei­cher wissenschaftlicher Klassifikationen. Hierarchische Datenmodelle wurden bereits von frühen Datenbanksystemen (IMS, [McGee, 77]) aufgegriffen und hierarchische Verzeich­nisstrukturen bilden seit MULTICS [Daley, 65] den organisatorischen Rahmen für Datei­systeme. Hierarchische besitzen gegenüber flachen Namensräumen folgende Vorteile:

·      Hierarchische Namen erlauben das Delegieren der Zuständigkeiten für Teile des Namens­raums. Somit können wesentlich mehr Namen verwaltet werden, ohne die Überlastung einer zentralen Instanz zu verursachen.

·      Durch die hierarchische Organisation wird die Abkapselung von Namensräumen möglich, so daß die Namens­verwaltung für jede Ebene individuell zugeschnitten werden kann. Jeder Unterbaum im hierarchischen Namens­raum kann wie­derum als vollwertiger Namens­raum betrachtet werden, in dem struktu­relle Veränderungen nicht an den übergeord­neten Namens­raum propagiert werden müssen.

·      Sie ermöglichen die autonome Vergabe von Namenskomponenten durch Autoritäten, die wieder anderen Autoritäten untergeordnet sind.

·      Namen müssen nur innerhalb des jeweiligen Kontextes eindeutig sein und sind daher einfa­cher zu erzeugen.

·      Die Namensauflösung kann effizient gestaltet werden, indem sie der hierarchi­schen Struktur des Namensraums angepaßt wird.

·      Hierarchische Namensräume ermöglichen eine Verteilung der Namensinterpretation auf verteilte Instanzen, die dann meist mit den genannten Autoritäten zusammengefaßt werden. Jede Instanz vertritt dabei einen oder mehrere Kontexte.

·      Hierarchische Namensräume können an beliebiger Stelle miteinander verbunden werden und erlauben ein Wachstum des Namensraums (Skalierung) in alle Richtungen (vgl. Abschnitt 2.2.4). Die Extraktion und das Anfügen hierarchischer Namens­räume sind die Basis der Konstruk­tion großer verteilter Namens­räume.

Trotz der aufgezeigten Vorteile sind einige gravierende Nachteile streng hierarchischer Namens­räume nicht zu übersehen:

·      Werden hierarchische Namensräume verwendet, um die Eigenschaften von Objekten zu beschreiben, so besteht das Problem, im hierarchischen Namensraum Objekte zu unter­stüt­zen, die alle bis auf eine übergeordnete Eigenschaft besitzen.

·      Es ist schwierig, logisch unabhängige oder nicht-kontext-beschränkte Informationen in hier­archische Namensräume aufzunehmen.

·      Die hierarchische Organisation von Namen etabliert subjektive Sichten auf die verwalteten Objekte, die nur eine bestimmte Form von Abfragen erlauben[4]. Die Reihenfolge, in der Namensteile angegeben werden müssen, ist daher signifikant.

·      Die vollständige Beschreibung der Eigenschaften eines Objekts durch hierarchische Namen führt zu sehr langen Namen und tiefen Verschachtelungen, die schwer handhabbar sind.

·      Die Kontextabhängigkeit der Namen erschwert die Suche nach generischen Namen. Diesel­ben Namensteile und Eigenschaften treten u.U. in mehreren Unterbäumen auf, wodurch die generische oder attributierte Suche aufwendiger wird, da alle Teilbäume traversiert werden müssen.

·      Sind hierarchische Namen bezüglich physikalischer, geogra­phischer oder organisatorischer Strukturen organisiert, so ist es schwierig, Objekte zu relozieren, ohne sie umzubenennen.

Die hier angeführten Nachteile lassen sich abschwächen, indem die strenge Hierarchie aufgelöst und in mehrere Teilbäume aufgebrochen wird. Diese Teilbäume werden so miteinander verbun­den, daß ein Graph entsteht. Ansätze hierzu zeigen die folgenden Abschnitte. Weitgehende Freiheiten zur Beschreibung von Objekten durch Namen bieten generische und attributierte Namen, die in den folgenden Abschnitten behandelt werden. Besonders bei der logischen Parti­tionierung von Namensräumen sind attributierte Namen vorteilhaft.

2.2.2.4       Syntax generischer hierarchischer Namen

Soll eine Menge von Objekten durch Namen identifiziert werden, so geschieht das durch generische Namen. Zur Beschreibung generischer Namen wird die Syntax strukturierter Namen um Symbole erweitert, die repräsentativ für beliebige Zeichen und Namensteile stehen. Generi­sche strukturierte Namen setzen sich aus primitiven Namen und Platzhaltern (Wildcards) zusam­men. Primitive Namen können ihrerseits generisch sein und Platzhalter enthalten.

Als Platzhalter oder Wildcard für ein beliebiges Zeichen innerhalb eines primitiven Namens steht beispielsweise ein Stern "*", wie er auch von anderen Systemen (z.B. MS-DOS) bekannt ist. Ein primitiver generischer Name besitzt dann folgende syntaktische Beschreibung:

Beliebige Namensteile in strukturierten Namen können durch ein Fragezeichen "?" repräsentiert werden, so daß ein strukturierter generischer Name folgender syntaktischen Beschreibung genügt:

Sowohl der Platzhalter für beliebige Zeichen innerhalb eines Namens als auch derjenige für beliebige Namen innerhalb eines strukturierten Namens kann in beliebiger Wiederholung auftreten. Die Anzahl der Repetitionen wird durch einen Bereich spezifiziert, der in spitzen Klammern „< >“ angegeben wird und im Anschluß an den Platzhalter folgt. Eine beliebig häufige Wiederholung wird durch einen offenen Bereich gekennzeichnet.

Dem generischen Namen "Universit*<1,3>" entsprechen beispielsweise die Namen "Universität", "University" oder "Universitaet". Das nachfolgende Beispiel für einen generischen Namen kann z.B. alle Einrichtungen der Universität Ulm erfassen, die einen WWW-Dienst offerieren.

/uni.ulm.?<1,2 >.www

Der Platzhalter "?<1,2 >" läßt beispielsweise die Optionen "informatik.dbis", "informatik.vs" oder "rz" zu. Platzhalter für Zeichen und primitive Namen können in strukturierten Namen auch in Kombination auftreten.

Die soeben beschriebenen generischen Namen weisen Ähnlichkeiten mit deskriptiven oder attributierten Namen auf, da diese ebenfalls flexible Namensanfragen erlauben. Den Besonder­heiten attributierter Namen wendet sich der nach­folgende Abschnitt zu.

2.2.2.5       Deskriptive und attributierte Benutzer-Namen

Die Bindung von Namen an Objekte kann einer willkürlichen Zuordnung entsprechen. Namen müssen daher keine erfahrbaren Eigenschaften eines Objekts repräsentieren. Zusätzlich zum Namen existieren über Objekte weitere Informationen, die ihre Charakteristika beschreiben und zur Identifizierung eines Objekts herangezogen werden können. [AL8] 

Die Beschreibungsinformationen für Objekte lassen sich in Hinblick auf den Verwendungs­zweck in vier Kategorien unterteilen[5]:

•     Merkmalsinformationen sind für ein Objekt spezifische Merkmale, die ein hohes Maß an Stabilität besitzen und i.d.R. für die gesamte Lebensdauer dem Objekt erhalten bleiben.

•     Zustandsinformationen sind kurzlebige Informationen, deren Änderungsrate die Abfrage­­rate übertrifft. Sie werden nicht als Attributwert abgelegt, sondern zum Abfrage­zeitpunkt aktuell ermittelt.

•     Zugangsinformationen enthalten die für den Objektzugriff notwendigen Informationen. Hierzu zählen u.a. Objekt-Bezeichner und Zugriffsrechte auf Objekte.

•     Verwaltungsinformationen dienen den operationellen Erfordernissen der Verwaltung von Objekten (z.B. Zeitstempel und Zugriffsrechte).

Die Beschreibung der Eigenschaften von Objekten erfolgt durch typisierte Attribute mit einem bestimmten Wertebereich. Alle oder einzelne dieser Attribute eines Objekts können verwendet werden, um als Komponenten eines attributierten Namens ein Objekt zu identifizieren. [AL9] 

Attributierte oder deskriptive Namen bestehen aus einer Folge von Attributen in Form von typisierten Attribut/Wert-Paaren, die für ein Objekt zutreffen und es beschreiben. Die Bezeich­nung „Folge“ impliziert bereits, daß eine Ordnung unter den Attributen existieren kann. Die Flexibilität attributierter Namen wurde insbesondere durch Bowman und Peterson [Bowman, 90a] eingehend dargelegt. Einen deskriptiven Namen bilden z.B. folgende Attribut/Wert-Paare:

 (Farbe:grün) (Größe:groß) (Form:rund)

Die Darstellung attributierter Namen kann in Form von Tabellen erfolgen [Sechrest, 92]. In den Spalten der Tabelle werden dabei die Attributtypen und in den Zeilen die Werte der Attribute für die Objekte angetragen. Ein Beispiel für die Beschreibung von Objekten anhand diskreter Attribute gibt Abbildung 2.7.

Abbildung 2.7: Tabellendarstellung orthogonaler Attribute

Attributetypen in Abbildung 2.7 sind die Farbe, die Größe und die Form eines Objekts. Attri­butwerte sind z.B. rot, klein und rund. Eine äquivalente Darstellung für attributierte Namens­räume sind Mengen­diagramme [Hauzeur, 86]. Die Identifizierung von Objekten erfolgt durch den Schnitt von Objektmengen gleicher Attribute (vgl. Abbildung 2.8).

Abbildung 2.8: Mengendarstellung orthogonaler Attribute

Wie bereits erwähnt, bestehen attributierte Namen aus einer Folge von Attributen. Die Attribute eines Objekts wiederum werden als Tupel aus Attributtyp und Attributwert definiert:

Attribut := (Attributtyp: {Attributwert})

Attributierter Name := {Attribut1 … Attributn}

Attributtypen sind einfache Zeichenketten, die ein Attribut typisieren. Sie haben vornehmlich die Aufgabe, den Benutzer über die Bedeutung des Attributwerts zu informieren und in der Daten­bank die Relation zu benennen. Ferner wird durch den Attributtyp der Wertebereich eines Attri­buts bestimmt. Daher muß zu jedem Attributtyp der zuge­hörige Wertebereich spezifiziert werden. Teil einer solchen Spezifikation ist zum einen die Beschreibung des Wertebereichs und zum anderen eine Auswertungsfunktion, die die Ordnung zwischen den Werten definiert. Die Auswertungs­funktion kann bei Basistypen in der Namensverwaltung integriert sein oder gesondert definiert werden. Bei der Auswertung lassen sich diskrete und kontinuierliche Attri­butwerte unterschei­den.[AL10] 

Attribute können einfache oder mehrfache Attributwerte besitzen. Einwertige Attribute umfassen immer nur einen Wert, mehrwertige hingegen ein Wertemenge. Der subtile Unterschied liegt in der Behandlung der Einfügeoperation. Während das Einfügen in eine Menge den Wert ergänzt, wird der Wert einer einelementigen Menge ersetzt.

(Farbe:grün) (Größe:groß) (Form:(rund) (eckig))

Für den Anwender verfügbare Objektinformationen sind in expliziten Attributen abgelegt. Zugangs- und Verwaltungsinformationen der Namens- und Objektverwaltung werden in impli­ziten Attributen geführt. Auch für Attributeinträge sind Zugangs- und Verwaltungs­informatio­nen erforderlich, die ebenfalls als implizite Attribute angelegt werden können. Die Sicht­barkeit von Attributen für den Anwender kann durch attributspezifische Zugangsinforma­tionen flexibel gehandhabt werden.

Unter den Attributen eines Objekts lassen sich identifizierende Attribute definieren. Diese kenn­zeichnen ein Objekt eindeutig und sind zwingend für ein Objekt anzugeben. Während für belie­bige Attribute keine Eindeutigkeit vorliegen muß, erfordern identifizierende Attribute operatio­nelle Maßnahmen zur Gewährleistung der Eindeutigkeit. Identifizierend für ein Objekt kann beispielsweise ein willkürlich gesetzter Name oder der Objekt-Bezeichner sein.

Die Werte eines Attributs können statisch zugeordnet sein oder sich dynamisch ändern. Stati­sche Attributwerte dienen der Objektbeschreibung und werden nur explizit geändert. Dynami­sche Attributwerte enthalten Zustands­informationen, die einer stetigen Änderung unterworfen sind. Aus Aktualitätsgründen werden diese erst zum Zeitpunkt der Anfrage ermittelt.

Anstelle von Zeichenketten können als Werte reguläre Ausdrücke angegeben werden. Hierdurch kann ein endlicher Wertebereich spezifiziert werden, der alternative Schreib­weisen oder gebräuchliche Abkürzungen berücksichtigt. Hinsichtlich einer vertiefenden Diskussion dieser Repräsentationsmöglichkeiten wird auf die Arbeiten von Peterson [Peterson, 88a] und Bowman [Bowman, 90a] verwiesen.

Attributierte Namen können unvollständig sein, zum einen weil sie vom Benutzer nicht exakt spezifiziert wurden, zum anderen aus verwaltungs­technischen Gegebenheiten[AL11]  der Datenbank. Dieser Umstand motiviert die Einführung von Präferenzen [Bowman, 90a], die verschiedene Qualitäten von Attributen bezeichnen. Präferenzen dienen bei der Auflösung von Namen dazu, bestimmten Attributen oder Attributwerten ein höheres Gewicht zu verleihen als anderen. Objekte, die durch eine Menge von priorisierten Attributen beschrieben sind, werden bevorzugt ausgewählt. Präferenzen können als Meta-Attribute[AL12]  der internen Repräsentation eines Attributs verstanden werden. Verschiedene Präferenzen dienen lediglich Administrations­zwecken und sind für den Benutzer nicht sichtbar. Andere wiederum können entweder bereits bei der Regi­strierung in der Datenbank zu einem Attribut abgelegt oder bei der Auflösung eines attributierten Namens spezifiziert werden.

Attributpräferenzen lassen sich zu Klassen zusammenfassen [Bowman, 90b]. Innerhalb der Klassen besteht eine Ordnung der Attributpräferenzen, die die Bevorzugung von Attributen bei der Auflösung attributierter Namen regelt. Diese Klassen können in Benutzer- und in Daten­bankpräferenzen eingeteilt werden.

•     Benutzerpräferenzen sind für Benutzer bei der Spezifikation von Anfragen sichtbar. Hierzu zählt die Registrierungspräferenz, die angibt, ob ein Attribut optional oder obligato­risch registriert werden muß. Eine Suchpräferenz  beeinflußt die Suchkriterien bei der Auflösung von Namen. Die Gültigkeitsdauer von Attributwerten wird durch die Änderungs­präfe­renz (dynamisch oder statisch)  beschrieben. Die Eindeutigkeits­präferenz gibt an, ob Attri­butwerte eindeutig sein müssen. Auch die Reihenfolge der Angabe von Attributen kann eine Präferenz bei der Auflösung von Namen darstellen.

•     Datenbankpräferenzen sind für die Verwaltung von Attributen vorgesehen. So kann eine Auswahlpräferenz die Übereinstimmung von Attributen mit der gegebenen Beschrei­bung regeln. Entsprechend werden Objekte ausgewählt, deren Attribute eindeutig, exakt, partiell oder nur möglicherweise überein­stimmen. Eine Votierungspräferenz regelt die Exaktheit der ermittelten Objektbeschrei­bungen. Zeitpräferenzen geben Auskunft über die Aktualität der Einträge und priorisieren bei der Auswahl originale vor vorgehaltenen oder ungültigen Einträgen.

Ein mögliches Kriterium für die Auswahl von Einträgen stellt die Anzahl der Objekte dar, für die ein Attribut registriert wurde. Attribute, die für wenige Objekte zutreffen, können bevorzugt behandelt werden, da ihr Informationsgehalt höher ist als der anderer. Dieses Vorgehen ist insbesondere bei der verteilten Verwaltung von Namenseinträgen sinnvoll, wie sich in den nachfolgenden Kapiteln zeigen wird.[V13] 

Eine typische Operation auf attributierten Namensräumen ist das Auflösen eines Namens in Form vorgegebener Attribut/Wert-Paare. Schnell wird klar, daß die Identifizierung von Objek­ten anhand von Attributen nicht notwen­digerweise eindeutig ist. Dieselben Attribut/Wert-Paare können mehrere Objekte bezeichnen. Erst in Kombina­tion mit identifizierenden Attributen wird die Eindeutigkeit erreicht. Die Auflösung deskriptiver Namen liefert entweder den vollständigen Satz von Attributen zurück, oder das Ergebnis wird auf eine Teilmenge der vorhandenen Attri­bute projiziert.

Attributierte Namen sind prädestiniert zur Identifizierung von Objekten anhand ihrer Eigen­schaften. Ein inhärentes Problem bleibt jedoch die globale Verwaltung attributierter Namens­räume. Hierarchische Namens­räume eignen sich sehr viel besser für die verteilte Verwaltung, da die Position eines Namens im Namensraum bereits einen Hinweis auf den zuständigen Namensverwalter enthält.

2.2.3          Eigenschaften von Benutzer-Namen

Namen jeder Ausprägung tragen oft eine Bedeutung, die teilweise mit den Eigenschaften der benannten Objekte korreliert. Darüber hinaus besitzen Namen selbst bestimmte Eigen­schaften, die Einfluß auf die Verwal­tung von Namen besitzen.

2.2.3.1       Gültigkeitsbereich und Eindeutigkeit von Namen

Eine der Grundanforderungen, die an Namen gestellt werden, ist Eindeutigkeit. Der Bereich, in dem Namen bekannt und eindeutig sind, wird Gültigkeitsbereich eines Namens genannt. Namen können unterschiedliche Verbreitungsgrade aufwei­sen. Der Gültigkeitsbereich kann sowohl auf physische Bereiche, wie einzelne Rechner, Namensverwalter oder Netzwerk­berei­che als auch auf logische und organisatorische Bereiche, wie Arbeitsbereiche, Benutzer­umge­bungen und Kontexte, beschränkt sein. Gültigkeitsbereiche erleichtern einerseits das Herstellen der Eindeutigkeit von Namen und erhöhen ander­er­seits die Sicherheit im System.

Folgende Differenzierung der physischen Verteilung von Namen hat sich als geeignet erwiesen:

·      Lokale Namen: Im einfachsten Fall werden Namen nur lokal registriert und verwendet. Eine Verteilung der Namenseinträge über Verwaltergrenzen hinaus findet dabei nicht statt, so daß sie außerhalb des lokalen Namensverwalters nicht bekannt sind.

·      Verbundweite Namen: Besonders in Rechnerverbund­systemen ist es aufgrund des hohen Kooperationsgrades notwendig, Namen allen Knoten im Verbund zugänglich zu machen. Hierzu werden Namen entweder verbundweit propagiert oder ihre Gültigkeit auf bestimmte Namensver­walter beschränkt. Eine globale Verteilung von Namen ist hierbei weder wün­schens­wert noch erforderlich.

·      Globale Namen: Vielfach müssen Objekte über Namen auch außerhalb des lokalen Kno­tens und Rechner­verbundes global zugänglich sein. Dazu werden Namen global eindeutig vergeben und so im Verwalternetz verteilt, so daß sie global aufgelöst werden können.

Abbildung 2.9: Inklusion von Namen

Die Menge der lokalen Namen ist dabei eine Obermenge der verbundweiten Namen und diese wiederum ist eine Obermenge, der global registrierten Namen. Die Beschränkung der Regi­strierung und Auflösung von Namen auf Gültigkeitsbereiche ermöglicht dem Anwender der Namensverwaltung, die Gültigkeit von Namen seinem Wirkungskreis und seinen Sicherheits­bedürfnissen entsprechend anzupas­sen. Weitreichende administrative Entscheidungen, wie die Auswahl des administrativen Namensverwalters für einen Namenseintrag oder die Zuweisung eines Segments des Namens­raums zu einem Namens­verwalter bleiben hierbei der Namens­ver­waltung vorbehalten. Die in dieser Arbeit vorgestellte dynamische globale Namensver­waltung plaziert entsprechend dem Gültigkeitsbereich eines Namens den zugehörigen Namens­eintrag auf dem hierfür zuständigen Namensverwalter.

Neben den physischen existieren darüber hinaus auch logische Gültigkeitsbereiche in Form von Kontexten oder Benutzer- und Arbeitsbereichen. Hierarchische Namen dabei sind stets bezüg­lich eines Kontextes eindeutig, da Bindungen nur in gegebenen Kontexten existieren (vgl. Abbildung 2.10). Generische und attributierte Namen hingegen sind u.U. im gesamten Namens­raum mehrdeutig, können jedoch durch Arbeitsbereiche eingeschränkt werden.

Entspricht der Gültigkeitsbereich dem gesamten Namensraum, dann wird ein Name als absolu­ter Name bezeichnet. Da absolute Namen häufig flache Namen sind und in bezug auf den glo­balen Kontext aufgelöst werden, sind sie migrations­transparent und sehr benutzer­freundlich.

absoluter Name = Concat(Kontext-Name , „.“, relativer Name)

Entspricht der Gültigkeitsbereich des Namens n einer echten Teilmenge des gesamten Namens­raums, dann wird er als relativer Name bezeichnet. Relative Namen beginnen, vorausgesetzt der Name kann im Kontext interpretiert werden, nicht mit dem Symbol für die Wurzel (z.B. „/“), sondern bestehen aus dem vollständigen globalen Namen abzüglich dem Namen des Kontexts, in dem der Name gültig ist (Präfix/Suffix). Die Interpretation relativer Namen erfolgt in Bezug auf einen Start-Kontext. Die Eindeutigkeit relativer Namen ist einfach zu gewährleisten, da sie jeweils nur im Kontext eindeutig sein müssen.

Abbildung 2.10: Kontextabhängigkeit eindeutiger hierarchischer Namen

Für das Verständnis der Mechanismen der dynamischen globalen Namensverwaltung sind die aufgezeigten Definitionen des Gültigkeitsbereichs und der Eindeutigkeit hinreichend. Eine formale Definition der Begriffe findet sich in [Comer, 89].

2.2.3.2       Lebensdauer von Namen

Eine primäre Eigenschaft von Namen ist ihre Lebensdauer. Hierbei wird zwischen kurzlebigen und langlebigen Namen unterschieden. Ungeklärt blieb bisher die Frage, wie weit die Lebens­dauer eines Namens an die Existenz eines Objekts gebunden ist. Im einfachsten Fall kann die Existenz eines Namens in direktem Bezug zur Existenz des benannten Objekts stehen. Wird ein Name für die gesamte Lebensdauer (LT) einem Objekt zugeordnet, so handelt es sich um einen statischen Namen und es gilt:

Namen können Objekte durchaus überleben. Der Name ist dann im Laufe seines Lebens mehreren Objekten in chrono­logischer Folge zugeordnet. Die Existenz eines Namens ist nicht unmittelbar mit der Existenz einer Bindung für diesen Namen gleichzu­setzen, d.h. ein gültiger Namen muß nicht unbedingt gebunden sein.

Existieren Objekte länger als die an sie gebundenen Namen, so spricht man von temporären Namen. Insbesondere Synonyme sind häufig nur kurzzeitig an Objekte gebunden. Die Existenz eines Objekts ist nicht notwendigerweise mit der Existenz eines Namens verbunden.

Die Überlegungen zur Existenz von Namen und Objekten motivieren die Frage, wann Namen eigentlich existieren. Mattes vertritt die Auffassung, Namen seien ein Betriebsmittel und lassen sich wie ein solches verwalten [Mattes, 91]. Durch Erzeugen und Aufgeben werden potentielle Namen und verfügbare Namen[AL14]  ineinander übergeführt. Durch das Binden eines verfügbaren Namens an ein Objekt (Belegen) wird der Name gültig. Das Freigeben bei Aufhebung der Bin­dung macht den Namen erneut verfügbar (vgl. Abbildung 2.11).

Abbildung 2.11: Verwaltung von Namen als Betriebsmittel

Dieser These ist entgegen­zuhalten, daß Namen nicht nur im Betriebssystem erzeugt, belegt und freigegeben werden, sondern der Benutzer mit einem Namen ein bestimmtes Objekt assoziiert. Diese Assoziation kann jedoch nicht im gleichen Maße freigegeben und erneut belegt werden wie ein Betriebsmittel.

2.2.4          Wachstum von Namensräumen

Eine grundlegende Anforderung an Namensverwaltungen ist Skalierbarkeit. Voraussetzung hierfür ist, daß die Struktur von Namensräumen das Wachstum eines verteilten Systems berücksichtigt. Somit verbie­ten sich statische Strukturen, z.B. in Form fester Hierarchiestufen, die das Wachstum von Namensräumen limitieren. Verschiedene Arten des Wachstums lassen sich bei Namensräumen identifizieren:

·      numerisch

·      administrativ

·      geographisch

Das numerische Wachstum eines Namensraums geht einher mit der Zunahme benannter Objekte und bewirkt normalerweise zunächst eine horizontale Ausdehnung des Namensraums. Erst wenn sich die Namensverwaltung oder der Anwender nicht mehr im Stande sieht, die Flut von Namen durch die horizontale Verbreiterung des Namensraums zu bewältigen, wird der Namensraum administrativ wachsen. Hierbei nimmt die Tiefe des hierarchischen Namens­raums zu. Das geographische Wachstum eines Namensraums wird durch den Aspekt der Verteiltheit motiviert. Insbesondere das Verbinden lokaler Namensräume zu einem einheitlichen globalen Namensraum erfordert in verteilten Systemen besondere Aufmerk­sam­keit.

2.2.4.1       Horizontales und vertikales Wachstum hierarchischer Namensräume[AL15] 

Frühe Namensverwaltungen unterstützten lediglich eine feste Anzahl von Hierarchie­stufen des Namensraums (vgl. Grapewine und Clearinghouse in Anhang B). Ihr Wachstum war ebenso wie das Wachstum flacher und attributierter Namensräume auf die horizontale Ausdeh­nung beschränkt. Obwohl dieser Ansatz nicht beliebig skalierbar ist, genügte er doch den Anfor­de­rungen zur Verwaltung einiger tausend Namen. Insbesondere bestand die Schwierig­keit, mit zunehmender Anzahl benannter Objekte auf den jeweiligen Hierarchiestufen aussagekräftige und eindeutige Namen zu finden. Das horizontale Wachstum verursacht besonders bei der verteilten Auflösung generi­scher Namen hohe Kosten, da in breiten Namens­räumen Anfragen eventuell an alle Verwalter untergeord­neter Kontexte propagiert werden müssen.

Abbildung 2.12: Horizontales und vertikales Wachstum hierarchischer Namensräume

Die Zahl der Hierarchieebenen in baumartigen Namensräumen kann aus Gründen der Einfach­heit fest sein. Dieser Ansatz skaliert jedoch nicht, denn je weniger Ebenen vorgesehen sind, desto schwieriger wird die Verteilung von Namen in einem globalen Netzwerk. Um ein admini­stratives Wachstum zu ermöglichen, muß die Anzahl der Hierarchieebenen variabel sein. Namens­räume wachsen zum Beispiel vertikal, wenn sie zur Bildung eines größeren Namens­raums miteinander verbunden werden. Mit zunehmender Tiefe des Namensraums wird jedoch die Auflösung von Namen teurer, da mehr Resolutionsschritte notwendig werden.

Zur Benennung von Rechnerknoten reichen im allgemeinen zwei bis drei Hierarchieebenen aus; im Internet werden beispielsweise häufig drei Ebenen verwendet. Dabei ist dann eine 1:1-Zuordnung von Kontexten zu verwaltenden Instanzen möglich. Zur Benennung weiterer Objekte sind jedoch beliebig viele Ebenen wünschenswert; Dateien in einem verteilten Datei­system können beispielsweise in Verzeichnissen mit beliebig vielen Hierarchiestufen abgelegt sein. In diesem Fall verwaltet aus Effizienzgründen eine Instanz meist mehrere Kontexte.

2.2.4.2       Geographisches Wachstum von Namensräumen

In verteilten Systemen stellt insbesondere das geographische Wachstum von Namensräumen eine Herausforderung dar. Die Konstuktion verteilter Namensräume wäre nicht denkbar, ohne die Möglichkeit lokale, autonome Namensräume durch verschiedene Mechanismen zu verbin­den:

·      Einführen einer neuen Dimension

·      Mehrpunktverbindungen

·      Einführen einer gemeinsamen Wurzel (super root)

·      Montieren von Verzeichnissen

·      Lokale Namensräume als Blätter eines globalen Namensraums

Der älteste Ansatz zum Verbinden autonomer Namensräume ist das Einführen einer zusätzlichen Dimension. Lokale Verzeichnisse werden durch ein orthogonales Verzeichnis von Knoten- oder Volume-Namen miteinander verbunden. Globale Dateinamen bestehen dann aus dem Knoten­namen und dem lokalen Dateinamen. Dieser Ansatz ist daher kaum orts- jedoch weitgehend zugriffstransparent.

Eine weitere Möglichkeit zum Verbinden lokaler Namensräume sind Mehrpunktverbin­dungen (Multicast/Broadcast) (vgl. Abbildung 2.13). Die einzelnen Namensräume existieren gleichbe­rechtigt nebeneinander und besitzen keine gemeinsame Wurzel. Sie werden implizit durch Broadcast-Nachrichten verbunden. Bei der Auflösung und Registrierung von Namen wird der für einen Namensraun zuständige Verwalter durch Broadcast-Nachrichten kontaktiert. Ein Vor­teil dieses Verfahrens ist, daß keine externen Verweise verwaltet werden müssen. Broadcast-Verfahren sind jedoch i.a. sehr teuer und skalieren nicht. Ursache hierfür ist primär nicht die Anzahl der erforder­lichen Netzwerk­nachrichten, sondern deren Bearbeitung. Jeder Netzwerk­knoten muß die Broadcast-Nachricht bearbeiten, unabhängig davon, ob sie ihn betrifft oder nicht. Oftmals besitzt das Kommunika­tions­medium auch keine Mehr­punkt­fähigkeit.

Abbildung 2.13: Methoden zum Vereinigen von Namensräumen

Die Konstruktion großer verteilter Namensräume wäre nicht möglich ohne die Fähigkeit, lokale Namensräume zu kombinieren. Eine verbreitete Methode, autonome Verzeichnisse in einer verteilten Struktur zu arrangieren, ist das Einführen einer gemeinsamen Wurzel (super root). Lokale Verzeichnisse werden hierbei orts- und zugriffs­trans­parent unter der sogenannten super root zu einem Verzeichnis zusammen­gefaßt, das alle Unterbäume enthält. Super root-Einträge sind virtueller Natur und werden durch die Software-Schichten realisiert.

Eine der Eigenschaften des hierarchischen Namensmodells, die es für die Namensverwaltung so wertvoll machen, ist, daß die Wurzel einer jeden Hierarchie an jeden beliebigen Knoten einer anderen Hierarchie gebunden werden kann und so ein Konstrukt entsteht, das wiederum eine Hierarchie darstellt (Montieren). Formaler ausgedrückt, die Klasse der hierarchischen Namens­räume ist abgeschlossen unter der Operation des Zusammenfügens.

Die Verwaltung lokaler Namensräume als Blätter hierarchischer globaler Namensräume (vgl. Abbildung 2.14) ist eine Verallgemeinerung des super root-Ansatzes. An den Blättern befinden sich flache, hierarchische oder auch attributierte Namensräume, die von der globalen Namens­verwaltung autonom sind. Die unterschiedlichen Namensräume lassen sich oft durch einen syntaktischen Bruch in globalen Namen identifizieren (z.B.: hermes.informatik.uni-ulm.de/papers /naming/dns).

Abbildung 2.14: Lokale Namensräume als Blätter eines globalen Namensraums

Ein verbreiteter Ansatz zur Konstruktion knotenübergreifender Verzeichnis­strukturen ist das wechselseitige Montieren autonomer Namensräume. In Unterver­zeichnissen sind hierzu Ver­weise auf entfernte Verzeichnisse angelegt (vgl. NFS), die lokal in sog. Mount-Tabellen gehal­ten werden. Das Montieren von Verzeichnissen bietet einen hohen Grad an Flexibilität in der Konfiguration. Da jeder Knoten seine eigene Verzeichnisstruktur besitzt, ist das Ziel der Ort­stransparenz nur bedingt realisierbar. Durch das wechselseitige Montieren gemeinsam genutzter Bereiche kann jedoch eine einheitliche Verzeichnisstruktur erzeugt werden (vgl. Coda). Da jeder Punkt in einem „gemounteten“ Verzeichnis selbst wieder ein „Mount“-Punkt sein kann, impli­ziert der Ausfall eines Knotens das Verschwinden einer Menge von Unterver­zeichnissen. Die Skalierbarkeit des Konzepts ist durch die Verwaltung der entfernten Verweise in Mount-Tabel­len beschränkt.

 

Die Struktur und die Eigenschaften des Namensraums geben wesentliche Rahmen­bedingung für den Entwurf einer dynamischen globalen Namensverwaltung vor.

 

2.3         Integration attributierter und hierarchischer Namen

Hierarchien bilden einen vergleichsweise restriktiven organisatorischen Rahmen. Datenbank-Designer haben bereits früh erkannt, daß ausschließlich hierarchi­sche Strukturen nicht geeignet sind, um die komplexen Beziehungen realer Objekte in Daten­banken zu repräsentieren[AL16] . Daher wurden Anstrengungen unternommen, um die hierarchische Struktur ganz zu über­winden. Zur Identifizierung von Objekten in verteilten Systemen wurden attributierte Namensverwaltungen untersucht (vgl. hierzu z.B. [Bowman, 90a], [Peterson, 88a]). Unter der Annahme, daß die attributierten Namen eines Objekts orthogonal sind, legten sie diese in flachen Namensräumen ab. Das Fehlen von Gültig­keits­bereichen für Attribute und von Naviga­tions­informationen setzt der Skalierbarkeit attributierter Namensverwaltungen jedoch enge Grenzen und ver­hindert die Übertragung dieser Konzepte auf globale verteilte Systeme.

Die Konzepte der in dieser Arbeit vorgestellten dynamischen globalen Namens­verwal­tung geben dem Anwender die Möglichkeit, globale Objekte selbständig zu benennen und durch Namen zu beschreiben. Nachfolgender Abschnitt diskutiert Ansätze, um attributierte Namen in hierarchischen Namens­räumen zu repräsentieren und so die verwaltungs­technischen Vorteile hierarchischer Namens­räume mit der Flexibilität attribu­tierter Namens­räume zu ver­binden.

2.3.1          Bestehende Ansätze zur Integration attributierter und hierarchischer Namensräume

Aufgrund der Unzulänglichkeiten sowohl hierarchischer als auch attributierter Namens­verwal­tungen wurde in den vergan­genen Jahren eine Vielzahl von Modellen vorgeschlagen, die das herkömmliche hierarchische Organi­sationsschema um Elemente der attributierten Namens­ver­waltung erweitern.

Verschiedene attributierte Namensmodelle wurden für hierarchische Dateisysteme entwickelt. Diese Ansätze versuchen eine attributierte Charakterisierung von Dateien zu ermöglichen, wobei gleichzeitig die Vertrautheit und Einfachheit der hierarchischen Organisa­tion soweit wie möglich erhalten bleiben soll. In dem von Mogul [Mogul, 86] vorgeschla­genen Schema besitzt eine Datei einen eindeutigen hierarchischen Pfadnamen und zusätzlich eine orthogonale Menge von typisierten Attributen in einem flachen attributierten Namens­raum (vgl. Abbildung 2.15). Das Semantic File System [Gifford, 91] wendet Analyse­programme auf Dateiinhalte an und gene­riert aus den gewon­nenen Informationen und Dateieigen­schaften virtuelle Verzeichnisse, deren Einträge Attribut­werte sind. Prospero [Neuman, 93] ermöglicht die Anbindung eines Filterpro­gramms an einen Pfad, das die Interpretation des restlichen Namens bestimmt.

Diese Ansätze bieten eine höhere Flexibilität als streng hierarchische Namensver­waltungen, sie erzwingen jedoch, daß jede Dateieigenschaft entweder in einem flachen attribu­tierten Namens­raum oder als Teil einer Hierarchie abgelegt wird. Hierdurch wird das Spektrum der repräsen­tierbaren Namenskonstrukte deutlich eingeschränkt.

Abbildung 2.15: Speicherung von Attributen im hierarchischen Namensraum

Ein weiteres Beispiel für eine semi-hierarchische Namensverwaltung ist der X.500 Directory Service [CCITT/ISO, 88]. Jede Ebene der X.500-Namenshierarchie enthält eine bestimmte Menge von Attributen. Daher besteht zwischen den Attributen unterschiedlicher Ebenen eine vordefinierte Ordnung. Neufeld [Neufeld, 89] schlägt für die Flexibilisierung dieses Schemas eine Lockerung der Ordnung der Namens­komponenten vor.

Erste allgemeine Ansätze zur Verein­heit­lichung attributierter und hierarchischer Namen finden sich in [Sechrest, 92]. Die Schwächen dieser Ansätze liegen insbesondere in der fehlenden syntaktischen Unterstützung der selbstän­digen Konfigurierung des Namensraums.

Keines der vorgestellten Systeme stellt für sich eine befriedigende Lösung dar. Vielmehr zeigen sie Konzepte auf, die sinnvoll in einen Rahmen gebracht werden müssen, der eine Vielzahl von Namens­modellen unterstützt. Dabei ist vor allem darauf zu achten, daß sowohl für attributierte als auch für hierarchische Namen eine einheitliche Syntax und Interpretationsvorschrift besteht. Wie Pike und Wineberger [Pike, 85] herausstellen, bieten Systeme, in denen jeder Teil eines Namens syntaktisch uneinheitlich inter­pretiert wird, sehr viel weniger Flexibilität, als ein System, das jede Komponente gleich behandelt. Sowohl die tool-basierten Umge­bungen moderner Betriebssysteme als auch die umfangreichen Namensräume verteilter Datei­systeme sind zum Teil deshalb so erfolgreich, weil sie auf einem einheitlichen Namensschema basieren.

2.3.2          Ein graph-orientierter Ansatz zur Integration hierarchischer und attributierter Namensräume

Um die Problematik der Integration attributierter und hierarchischer Namensräume zu verdeutli­chen und mögliche Ansätze zur Integration aufzuzeigen, sei der weiteren Diskussion zunächst ein Beispiel vorangestellt. Betrachten wir ein typisches Problem: Eine Menge von Geräten der Fakultät für Informatik soll benannt werden, um später auf sie zuzugreifen (vgl. Tabelle 2.1).

 

Objekt 1

600 dpi PostScript Laser-Drucker der Abteilung „Verteilte Systeme (vs)“ der Fakultät „Informatik“ mit der Bezeichnung „KomLab“

Objekt 2

AppleShare Datei-Server der Abteilung „Verteilte Systeme (vs)“ der Fakultät „Informatik“ mit der Bezeichnung „VSServer“

Objekt 3

300 dpi PCL Tintenstrahl-Drucker der Abteilung „Verteilte Systeme (vs)“ der Fakultät „Informatik“ mit der Bezeichnung „VSOffice“

Tabelle 2.1: Natürlichsprachliche Beschreibung von Geräten anhand ihrer Eigenschaften

Ausgehend von dieser Menge von zu benennenden Objekten und deren Beschreibung muß zunächst eine Menge atomarer Ausdrücke identifiziert werden, die die Objekte eindeutig beschreiben und als Namenskomponenten verwendet werden können. Dabei ist festzustellen, daß die vorliegende Beschreibung der Objekte sowohl Eigenschaften als auch natürliche Namen enthält. Um nun einen Namensraum zur Beschreibung dieser Objekte aufzubauen, sind zwei grundlegende Ansätze denk­bar:

•     Ein graph-orientiertes Namensmodell, das die Namensteile als Kanten in einem Graphen repräsentiert. Ein vollständiger Name in diesem Modell beschreibt einen Pfad im Graphen von der Wurzel zum benannten Objekt. Dieses graph-orientierte Modell ist die Basis der hierarchischen Namensverwaltung.

•     Ein mengen-orientiertes Namensmodell, das den Namensraum in Form einer Tabelle reprä­sentiert. Die Attribute, die ein Objekt identifizieren, sind in den Spalten der Tabelle aufführt (vgl. Abschnitt 2.2.2.5). Ein attributierter Name im mengen-orientierten Modell entsteht durch den Schnitt von Mengen und wird durch die Zeilen der Tabelle repräsentiert.

Der wesentliche Unterschied zwischen diesen Namensmodellen ist, daß die Einbindung von Attributen in einen Graphen eine Reihe von Einschrän­kungen über ihren Gebrauch in Namen festlegt.

Nehmen wir nun an, daß diese kleine Menge von Informationen aus Tabelle 2.1 so in einen hierarchischen Namens­raum aufge­nommen werden soll, daß jedes Gerät aus einer willkürlichen Menge anderer Geräte einfach herausgefunden werden kann. Dabei sollen zunächst keine Attri­buttypen im Namensraum repräsentiert werden.

Abbildung 2.16: Partielle Darstellung der Informationen aus Tabelle 2.1 in einem Graphen

Abbildung 2.16 zeigt einen einfachen Graphen, der einige der Informationen aus Tabelle 2.1 enthält. Die Struktur ist intuitiv und leicht nachzuvollziehen. Würden jedoch alle Informa­tionen aus Tabelle 2.1 dargestellt, so wären die Namen der Objekte viel zu lang, um noch handhabbar zu sein. Die zu repräsentierenden Objekteigenschaften sind teilweise logisch unabhängig. Der Anwender hat daher bei der Registrierung zu entscheiden, welche Eigenschaften im hierarchi­schen Namensraum zu akzentuieren sind.

Gleichzeitig erzwingt die Repräsentation von Informationen in Graphen eine feste Ordnung. Während die üblichen Suchfunktionen in hierarchischen Systemen adäquat sind, um im Namensraum in Abbildung 2.16 alle Drucker der Abteilung „Verteilte Systeme“ aufzulisten, so gibt es keine einfache Möglichkeit, alle Laser-Drucker mit 600 dpi zu ermitteln. Streng hierar­chische Strukturen allein sind für eine derartige Selektion von Objekten nicht geeignet, da dazu das Traversieren des gesamten Namensgraphen notwendig ist.

Abbildung 2.17: Tabellarische Darstellung der Informationen aus Tabelle 2.1

Im Vergleich hierzu zeigt Abbildung 2.17 eine Tabelle, die sämtliche[AL17]  Informationen aus Tabelle 2.1 enthält. In den Zeilen der Tabelle befinden sich attributierte Namen als Prädikate aus Attri­butwerten, die in den Spalten der Tabelle dargestellt werden. So ist es möglich, Objekte zu identifizieren, indem beliebige Kombinationen von Informationen über sie verwendet werden. Es gibt keine willkürliche Festlegung, welche Information wichtiger ist, wie in hierarchischen Namensräumen.

Diese Freiheit hat jedoch ihren Preis. Was verlorengeht, sind die Ortsinformationen, die hierar­chi­sche Namensräume enthalten. Während graph-orientierte Namensräume die Navigation im Verwalternetz bei der Namensauflösung unter­stützen, sind attribut-basierte Namensräume mehr für die iterative Verfeinerung von Informa­tio­nen geeignet. Diese beiden Vorzüge sind für die Organisation von Informationen komplementär zueinander.

Abbildung 2.18: Hierarchische und tabellarische Darstellung der Informationen aus Tabelle 2.1

Die Stärken der beiden unterschiedlichen Darstellungen für Namensräume können in vielerlei Hinsicht kombiniert werden. So werden in Abbildung 2.18 einige der Eigenschaften, die im Namens­graphen nicht dargestellt sind, als Attribute in einem orthogonalen, attributierten Namensraum erfaßt. Dies ist die Basis der Darstellung von Dateiattributen, die von Mogul [Mogul, 86] und Gifford [Gifford, 91] vorgeschlagen wurde.

Die im folgenden vorgestellte einheitliche Darstellung für hierarchische und attributierte Namensräume berücksichtigt Beziehungen zwischen Attributen. Ohne Attribute und Objekte in eine einzige Baumstruktur zu zwängen, können so bestehende Abhängigkeiten zwischen Attri­buten in einem Namensraum modelliert werden. Im Zentrum dieses Ansatzes steht folgende Überlegung:

     Ein hierarchischer Name „info.vs.Drucker.KomLab“ kann sowohl eine Charakterisierung eines Objekts bei der Erzeugung als auch in einer Suchanfrage darstellen. Wie gezeigt, unter­liegen beide Aktivitäten starken Einschrän­kungen durch die hierarchische Struktur. Obwohl die Kategorie „Drucker“ logisch orthogonal zu „vs“ erscheint, ist der Anwender dennoch ge­zwungen, zu entscheiden, welcher Namensteil bevorzugt, d.h. weiter oben im Namensraum zu positionieren ist. Es gibt keinen ersichtlichen Grund, warum „Drucker.info.vs.KomLab“ kein gleich­wertiger Name des Objekts O1 sein sollte (vgl. Abbildung 2.19).

Abbildung 2.19: Restrukturierung von Hierarchien mit Teilordnungen

Es wird klar, daß die Struktur eines hierarchischen Namensraums eine vordefinierte Sicht auf die darin benannten Objekte darstellt. Auswertungen von Namen nach Kriterien, die dieser Sicht nicht entsprechen, sind sehr aufwendig. Bei genauerer Betrachtung hierarchischer Namensräume wird deutlich, daß die hierarchische Ordnung der Namen in Teilordnungen zer­fällt. Innerhalb einer Teilordnung ist keine Vertauschung von Namensteilen möglich, da zwischen ihnen Abhängigkeiten in Form von Inklusionen bestehen. Falls die Reihenfolge von attributierten Namen oder von Teilordnungen von attributierten Namen nicht signifikant ist, werden diese als orthogonal zueinander bezeichnet. Orthogonale Attribute können umgeordnet werden, ohne daß sich die Eigenschaften beschriebener Objekte ändern (vgl. Abbildung 2.19).

Abbildung 2.20: Orthogonale Attribute aus Tabelle 2.1 in hierarchischen Namensräumen

Im Graphen in Abbildung 2.20 ist nun die ganze Information aus Tabelle 2.1 enthalten. Im Vergleich zu Abbildung 2.16, sind hier auch Attributtypen wie Fakultät, Abteilung und Geräte im Namensraum repräsentiert. Volle Linien in Abbildung 2.20 kennzeichnen hierarchische und komplementäre Beziehungen zwischen Attributen, graue Linien repräsentieren orthogonale Attribute. Die Interpretation eines Namens kann mehreren grauen Linien folgen, jedoch immer nur einer vollen Linie. Die im Graphen repräsentierten Beziehungen zwischen Attributen schränken somit die Interpretation von Namen ein.

Innerhalb einer Teilordnung können wiederum Teilordnungen existieren, die zueinander ortho­gonal sind (z.B. Seitenbeschreibung, Druckwerk und Auflösung in Abbildung 2.20). Hieraus ergibt sich eine rekursive Verschachtelung von Teilordnungen. Die Vertauschbarkeit ist dabei nur zwischen Teilordnungen derselben Ebene gegeben. Orthogonale Attribute, zwischen denen keine hierarchische Ordnung besteht, bilden einen attributierten Namensraum und können in separaten Teilbäumen untergebracht werden. Dieses Vorgehen erhält die Vorteile hierarchi­scher Namensräume bei der Navigation im Verwalternetz, während gleichzeitig die Restrik­tionen einer strikten Hierarchie weitgehend vermieden werden.

2.3.3          Konzepte zur Integration attributierter und hierarchischer Namen

In hierarchischen Namensräumen wird die Interpretation eines Namens einzig durch den Kontext bestimmt, in dem er enthalten ist. Es ist gerade diese Interpretationsvorschrift, die hier­archische Namensräume so mächtig macht. Diese Kontextabhängigkeit verursacht jedoch viele der Einschränkungen graph-orientierter Namensverwaltungen (vgl. Abschnitt 2.2.2.2).

Für die Repräsentation von Attributen wird die Semantik hierarchischer Namen erweitert, wobei die von hierarchischen Namensräumen bekannte Semantik der Namensinterpretation weit­ge­hend erhalten bleibt. Ein Attribut stellt einen Kontext (virtuelles Verzeichnis) dar, der alle Objekte einer bestimmten Eigenschaft enthält. Das Maß, in dem Attribute mit den einzelnen Namenskontexten verbunden sind, bestimmt den Grad, in dem der Namensraum graph-orien­tierte Semantiken verkörpert. Namen werden sukzessive im Kontext des vorangegangenen Namens­teils interpretiert. Jeder neue Namensteil fügt dem Prädikat, das die Interpretation des Namens bestimmt, eine weitere Komponente hinzu. Jeder vollständige Name repräsentiert ein Prädikat, das entweder ein einzelnes Objekt oder einen Kontext identifiziert. Jedes Präfix eines vollstän­digen Namens repräsentiert einen Kontext, so daß die Notation des aktuellen Verzeich­nisses, bezüglich dessen relative Pfad­namen inter­pretiert werden, seine Gültigkeit behält.

Ein Namensraum in diesem Schema wird aus einer Menge von Attributen und einer Menge von Interpretationsvorschriften bestimmt. Diese Interpretationsvorschriften definieren die Beziehun­gen zwischen den Attributen und somit die Struktur des Namensraums. Werden diese Interpre­ta­tionsvorschrif­ten strikt angewendet, so sind sie hinreichend, um eine gewöhnliche Hierarchie zu bilden. Indem syntaktisch mehr oder weniger Beschränkungen eingeführt werden, kann ein ganzes Spektrum von möglichen Namenskonstrukten abgedeckt werden.

Im folgenden wird ein Rahmenwerk zur Namensverwaltung vorgestellt, das hierarchische und attributierte Prinzipien vereint. Die Basis des hier vorgestellten Ansatzes ist die Darstellung der Beziehungen, die die Struktur des Namensraums bilden, als explizite Interpretationsvor­schrif­ten. Indem Klassen von Interpre­tationsvorschriften definiert werden, die verschiedene Facetten von Namens­raum-Semantiken widerspiegeln, können Namensräume erzeugt werden, die alle Kombi­nationen dieser Semantiken enthalten. Nachfol­gend werden Namenskonstrukte für die Integration hierarchischer und attributierter Namensräume vorgestellt:

·      Hierarchische Namensräume             sind ein fundamentales und hilfreiches Konstrukt. Jeder Kontext des hierarchischen Namensraums beschreibt eine Eigenschaft, die alle Objekte rela­tiv zu diesem Kontext erben. Ein Objekt besitzt dann eine bestimmte Eigenschaft, wenn es sich in einem Kontext befindet, der ein Attribut mit dieser Eigenschaft darstellt.

·      Mehrere unabhängige Hierarchien: Das Konzept graph-förmiger Namensräume kann durch mehrfache Hierarchien, die orthogonale Objekteigen­schaften enthalten, erweitert werden. Nicht alle Eigen­schaften eines Objekts sind miteinander vereinbar und lassen sich in dersel­ben Hierarchie unterbringen, da sie oft nicht in direkter Beziehung zueinander stehen.

·      Optionale Kontexte: Eine wesentliche Einschränkungen hierarchischer Namensräume ist der Zwang, Objekte extensiv charakterisieren zu müssen. Werden einzelne Teile von Namen als optional gekennzeichnet, dann ist es einfacher tiefe Verschach­telungen zu bilden, die die enthaltenen Objekte voll charakterisieren.

·      Graph-förmige Namensräume: Durch Kontexte, die Verweise in andere Kontexte enthalten, und durch Synonyme entstehen graph-förmige Namensräume, die eine individu­elle Anpas­sung des Namensraums an die Erfordernisse eines Anwenders erlauben.

·      Nicht-hierarchische Namensräume als Blätter hierarchischer Namensräume: Hierarchien eignen sich bestens für die oberen Ebenen eines großen Namensraums. Jeder hierarchi­sche Namensraum kann attributierte Namensräume in seinen Blättern enthalten. (vgl. Abschnitt 2.2.4 und Abbildung 2.23).[AL18] 

·      Implizite und explizite Repräsentation von Attributtypen: Einerseits können Attributtypen implizit in den Knoten des Namensgraphen abgelegt werden, wobei im hierarchischen Namensraums nur Attribut­werte enthalten sind (vgl. Abbildung 2.16), andererseits können sowohl Attributtypen als auch Attribut­werte im Namensraum repräsentiert sein.

Die vorgestellten Konzepte für sich stellen jeweils nur einzelne Ansätze zur Konstruk­tion globaler attributierter Namensverwaltungen dar. Erst die Kombination dieser Konzepte bildet ein Rahmen­werk zur Namensverwaltung, das Namensräume mit vielen unterschiedli­chen Strukturen ermöglicht und es den Anwendern erlaubt, Namensräume zu erzeugen, die ihren individu­ellen Anforderungen genügen. Gleichzeitig läßt dieses Schema es zu, Namens­räume unterschiedlicher Struktur zu kombinieren, um weiträumige verteilte Systeme zu bilden.

2.3.3.1       Abhängige und orthogonale Attribute in hierarchischen Namensräumen

Die Darstellung der Attribute aus Abbildung 2.7 in einem streng hierarchischen Namensraum zeigt Abbildung 2.21. Die Farb-, Form- und Größen-Attribute sind logisch unabhängig und orthogonal zueinander, jedoch erzwingt die Darstellung in streng hierarchischen Namens­räumen das Festlegen einer willkürlichen Ordnung (vgl. Abbildung 2.21). Diese Ordnung schränkt die Möglichkeiten zur attributierten Suche nach Objekten erheblich ein. Da die Attribute orthogonal sind, ist der Name „rot.mittel.eckig“ prinzipiell äquivalent mit dem Namen „eckig.rot.mittel“, jedoch erlaubt es ein streng hierarchischer Namensraum nicht, letzteren Namen aufzulösen, wenn er nicht zuvor in dieser Reihenfolge registriert wurde.

Abbildung 2.21: Alternative Repräsentation von Attributwerten in hierarchischen Namensräumen

Um Namen unabhängig von der Reihenfolge ihrer Komponenten aufzulösen, bieten sich verschiedene Möglichkeiten an. Zum einen können orthogonale Komponenten von Namen permutiert werden, um diese Permutationen jeweils separat im hierarchischen Namensraum abzulegen. Da somit alle möglichen Darstellungen eines Namens im Namensraum repräsentiert sind, ist die Reihenfolge der Attribute im Prädikat bei der Suche nicht signifikant.

            eckig.rot.mittel          wird registriert als:        eckig.rot.mittel,  rot.mittel.eckig

Alternativ besteht die Möglichkeit, die orthogonalen Attribute eines Namens in der gegebenen Reihenfolge zu registrieren und erst bei der Suche unabhängige Attribute im Prädikat zu permu­tieren.

            eckig.rot.mittel          wird gesucht als:           eckig.rot.mittel,  rot.mittel.eckig

Die Namenskomponenten „rot.mittel“ stellen in obigem Beispiel eine Teilordnung dar. An dieser Stelle sei nochmals darauf hingewiesen, daß Teilordnungen innerhalb orthogonaler Attri­but­hierarchien verschachtelt sein können. Ebenso sind im hierarchischen Namensraum in Abbildung 2.21 keine Attributtypen, sondern nur Werte repräsentiert.

2.3.3.2       Separate Hierarchien für orthogonale Attribute

Um eine attributierte Suche im Namensraum zu erleichtern, sollten sich einerseits orthogonale Attribute von Attributen mit einer Ordnungsbeziehung in der Syntax der Namen unter­scheiden, andererseits sollten orthogonale Attribute auch in der Struktur des Namens­raums repräsentiert werden.

Um orthogonale Attribute in Namen zu kennzeichnen, wird in der dynamischen globalen Namensverwaltung die streng sequentielle Interpreta­tions­vorschrift für Namen, die Kontexte z.B. durch Punkte „.“ trennt, um die Notation der runden Klammer „()“ erweitert. Attribute, die durch runde Klammern zusammengefaßt sind, definieren eine Teilordnung. Der Name „eckig.(rot.mittel)“ kann somit als „eckig.rot.mittel“ oder „rot.mittel.eckig“ interpretiert werden.

Orthogonale Attribute und Teilordnungen, die in Namen durch runde Klammern getrennt sind, können in unabhängigen Hierarchien verwaltet werden. Diese Art der Repräsentation reduziert die Tiefe der Verschachtelung der Namens­räume, ermöglicht eine bessere Parallelisierung der Suche und vermeidet eine willkür­liche Ordnung zwischen orthogonalen Attributen. Optionale Pfade in einem Kontext kennzeichnen orthogonale Attribute. Separate Teilbäume für orthogo­nale Attribute bilden auf der obersten Ebene einen attributierten Namensraum als Wurzel für untergeordnete hierarchische Namensräume.

Abbildung 2.22: Repräsentation orthogonaler Attribute in separaten Hierarchien

Abbildung 2.22 zeigt unabhängige Attribute in separaten Hierarchien. Wie ersichtlich ist, sind die Einträge an den Blättern der Teilbäume nicht mehr eindeutig, selbst wenn die einzelnen Objekte eindeutige Beschreibungen durch Attribute aufweisen.

Da die globale attributierte Suche nach einem bestimmten Objekt durch die Notwendigkeit der Schnittmengenbildung der zu den einzelnen, spezifizier­ten Attributen ermittelten Objekt­mengen einen hohen Aufwand und eine erhebliche Netzwerklast verursacht, ist es sinnvoll, in jeder Teilhierarchie alle Attribute eines Objekts vollständig abzulegen (vgl. Kapitel 4).

2.3.3.3       Attributierte Namensräume als Blätter hierarchischer Namensräume

Der Gültigkeitsbereich eines Attribut­s wird durch die Interpretationsvorschrift definiert. In streng hierarchischen Namensräumen wird ein Attribut stets relativ zu einem Kontext inter­pre­tiert und hat somit nur lokal eindeutig zu sein. Attribute in unterschied­lichen Teilbäumen eines hierarchischen Namensraums können daher dieselben Bezeich­nungen besitzen.

Abbildung 2.23: Attribute in den Blättern eines hierarchischen Namensraums

Da jedes Attribut in einer Hierarchie einen separaten Kontext einführt, besteht zwischen den Komponenten eines attributierten Namens eine Ordnung. Diese Ordnung kann gelockert wer­den, wenn Attribute zugelassen werden, die keinen neuen Kontext einführen. Die Attribute Farbe, Größe und Form werden im Kontext „info.vs.KomLab“ interpretiert, der das unterste hierarchische Attribut darstellt. Die Attribute Farbe, Form und Größe spannen einen attributier­ten Namens­raum auf und schließen sich nicht gegenseitig aus (orthogonal):

info.vs.KomLab.(Farbe.blau) (Größe.klein) (Form.eckig)[AL19] 

Neben der Koexistenz orthogonaler Attribute im selben Kontext besteht weiterhin die Möglich­keit, daß für ein Objekt Attribute mit mehreren, nicht-exklusiven Attributwerten registriert wer­den. Die Darstellung mehrwertiger Attribute in hierarchischen Namensräumen erfolgt durch optionale Pfade. Schließen sich Attributwerte gegenseitig aus, so sind die Mengen der Objekte mit diesen Attributwerten disjunkt und die Pfade im Graphen exklusiv. Auf diese Art können Elemente der attributierten Namensverwaltung in hierarchische Namensräume eingebracht wer­den. Das Attribut Farbe kann beispielsweise für ein Objekt mehrere Werte annehmen, während die Werte des Attributs Größe komplementär zueinander sind:

info.vs.KomLab.(Farbe.(blau) (rot)) (Größe.klein) (Form.eckig)

Zusätzlich zu den im hierarchischen Namensraum bereits erfaßten Attributen können weitere orthogonale Attri­bute eines Objekts in attributierten Namens­räumen an den Blättern eines hierarchischen Namensraums abgelegt werden (vgl. Abbildung 2.23). Als Nachteil ist hierbei anzusehen, daß diese Attribute nicht nach der­selben Interpre­­tationsvorschrift behandelt werden können, wie die Attribute im hierarchi­schen Namensraum. Außerdem ist bei der Suche nach Objekten mit Eigen­schaften, die nicht in der Hierarchie erfaßt sind, die Hierarchie, in deren Blätter sich die gesuchten Attribute befinden, immer vollständig zu durchlaufen. In den Blättern eines hierarchischen Namensraums empfiehlt es sich deshalb, primär Attribute zu speichern, die keinen diskreten Werte­bereich aufweisen oder ständigen Änderungen unterworfen sind.

2.3.3.4       Zyklische und azyklische hierarchische Namensräume

Eine Möglichkeit zur Erhöhung der Flexibilität bei der Vergabe und Verwendung von Namen bieten unvoll­ständige Namen in hierar­chischen Namens­räumen. Diese können realisiert werden, indem bestimmte Namensteile optional registriert werden, sich aber ansonsten normal in die Hierarchie einfügen. Realisiert werden kann dies durch Querverweise (Links) oder durch optio­nale Kontexte bei der Registrierung von Namen. Im nachfolgenden Namen ist der Teilname „uni-ulm“ optional:

 (uni-ulm).info.vs

Optionale Kontexte erzeugen keine Baumstruktur, sondern einen zyklischen, gerichteten Graphen (vgl. Abbildung 2.24). Da in derartigen Graphen die Ordnung nicht signifikant ist, ist es nicht erforderlich, alle Namensteile zu spezifizieren, um ein Objekt zu identifizieren. Falls Kontexte durch Verweise beliebig verbunden werden, besteht beim Durchlaufen eines Graphen die immanente Gefahr der Entstehung von Zyklen. Diese sind zu erkennen, um ein Terminieren der Operationen auf dem Namensgraphen zu gewährleisten.

Abbildung 2.24: Optionale Namensteile im zyklischen gerichteten Graphen

Für attributierte Namen sind u.a. Namens­räume in Form zyklischer Graphen gebräuchlich. Neben der Möglichkeit zur Angabe unvollständiger Namen mit optionalen Teilnamen in zykli­schen, gerichteten Namensgraphen sollte ein Objekt gleichzeitig durch mehrere alternative Namen identifiziert werden können. Im folgenden Beispiel wird der Kontext „uni-ulm.info“ auch durch den alternativen Namen „home“ bezeichnet:

(uni-ulm.info) (home).vs

Im Gegensatz zu Bäumen besteht in azyklischen gerichteten Graphen die Möglichkeit, daß zu einem Knoten im Graphen mehrere Kanten mit alternativen Namen (Synonyme vgl. Abschnitt 4.4.2.3) führen. Zu beachten ist, daß ein Knoten im Namensgra­­phen nicht notwendigerweise nur einen Vorgänger besitzt. Somit ist die Flexibilität gegeben, Objekte in verschiedenen Kontexten zu benennen.[AL20] 

Abbildung 2.25: Darstellung von Synonymen im azyklischen gerichteten Graphen und in Baumstukturen

Die Darstellung synonymer Namen für Kontexte kann in azyklischen gerichteten Graphen oder auch in Baumstrukturen erfolgen (vgl. Abbildung 2.25). In der Baumstruktur bezeichnen „uni-ulm“ und „home“ nach wie vor denselben Kontext, wobei der Kontext allerdings durch verschiedene Knoten im Graphen repräsentiert wird. Dieser Umstand ist jedoch für die Vertei­lung von Kontexten auf Namensverwalter hinderlich (siehe Kapitel 4)[AL21] .

Die Unterstützung synonymer und generischer Namen steigert die Benutzerfreund­lich­keit einer Namensverwaltung. Um als Optionen für die Auflösung von Namen zur Verfügung zu stehen, müssen diese jedoch bereits bei der Registrierung Berücksichti­gung finden.

2.3.3.5       Syntaktische Repräsentation von Attributtypen in Namen

In den vorangegangenen Abschnitten traten Attributtypen wie Farbe, Form und Größe in Namen nicht explizit in Erschei­nung:[AL22] 

blau.klein.rund

Implizite Attributtypen werden in den Knoten des Namensgraphen abgelegt. Sie sind allenfalls für Vergleiche beim Traversieren im Namensgraphen relevant, treten im Graphen jedoch selbst nicht in Erscheinung. Aufgrund der impliziten Repräsentation der Attributtypen ist die Reihen­folge, in der die Attributwerte im Namen angegeben werden, signifikant und muß vorab defi­niert werden, da aus dem Namen allein keine Zuordnung von Wert zu Attribut möglich ist. Hierdurch wird jedoch die Flexibilität bei der Namensvergabe erheblich eingeschränkt.

Attributtypen können in Objektnamen auftreten, ohne daß sie sich syntaktisch von Attribut­wer­ten unterschieden. Die Interpretation derartiger Namen behandelt daher Attributtypen und -werte gleich. Einen Namen, in dem Attributtypen zwar enthalten, jedoch syntaktisch nicht hervorge­hoben sind, zeigt folgendes Beispiel:[AL23] 

Farbe.blau.Größe.klein.Form.rund

Um Attributtypen in Namen explizit darzu­stellen, kann die übliche Namens­syntax, in der die Teile hierarchischer Namen durch einen Punkt getrennt wurden, durch den Doppelpunkt „:“ erweitert werden, der den Attribut­typ vom Attributwert trennt (vgl. X.500 [CCITT/ISO, 88]). Explizite Attributtypen enthält z.B. die Beschreibung der Eigenschaften von Objekt 1 aus Abbildung 2.21 durch folgenden Ausdruck:

Farbe:blau.Größe:klein.Form:rund

Hierbei ist zu beachten, daß der obige Ausdruck eine Ordnung (Inklusion) auf den Attributen definiert. Die hervorgehobenen Attributtypen können explizit im Namensgraphen repräsentiert sein (vgl. Abbildung 2.26 und Abbildung 2.27) oder aber auch implizit in Knoten abgelegt werden, so daß sie nicht im Namens­graphen in Erscheinung treten (vgl. Abbildung 2.21).

2.3.3.6       Repräsentation von Attributtypen im Namensraum

Unabhängig von der Repräsentation von Attributtypen in Namen können diese unterschiedlich im Namensraum dargestellt werden. Werden Attributtypen implizit in den Knoten des Namens­graphen erfaßt (vgl. Abbildung 2.26), so treten an den Kanten des Graphen lediglich Attribut­werte und keine Attributtypen auf. Unter Umständen können unterschiedliche Attribute diesel­ben Werte besitzen, so daß die Namen an den Kanten eines Knotens nicht notwen­digerweise eindeutig sind. Um ein gewünschtes Objekt zu lokalisieren, muß die Namensinter­pretation den impliziten Attributtyp mit einbeziehen, bevor entschieden werden kann, welchem Pfad zu folgen ist. Diese Vorgehensweise impliziert eine Änderung der Interpretations­vorschrift hierarchischer Namen.

Abbildung 2.26: Implizite Attributtypen

Die Änderung der Interpretationsvorschrift kann vermieden werden, falls Attributtypen explizit im Namensraum repräsentiert werden. Im Vergleich zur impliziten (vgl. Abbildung 2.26) bedeutet die explizite Repräsentation der Attributtypen eine Flexibilisierung der Namens­ver­waltung. Ein Attributtyp wird in hierarchischen Namens­räumen durch einen Kontext und die zugehörigen Attributwerte durch Einträge in diesem Kontext repräsentiert (vgl. Abbildung 2.27).

Abbildung 2.26 zeigt die hierarchische Darstellung des Attributes Farbe mit den Werten rot, grün und blau. Zwischen den Attributen können Abhängigkeiten (Inklusionen) bestehen, die sich in der Ordnung der Namensteile ausdrücken. Abbildung 2.27 zeigt die Darstellung abhängiger und unabhängiger Attribute in einer hierarchischen Struktur. Die Attribute Farbe und Größe sind orthogonal zueinander, hängen jedoch beide vom Attribut Form ab. Objekt 1 kann so durch den Namen Form.rund.(Farbe.blau) (Größe.klein) beschrieben werden.

Abbildung 2.27: Aufnahme von Attributtypen in den hierarchischen Namensraum

Wie Abbildung 2.27 verdeutlicht, können in verschiedenen Unterbäumen dieselben Attribute vorhanden sein. Dieser Umstand erhöht den Aufwand für die Suche nach Objekten mit Eigen­schaften, die tief in der Hierarchie dargestellt sind. Schließlich erzeugt diese Art der Repräsen­tation von Attributtypen mehr Einträge und eine tiefere Verschachtelung als die implizite Dar­stellung.

Abbildung 2.28: Repräsentation von expliziten Attributtypen in hierarchischen Namensräumen

Die explizite syntaktische Kennzeichnung von Attributtypen ermöglicht die Darstellung von Attributen in separaten Hierarchien (vgl. Abbildung 2.28). Attributtypen und Attributwerte werden dazu in unterschiedlichen Teilbäumen erfaßt. Falls z.B. die Attribute Größe und Farbe eines Objekts im folgenden Ausdruck

Form: rund. (Farbe: blau) (Größe: klein)

orthogonal sind (runde Klammern fassen orthogonale Ausdrücke zusammen), jedoch beide von der Form abhängig sind, stellen sich die Attribute im Namensgraphen wie in Abbildung 2.28 gezeigt dar. Die Verwaltung orthogonaler Attribute in separaten Unterbäumen erleichtert die Repräsentation von Objekteigenschaften, falls bestimmte Attribute optional sind. Sie führt dazu, daß sich an den Blättern, die Attributwerte repräsentieren, mehrfache Objekt­ein­träge befinden, auch wenn die einzelnen Objekte eindeutig identifiziert sind. Nachteil der expliziten Reprä­sentation von Attributtypen ist die Notwendigkeit zur Erweiterung der Syntax und der Interpre­tationsvorschriften für Namen.

Der in Abschnitt 2.3 aufgezeigte Ansatz ermöglicht die selektive Lockerung der Einschrän­kun­gen des hierarchischen Namens­modells. Hierdurch kann ein einheitlicher graph-förmiger Namensraum konstruiert werden, in den attributierte Namen integriert sind. Somit wird dem Anwender die Möglichkeit gegeben, in der dynamischen globalen Namens­verwaltung attribu­tierte Namen für die Beschreibung von Objekten zu verwenden.

 

Das Aufbrechen des streng hierarchischen Organisationsschemas ermöglicht die flexible Verwaltung von Objekten anhand ihrer Eigenschaften, wobei die administrativen Vorzüge hier­archischer Organisationsstrukturen für die globale Namensverwaltung erhalten bleiben.

 

2.4         Beziehungen zwischen Namen und Objekten

Namen für Objekte finden in verteilten Systemen dann Anwendung, wenn die menschliche Interaktion zur Erfüllung bestimmter Aufgaben erforderlich wird und infolge­dessen von der physikalischen Erscheinungsform eines Objekts abstahiert werden muß. Jedes adressierbare Objekt kann prinzipiell einen Namen tragen und von der Namensverwaltung erfaßt werden. Der nachfolgende Abschnitt handelt von den Beziehungen, die zwischen Namen und Objekten bzw. deren Bezeichnern bestehen. Bezüglich der Definitionen der hierbei in Beziehung gesetzten Mengen O und N sei auf Abschnitt 2.1 und 2.2 verwiesen.

2.4.1          Beziehungen zwischen Objekten und Adressen

Adressen sind absolute Ortsangaben und beschreiben entweder den physikalischen Aufenthalts­ort oder eine physikalische Identifikation eines Objekts. Jedes logische Objekt kann mehrere physikalische Replikationen besitzen und daher unter verschie­denen Adressen zu finden sein. Umgekehrt ist es nicht möglich, unter derselben Adresse mehrere Objekte abzulegen, d.h. die Abbildung von Objekt auf Adresse ist injektiv. Diese Eigenschaft der Adreßzuordnung verdeut­licht Tabelle 2.2.

 

Objekt

Objekt-Adresse

$14567834

$13465123, $23765328

$73565922

Tabelle 2.2: Zuordnung von Objekt zu Adressen

Adressen sind im Gegensatz zu Objekt-Bezeichnern Änderungen unterworfen und nur temporär zugeordnet. Die Adresse eines Objekts ändert sich beispielsweise bei der Migration oder der Substitution des Objekts.

2.4.2          Abbildungen zwischen Objekten und Objekt-Bezeichnern

Objekte werden auf der Benutzerebene in der Regel durch grafische Symbole (Piktogramme) dargestellt. Mit diesen Symbolen kann zwar der Anwender sehr bequem arbeiten, nicht jedoch das System selbst. Protokolle verwenden für die Identifizie­rung von Objekten sogenannte Objekt-Bezeichner, in der Regel ganze positive Zahlen mit ausrei­chen­­der Kardinalität.

 

Objekt-Bezeichner

Objekt

#1

#2

#3

Tabelle 2.3: Zuordnung von Objekt-Bezeichnern zu Objekten

Bei der Erzeugung von Objekten generiert das System für jedes Objekt einen Bezeichner, der es für die gesamte Lebensdauer eindeutig in Zeit und Raum von anderen Objekten unterscheidet (vgl. Tabelle 2.3). Die Zuordnung eines Objekts zu einem Objekt-Bezeichner ist bijektiv (injektiv und surjektiv) und damit umkehrbar, d.h. ein Objekt-Bezeichner kann nicht mehrere Objekte identifizieren und jedem Objekt ist genau ein Objekt-Bezeichner eindeutig zugeordnet. Aufgrund dieser Bijektion werden im folgenden die Begriffe Objekt und Objekt-Bezeichner äquivalent verwendet.

2.4.3          Abbildungen zwischen Namen und Objekten

Die Identifizierung von Objekten anhand von Objekt-Bezeichnern ist für Anwender nicht prakti­kabel, da diese aufgrund der fehlenden Mnemonik wenig einprägsam sind. Namen hin­gegen eignen sich hierfür wesentlich besser, weshalb Objekte zusätzlich zu Objekt-Bezeichnern sym­bolische Namen besitzen.

 

Objekt-Name

Objekt(-Bezeichner)

Telefon

#1

Ball, Kugel

#3

Tabelle 2.4: Zuordnung von Namen zu Objekt-Bezeichnern

Tabelle 2.4 läßt bereits erkennen, daß einem Objekt(-Bezeichner)  mehrere Namen  zugeordnet sein können. Umgekehrt kann ein primitiver Name  eine ganze Gruppe von Objekten  bezeichnen.

Die beiden grundlegenden Funktionen, die die Beziehungen zwischen Namen und Objekten beschreiben, sind das sog. Binden und das Mapping: Als Binden wird die erstmalige Zuord­nung eines Namens zu einem Objekt bezeichnet. Die Abbildung eines gegebenen Namens auf ein Objekt bzw. dessen Bezeichner wird Mapping genannt.

Definition: Binden

Die erstmalige Zuordnung eines Namens n im Namensraum N zu einem Objekt  wird als Binden bezeichnet.

Definition: Mapping

Die Abbildung , die jedem Namen  genau ein Objekt  zuordnet, heißt Mapping vom Namen zum Objekt.

Die Abbildung  ist bijektiv, wenn ein Objekt  genau einen Namen  besitzt. Bezeichnet ein Name  eine Menge von Objekten , dann ist keine Abbildung. Trägt ein Objekt o mehrere Namen , so ist die Abbildung surjektiv[6] aber nicht injektiv.

Das Mapping vom Namen zum Objekt kann mehrstufig sein. Namen können ihrer­seits wieder als Objekte verstanden und durch ein anderes Namensschema benannt werden. Somit entstehen verschie­dene Ebenen der Abstraktion (z.B. die Abbildung von Dateinamen auf I-Nodes und Dateien oder von Domain-Namen auf IP- und Ethernet-Adressen).

2.4.4          Quantitative Beziehungen zwischen Namen und Objekten

Namen können sowohl an einzelne Objekte als auch an Gruppen von Objekten gebunden sein. Umgekehrt können Objekte gleichzeitig mehrere Namen tragen. Diese mehrfachen Bindungen müssen bei der Namensverwaltung Berücksichtigung finden. Zur Ermittlung der Anforde­run­gen von Mehrfachbindungen an die Namensver­waltung ist eine quantitative Kategorisierung von Namen-Objekt-Bindungen hilfreich.

Eine Klassifizierung von Namen-Objekt-Bindungen zeigt Abbildung 2.29. Die Funktion |{o}| liefert hier die Anzahl der Objekte, die Funktion |{n}| die der zugehörigen Namen. Bezeichnet ein eindeutiger Name genau ein Objekt (|{n}| = |{o}|=1), so liegt ein individueller Name vor. Identifiziert ein Name n mehrere Objekte (|{n}|=1, |{o}|>1), so ist n ein mehrfacher Name. Mehrfache Namen werden unterschieden in Gruppen-Namen und generische Namen. Gruppen- oder Multicast-Namen sind von Bedeutung, um transparent Nachrichten an eine Gruppe von Empfängern senden zu können und um gleichzeitig auch einen vorhandenen, effizienten Multicast-Dienst auszunutzen, wie er z.B. vom Ethernet angeboten wird. Generische Namen identifizieren u.U. eine Menge von Objekten, die der unvollständigen Beschreibung entspre­chen.

 [AL24] 

Abbildung 2.29: Quantitative Beziehungen zwischen Namen und Objekten

Trägt ein Objekt mehrere Namen (|{n}|>1, |{o}|=1), so spricht man von synonymen Namen. Falls synonyme Namen gleich­berechtigt neben­einander koexistieren, werden sie Synonyme genannt. Existiert ein primärer Name, dem die weiteren Namen eines Objekts untergeordnet sind, so bezeichnet man die sekundären Namen als Alias-Namen.

Abkürzungen sind primitive synonyme Namen, die relativ zu einem gegebenen Kontext inter­pretiert werden und nur innerhalb dieses Kontexts eindeutig sind, der durch einen Benutzer oder durch einen Prozeß definiert wird. Spitznamen sind primitive synonyme Namen mit globaler Signifikanz (absolut).

2.4.5          Abbildungen zwischen Namen unterschiedlicher Systemsichten

Die Namen der unterschiedlichen Namensräume eines verteilten Systems stehen zueinander in Beziehung (vgl. Abbildung 2.30). Die Bindungen zwischen Namen auf der Anwen­dungsebene werden vom Benutzer und auf der System-Ebene durch das Betriebssystem hergestellt.

Abbildung 2.30: Einstufige Abbildung von Namen auf Adressen

Prinzipiell ist eine einstufige Namensverwaltung denkbar, die symbolische und physikalische Namens­räume direkt zueinander in Beziehung setzt. Dies hat den Vorteil, daß nur eine einzige, über das System verteilte Abbildung von Namen auf Adressen realisiert werden muß. Wie aus Abbildung 2.30 ersichtlich ist, sind durch einstufige Abbildungen sowohl Synonyme als auch Replikationen von Objekten realisierbar. Dennoch hat die einstufige Abbildung von Namen auf Adressen besonders in verteilten Systemen viele negative Aspekte:

·      Die Migration von Objekten bewirkt eine Änderung der Adresse und des Zugriffspfades. Die Namensverwaltung muß daher die Bindung des Namens zur Adresse des migrierten Objekts aktualisieren. Um den Kontakt zum migrierten Objekt nicht zu verlieren, muß der Objektzu­griff durch den Anwender stets über den Namen erfolgen und dieser muß jedesmal erneut aufgelöst werden.

·      Greifen Anwender nicht über Namen, sondern direkt über Adressen auf Objekte zu, so hat die Namens­verwaltung dafür Sorge zu tragen, daß bei der Migration eines Objekts alle Refe­renzen des Anwenders auf das Objekt aktualisiert werden (vgl. [Traub, 94]).

·      Allein anhand von Adressen ist nicht zu erkennen, ob zwei unterschiedliche Namen verschie­dene Replikationen desselben logischen Objekts bezeichnen. Es besteht keine Möglichkeit, die Zugehörigkeit verschiedener Adressen zum selben Objekt festzu­stellen.

Der Wunsch nach Ortsunabhängigkeit und Migrationsinvarianz motiviert mehrere Namens­räume mit System-Namen unterschiedlicher Ausprägung.[AL25]  Ein zusätzlicher Namensraum mit eindeutigen Objekt-Bezeichnern vermeidet die angeführten Nachteile, erfordert allerdings eine zusätzliche Abbildungs­stufe (von Objekt-Bezeichnern auf Adressen).

Viele verteilte Betriebssysteme, wie z.B. Xero [Kato, 91] und PluriX [Traub, 94], verwalten aus dem obengenannten Grund drei Namensräume. Auf der ober­sten Ebene findet der Anwender symbolische Namen (Benutzer-Namen) vor. Das System identifiziert logische Objekte anhand global eindeutiger Objekt-Bezeichner. Der Aufenthaltsort physikalischer Instan­zen logischer Objekte wird durch Adressen beschrieben.

Abbildung 2.31: Die zweistufige Abbildung zwischen den Namensräumen in verteilten Systemen

Die Einführung eines Namensraums mit global eindeutigen Objekt-Bezeichnern (OID) hat den Vorteil, daß OIDs ortsunabhängig und damit migrations­invariant gewählt werden können. Somit kann ein Objekt migrieren, ohne daß die Bindung vom Namen zum Objekt angepaßt werden muß. Durch die Verwendung von OIDs sind synonyme Namen für Objekte durch die Namensverwaltung leichter zu handha­ben, und die Replikation von Objekten bleibt für die Namensverwaltung transparent.

Schwierig­keiten hingegen bereiten die global eindeutige Generierung von OIDs und die Lokali­sierung von Objekten, wenn nur die OID bekannt ist und diese keine Ortsinformation enthältenthältenthält. Diese Fragen tangieren jedoch v.a. die Objektverwaltung und die zugrundeliegenden Kommu­nikations­dienste und sind nicht zentraler Gegenstand dieser Arbeit[7]. Die globale dynamische Namensverwaltung beschäftigt sich daher primär mit der globalen Verwaltung von Bindungen von Benutzer-Namen an Objekt-Bezeichner.

 

Objekt-Bezeichner bieten eine zusätzliche Abstraktion vom physikalischen Objekt und ermögli­chen Migrations- und Replikationstransparenz für die Namensverwaltung.

2.5         Operationen auf lokalen Namensräumen

Nachdem die grundlegenden Beziehungen zwischen Namen und Objekten diskutiert wurden, wendet sich dieser Abschnitt der Verwaltung lokaler Namensräume zu. Diese wiederum bildet die Grundlage für die dynamische globale Namensverwal­tung.

2.5.1          Lokale Basisoperationen auf flachen Namensräumen

Zu den Grundfunktionen einer Namensverwaltung zählen das Registrieren, Auflösen und Löschen primitiver Namen in der Namensbasis lokaler Namensverwalter. Diese Funktionalität bietet prinzipiell jede Standarddatenbank. Basierend auf diesen Funktionen werden die lokalen Operationen auf hierarchischen Namensräumen definiert.

Da die dynamische globale Namensverwaltung dem Anwender die Möglichkeit geben soll, selbständig Namen zu vergeben, wird in dieser Arbeit der Registrierung von Namen besondere Bedeutung zugemessen. Das lokale Registieren eines Namenseintrags[8] entspricht dem im vor­angegangenen Abschnitt beschriebenen Binden eines primitiven Namens an ein Objekt. Die Funktionen zur Registrierung hierarchischer und globaler Namen bauen hierauf auf (vgl. Abbildung 3.7).[AL26] 

Die primäre Funktion einer Namensverwaltung ist das Auflösen von Namen. Das im vorange­gangenen Abschnitt beschriebene Mapping von Namen zu Objekten entspricht dem lokalen Auflösen primitiver Namen. Dabei kann der Suchhorizont durch die Vorgabe eines Kontextes eingeschränkt werden. Die lokale Auflösungsfunktion ermittelt alle Namen-Objekt-Bindungen, die den gesuchten Namen enthalten. Das Ergebnis der lokalen Auflösung primitiver Namen muß jedoch nicht notwendigerweise immer eindeutig sein, z.B., wenn ein generischer Name oder ein partieller Name eines attributierten Namens gesucht ist.

[AL27] Um die Eindeutig­keit primitiver Namen zu gewährleisten, wird vor dem Registrieren lokal nach einem Namenseintrag gesucht, der den neuen Namen enthält. Wird kein derartiger Namens­ein­trag ermittelt, so kann der neue Name in das Verzeichnis des lokalen Namensverwalters aufge­nommen werden. Die Gültigkeit des flachen Namens kann dabei gegebenfalls wieder durch die Angabe eines Kontextes eingeschränkt werden. Tritt ein Konflikt durch doppelte Namen auf, so wird der primitive Name nur dann registriert, wenn es sich um einen partiellen Namen eines attributierten Namens handelt. Nur bei der Registrierung attributierter Namen ist es möglich, daß partielle Namen im selben Kontext auf verschiedene Objekte verweisen (vgl. Abschnitt 4.4).

Dem Wesen einer dynamischen Namensverwaltung entspricht es, daß Namenseinträge nicht nur regis­triert, sondern auch wieder entfernt werden, entweder weil die Bindung eines Namens an ein Objekt aufgehoben oder weil im Rahmen einer Aktualisierung ein Eintrag durch einen modi­fizierten ersetzt wird. Hierbei kann zwischen dem aktiven Löschen seitens des Anwenders und dem passiven Löschen durch die Alterung bestimmter Arten von Namens­einträgen unter­schie­den werden (vgl. Kapitel 5). An dieser Stelle sei bereits darauf hinge­wiesen, daß in der dynamischen globalen Namensverwaltung das Ändern einer Namen-Objekt-Bindung nicht als atomare Funktion realisiert ist, sondern als zusammengesetzte Transaktion aus Löschen und erneutem Registrieren.

Der Löschvorgang besteht aus zwei Phasen, dem Ermitteln und dem Entfernen des zu löschen­den Namenseintrags. Für das Löschen eines primitiven Namens ist nicht nur der vom Namens­eintrag belegte Speicher zu entfernen, sondern auch alle Referenzen, die auf den Namenseintrag verweisen. Besitzt das Betriebs­system eine automatische Freispeichersammlung (Garbage Collection), so genügt das Entfernen aller Referenzen, um den Eintrag freizugeben. Er wird dann bei Gelegenheit von der Garbage Collection aus dem Speicher entfernt, da er nicht mehr referenziert wird.

Pseudocode für die Funktionen der dynamischen globalen Namensverwaltung zur lokalen Ver­waltung primitiver Namen findet der interessierte Leser in Anhang D. Die Struktur der Namens­einträge ist in Anhang C beschrieben.

2.5.2          Lokale Operationen auf hierarchischen Namensräumen

In den vorangegangenen Abschnitten wurden Beziehungen zwischen primitiven Namen und Objekten betrachtet. Bei flachen Namensverwaltungen gibt es eine einzige Abbildung , so daß gilt:

[9]

Typischerweise sind Namen jedoch kontextbezogen, um die Mächtigkeit des Namensraums zu vergrößern und die Eindeutigkeit von Namen besser gewährleisten zu können. Für eine formale Definition kontextbezogener Namen (vgl. [Younger, 92]) wird die Menge O der Objekte in m Teilmengen  zerlegt. Für jede Teilmenge  sei weiter eine Funktion  gegeben, so daß gilt:

Die Funktionen  werden als Kontexte bezeichnet, die jeder für sich eine flache Namens­ver­waltung bilden, in der nur die Objekte aus  benannt werden. Die Kontexte  sind surjektiv. Sie können bijektiv sein, wenn auf Synonyme verzichtet wird. Die aus einzelnen Kontexten zusammengesetzte Gesamtabbildung  kann dennoch mehrdeutig sein. Die flachen Namen sind dabei nur innerhalb eines bestimmten Kontextes eindeutig. Das Objekt o wird durch das Tupel  bestimmt.

Die Frage bleibt, wie ein Kontext identifiziert wird. Die natürliche Antwort lautet: Er wird eben­falls benannt. So kann eine Namensverwaltung konstruiert werden, die eine wei­tere Menge von Kontexten enthält und Namen auf Kontexte in  abbildet. An dieser Stelle sei darauf hinge­wiesen, daß dieser Vorgang potentiell unendlich ist, da jeder Kontext in einem Kontext höherer Stufe benannt wird. Um das zu vermeiden, muß es auf einer Stufe der Hierarchie von Kontex­ten einen oder mehrere (Wurzel-)Kontexte geben, die folgende Eigenschaften besitzen:

•     Sie benennen alle Kontexte auf der nächst niedrigeren Stufe.

•     Sie sind in keinem höheren Kontext benannt und ein implizi­ter Teil der Namensverwaltung.

Die bislang entwickelte Namensverwaltung besteht aus,

•     einem oder aus mehreren Wurzel-Kontexten, die nicht benannt werden müssen,

•     einer Hierarchie von Kontexten fester Tiefe (potentiell unendlich), wobei jeder Kontext auf einer gegebenen Stufe in wenigstens einem Kontext einer höheren Stufe benannt ist,

•     und einer niedrigsten Stufe von Kontexten, auf der keine Kontexte mehr, sondern einfache Objekte benannt werden.

Formal läßt sich diese hierarchische Namensverwaltung wie folgt beschreiben [Younger, 92]:

Gegeben sei eine Menge von zu benennenden Objekten O, sowie m Teilmengen Oi von O. Ferner eine Menge von m Relationen , so daß gilt:

Gleichzeitig seinen n Teilmengen  und n Relationen  gegeben, die die Kontexte in  benennen. Weiter wird vorausgesetzt, daß es eine Menge von Kontexten  gibt, die in einem oder mehreren Wurzel-Kontexten benannt werden.[AL28] 

Verallgemeinert man weiter, so läßt sich die Eigenschaft der festen Tiefe der Hierarchie elimi­nieren. Dazu wird erlaubt, einen Kontext oder ein Objekt von einem Kontext auf jeder höheren Stufe der Hierarchie aus zu benen­nen. Die Funktionen  stellen sich dann wie folgt dar:

Dieses Prinzip erlaubt die Benennung eines jeden Objekts oder Kontextes im System. Im fol­genden wird ohne Beschränkung der Allgemeinheit ein einziger Wurzel-Kontext  vor­ausge­setzt. Eine Funktion resolve zur lokalen Auflösung absoluter hierarchischer Namen wird dann wie folgt definiert:

Die gegebene Definition der kontextbezogenen Namensauflösung begründet die Vorstellung von Pfadnamen als geordnete Liste von Namen. Die Namensinformation im System kann als Graph mit der Relation „ist benannt in“ dargestellt werden, wobei die Knoten im Graphen die Kontexte und Objekte repräsentieren, und eine direkte Verbindung zwischen Kontext 1 und Kontext 2 besteht, wenn Kontext 2 in Kontext 1 benannt wird. Werden die resultierenden Kanten mit dem Namen versehen, an den Kontext 2 in Kontext 1 gebunden ist, dann ist die Auflösung eines Pfadnamens ein Wandern durch den Graphen mit der Relation „ist benannt in“.

Oben vorgestellte lokale Auflösungsfunktion resolve beginnt die Auflösung von Namen stets beim Wurzelkontext. In tief verschachtelten hierarchischen Namensräumen ist das jedoch sehr ineffizient, weshalb viele Systeme einen Kontext oder den Namen eines Kontexts speichern, der als alternativer Startkontext zum Wurzelkontext verwendet werden kann. Abhängig davon, ob der Name mit dem Wurzelsymbol „/“ beginnt oder nicht, wird der Name entweder als absoluter Name bezogen auf den Wurzelkontext oder als relativer Name bezogen auf den Startkontext aufgelöst.

Bisher wurde eine statische Namensverwaltung beschrieben. Eine dynami­sche Namens­verwal­tung muß um Opera­tionen zum Ändern der Bindungen zwischen Namen, Kontexten und Objekten ergänzt werden. Das ist nicht trivial, da Kontexte auf einer bestimmten Ebene durch die Kontexte der nächst niedrigeren Stufe bestimmt werden.

Die Funktionen register und remove manipulieren Bindungen von Kontexten oder Objekten zu primitiven Namen in einem gegebenen Kontext und werden wie folgt formal beschrieben:

Ausgehend von der formalen Definition der kontextbezogenen Operationen auf Namensräumen, werden in den folgenden Abschnitten die lokalen Operationen auf hierarchischen Namens­räu­men der dynamischen globalen Namensverwaltung weiter präzisiert.

2.5.2.1       Lokale Auflösung hierarchischer Namen

Die lokale Funktion resolve bildet die Grundlage für die globale Auflösung hierarchischer und attributierter Namen in der dynami­schen globalen Namensver­waltung. Die lokale Auflösung hierarchischer Namen kann als syntaxgesteuertes Traversieren des Namensgraphen implemen­tiert werden und basiert auf zwei Grund­operationen, dem Wandern nach oben zum Wurzel-Kontext und dem Wandern zum nächsten, unteren Knoten im Namens­graphen. Die schritt­weise lokale Auflösung hierarchischer Namen mit der Funktion resolve nimmt dabei verschiedene Zustände  an, und jeder Auflö­sungs­schritt liefert einen neuen Teilnamen, der weiter inter­pretiert wird.

Beginnend beim Aus­gangs­­zu­stand start werden abhängig von den Beziehungen zwischen dem gesuchten und den im Namensraum N existie­renden Namen die jeweiligen Zwischen­zustände search, prev context und next context angenom­men. Schließlich terminiert die Auflösung mit einem der Endzustände found, not found oder global search.

Die Beziehungen zwischen einem gegebenen hierarchischen Namen n und den Namen in einem Namensraum N lassen sich wie folgt definieren:

 

no match(n, N)

z.B. n=a.b.c, m=e.f.g

related(n, N)

z.B. n=a.b.c, m=a.b.d

partial match(n, N)

z.B. n=a.b.c , m=a.b

full match(n, N)

z.B. n=a.b.c, m=a.b.c

 

Unter Berücksichtigung der o.g. Zustände und der soeben definierten Beziehungen zwischen Namen läßt sich die lokale Interpretation eines hierarchischen Namens n wie folgt beschreiben:

Beginnend im aktuellen Kontext  (Zustand: start) wird versucht, den ersten Teil des hierarchi­schen Namens zu interpretieren (Zustand: search) (vgl. Abbildung 2.32). Wird hier keine Über­einstimmung mit vorhan­denen Namens­einträgen festgestellt (no match, related), so wechselt sich die Auflösung zum übergeord­neten Kontext (Zustand: prev context) und versucht, falls dieser existiert (prev context found), dort erneut einen Teil des Namens zu ermitteln (Zustand: search). Wenn dieser nicht vorhan­den ist und kein externer Verweis existiert (prev context not found), wird die Auflösung erfolglos abgebrochen (Zustand: not found). Existiert jedoch ein Verweis auf einen externen Namensverwalter (prev node found), dann wird die Auflösung bei diesem fortgesetzt (Zustand: global search).

Gelingt im Zustand search im aktuellen Kontext die teilweise Interpretation (partial match), so wechselt die Auflösung zu dem Kontext, dessen Name erkannt wurde (Zustand: next context). Ist der Name vollständig interpretiert (full match), so terminiert das Verfahren und gibt die Objekt- oder Kontext-Bezeichner der letzten Station der Auflösung aus (Zustand: found). Wenn der Name nur partiell interpretiert wurde (Zustand: next context) und kein Nachfolge­kontext mehr existiert (next context not found), so terminiert die Auflösung erfolglos (Zustand: not found). Andernfalls (next context found) wird die Suche nach weiteren Namensteilen aufge­nom­men (Zustand: search). Kann der Name weiter interpretiert werden (partial match), so wird der Kontext, den der partielle Name bezeichnet, zum aktuellen Kontext (Zustand: next context). Falls kein weiterer Teil des Namens ermittelt werden kann (no match), wird die Suche erfolglos abgebrochen (Zustand: not found).

Bei der Auflösung von Namen relativ zu einem Startkontext läuft die Suche den Kanten des Namensbaumes entlang nach oben (Zustand: prev context), bis ein partieller Name gefunden oder die Suche erfolglos beendet wird. Existieren dabei im Graphen mehrere Pfade, über die ein Knoten im Graphen (Kontext oder Objekt) erreicht werden kann, so wird ein Pfad ausgewählt, und die übrigen Namenseinträge werden für eine spätere Bearbeitung festgehalten. Alternativ können in einem Multitasking-Betriebssystem separate Prozesse abgespalten werden, die optio­nale Pfade verfolgen und die jeweiligen Resultate ermitteln.[AL29] 

Abbildung 2.32: Zustände der lokalen Auflösung hierarchischer Namen (resolve)

Um die Auflösung von Namen zu beschleunigen, sollte sie in einem Startkontext beginnen. Namen werden dann relativ zu diesem Startkontext aufgelöst. Sofern relative Namen aufzulösen sind, läßt sich hierdurch die Anzahl der notwendigen Auflösungs­schritte entscheidend verrin­gern. Liegen jedoch absolute Namen vor, so beginnt die Auflösung stets an der Wurzel. Abso­luten Namen steht als Präfix das Symbol für die Wurzel (z.B. „/“) voran, wodurch die Wurzel als Startkontext feststeht und die aufsteigende Suchphase entfallen kann.

Die Auflösung absoluter Namen kann auch die Ähnlichkeit des gesuchten Namens mit dem Namen des aktuellen Kontexts berücksichtigen. Besteht weitgehende Überein­stimmung des gesuchten absoluten Namens mit dem Namen des aktuellen Startkontexts (related), so ist es u.U. effektiver, die Suche nicht bei der Wurzel zu beginnen, sondern sich schrittweise nach oben zur Wurzel vorzuarbeiten. Diese Art der Suche gewinnt jedoch erst bei der globalen Auf­lösung von Namen verstärkt an Bedeutung.

2.5.2.2       Lokales Registrieren hierarchischer Namen

In Betriebssystemumgebungen werden gewöhnlich zur Strukturierung von Namen Unterver­zeichnisse als Kontexte angelegt. Diese werden nicht ad hoc, sondern vielmehr sukzessive durch den Anwender explizit mittels Befehls­sequenzen zum Erzeugen und zum Wechseln von Verzeich­nissen generiert. Neue Kontexte werden relativ zum aktuellen Kontext erzeugt. Zuletzt wird der primitive Name des Objekts im aktuellen Kontext registriert.

md uni, cd uni, md vs, …

Im Gegensatz zu den meisten anderen Namensverwal­tungen ist es in der dynamischen globalen Namensverwaltung nicht Aufgabe des Benutzers oder Administrators, Kontexte oder Verzeich­nisse anzulegen. Benutzer registrieren stets nur vollständige Objektnamen, jedoch keine Kon­textnamen (Verzeichnisse). Wird ein hierarchischer Objektname registriert, für den noch kein geeigneter Kontext existiert, so werden die Namenseinträge für die fehlenden Kontexte von der Namens­verwal­tung selbständig erzeugt.

Wird ein hierarchischer Name für ein Objekt registriert, so muß zunächst die Eindeutigkeit des Namens geprüft werden. Dabei dürfen verschiedene Objekte oder Kontexte nicht die gleichen hierarchischen Namen tragen[10]. Umgekehrt darf ein Objekt oder Kontext jedoch mehrere Namen besitzen. Die lokale Eindeutigkeit eines Namens wird geprüft, indem der Registrierung eine Auflösung vorangestellt wird. Erst wenn der Name so weit wie möglich aufgelöst und des­sen Eindeutig­keit sichergestellt ist, werden der restliche Teil des Namens sukzessive registriert und fehlende Kontexte erzeugt. Den Ablauf einer Registrierung zeigt Abbildung 2.33.

Abbildung 2.33: Zustände der lokalen Registrierung hierarchischer Namen

Das Registrieren eines neuen Namens im Namensraum geschieht zunächst nur im lokalen Namens­verwalter. Lokale Einträge sind den übrigen Namensverwaltern nicht bekannt. Soll der Name über die Grenzen des lokalen Namensverwalters hinaus bekannt gegeben werden, so muß er entweder im Broadcast-Bereich oder global registiert werden.

2.5.2.3       Lokales Löschen hierarchischer Namen

In der dynamischen globalen Namensverwaltung besteht analog zum Registrieren von Namen für den Anwender zunächst lediglich die Möglichkeit, einzelne Namen von Objekten aus der lokalen Namensbasis zu löschen. Soll eine Gruppe von Namen oder gar ein Kontext gelöscht werden, so werden diese durch einen attributierten oder generischen Namen beschrieben, wobei alle Namenseinträge entfernt werden, auf die die Beschreibung zutrifft.

Abbildung 2.34: Zustände des lokalen Löschens hierarchischer Namen

Vor dem Löschen eines lokalen Namens wird dieser aufgelöst, um den zugehörigen Namens­eintrag in der lokalen Namensbasis zu ermitteln. Bezeichnet der Name ein Objekt, so wird der entsprechende Namenseintrag gelöscht. Kontexte werden nur dann entfernt, wenn keine nach­folgenden Namenseinträge vorhanden sind, d.h. der Kontext leer ist (vgl. Abbildung 2.34). Werden durch das Löschen von Objektnamen übergeordnete Kontexte obsolet, so werden diese so lange rekursiv entfernt, bis weitere Einträge enthalten sind. Anschließend wird erneut ver­sucht, den zu löschenden Namen aufzulösen. Dadurch werden beim Löschen generischer Namen alle Einträge entfernt, die der gegebenen Beschreibung entsprechen[AL30] .[AL31] 

2.5.2.4       Die lokale Umkehrabbildung zur hierarchischen Namensauflösung

Gelegentlich muß der Anwender über im System auftretende Ereignisse informiert werden. Beziehen sich diese Ereignisse auf Benutzerobjekte, so ist es erforderlich, den für den Benutzer relevanten Namen anstatt eines Objekt-Bezeichners auszugeben (z.B. „Rechner alpha wurde abgeschaltet!“). Aus diesem Grund muß die Namensverwaltung eine Umkehrabbildung von Objekt-Bezeichnern auf hierarchische Namen bereitstellen.

Um zu einem gege­benen Objekt-Bezeichner den zugehörigen hierarchischen Namen, der die Kanten des Pfades von der Wurzel zum Namenseintrag mit dem Objekt-Bezeichner benennt, zu bestimmen, wird zunächst der zugehörige Namenseintrag ermittelt (vgl. Abbildung 2.35). Falls zu einem Objekt-Bezeichner ein Namenseintrag existiert, wird der enthaltene primitive Name ausgegeben. Anschließend wird zum übergeordneten Kontext gewechselt und der primitive Name des Kontexts im übergeordneten Kontext ausgegeben. Dieser Vorgang wiederholt sich, bis die Wurzel des hierarchischen Namensraums erreicht ist. Auf diese Weise wird der hierar­chische Namen eines Objekts sukzessive aus dem primitiven Namen des Objekts und den primitiven Namen der übergeord­neten Kontexte konkateniert.

Abbildung 2.35: Lokales Ermitteln des hierarchischen Namens eines Objekts

Wie bereits die vorangegangenen Abschnitte gezeigt haben, liefert die Namensauflösung nicht notwen­digerweise stets eindeutige Resultate. Insbesondere generische und attributierte Namens­anfragen, wie sie in Abschnitt 4.4 eingehender diskutiert werden, geben in der Regel als Resultat eine Menge von Objekten zurück. Bestehen bei der Ermittlung des Namens eines Objekts durch Synonyme und Querverweise alternative Pfade vom Namenseintrag zur Wurzel, so werden diese in der dynamischen globalen Namensverwaltung zunächst in einer besonderen Daten­struktur (vgl. Abschnitt 4.3.2) vermerkt und anschließend abgearbeitet.

 

Die lokalen Namensoperationen auf hierarchischen Namensräumen bilden die Basis für die dynamische Verwaltung globaler Namen.


[1]       Die relative Entfernung kann z.B. aus der Nachrichtenlaufzeit, der Zugriffszeit oder der Anzahl der Zwischen­knoten abgeleitet werden.

[2]       Flache Namen werden in der Literatur häufig auch als primitive, einfache oder atomare Namen bezeichnet.

[3]       Dennoch existieren Algorithmen, die flache Namen netzwerkweit eindeutig vergeben [Segall, 84].

[4]       Abgesehen davon, daß eine beliebige Anordnung der Attribute eine vollständige Suche erfordern würde.

[5]       [Mattes, 91] identifiziert drei Kategorien, die sich von den hier aufgezeigten teilweise unterscheiden.

[6]       Vorausgesetzt, es existieren keine versteckten Objekte, die über Namen nicht zu erreichen sind.

[7]       Der interessierte Leser sei hierzu auf die Literatur verwiesen (vgl. z.B. [Kato, 91]).

[8]       Die Struktur von Namenseinträgen wird in Anhang C dargestellt.

[9]       Diese Forderung kann aus Sicherheitsgründen durchbrochen werden (versteckte Objekte oder Kontexte).

[10]     Ausnahmen bilden lediglich partielle hierarchische Namen eines attributierten Namens, falls diese Objekt­eigenschaften repräsentieren, die für mehrere Objekte zutreffen können.

 [AL1]Struktur!!

 [AL2]Sollte es hier nicht besser Objekt heißen????

 [AL3] Warum kann man nicht auf alle Namen effizient zugreifen?

 [AL4] nicht immer, z.B. GSM und Ethernet

 [AL5] „scheinbare Hierarchie“ auf der Benutzerebene

 [V6] Diesen Anschnitt könnte man auch in Kapitel 4 gut unterbringen, da die Partitionierung etwas mit der Verteilung auf Namensverwalter zu tun hat.

 [AL7] Rekursive Partitionierung

 [AL8]Keine Unterscheidung Namen Attribute, der Name ist eben falls ein Attribut.

Jedes Objekt hat eine Adresse als Attribut (email, IP, Telefon). Zusätzliche Attribute sind Paßwörter, homedirectories, Versionsnummern usw.

 [AL9]Daten der Namensverwaltung liegen oftmals als Paare (Name, Attribute) vor. Typischerweise werden Attribute der Art (Typ, Wert) zu Namen gespeichert.

 

 [AL10]Ordnung auf den Attributen ><= usw.

 [AL11]    Welche sind das?

 [AL12]inplizite Attribute

 [V13] Welchen Einfluß hat das auf die Namensauflösung von attributierten Namen in Kapitel 4 und weiter hinten??

 [AL14] Wo liegt denn der genaue Unterschied zwischen potentiellen und verfügbaren Namen.

 [AL15]etwas durcheinander!

 [AL16]Ref

 [AL17]Bis auf den Namen

 [AL18]Das ist noch schief!!

 [AL19]Kann es danach noch weitergehen???

 [AL20]Probleme bei der Lokation, Zusammenfügen

Verschiedene Prozesse treffen sich beim Ergebnis

Ver schiedene Prozesse liefern das Ergebnis an den Namensverwalter zurück, der die Schnittmenge bildet

Jeder Prozeß enthält die vollständige Beschreibung der Suchanfrage und liefert nur Ergebnisse, die dieser Angabe entsprechen.

 

Nachteil Ermitteln der Kontexte

Kontexte als Blätter ergeben ein Weglenkungsproblem

 

Problem: gleiche Objekt und Kontextnummern

 

Kontexte an den Blättern

 

Wie werden Kontext verteilt zusammengefaßt?

 

Wie erhalten solche Kontexte eine eigene ID?

 

 

 

 

 [AL21]Wie wirkt sich das auf die globale Registrierung und die Lokation aus aus???

Unspezifische Anfragen

 [AL22]Im Namensgraphen können auch verschiedene Attribute nebeneinander implizit auftreten.

 [AL23]Repräsentation im Grahpen wie bei Werten

Nachteil bei Einsortieren, Clustern

Der Name "uni-ulm" enthält Attrinut und Wert in einem Namen.

 

 [AL24]Aliases

 [AL25]Dieser Satz ist noch schief!

 [AL26]Flexible Erzeugung von IndexBäumen von expliziten Attributen???

 [AL27]Das gilt aber nicht für attributierte NAMEN!!!!!!!

 [AL28]Stimmt das so????

 [AL29]Wie wirkt sich das ganze auf den Hintstack und das Zusatndsdiagramm aus????

 [AL30] Eventuell sollte man die Kontexte noch eine Weile behalten, obwohl temorär keine Objekte darin sind, damit keine nützliche Information verloren geht.

 [AL31]Sind das Einfügen und das Löschen von Namen kommutativ?