Basics: We consider a name space consisting of nodes that contain information on entities . Nodes can be named.

Context: A function that maps names to nodes

• Bind: create a name for a node in a context:

bind(context,name,node) -> void
 
• Resolve: determine the node to which a name in a given context is mapped:

resolve(context,name) -> node
 
• Contex node (directory): a node containing a context

context(node) -> context

Compound name : a nonempty sequence of names [name1,...,nameK]

Compound names are resolved recursively:

• resolve(context,[name]) = resolve(context,name)
• resolve(context,[name1,...,nameK]) = resolve(context(resolve(context,name1)),[name2,...,nameK])

Meaning of a Name

Pure name: A name that has no meaning at all; it is just a "randomly" chosen string. Pure names can be used for comparison only.

Opposite of pure name is a description: List of properties that an object satisfies (most names are somewhere in between)

Identifier: A name having the following properties:

P1 Each identifier is bound to at most one entity
P2 Each entity is named by at most one identifier
P3 An identifier remains bound to the same entity (prohibits reusing an identifier)
P4 An entity is never assigned a new identifier (prohibits renaming)

Note: P3 <-> P4

An identifier need not necessarly be a pure name, i.e., it may have content. However, that content is never allowed to change, as this would violate P4.

Attributes

• Type of the entity
• An identifier for that entity
• Address of the entity?s location
• Nicknames
• ...

Name Resolution

Closure mechanism: The mechanism to select the implicit context from which to start name resolution:

• cs.rice.edu: contact local DNS name server
• /home/druschel/myFile: start at local filesystem's root directory
• +1 713 527 4664: dial the number at a telephone

Observation: A closure mechanism may also determine how name resolution should proceed
 
 
 
 
 
 

Hard link: What we have described so far as a name-to-entity binding

Soft link: Allow a node O to contain a name of another node:

• First resolve O?s name (leading to O)
• Read the content of O, yielding name
• Name resolution continues with name

• The name resolution process determines that we read the content of a node, in particular, the name in the node

 
• One way or the other, we know where and how to start name resolution given name

Name Linking (2/2)



Observation: Node n5 has only one name

Name Space Implementation

Consider a hierarchical naming graph and distinguish three levels:

Global level: Consists of the high-level context objects. Main aspect is that these context objects have to be jointly managed by different administrations

Administrational level: Contains mid-level context objects which can be grouped in such a way that each group can be assigned to a separate administration.

Local level: Consists of low-level context objects within a single administration. Main issue is effectively mapping context objects to local name servers.
 
 
 
 
 
 
 

Iterative Name Resolution

• resolve(context,[name2,...,nameK]) is sent to Server0 responsible for context
• Server0 resolves resolve(context,name1) -> context1, returning the identification (address) of Server1, which stores context1
• Client sends resolve(context1,[name2,...,nameK]) to Server1
• etc.

Recursive Name Resolution

• resolve(context,[name2,...,nameK]) is sent to Server0 responsible for context
• Server0 resolves resolve(context,name1) -> context1, and sends resolve(context1,[name2,...,nameK]) to Server1, which stores context1
• Server0 waits for the result from Server1, and returns it to the client

Merging Name Spaces (1/3)

Solution 1: Introduce a naming scheme by which pathnames of different name spaces are simply concatenated (URLs).

Solution 2: Introduce nodes that contain the name of a node in a ?foreign? name space , along with the information how to select the initial context in that foreign name space (Jade).

Solution 3: Use only full pathnames, in which the starting context is explicitly identified, and merge by adding a new root node (DEC? s Global Name Space).
 
 

Note: In principle, you always have to start in the new root
 

Scalability Issues (1/2)

Solution: Assume (at least at global and administrative level) that content of nodes hardly ever changes. In that case , we can apply extensive replication by mapping nodes to multiple servers, and start name resolution at the nearest server.

Observation: An important attribute of many nodes is the address where the represented entity can be contacted. Replicating nodes makes large-scale traditional name servers unsuited for locating mobile entitities.
 
 
 
 
 
 
 
 
 

Geographical scalability: We need to ensure that the name resolution process scales across large geographical distances.

Problem: By mapping nodes to servers that may, in principle, be located anywhere, we introduce an implicit location dependency in our naming scheme.

Solution: No general one available yet.
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Internet name service that translates "domain names" to IP addresses. See Notes.
 

World-wide, attribute based directory service, originally designed to supersede telephone directories (yellow and white pages).

• committee design, ignores implementation issues
• scalability properties still unknown
• hierarchical namespace (similar to DNS)

• domain name
• set of attributes

• read(domain-name,{set of attributes}) -> {set of attribute values}

returns the requested set of attribute values, corresponding to the requested domain-name
Example: read(us.rice.cs.druschel,{office-phone#,email-addr}) ->
                                        {+1 713 527 4664, druschel@cs.rice.edu}
 
• search(name, {filter-expression}) -> {set of domain-names}

returns the set of domain names in the directory tree rooted at domain-name that satisfy the filter-expression. The filter-expression is a boolean expression that specifies a search criterion: a logical combination of test of any of the attributes in the directory entry.
Example: search(us.rice.cs, {office=DH3013} ->
                                        {us.rice.cs.gradstudent.ssiyer, us.rice.cs.gradstudent.sameh}

• protocol (defined by WWW)
• DNS domain name
• server filesystem namespace

Hierarchical Namespaces

• useful for namespace organization, easy to ensure name uniqueness
• can be exploited to guide lookup in distributed nameservers
• server hierarchy resembles namespace hierarchy
• case 1: namespace hierarchy reflects object proximity
• (e.g., www.ai.mit.edu/pub/GNU/emacs)
• (e.g., www.cs.rice.edu/courses/comp413)
• can exploit lookup locality
• natural distributed administration of name bindings
• case 2: weak correlation between namespace hierarchy and object location
• (e.g., computers/software/free/GNU/emacs/)
• (e.g., /education/comp-sci/dist-systems/courses/Rice-comp413)
• lookup locality less likely (at least with human users)
• complex administration of name bindings

• critical for scalability (reduce non-local lookup frequency)
• weak consistency

Location service: Solely aimed at providing the addresses of the current locations of entities.

Assumption: Entities are mobile, so that their current address may change frequently .

Naming service: Aimed at providing the content of nodes in a name space, given a (compound) name. Content comprises different (attribute,value) pairs.

Assumption: Node contents at global and administrative level is relatively stable for scalability reasons.

Observation: If a traditional naming service is used to locate entities, we also have to assume that node contents at the local level is stable, as we can use only names as identifiers (think of Web pages).
 
 
 

Problem: It is not realistic to assume stable node contents down to the local naming level

Solution: Decouple naming from locating entities

Name: Any name in a traditional naming space

Object handle: An object identifier (P1, P3)

Contact address: An address providing all information necessary to contact an object

Observation: An object? s name is now completely independent of its location.

Broadcasting: Simply broadcast the OID, requesting the object to return its current address.

• Can never scale beyond local-area networks
• Requires all processes to listen to incoming location requests

• Dereferencing can be made entirely transparent to clients by simply following the chain of pointers
• Update a client? s reference as soon as present location has been found
• Geographical scalability problems:
• Long chains are not fault tolerant
• Increased network latency at derefencing
• Essential to have separate chain reduction mechanisms

Single-tiered scheme: Let a home keep track of where the object is:

• An object? s home address is registered at a naming service
• The home registers the foreign address of the object
• Clients always contact the home first, and then continue with the foreign location

Two-tiered scheme: Keep track of visiting objects

• Check local visitor register first
• Fall back to home location if local look-up fails

• The home address has to be suppoted as long as the object lives.
• The home address is fixed, which means an unnecessary burden when the object permanently moves another location
• Poor geographical scalability (the object may be next to the client)

Basic idea: Build a large-scale search tree for which the under lying network is divided into hierarchical domains. Each domain is represented by a separate directory node.

• The address of an object is stored in a leaf node, or in an intermediate node
• Intermediate nodes contain a pointer to a child if and only if the subtree rooted at the child stores an address of the object
• The root knows about all objects

Basic principles:

• Start look-up at local leaf node
• If node knows about the object, follow downward pointer, otherwise go one level up
• Upward look-up always stops at root

Observation: If an object O moves regularly between leaf domains D1 and D2, it may be more efficient to
store O? s contact record at the least common ancestor LCA of D1 and D2.

• Look-up operations from either D1 or D2 are on aver age cheaper
• Update operations (i.e ., changing the current address) can be done directly at LCA
• Note: assuming that O generally stays below LCA, it does make sense to cache a pointer to LCA

Size scalability: Again, we have a problem of overloading higher-level nodes:

• Only solution is to partition a node into a number of subnodes and evenly assign objects to subnodes
• Naive partitioning may introduce a node management problem, as a subnode may have to know how its parent and children are partitioned.

• If object O generally resides in California, we should not let a root subnode located in France store O? s contact record.
• Unfortunately, subnode placement is not that easy, and only few tentative solutions are known