Names, Identifiers, Addresses

Names

Defining a (distributed) naming system amounts at. . .

defining a set of the admissible names
defining the set of the named entities
defining the association between names and entities

What is a name?
A name is something that refers to an entity
A string, a sequence of symbols, . . .
Defining the set of the admissible names determines how we can
speak about the system

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 7 / 29

 Names, Identifiers, Addresses

Entities

Entities are to be used

An entity is something one can operate on
by accessing to it
through an access point

Access point
A special sort of entity in distributed systems
used to access an entity
like, the cell phone to access yourselves

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 8 / 29

 Names, Identifiers, Addresses

Entities

Entities are to be used

An entity is something one can operate on
by accessing to it
through an access point

Access point
A special sort of entity in distributed systems
used to access an entity
like, the cell phone to access yourselves

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 8 / 29

 Names, Identifiers, Addresses

Addresses

Accessing an entity thru an access point. . .

requires an address
like, your cell phone number
In short, the address of an access point to an entity can be called the
address of the entity

Can’t we use addresses as names?

They are names of some sort
But, quite unfriendly for humans
Location independence might be desirable

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 9 / 29

 Names, Identifiers, Addresses

Addresses

Accessing an entity thru an access point. . .

requires an address
like, your cell phone number
In short, the address of an access point to an entity can be called the
address of the entity

Can’t we use addresses as names?

They are names of some sort
But, quite unfriendly for humans
Location independence might be desirable

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 9 / 29

 Names, Identifiers, Addresses

Identifiers

Another type of name

1 An identifier refers to at most one entity
2 Each entity is referred to by at most one identifier
3 An identifier always refers to the same entity – it’s never reused

Addresses vs. identifiers

Identifiers are sorts of names
But, different purposes
E.g., while my user name andrea.omicini is not to be reused for
another person of the Alma Mater (identifier), my cell number could
instead be reused by someone else (address)

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 10 / 29

 Names, Identifiers, Addresses

Identifiers

Another type of name

1 An identifier refers to at most one entity
2 Each entity is referred to by at most one identifier
3 An identifier always refers to the same entity – it’s never reused

Addresses vs. identifiers

Identifiers are sorts of names
But, different purposes
E.g., while my user name andrea.omicini is not to be reused for
another person of the Alma Mater (identifier), my cell number could
instead be reused by someone else (address)

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 10 / 29

 Names, Identifiers, Addresses

Human-friendly Names

Identifiers and addresses are often in machine-readable form

Humans cannot handle them easily
This might create problems in the use, monitoring and control of
distributed systems
Human-friendly names

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 11 / 29

 Names, Identifiers, Addresses

Resolving Names to Addresses

Main issue in naming

How do we associate names and identifiers to addresses?
In large, distributed, mobile, open systems, in particular?

Examples
The simplest case: name-to-address binding, with a table of
hname, addressi pairs
← Problem: a centralised table does not work in large networks
The DNS case: hierarchical composition
→ www.apice.unibo.it hierarchically resolved through a recursive
lookup

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 12 / 29

 Names, Identifiers, Addresses

Resolving Names to Addresses

Main issue in naming

How do we associate names and identifiers to addresses?
In large, distributed, mobile, open systems, in particular?

Examples
The simplest case: name-to-address binding, with a table of
hname, addressi pairs
← Problem: a centralised table does not work in large networks
The DNS case: hierarchical composition
→ www.apice.unibo.it hierarchically resolved through a recursive
lookup

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 12 / 29

 Flat & Structured Naming

Outline

1 Basics

2 Names, Identifiers, Addresses

3 Flat & Structured Naming

4 Attribute-based Naming

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 13 / 29

 Flat & Structured Naming

Flat Naming

Basic Idea
A name is just a flat sequence of chars / symbols
Works in LANs

Examples
Broadcasting: messages containing the identifier of the target entity
is sent to everyone, only the machine containing the entity responds
Example: ARP (Address Resolution Protocol)
Problem: inefficient when the network grows
Multicasting: only a restricted group of hosts receives the request
Example: data-link level in Ethernet networks

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 14 / 29

 Flat & Structured Naming

Flat Naming

Basic Idea
A name is just a flat sequence of chars / symbols
Works in LANs

Examples
Broadcasting: messages containing the identifier of the target entity
is sent to everyone, only the machine containing the entity responds
Example: ARP (Address Resolution Protocol)
Problem: inefficient when the network grows
Multicasting: only a restricted group of hosts receives the request
Example: data-link level in Ethernet networks

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 14 / 29

 Flat & Structured Naming

Structured Naming

Basic Idea
Flat names are good for machines, not for humans
Structured names are composed by simple human-readable names –
thus matching the natural limitations of human cognition

Example
Internet name space

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 15 / 29

 Flat & Structured Naming

Structured Naming

Basic Idea
Flat names are good for machines, not for humans
Structured names are composed by simple human-readable names –
thus matching the natural limitations of human cognition

Example
Internet name space

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 15 / 29

 Flat & Structured Naming

Name Spaces
Basic Idea
Names are organised hierarchically, according to a labelled, directed
graph – a naming graph
Leaf nodes represent named entities
Directory nodes have a number of outgoing edges, each labelled with
an identifier

Symbolic link in a naming graph

[Tanenbaum and van Steen, 2007]
Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 16 / 29
 Flat & Structured Naming

The Internet Domain Name Space (DNS)

The DNS Name Space

Hierarchically organised as a rooted tree
Each node (except root) has exactly one incoming edge, labelled with
the name of the node
A subtree is a domain
A path name to its root node is a path name
A node contains a collection of resource records

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 17 / 29

 Flat & Structured Naming

Resource Records

Most relevant types of resource records in a DNS node

[Tanenbaum and van Steen, 2007]

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 18 / 29

 Attribute-based Naming

Outline

1 Basics

2 Names, Identifiers, Addresses

3 Flat & Structured Naming

4 Attribute-based Naming

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 19 / 29

 Attribute-based Naming

Limits of Flat & Structured Naming

Beyond Location Independence

Flat naming allow for unique and location-independent way to refer to
distributed entities
Structured naming also provides for human-friendliness
However, distributed systems are more and more information-based –
information could also be the basis for looking for an entity
Exploiting information associated to entities to locate them

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 20 / 29

 Attribute-based Naming

Attribute-based Naming

Description as pairs
Many way to describe an entity could be used
Most popular: a collection of hattribute, valuei pairs associated to an
entity to describe it
Attribute-based naming

A.k.a. Directory services

Attribute-based naming systems are also known as directory services
The essential point: choosing the right set of attributes to describe
resources

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 21 / 29

 Attribute-based Naming

Attribute-based Naming

Description as pairs
Many way to describe an entity could be used
Most popular: a collection of hattribute, valuei pairs associated to an
entity to describe it
Attribute-based naming

A.k.a. Directory services

Attribute-based naming systems are also known as directory services
The essential point: choosing the right set of attributes to describe
resources

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 21 / 29

 Attribute-based Naming

Resource Description Framework (RDF)

RDF: A model for describing resources

Each resource is a triplet hSubject, Predicate, Objecti
E.g., hFootballPlayer , fullname, ”Gaby Mudingay ”i describe a
resource FootballPlayer whose fullname is ”Gaby Mudingay ”
Each subject, predicate, object can be a resource itself
References in RDF are essentially URLs

Querying a directory service

If resource description are stored, they can be queried when looking
for a certain resource
The query could return a reference to the resource, to be fetched by
the application

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 22 / 29

 Attribute-based Naming

Resource Description Framework (RDF)

RDF: A model for describing resources

Each resource is a triplet hSubject, Predicate, Objecti
E.g., hFootballPlayer , fullname, ”Gaby Mudingay ”i describe a
resource FootballPlayer whose fullname is ”Gaby Mudingay ”
Each subject, predicate, object can be a resource itself
References in RDF are essentially URLs

Querying a directory service

If resource description are stored, they can be queried when looking
for a certain resource
The query could return a reference to the resource, to be fetched by
the application

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 22 / 29

 Attribute-based Naming

Hierarchical Implementations I

Combining structured & attribute-based naming

Distributed directory services
Lightweight Directory Access Protocol (LDAP)
Example: MS Active Directory

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 23 / 29

 Attribute-based Naming

Hierarchical Implementations II

Hierarchy through LDAP attribute-based names

An LDAP directory service contains a number of directory entries – a
collection of hattribute, valuei pairs, similar to DNS resource records
The directory entries in an LDAP directory service constitute the
directory information base (DIB)—there, each record is uniquely
named
Naming attributes are called Relative Distinguished Names
(RDN)—they are combined to form a globally-unique name, which is
a structured name
As a result, the Directory Information Tree (DIT) is a collection of
directory entries forming the naming graph of an LDAP directory

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 24 / 29

 Attribute-based Naming

Hierarchical Implementations III

Two LDAP directory entries with hierarchical naming. . .

[Tanenbaum and van Steen, 2007]

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 25 / 29

 Attribute-based Naming

Hierarchical Implementations IV

. . . along with the corresponding (partial) DIT

[Tanenbaum and van Steen, 2007]

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 26 / 29

 Conclusions

Summing Up

Naming is a general issue

Particularly relevant in the distributed setting
Different approaches to naming are possible: flat, structured,
attribute-based
Typically, naming systems take a hybrid stance to the naming problem
DNS and LDAP are paradigmatic examples of naming systems

Andrea Omicini (Università di Bologna) 6 – Naming A.Y. 2010/2011 27 / 29