Module 9: Application layer Flashcards
What is an application-layer protocol
“Overlay Network”
runs on top of TCP/UDP
each node is an end-host
Why should we prefer overlay networks?
Route by content rather than addresses
Solution 1 for P2P search: Centralized Index
example: napster
assume a centralized index system that maps files to machines that are alive
how to find a file:
query the index system -> return a machine that stores the required file
download the file via FTP
advantages: simplicity, easy to implement sophisticated search engines on top of the index system
disadvantages: robustness, scalability
Solution 2 for P2P Search: Flood-based Approach
Example: Gnutella network
flood-based
- send request to all neighbors
- neighbors recursively forward the request
- eventually a machine that has the file receives the request, and it sends back the answer
advantages: totally decentralized, highly robuse
disadvantages: not scalable, the entire network can be swamped with request (to alleviate this problem, each request has a TTL)
flood-based approach
Solution 3: DHT-based Approach
Does DHTs have a flattening effect with the increase in the number of nodes?
True
Content Addressable Network
Associate to each node and item a unique id in a d-dimensional coordinate space
Properties
Routing table size O(d)
guarantees that a file is found in at most d*nˆ1/2 steps, where n is the total number of nodes
CAN example: 2-D space
chord is a DHT
associate to each node and item a unique id in a uni-dimensional space 0..2ˆm - 1
key design decision: decouple correctness from efficiency
properties
- routing table size O(log(N)) where N is the total number of nodes
- guarantees that an item is found in O(log(N)) steps using its key
consistent hash [karger 97]
desired features:
- balanced - load is equal across buckets
- smoothness - little impact on hash bucket when buckets are added/removed
Why is hashing not good for guaranteeing load-balancing?
Is not flexible to change in the number of servers
Consistent Hash [Karger 97]
Lookup for chord protocol (naive)
Ring stabilization is a combination of a stabilize function and a notify function.
true
what does chord protocol do to achieve robustness?
DHT Optimizations
