Transcript Naming

Naming
A name in a distributed system is a string of bits or characters
used to refer to an entity.
To resolve names a naming system is needed.
Naming Entities
•
•
•
•
•
•
•
•
An entity can be anything
An entity can be operated on
To operate on an entity we need an access point
An access point in a DS is called address
An address is a special type of name
A name for an entity independent from its address is called location
independent
A true identifier is a special type of name that uniquely identifies an
entity and has the following properties:
- An identifier refers to at most one entity
- Each entity is referred to by at most one identifier
- An identifier always refers to the same entity
Human friendly name is another type of name
Name Spaces
Names in a DS are organized in a name space
Directory table
A naming space can be represented as a graph with leaf nodes (containing entity information)
and directory nodes.
Absolute and relative path names are related to a directory node
A global name denotes the same entity in the system
A local name depends on where the name is being used
Name Resolution
Linking and Mounting
Name resolution can take place only if how and where to start is known (a.k.a. closure
mechanism)
An alias is another name for the same entity (multiple absolute reference or symbolic
link)
The concept of a symbolic link explained in a naming graph within a single name space.
Linking and Mounting
Name space B
Name space A
Protocol
Server
Mounting point
Mount point
Mounting point
Mounting remote name spaces through a specific process protocol ( i.e. in NFS) to
merge different mane spaces
Linking and Mounting
A different approach to merge name spaces (with scalability problems)
Mapping table
New root node
Organization of the DEC Global Name Service
Names in GNS always include the id of the node from where resolution should start
Name Space Distribution (1)
Rarely
changed
Relatively
stable
An example: partitioning of the DNS name space, including Internet-accessible files,
into three layers.
A zone is a part of the name space implemented by a separate name server
Name Space Distribution (2)
Item
Global
Administrational
Managerial
Geographical scale of network
Worldwide
Organization
Department
Total number of nodes
Few
Many
Vast numbers
Responsiveness to lookups
Seconds
Milliseconds
Immediate
Update propagation
Lazy
Immediate
Immediate
Number of replicas
Many
None or few
None
Is client-side caching applied?
Yes
Yes
Sometimes
A comparison between name servers for implementing nodes from a large-scale name
space partitioned into a global layer, an administrational layer, and a managerial
layer.
Replication and caching can be difficult to implement maintaining consistency
Implementation of Name Resolution
Ex: resolution of root:<nl, vu, cs, ftp, pub, globe, index.txt>
The principle of iterative name resolution.
Implementation of Name Resolution
Ex: resolution of root:<nl ,vu, cs, ftp, pub, globe, index.txt>
The principle of recursive name resolution.
Implementation of Name Resolution
The comparison between recursive and iterative name resolution
Naming versus Locating Entities
usually nodes in managerial layers vary very often…
a)
b)
Direct, single level mapping between names and addresses.
Two-level mapping using identifiers.
Simple example in LAN : ARP via broadcasting
Forwarding Pointers
when an entity moves, it leaves a reference to its new location
The principle of forwarding pointers using (proxy, skeleton) pairs or SSP (stub and scion pair)
Problems when the chain is broken
Forwarding Pointers
Redirecting a forwarding pointer, by storing a shortcut in a proxy.
The current location is sent back to the caller
Home-Based Approaches
for mobile entities in large scale networks
a home location keeps track of the current location of an entity
The principle of Mobile IP (2 tiered case)
Each mobile host has a fixed IP add., communications directed to the host home agent
IP address is used ad an identifier
Hierarchical Approach Mechanism
Hierarchical organization of a location service into domains, each having an associated
directory node.
Each entity in a domain is represented by a location record in the directory node.
The root node has a location record for each entity, storing a pointer to the directory node
where the entity is.
Hierarchical Approaches
An entity may have multiple addresses.
If an entity has an address in different leaf domains D1 and D2, then the directory node of the
smallest domain containing D1 and D2 will have 2 pointers.
Hierarchical Approaches
address
client
Looking up a location in a hierarchically organized location service.
Hierarchical Approaches
Update operation in a hierarchical location service (top-down)
a)
b)
An insert request is forwarded to the first node that knows about
entity E (replica).
A chain of forwarding pointers to the leaf node is created.
Pointer Caches
Caching in a hierarchical location service supporting mobile entities is not effective
Caching is effective only if data rarely change, or entity moves within the domain
Pointer caching let the lookup start at the directory of the smallest domain in which a
mobile entity moves regularly
Caching a reference to a directory node of the lowest-level domain in which an entity
will reside most of the time.
Scalability Issues
hierarchical location services have bottlenecks at root directory
level nodes
partitioning high
The scalability issues is related to uniformly placing sub-nodes of a partitioned root
node across the network covered by a location service. Choice of partitions is critical
The Problem of Unreferenced Objects
When an entity can no longer be accessed, it has to be removed
A graph representing objects containing references to each other
Entities that are not directly or indirectly referenced by root nodes have to be removed.
Removing unreferenced entities
• Reference counting
reference to the object are counted, dynamically
• Reference listing
a skeleton maintains the explicit listing of the proxies that point to it
• Tracing-based garbage collection
all entities in a DS are traced, checking which entity can be reached
from the root set.
In a distributed system garbage collection requires network
communication