论文部分内容阅读
基于应用层的覆盖网络技术正迅速兴起并得到广泛的应用。结构化P2P覆盖网络凭借其去中心化、扩展性好、容错性高等优点，日益在互联网信息共享方面显示出巨大潜力。而拓扑构造和资源定位是结构化P2P覆盖网络研究两个核心问题，直接影响了结构化P2P覆盖网络的可用性和系统效率。结构化P2P覆盖网络的拓扑性质决定了其拓扑维护的代价以及节点间路由寻址的性能。常数度结构化P2P覆盖网络在保证了高效路由的同时具备稳定性强、控制信息少、网络负载小等优点，而利用小世界网络理论构造的覆盖网络较小的平均路径长度和较大的聚类系数等优点有利于提高网络的路由效率，这两点对近年来的覆盖网络拓扑研究都产生了一定的影响。结合这些因素构造具有优良特性的结构化网络拓扑是结构化P2P覆盖网络构造的重要研究方向。分布式哈希表技术使结构化P2P覆盖网络能准确定位具有精确标识符的资源，但对于不具备精确标识符的资源却非常困难。在结构化P2P覆盖网络没有目录服务器、各个节点没有全局索引的前提下，为资源定位提供更强大的查询手段是结构化P2P覆盖网络能否得到广泛应用的重要因素。论文以上述两个核心问题为主线，主要开展了以下几方面的研究工作：1.具有小世界网络特性的常数度结构化P2P覆盖网络拓扑构造。基于群论中的半直积方法和具有小世界网络特性的凯莱图模型，提出了一种新型的常数度结构化覆盖网络CayDHT。CayDHT继承了凯莱图的点可迁特性，具有简单高效的路由算法，而常数度特性使得构造大规模的对等网络称为可能。理论分析和实验表明，CayDHT具有O (l)大小的常数路由表、 O (log N)大小的网络直径和优良的容错能力，并具有小世界网络的特性。2.结构化P2P覆盖网络的多关键字搜索研究。一般来说，在结构化P2P覆盖网络中通过多关键字来定位资源需要分布式倒排索引等额外机制。水平切分和垂直切分是分布式倒排索引的两种主要存储方式，本文讨论和分析了结构化P2P覆盖网络在这两种模式下实现多关键字超集搜索的关键问题，并基于CayDHT对这两种模式进行了详细的理论分析和实验对比。3. CayDHT的复杂搜索(盲目搜索)研究。和其他结构化P2P覆盖网络一样，基于分布式哈希表的CayDHT对于不限定搜索形式的复杂搜索缺乏支持，引入传统非结构化覆盖网络的基于广播/洪泛的盲目搜索方法是必要的。本文通过分析CayDHT拓扑的性质，结合凯莱图的点可迁特性，提出了一种基于虚拟搜索树的复杂搜索算法(VTCS)，无需额外维护树结构，具有良好的负载平衡特性，可以在O(logN)的时间复杂度内完成无冗余消息的搜索分发。4.结构化P2P覆盖网络的分区复杂搜索研究。基于复杂搜索和盲目搜索的资源定位都依赖于初始化TTL参数来控制搜索的范围和减少冗余消息，而很多研究显示这种控制方法还存在比较大的缺陷。本文通过借鉴了超节点混合对等网络的优点，使用图控制集理论及网络资源布局理论，基于CayDHT提出了一种分区盲目搜索模型，该模型在搜索时只需要通过小部分搜索分发节点进行TTL参数较小的洪泛式搜索。理论分析和实验表明这种方法可以较好的控制搜索范围，并且可以保证搜索的完全性。