Naming in Distributed
Systems
Outline
• Introduction
• Some basic Concepts
• INS :)
• Yet another naming Scheme.
Why Name?
Convenience in Accessing/Sharing
Objects (Files)
Fundamental concept in
Communication (mailboxes, remote nodes)
What does Naming get us?
• Mapping between names->objects
• Provide info on those objects
• Locate/discover objects and their attributes
Thus it directly affects :
• Sharing, migration, replication, security
Names
• Most definitions are inadequate.
• ISO : It is an identifier that denotes an
object.
Classification
• Non-Ambiguous. 1->N (Name->Object)
• Non-Unique. N->1
• Global.
Names, Addresses And Routes
• Name specifies WHAT, address WHERE, routes
HOW to get there.
• Each is a tighter binding of information.
• System names / Communication names.
• Name is usually user-friendly. Naming facility
translates names-> addresses-> routes.
Routing is part of naming!
Name Structure
• Flat : No internal structure.
• Partitioned : Usually hierarchical and have a
naming context.
• Descriptive : Attribute Based.
Partitioned name is subclass. Non-unique
Names. Std. Structure & Semantics needed.
Naming Context/Domain
• A context can be defined as the
environment in which a name is valid.
(Global names have no context.)
• Helps partition the name space.
• Implicit Context : Relative naming
conventions.
Naming schemes
• Hierarchical :
– Extensible/scalable.
– Goes with logical view of the system.
– Implicit context -> smaller names.
– Configuration is (usually) not simple.
Naming Schemes (cont’d)
• Descriptive :
– Supports ‘services’.
– Scalable.
– Easily supports fault-tolerance, group
communication.
– Processing overhead is usually large.
Naming Schemes (cont’d)
• Flat :
– No internal structure.
– Names remain same even if object moves.
– Easily hashed and stored (no processing
overhead) : efficient.
– Easier to implement?
– Not scalable.
Factors in Designing Naming
Facility
• Ease of Name generation.
• Location Transparency: Dynamic binding of names-
>addresses. Object mobility.
• Two levels of identification : user-friendly,
machine-friendly.
• Efficient : Delay, #messages exchanged must be
minimum.
• Support for 1->N mapping between
names & addresses :
– Fault Tolerance
– Group Communication.
INS
• LCS, MIT. 1999
• Part of self-organizing adaptive networks
research.
Motivation
• How to adapt to dynamicity in networks seamlessly -
mobility of devices and services.
• Dynamic resource discovery and service location.
• Software and service mgmt cost > HW
• E.g. : good ol’ printer, finding least loaded server, etc.
Design Goals
• Expressiveness : in finding/discovering
devices/services.
• Responsiveness : adapt quickly to mobility.
• Robustness : Name service failures, inconsistent
state.
• Easy Configuration : minimal manual
intervention, dynamic load distribution.
What is meant by INS
• Describe ‘what’ (intent) to look for, not
where.
• Intentional names implemented using
name-specifiers :- Hierarchy of attributes
and values.
• Message headers contain name-specifiers
not IP addresses.
INS Architecture
• INRs form overlay network.
• Services register with the INRs (periodic
advertisement)
• Clients send messages to INRs.
• Early/Late binding.
• Intentional anycast/multicast.
INR boot-up
• DSR (Domain Space Resolver) maintains
list of active/candidate INRs.
• New INR : ping every other INR.
Establish neighbour relation.
• Spanning tree of INRs.
Service Registration
• Soft State, Soft State, Soft State! :-
robustness.
• Periodically advertise intentional names
to INR.
• INR relays names to other INRs
periodically :- All INRs know all names!
Client side
• Intentional Anycast : Send to any server
satisfying request.
• Intentional Multicast : All servers satisfying
request
• Early Binding : Similar to DNS.
• Late Binding : Message routing at name
resolution time.
Load Balancing, Scaling
• Spawn INRs on candidates. Kill if below
threshold.
• Divide name-space :
– Handle only part of name space.
– Cache popular ones.
– Refer to root (DSR) otherwise.
Naming & Addressing without
Unique Identifiers
• Sony CSL.
• Muse operating system.
Motivation
• Scalability. Ability to generate unique ids
regardless how how big system grows.
• Mobility : Of hosts and dynamically
adapting to it.
Design Goals
• Uniqueness : One name should only represent
one object.
• Location transparency.
• Scalability
• Short repstn. to logically nearby objects.
• Availability and fault tolerance of name service.
Assumptions
• Ultra large scale : broadcast impossible.
• Communication with distant objects is
rare compared to local ones.
• Local naming contexts with hierarchical
structure.
Design
• One root naming context
• Relative representation.
• OIDs, OADs, LIDs, LADs :
– Format of OID.
– Interpretation of OID
– Translation of OID/OAD
– Message Passing
– Object Migration
Close
