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
How do you achieve robustness if requests or lookup requests along the way fail due to node failure or message losses?
A. Hop-by-hop reliability
B. End-to-end reliability
C. Ring robustness
A and B
