On the Structure of Overlay Networks

 RAJMOHAN RAJARAMAN


 In recent years, a number of different structures have been proposed
 as underlying topologies for overlay networks, including the
 hypercube, butterfly, de Bruijn graph, rings and meshes, and
 structured graphs with "small-world" edges.  Another approach,
 consistent with the design of commercial peer-to-peer systems, is to
 impose no structure at all.  In this talk, we will discuss the impact
 of structure (or lack theoreof) on some fundamental tradeoffs among
 overlay network performance metrics such as routing diameter, stretch,
 storage overhead, and fault resilience.