DISTRIBUTED SYSTEMS
Principles and Paradigms
Second Edition
ANDREW S. TANENBAUM
MAARTEN VAN STEEN
Chapter 5
Naming
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Names, Identifiers, And Addresses
Properties of a true identifier:
• 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
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Forwarding Pointers (1)
Figure 5-1. The principle of forwarding pointers
using (client stub, server stub) pairs.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Forwarding Pointers (2)
Figure 5-2. Redirecting a forwarding pointer by
storing a shortcut in a client stub.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Forwarding Pointers (3)
Figure 5-2. Redirecting a forwarding pointer by
storing a shortcut in a client stub.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Home-Based Approaches
Figure 5-3. The principle of Mobile IP.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Distributed Hash Tables
General Mechanism
Figure 5-4.
Resolving key
26 from node 1
and key 12 from
node 28 in a
Chord system.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Hierarchical Approaches (1)
Figure 5-5. Hierarchical organization of a location service into
domains, each having an associated directory node.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Hierarchical Approaches (2)
Figure 5-6. An example of storing information of an entity
having two addresses in different leaf domains.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Hierarchical Approaches (3)
Figure 5-7. Looking up a location in a hierarchically
organized location service.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Hierarchical Approaches (4)
Figure 5-8. (a) An insert request is forwarded to the
first node that knows about entity E.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Hierarchical Approaches (5)
Figure 5-8. (b) A chain of forwarding pointers
to the leaf node is created.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Name Spaces (1)
Figure 5-9. A general naming graph with a single root node.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Name Spaces (2)
Figure 5-10. The general organization of the UNIX file system
implementation on a logical disk of contiguous disk blocks.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Linking and Mounting (1)
Figure 5-11. The concept of a symbolic link
explained in a naming graph.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Linking and Mounting (2)
Information required to mount a foreign
name space in a distributed system
• The name of an access protocol.
• The name of the server.
• The name of the mounting point in the
foreign name space.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Linking and Mounting (3)
Figure 5-12. Mounting remote name spaces
through a specific access protocol.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Name Space Distribution (1)
Figure 5-13. An example partitioning of the DNS name space,
including Internet-accessible files, into three layers.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Name Space Distribution (2)
Figure 5-14. 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.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Implementation of Name Resolution (1)
Figure 5-15. The principle of iterative name resolution.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Implementation of Name Resolution (2)
Figure 5-16. The principle of recursive name resolution.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Implementation of Name Resolution (3)
Figure 5-17. Recursive name resolution of <nl, vu, cs, ftp>. Name
servers cache intermediate results for subsequent lookups.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Example: The Domain Name System
Figure 5-18. The comparison between recursive and iterative
name resolution with respect to communication costs.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
The DNS Name Space
Figure 5-19. The most important types of resource records
forming the contents of nodes in the DNS name space.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
DNS Implementation (1)
Figure 5-20. An excerpt from the DNS
database for the zone [Link].
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
DNS Implementation (2)
Figure 5-20. An excerpt from the DNS
database for the zone [Link].
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
DNS Implementation (3)
Figure 5-21. Part of the description for the [Link]
domain which contains the [Link] domain.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Hierarchical Implementations: LDAP (1)
Figure 5-22. A simple example of an LDAP
directory entry using LDAP naming conventions.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Hierarchical Implementations: LDAP (2)
Figure 5-23. (a) Part of a directory information tree.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Hierarchical Implementations: LDAP (3)
Figure 5-23. (b) Two directory entries
having Host_Name as RDN.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Mapping to Distributed Hash Tables (1)
Figure 5-24. (a) A general description of a resource.
(b) Its representation as an AVTree.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Mapping to Distributed Hash Tables (2)
Figure 5-25. (a) The resource description of a query.
(b) Its representation as an AVTree.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Semantic Overlay Networks
Figure 5-26. Maintaining a semantic overlay through gossiping.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5