科研之友
微信
新浪微博
Facebook
分享链接
摘要
The topological properties of overlay networks are critical for the performance of peer-to-peer (P2P) systems. Most existing overlay networks are based on static interconnect networks, since these networks behave good topological features in static environments. The Moore bound sets the optimal tradeoff between diameter and degree for these static networks, but the Moore bound cannot give a good description for existing P2P systems due to their dynamic features. In this study, therefore, we first prove new lower bounds of the network diameter and average query distance in a highly dynamic environment. The routing latency of the existing systems cannot be better than the new bounds. This is because the existing systems require a fixed number of peers known a priori, and P2P systems on the other hand, typically are dynamic, meaning that peers frequently join or leave. In addition, most proposed overlay networks have their unique maintenance mechanisms specific to the interconnect networks on which they are based. To solve the issues, we propose the dynamic multi-way Trie tree structure, a universal framework based on which any interconnect network can be adopted to construct a P2P system. The universal framework also consists of a series of optimal schemes for P2P systems. We show the power of the constructive scheme by applying it to deBruijn and Butterfly graphs to propose two new P2P systems whose performances can exceed the new bounds. Also, the schemes for deBruijn and Butterfly graphs can be easily applied to other interconnection networks after minimal modifications, such as, Hypercube, Kautz, Shuffle-exchange and CCC.
- 出版日期2011
- 单位东北大学
