Non-Sticky Fingers: Policy-Driven Self-optimization for DHTs

It is a common situation with distributed hash tables (DHT) that insertions and lookups frequently target only specific fractions of the entire value range. We present in this paper a self-optimization scheme for DHTs that optimizes the routing behavior in such situations. In our scheme, called Non-Sticky (NS) fingers, each node continuously measures the routing behavior and guides neighboring nodes to adjust their NS fingers (a subset of all the long distance links that the node establishes) accordingly in order to shortcut the most popular sections of routes. Our scheme enables self-optimization, which means that it adapts to the current system state and only operates when advantageous. It is also policy-driven, which means that the application can specify its policy on the tradeoff between performance and cost efficiency. We implemented the NS-fingers scheme for an existing order-preserving DHT and report the evaluation results. Our simulation results show that in a realistic application scenario, NS-fingers can halve the number of routing hops.