Application-level Multicasting
Last updated
Last updated
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.
How many times does a message pass through the same network link?
Racio in delays between the ALM path and the network path.
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.
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).
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).
Each node knows of only log N other nodes.
Node n’s i-th entry: first node ≥ n + 2^i-1.
Node 32.
lookup(82): 32 → 70 → 80 → 85
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.
