Application-level Multicasting
Organizing nodes of a distributed system in an overlay network and using it to disseminate data:
Usually by using a tree with single paths.
Alternatively, using a mesh, which requires some type of routing.
Costs
Link stress
How many times does a message pass through the same network link?
Stretch
Racio in delays between the ALM path and the network path.
Flooding
A node sends a message to each one of its neighbors. each neighbor re-sends it to its neighbors, with the exception of the original, and only if it had not received the message before.
Other algorithms:
Epidemiologic.
Anti-entropy.
Rumors.
Chord
Originally proposed by Ion Stoica et al:
It’s a Scalable P2P Lookup Protocol for Internet Applications.
It’s also an algorithm for structured distributed hash tables (DHT).
Provides a deterministic approach for locating resources, services, and peers.
Resources are expressed as key, value pairs.
Load balancing through Consistent Hashing.
Small routing tables: Log n.
Small routing delay: Log n hops.
Fast join/leave protocol (polylog time).
Consistent Hashing
Assigns both nodes and objects from an m-bit key.
Order these nodes around an identifier circle according to the order of their keys (0 → 2^m- 1). This ring is known as the Chord Ring.
Object with key k is assigned to the first node whose key is ≥ k (called the successor node of key k).
An object with key k is stored at its successor (node with key ≥ k).
The Log N Finger
Each node knows of only log N other nodes.
Chord Finger Table
Node n’s i-th entry: first node ≥ n + 2^i-1.
Lookup
Node 32.
lookup(82): 32 → 70 → 80 → 85
Join
Initialize the predecessor and fingers of the new node. (Knowledge of predecessor is useful in stabilization)
Update the predecessor and the fingers of the existing nodes. (Thus notify nodes that must include N20 in their table. N113[1] = N20, not N32)
Transfer objects to the new node as appropriate.
Last updated
