  The design of scalable and robust overlay topologies has been a main research
subject since the very origins of peer-to-peer (p2p) computing. Today, the
corresponding optimization tradeoffs are fairly well-understood, at least in
the static case and from a worst-case perspective.
  This paper revisits the peer-to-peer topology design problem from a
self-organization perspective. We initiate the study of topologies which are
optimized to serve the communication demand, or even self-adjusting as demand
changes. The appeal of this new paradigm lies in the opportunity to be able to
go beyond the lower bounds and limitations imposed by a static,
communication-oblivious, topology. For example, the goal of having short
routing paths (in terms of hop count) does no longer conflict with the
requirement of having low peer degrees.
  We propose a simple overlay topology Obst(k) which is composed of k (rooted
and directed) Binary Search Trees (BSTs), where k is a parameter. We first
prove some fundamental bounds on what can and cannot be achieved optimizing a
topology towards a static communication pattern (a static Obst(k)). In
particular, we show that the number of BSTs that constitute the overlay can
have a large impact on the routing costs, and that a single additional BST may
reduce the amortized communication costs from Omega(log(n)) to O(1), where n is
the number of peers. Subsequently, we discuss a natural self-adjusting
extension of Obst(k), in which frequently communicating partners are "splayed
together".

Networking and Internet Architecture