PacketSkip: Skip Graph for Multidimensional Search in Structured Peer-to-Peer Systems
Andreas Disterhöft, Andreas Funke, Kálmán Graffi · 2017
The Internet is ubiquitous and nodes participating in it are becoming increasingly diverse and heterogeneous. Especially is this true in decentralized, overlay-based networks, which traditionally build upon the infrastructure of the Internet. An ability to search for nodes with specific capabilities becomes of growing interest, for example, to support the node capacity discovery in large scale, distributed networks, such as in peer-to-peer systems. With PacketSkip, we propose a distributed, ordered, multidimensional indexing structure based on a Skip Graph, which operates on top of popular distributed hash tables. Its purpose is to offer, among other functions, capacity-based, high dimensional range searches for peers and their dynamiccapacities. PacketSkip provides a very high search performance, also in comparison to other approaches, as well as low update and maintenance costs. Evaluations show that update and search durations are low and well scalable. Even in dynamic systems, its inner graph structure remains robust and stable.