Elastic Routing Table With Provable Performance for Congestion Control in DHT Networks

Download Now Date Added: Feb 2010
Format: PDF

Consistent hashing-based DHT networks have an inherent load balancing problem. The problem becomes more severe in heterogeneous networks with non-uniform and time-varying popular files. Existing DHT load balancing algorithms are mainly focused on the issues caused by node heterogeneity. To deal with skewed lookups, this paper presents an Elastic Routing Table (ERT) mechanism for query load balancing, based on the observation that high-degree nodes tend to receive more traffic load. The mechanism allows each node to have a routing table of variable size corresponding to node capacities. The in-degree and out-degree of the routing table can also be adjusted dynamically in response to the change of file popularity and network churn. Theoretical analysis proves that the routing table degree is bounded.