Overlay networks are widely used to deploy functionality at edge nodes without changing network routers. Each node in an overlay network maintains pointers to a set of neighbor nodes. These pointers are used both to maintain the overlay and to implement application functionality, for example, to locate content stored by overlay nodes. If an attacker controls a large fraction of the neighbors of correct nodes, it can ``eclipse'' correct nodes and prevent correct overlay operation. This Eclipse attack is more general than the Sybil attack. Attackers can use a Sybil attack to launch an Eclipse attack
by inventing a large number of seemingly distinct overlay nodes. However, defenses against Sybil attacks do not prevent Eclipse attacks
because attackers may manipulate the overlay maintenance algorithm to mount an Eclipse attack. This paper discusses the impact of the Eclipse attack on several types of overlay and it proposes a novel defense that prevents the attack by bounding the degree of overlay nodes. Our defense can be applied to any overlay and it enables secure implementations of overlay optimizations that choose neighbors according to metrics like proximity. We present preliminary results that demonstrate the importance of defending against the Eclipse attack and show that our defense is effective.

We compare structured and unstructured overlays and derive a hybrid overlay that can outperform both. Unstructured overlays build a random graph and use flooding or random walks on that graph to discover data stored by overlay nodes. Structured overlays assign keys to data items and build a graph that maps each key to the node that stores the corresponding data. Unstructured overlays are widely used in popular applications because they can perform complex queries more efficiently than structured overlays. It is also commonly believed that structured graphs are more expensive to maintain than unstructured graphs and that the constraints imposed by the structure make it harder to exploit heterogeneity to improve scalability. This is not a fundamental problem. We describe techniques that exploit structure to achieve low maintenance overhead, and we present a modified proximity neighbor selection algorithm that can exploit heterogeneity effectively. We performed detailed comparisons of structured and unstructured graphs using simulations driven by real-world traces. Inspired by these results, we developed a hybrid system that uses the graph from structured overlays with the data placement and search strategies of unstructured overlays. The results show that our hybrid system supports complex queries more efficiently than unstructured overlays in realistic scenarios.