4 - Naming Flashcards
What is a Name?
Used to denote entities in a distributed system
Bits or letters
Entity
Resources
Eg: Printer, host, hard drive
Address
Access point of an entity
Eg: Host address and port
Why have names different from addresses?
Different names for different entities with the same address
One name to represent several addresses
Addresses could change
Addresses are not user friendly
Real 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
Eg: MAC address
Is a phone number a real identifier?
No. It can change and be transferred
What are the challenges of naming systems?
Design and implementation
Resolution of names to addresses
Give three types of naming systmes
Flat (linear)
Structured (hierarchical)
Attribute based
Flat naming
Unstructured names with no information for locatisation of an entity
Flat naming: How would you find an entity?
Cached Address
Searching the net (flooding/random walks etc)
Search in structured network (DHT, HLS)
Look up in directories
DHT
Distributed Hash Table
Flat naming search te chniques
Broadcast/multicast
Random Walk
Distributed hash tables
Hierarchical Location Services
Broadcast/multicast search
Send every computer message.
Com,puter connected to entity replies with address
Disadvantage of broadcast/multicast search
Traffic
Unnecessary Requests
ARP
Address Resolution Protocol
ARP: Resolves what?
Resolves IP to MAC
ARP: Method
Broadcast IP to all computers
Computer with IP replies with MAC address
Random Walk Search
Msg to random neighbour until entity is found
Random Walk disadvantage
Might take a long time
Distributed Hash Table Search
Use hash function to determine identifier.
Find entity using structure of overlay net
DHT Nodes concept
Distribute items over set of nodes
Nodes given identifiers
Every item hashed to key which refers to the node.
Chord
Nodes organised into logical ring
Chord: VIrtual vs Actual Nodes
Acual nodes are storage locations
CHord: What are actual nodes aware of?
their successor (clockwise)
their predecessor (anti-clockwise)
additional nodes for fault tolerance
Chord Mapping: Virtual node storage
Items are assigned to the successor. ie actual node with smallest id >= k
Simple Key Location search
Simply go around the ring until node is reached
O(N) hops
Scalable Key Location search
Introduce shortcuts
Every node is provided with a finger table
Finger Table
Routing table that has m = log(N) entries i = 1,2, …, m
i-th entry: succ(p+2^(i-1)) where p is the current node
Scalable Key lookup
key k, current node p
if p < k < FTp, go to FTp(1) + stop.
Otherwise, forward to FTp(j) where FTp(j) <= k < FTp(j+1)
HLS
Hierarchical Location Services
HLS Summary
Build a search tree
Divide net into hierarchical domains
Each domain rep by sep dir node
HLS not to be confused with..?
Do not confuse with Hierarchical naming
This is a flat naming technique
HLS: Name resolution
Localitity principle:
Start at local leaf node
If node knows E, then follow downward
Else go up
Locality: Moved within domain…
If entity moved in domain, only update leaf.
Locality: Moved to other domain…
If moved domain, only update leafs up to first common ancestor.
Locality: Replicated to other domain
If entity replicated in other domain, update nodes from that domain up to common ancestor
How might you avoid searching in HLS?
Caching
Forwarding Pointers
Forwarding Pointers:
When an entity changes locaiton, it leaves a pointer to its new location.
Forwarding Pointers: Disadvantages
Long chain of pointers fault prone
Latency
Home-based Approaches
Forwarding Pointers: Disadv solution
When client calls server via forwarding pointer, client stub given new location
Pointer removed when required.
Home based approaches to avoiding searches
Mobile device has home base which maintains mobile address
Home based approach: Problems
Latency, home base maintenance.
Overhead if mobile address becomes static.
Poor geographic scalability
Structured Naming
Hierarchical Name Spaces
Can be split into meaningful parts
Structured Naming Examples:
Internet Domain,
File path,
phone number with country and area
Naming Graph
represented as directed graph
- Edge label is name part
- Directory node contains table of (ID,label) pairs
- Leaf represents entity
- Leaf attributes describe entity
UNIX: Boot block
Load OS into main mem
UNIX: Superblock
Info about file system: size, free blocks and index nodes
UNIX Index Nodes
Describes a dir, file or link.
Contains attributes
inode number corresponds to node id in naming graph
UNIX: Data Block
Actual file data
UNIX: Regular File
User data or exec. files
UNIX: Directory:
File that contains list of files including inode
UNIX: Name Linking
Unix allows hard links. The same path can reference the same entity
Symbolic Link
A type of alias where it does not directly refer to the entity but instead has the actual path as an attribute
Mounting
Used to merge name spaces in a transparent way
Mounting: Required info
Access protocol
Server name
Mounting point
Name Space Distribution: DNS
DNS is distributed over several systems:
Global: tables rarely change
Admin: Relatively stable
Managerial: Nodes change frequently
Iterative Name Resolution
Client resolves name step by step contacting servers itself.
Next address to check is provided to client
Recursive Name Resolution
Client asks name server to resolve.
Name server forwards requests.
Repeats until name server is reached with entity.
Iterative vs Recursive
Less work by servers - iterative
Better server-side caching - recursive
Lower latency - Recursive
Lower mem usage - Iterative
Attribute naming systems
Assume; Entities have pairs
Search entities by attributes
Resource Description Framework
Uniiversal language for describing resources (by relations)/
LDAP
Lightweight Directory Access Protocol
Use of LDAP
Accessing and maintaining distributed directory services
Main functions of LDAP
Update: modifying directory information
Query: searching and comparing directory info
Authentication
LDAP Schema
In terms of DNs and RDNs
Entries consist of set of attributes
Entries have unique distinguished names (DN) which subset these attributes
Each DN attribute is called a relative distinguished name (RDN)
Distributed LDAP Systems: DIT
Directory Information Tree can be distributed over multiple servers
Distributed LDAP servers:What agent does each have?
Each has a Directory Service Agent (DSA)
Distributed LDAP clients: What agent?
Each has a aDirectory User Agent (DUA) that communicate with DSAs to resolve queries
