Transcript Naming, Trading and P2P Systems

Powerpoint presention has been adapted from:
1) www.scs.ryerson.ca/~aabhari/DS-CH9.ppt
2) www.cloudbus.org/652/L10-Chap9NamingServices.ppt
3) www.buyya.com/cv.html
4) cs865team4.wikispaces.com/file/view/Peer-to-Peer_100228.ppt
Content
•
•
•
•
Naming & Trading
Case Study 1: The X.500 Directory Service
Peer-to-peer Systems
Case Study 2: Pastry
Content
•
•
•
•
Naming & Trading
Case Study 1: The X.500 Directory Service
Peer-to-peer Systems
Case Study 2: Pastry
Naming & Trading
Introduction
 In a distributed system, names are used to refer to a
wide variety of resources such as:
 Computers, services, remote objects, and files, as well
as users.
 Basic design issues for name services, such as the
structure and management of the spaces of names
recognized by the service and the operations that the
name service supports, are outlined and discussed in
the context of the Internet Domain Name Service.
Naming & Trading
Introduction
 Resources are accessed using identifier or reference
 An identifier can be stored in variables and retrieved
from tables quickly.
 Identifier includes or can be transformed to an
address for an object.
 E.g. NFS file handle, CORBA remote object
reference.
 A name is human-readable value (usually a string)
that can be resolved to an identifier or address.
 Internet domain name, file pathname,
process number
 E.g ./notes/week1, http://www.cdk3.net/
Naming & Trading
Introduction
 Key benefits
 Resource localization
 Uniform naming
 Device independent address (e.g., you can move domain
name/web site from one server to another server
seamlessly).
Naming & Trading
Introduction
Naming & Trading
Requirements for name spaces
 Allow simple but meaningful names to be used
 Potentially infinite number of names
 Structured
to allow similar subnames without clashes
to group related names
 Allow re-structuring of name trees
for some types of change, old programs should
continue to work
 Management of trust
Naming & Trading
Name Services
 A name service
 is a specific service whose aim is to provide a consistent
and uniform naming of resources, this allowing other
programs or services to localize them and obtain the
required metadata for interacting with them.
 stores a collection of one or more naming contexts, sets of
bindings between textual names and attributes for objects
such as computers, services, and users.
Naming & Trading
Iterative Navigation
 Namespaces allows for structure in names.
 URLs provide a default structure that decompose the
location of a resource in
 protocol used for retrieval
 internet end point of the service exposing the resource
 service specific path
 This decomposition facilitates the resolution of the
name into the corresponding resource
 Moreover, structured namespaces allows for iterative
navigation…
 the act of chaining multiple Naming Services in order to
resolve a single name to the corresponding resource.
Naming & Trading
Iterative Navigation
NS2
2
Client 1
NS1
Name
servers
3
NS3
A client iteratively contacts name servers NS1–NS3 in order to resolve a name
Reason for NFS iterative name resolution
This is because the file service may encounter a symbolic link (i.e. an alias) when
resolving a name. A symbolic link must be interpreted in the client’s file system name
space because it may point to a file in a directory stored at another server. The client
computer must determine which server this is, because only the client knows its
mount points.
Naming & Trading
Recursive Navigation
 The Iterative Navigation can be…
Recursive:
• it is performed by the naming server
• the server becomes like a client for the next server
• this is necessary in case of client connectivity
constraints
Non recursive:
• it is performed by the client or the first server
• if it is performed by the server it is “server controlled”
• the server bounces back the next hop to its client
Naming & Trading
 Non-recursive and recursive server-controlled navigation
NS2
NS2
2
2
1
client
4
NS1
client
3
1
4
NS1
3
5
NS3
Non-recursive
server-controlled
NS3
Recursive
server-controlled
A name server NS1 communicates with other name servers on behalf of a client
DNS offers recursive navigation as an option, but iterative is the standard
technique. Recursive navigation must be used in domains that limit client access
to their DNS information for security reasons.
Naming & Trading
DNS - The Internet Domain Name System
 A distributed naming database (specified in RFC 1034/1305)
 Name structure reflects administrative structure of the
Internet
 Rapidly resolves domain names to IP addresses
 exploits caching heavily
 typical query time ~100 milliseconds
 Scales to millions of computers
 partitioned database
 caching
 Resilient to failure of a server
 replication
Naming & Trading
DNS - The Internet Domain Name System
a.root-servers.net
(root)
au
purdue.edu
yahoo.com
....
ns1.nic.au
(au)
Note:
com.au
edu.au
Name server names
...
are in italics, and
the corresponding
domains are in
abc.unimelb.edu.au
parentheses.
(unimelb.edu.au)
Arrows denote
name server entries csse.unimelb.edu.au
*.unimelb.edu.au
ns0.ja.net
(edu.au)
ns.purdue.edu
(purdue.edu)
* .purdue.edu
usyd.edu.au
unimelb.edu.au
...
mulga.csse.unimelb.edu.au
(csse.unimelb.edu.au)
*.csse.unimelb.edu.au
DNS name servers
dns0-doc.usyd.edu.au
(usyd.edu.au)
*.usyd.edu.au
Naming & Trading
DNS server functions and configuration
 Main function is to resolve domain names for
computers, i.e. to get their IP addresses
caches the results of previous searches until they pass
their 'time to live'
 Other functions:
get mail host for a domain
reverse resolution - get domain name from IP address
Host information - type of hardware and OS
Well-known services - a list of well-known services
offered by a host
Other attributes can be included (optional)
Naming & Trading
DNS - The Internet Domain Name System
 Zone data are stored by name servers in files in one
of several fixed types of resource record.
Record type Meaning
Main contents
A
NS
CNAME
SOA
WKS
PTR
IP number
Domain name for server
Domain name for alias
Parameters governing the zone
List of service names and protocols
Domain name
HINFO
A computer address
An authoritative name server
The canonical name for an alias
Marks the start of data for a zone
A well-known service description
Domain name pointer (reverse
lookups)
Host information
MX
TXT
Mail exchange
Text string
Machine architecture and operating
system
List of <
Arbitrary text
Naming & Trading
DNS issues
 Name tables change infrequently, but when they do, caching
can result in the delivery of stale data.
 Clients are responsible for detecting this and recovering
 Its design makes changes to the structure of the name space
difficult. For example:
 merging previously separate domain trees under a new root
 moving subtrees to a different part of the structure (e.g. if Scotland became a
separate country, its domains should all be moved to a new country-level
domain.)
Naming & Trading
Directory and discovery services
 Sometime users wish to find a particular person or
resource, but they don’t know its name, only some of its
attributes.
What is the name of the user with a telephone
number 03-83441344?
What is the name of professor teaching Cloud
computing at UniMelb (e.g., ask Google!)
 Sometime users require a service, but they are not
concerned with what system entity provides it.
Where can I print high resolution colour image?
 Directory services can help with above situation: they
store collections of bindings and attributes and also looks
up entries that match attribute-based specs.
Naming & Trading
Directory and discovery services
 Directory service:- 'yellow pages' for the resources in a network
 Retrieves the set of names that satisfy a given description
 e.g. X.500, LDAP, MS Active Directory Services
• (DNS holds some descriptive data, but:
– the data is very incomplete
– DNS isn't organised to search it)
 Discovery service:- a directory service that also:
 is automatically updated as the network configuration changes
 meets the needs of clients in spontaneous networks
 discovers services required by a client (who may be mobile) within the
current scope, for example, to find the most suitable printing service
for image files after arriving at a hotel.
 Examples of discovery services: Jini discovery service, the 'service
location protocol', the 'simple service discovery protocol' (part of
UPnP), the 'secure discovery service'.
Content
•
•
•
•
Naming & Trading
Case Study 1: The X.500 Directory Service
Peer-to-peer Systems
Case Study 2: Pastry
The Global Name Service, The X.500 Directory Service
X.500 Directory Service
 X.500 and LDAP
 a hierarchically-structured standard directory service
designed for world-wide use
 X.500 is standardised by ITU (international
telecommunication union) and ISO
 accommodates resource descriptions in a standard form
and their retrieval for any resource (online or offline)
 never fully deployed, but the standard forms the basis for
LDAP, the Lightweight Directory Access Protocol, which is
widely used – IETF RFC 2251.
 A secure access to directory through authentication is also
supported.
The Global Name Service, The X.500 Directory Service
 Part of the X.500 Directory Information Tree (DIT)
X.500 Service (root)
Australia (country)
India
USA
Object class for NSW govt.
NSW (state)
Govt
Vic (state)
Private
Educational
UniMelb
Monash
CSSE
Medicine
Staff
Students
23
Content
• Naming & Trading
• Case Study 1: The Global Name Service, The
X.500 Directory Service
• Peer-to-peer Systems
• Case Study 2: Pastry
Peer-to-peer Systems
Introduction
 Client-Server relationships are more transactionbased than defined as permanent roles.
 Peer-to-Peer elevates clients to servers – on an
asynchronous basis
 Subordinate hosts need to be aware that they are
participating in the peer-to-peer system
 Objective – to build a reliable resource sharing layer
over an unreliable and untrusted collection of
computers and networks
Peer-to-peer Systems
Introduction
 Peer-to-Peer Systems
 Where data and computational resources are contributed
by many hosts
 Objective to balance network traffic and reduce the load
on the primary host
 Management requires knowledge of all hosts, their
accessibility, (distance in number of hops), availability and
performance.
 They exploit existing naming, routing, data replication and
security techniques in new ways
Peer-to-peer Systems
Introduction
 Goal of Peer-to-Peer Systems
Sharing data and resources on a very large scale
‘Applications that exploit resources available at
the edges of the Internet – storage, cycles,
content, human presence’ (Shirky 2000)
Uses data and computing resources available in
the personal computers and workstations
Peer-to-peer Systems
Introduction
 Characteristics of Peer-to-Peer Systems
Each computer contributes resources
All the nodes have the same functional
capabilities and responsibilities
No centrally-administered system
Offers a limited degree of anonymity
Algorithm for placing and accessing the data
• Balance workload, ensure availability
• Without adding undue overhead
Peer-to-peer Systems
Introduction
 Evolution of Peer-to-Peer Systems
 Napster – download music, return address
 Freenet, Gnutella, Kazaa and BitTorrent
• More sophisticated – greater scalability, anonymity and fault
tolerance
 Pastry, Tapestry, CAN, Chord, Kademlia
• Peer-to-peer middleware
 Immutable Files, (music, video)
 GUIDs (Globally Unique Identifiers)
 Middleware to provide better routing algorithms, react to
outages
 Evolve to mutable files
 Application within one company’s intranet
Peer-to-peer Systems
Napster and its Legacy

Napster




Provided a means for users to share music files –
primarily MP3s
Launched 1999 – several million users
Not fully peer-to-peer since it used central servers to
maintain lists of connected systems and the files they
provided, while actual transactions were conducted
directly between machines
Proved feasibility of a service using hardware and data
owned by ordinary Internet users
Peer-to-peer Systems
Napster and its Legacy
peers
Napster serv er
Index
1. Fil e lo cation
req uest
2. Lis t of pee rs
offerin g th e fi le
Napster serv er
Index
3. Fil e req uest
5. Ind ex upd ate
4. Fil e de livered
Peer-to-peer Systems
Napster and its Legacy
Peer-to-peer Systems
Peer To Peer Middleware
 To provide mechanism to access data resources
anywhere in network
 Functional Requirements :
Simplify construction of services across many hosts in
wide network
Add and remove resources at will
Add and remove new hosts at will
Interface to application programmers should be
simple and independent of types of distributed
resources
Peer-to-peer Systems
Peer To Peer Middleware
 Non-Functional Requirements :
Global Scalability
Load Balancing
Optimization for local interactions between
neighboring peers
Accommodation to highly dynamic host availability
Security of data in an environment simplify
construction of services across many hosts in wide
network
Anonymity, deniability and resistance to censorship
Peer-to-peer Systems
Peer To Peer Middleware
 Non-Functional Requirements :
Global scalability, dynamic host availability and
load sharing and balancing across large numbers
of computers pose major design challenges.
Design of Middleware layer
Knowledge of locations of objects must be
distributed throughout network
 Use of replication to achieve this
Peer-to-peer Systems
Peer To Peer Middleware
Peer-to-peer Systems
Routing Overlays
 Sub-systems, APIs, within the peer-to-peer
middleware
 Responsible for locating nodes and objects
 Implements a routing mechanism in the
application layer
Separate from any other routing mechanisms such as
IP routing
 Ensures that any node can access any object by
routing each request thru a sequence of nodes
Exploits knowledge at each node to locate the
destination
Peer-to-peer Systems
Routing Overlays
 GUIDs
‘pure’ names or opaque identifiers
• Reveal nothing about the locations of the objects
• Building blocks for routing overlays
Computed from all or part of the state of the
object using a function that deliver a value that is
very likely to be unique. Uniqueness is then
checked against all other GUIDs
Not human readable
Peer-to-peer Systems
Routing Overlays
 Tasks of a routing overlay
Client submits a request including the object
GUID, routing overlay routes the request to a node
at which a replica of the object resides
A node introduces a new object by computing its
GUID and announces it to the routing overlay
Clients can remove an object
Nodes may join and leave the service
Peer-to-peer Systems
Routing Overlays
 Types of Routing Overlays
DHT – Distributed Hash Tables
DOLR – Distributed Object Location and Routing
DOLR is a layer over the DHT that maps GUIDs and
address of nodes
DHT – GUIDs are stored based on the hash value
DOLR – GUIDs host address is notified using the
Publish() operation
Content
•
•
•
•
Naming & Trading
Case Study 1: The X.500 Directory Service
Peer-to-peer Systems
Case Study 2: Pastry
Case Study 2: Pastry
Pastry
 A routing overlay with the common characteristics
 All the nodes and objects are assigned 128-bit GUIDs
 Nodes are computed by applying a secure hash function such
as SHA-1 to the public key with each node is provided
 Objects such as files, the GUIDs is computed by a secure hash
function to the object’s name or to some part of the object’s
stored state
 The resulting GUID has the usual properties of secure hash
values randomly distributed in the range 0 to 2128 -1
 In a network with N participating nodes, the Pastry routing
algorithm will correctly route a message addressed to an
GUID in O(log N) steps
Case Study 2: Pastry
Pastry
 GUID delivers message to an identified active node,
otherwise, delivers to another active node numerically
closest to the original one
 Active nodes take responsibility of processing requests
addressed to al objects in their numerical
neighborhood
 Routing steps involve the user of an underlying
transport protocol (normally UDP) to transfer the
message to a Pastry node that is ‘closer’ to its
destination
Case Study 2: Pastry
Pastry
 The real transport of a message across the Internet
between two Pastry nodes may requires a substantial
number of IP hops
 Pastry uses a locality metric based on network distance
in the underlying network to select appropriate
neighbors when setting up the routing tables used at
each node
 The participated Hosts are fully self organizing
 Nodes obtains data from network to construct a
routing table and other required state from existing
members
 When a node fails, the remaining nodes reconfigure
the required changes in the routing structure
Case Study 2: Pastry
Pastry
 Pastry Routing Algorithm
The algorithm involves the user of a routing table
at each node to route messages efficiently.
Describe the algorithm in two stages
• Stage 1: Simplified form to routes messages correctly
but inefficiently without a routing table
• Stage 2: Describe full routing algorithm with routing
table which routes a request to any node in O(log N)
messages
Case Study 2: Pastry
Pastry
 Stage 1:
Each active node stores a leaf set – a vector L (of size
of 2l)
The vector contains the GUIDs and IP addresses of
the nodes whose GUIDs are numerically closest on
either side of its own (l above and l below)
Leaf sets are maintained by Pastry as nodes join and
leave
Even after a node failure they will be corrected within
a short time within the defined maximum rate of
failure
The GUID space is treated as circular
Case Study 2: Pastry
Pastry
 Stage 2:
Full Pastry algorithm
Efficient routing is achieved with the aid of routing
tables
Each Pastry node maintains a tree-structured
routing table giving GUIDs and IP address for a set
of nodes spread throughout the entire range of
2128 possible GUID values
Case Study 2: Pastry
Pastry