一个通用最优的动态网络构建框架

A Universal and Optimal Dynamic Network Constructive Framework

覆盖网络的拓扑特性对P2P系统的性能至关重要.现有的覆盖网络大多基于静态互联网络,因为互联网络在静态环境下表现出良好的拓扑特性.Moore下界给出这些静态网络的直径和结点度数的最佳折中理论值,但由于动态变化的网络,Moore下界不适合现存P2P系统.为此,该文根据现有P2P系统的特点,给出在高度动态环境下新的网络直径和路由平均距离的下界.现有系统的路由性能不能超越此下界,因为它们不能很好地适应高度动态的网络——这一P2P系统最重要的特点.另外已被提出的覆盖网络都针对其相应静态结构有不同的维护机制,并没有统一的构建方法.为解决上述问题,该文提出了动态Trie树结构这一通用框架,任何静态互联网络都可以基于该框架构造出新的P2P系统,同时此通用框架又包含了一系列最优的设计策略.根据该构造方法,文章采用deBruijn和Butterfly图构建出两个新P2P系统,并且它们的性能可以超越文中给出的下界.经少许修改,构建deBruijn和Butterfly的方法也可应用到其它互联网络如Hypercube、Kautz、Shuffle-exchange和CCC等.

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 fea- tures. In this study, therefore, we first prove new lower bounds of the network diameter and av- erage query distance in a highly dynamic environment. The routing latency of the existing sys- tems 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.