一种新的常数度数的P2P覆盖网络

许多结构式P2P系统使用DHT技术将数据映射到相应的节点,以便在数据的存放与查找方面有很好的扩展性.但是,在节点数为n的网络中,大多数结构式P2P系统的每一次查询(lookup)都需要O(logn)步,而且每个节点都要维护O(logn)个邻居.该文提出了一种新的常数度数的P2P系统,它模仿立方体互连圈(CubeConnectedCycle)的拓扑结构,命名为Cycloid.在节点数为n=d×2d的Cycloid系统中,每次查询只要Ο(d)步,并且每个节点只需要维护Ο(1)个邻居.模拟实验表明,在网络规模较大和节点出入频繁的动态P2P网络中,Cycloid比其它常数度数的P2P系统(如Viceroy和Koorde)具有更好的性能,尤其是Cycloid具有更高的搜索效率、更均匀的数据分配、更平衡的节点负载.

P2P软件中有关常数连接度覆盖网络系统的研究

Viceroy、Koorde和Cycloid都采用了分布式哈希表(DHT),Viceroy维护了一个具有常数度数和对数直径的类似蝴蝶网的连接图,一个位于1层的节点有7个指针指向它的邻居节点,每次查询的路径长度需要O(logn)步；Koorde结合了Chord环和de Bruijn图的特征,每个节点与其它节点的连接度为O(1),每次查询的路径长度需要O(logn)步；Cycloid将Pastry和CCC(cube-connected cycles)结合起来,每一个节点与网络中的其它节点连接只需要7项,总的路径长度O(d)步。