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