Balance and Proximity-Aware Skip Graph Construction

A skip graph is a valuable overlay network for searching for keys in a peer-to-peer application. A problem with the construction algorithm for skip graphs is that it does not consider the proximity of adjacent peers. Because of this, a skip graph often contains links with considerably high communication time. Another problem is that due to the random nature of the algorithm, a skip graph often exhibits structural imbalance. In this paper, we propose a topology reconstruction algorithm to solve these problems. This algorithm, iteratively executed by each node, evaluates both proximity and topological balance and reshapes the overlay topology if necessary. The results of simulations show that the skip graph constructed by our approach achieves shorter search delay than the original skip graph.