Load balancing in an Overlay Network

Heterogeneity and Load Balance in Distributed Hash Tables

Summary, key ideas

Instead of picking k virtual servers with random IDs, a node clusters those IDs in a random fraction f(k/n) of the ID space. This allows the node to share a single set of overlay links among all k virtual servers.

When a node leaves the system (same issue when a node arrives), the total load of the node will be given to its direct neighbor. This can result in cascading errors. A better approach when a node arrives is to pick random IDs and not contiguous IDs, in order to balance the load. A simple way to deal with heterogeneity is that a node hosts an amount of virtual servers proportional to its capacity.
A second issue is that it does not allow movement of virtual servers between nodes.