Small World Networks as (Semi)-Structured Overlay Networks

Recent research has shown that small world network (SWN) is navigable. In this position paper, we propose that SWN, for example those which are social networks, have nice properties which make them attractive as overlay networks. Such networks occupy a space between structured and unstructured overlay networks. Our thesis is that SWN may be attractive enough to be a replacement for traditional structured overlay networks which are usually based on chord-style distributed hash tables. Preliminary experiment results show that without node failure, the performance of greedy routing in SWN works very well and with additional links in SWN the robustness in routing can be improved as well as the resilience against node/link failure.