Performances Study of the Distributed Spanning Tree an Overlay Network for Server Lookup

Random graph and tree are two topologies used to build overlay networks. These overlay networks may be used by large scale discovery mechanisms to run search algorithms. The distributed spanning tree (DST) is another topology that may be used as overlay. In a DST, every computer is a leaf. DST´s non-leaf nodes are sets of computers instead of computers. Thus, it allows the use of tree traversal algorithms while avoiding the usual tree´s bottlenecks. As a result, the DST allows more efficient executions of search algorithms in term of number of sent messages and in term of load balancing. In this paper, we describe the results of several simulations of flooding algorithm executions. These simulations are run on the three previous topologies and for different numbers of nodes. These simulations indicate that the DST structure is more efficient than graph topology which, in turn, is more efficient than tree topology in term of traversal speed and in term of supported load for every simulated scale. We study as well the behaviour of the DST when nodes are added or deleted to show that the structure is adapted to dynamic environments.