Department of Computer Science & Engineering

In this paper, we propose a new distributed heap-based data structure called Cone. Cone maintains an ordering of key values in a distributed fashion, and can support queries of the form, "Find x resources of size > S." Cone can be built on any routing substrate as long as the substrate supports longest prefix match-based lookups. We describe the Cone data structure, the operations it supports, and its load balancing properties. We have implemented and evaluated Cone on a 1000-node ModelNet emulation platform and a 50-node PlanetLab distributed testbed. We show that Cone has good load-balancing properties and that it is stable and reactive even when there is considerable amount of dynamism in the system.

Pre-2018 CSE ID: CS2004-0782