Ulysses: a robust, low‐diameter, low‐latency peer‐to‐peer network

A number of distributed hash table (DHT)‐based protocols have been proposed to address the issue of scalability in peer‐to‐peer networks. In this paper, we present Ulysses, a peer‐to‐peer network based on the butterfly topology that achieves the theoretical lower bound of log n/ log log n on network diameter when the average routing table size at nodes is no more than log n . Compared to existing DHT‐based schemes with similar routing table size, Ulysses reduces the network diameter by a factor of log log n , which is 2–4 for typical configurations. This translates into the same amount of reduction on query latency and average traffic per link/node. In addition, Ulysses maintains the same level of robustness in terms of routing in the face of faults and recovering from graceful/ungraceful joins and departures, as provided by existing DHT‐based schemes. The performance of the protocol has been evaluated using both analysis and simulation. Copyright © 2004 AEI