论文摘要
结构化对等网络是一种采用纯分布式的消息传递机制和根据关键字进行查找的定位服务模型,目前在分布式存储、应用层多播、文件共享等领域已经得到广泛应用。结构化对等网络路由算法研究面临许多问题,例如状态和效率的折衷、拓扑失配、查询热点、结点异构等,如何解决这些问题具有重要意义。本文针对结点异构、查询热点、降低系统负载等关键技术问题进行了较为深入的研究,论文主要包括以下工作:（1）普遍认为在结构化P2P协议中实现能力感知会增加网络开销,如何建立高效、低开销的能力感知协议具有重要意义。分析了传统的结点通过周期性交换路由表信息实现能力感知的算法,该算法收敛时间长且不可避免增大网络开销。提出一种高效的能力感知协议-HeteroChord,HeteroChord协议在结点的路由表建立算法、更新算法、路由表维护算法中实现能力感知。HeteroChord协议在新结点加入时即可计算出需要更新的其他结点,能力感知速度快、效率高。实验结果表明,建立同样大小的网络,HeteroChord中结点更新算法产生的总开销远小于Chord;在动态环境下,HeteroChord具有比Chord更小的维护开销。（2）以HeteroChord为基础建立了一种虚拟双层结构化模型Vring,Vring的外层是由所有结点组建的结构化HeteroChord网络,内层是由超级结点组建的Chord网络。Vring与目前典型的双层结构化网络模型不同的是:超级结点具有和普通结点相同的路由表大小,仅比普通结点多维护一个超级叶子结点集,超级结点路由表维护简单;单个超级结点失败不会造成其他结点脱离网络,不存在单点故障。建立了三种Vring的简单应用系统,通过实验测试了基于本地索引的非DHT查找方式的数据共享系统的查询特征。（3） P2P系统是一种分布式系统,降低系统负载对提高P2P系统的扩展性具有重要意义。目前结构化P2P协议主要利用缓存方法解决查询热点问题,这些缓存方法对数据缓存后的收益无法预测,是一种较盲目的缓存,往往导致系统负载加重。提出一种结构化P2P协议中的缓存计算模型,该模型以降低系统负载为目标,结点采用一种文件访问统计方法跟踪查询本地文件的消息途经邻居结点的历史次数,根据文件访问历史统计记录预测缓存该文件到邻居结点可能减少的查询负载,然后与缓存后可能产生的更新开销对比,进而确定是否缓存文件到相应的邻居结点。实验表明,该缓存计算模型可以有效降低系统负载。（4）仅采用虚拟服务器、多Hash技术或复制不能解决Zipf查询环境下的负载均衡问题。提出一种自适应负载均衡方法,方法采用一种被动式结点负载统计方法生成局部负载视图;采用一种文件访问统计方法生成局部文件访问视图;当系统内结点负载存在差异,重载结点把指向自身的逻辑链路迁移至指向局部负载视图中的轻载结点,通过减小重载结点入度和增加轻载结点入度来减小结点间负载差异;当结点的请求负载较高时,通过局部文件访问视图计算需要缓存的热点文件及目标结点,降低承载热点文件的结点的请求负载。实验表明,在用户查询服从Zipf分布的环境下,自适应负载均衡方法可使结点负载达到较好的均衡。（5）分析了Zipf查询下无状态限制的结构化P2P协议的结点负载不平衡的形成因素,提出一种适合于该类结构化P2P协议的PLC负载均衡方法,该方法采用负载感知的被动式路由表维护算法和基于概率的路由算法提高轻载结点作为路由中继结点的概率,并通过一种缓存机制来降低承载热点文件的结点的请求负载。实验表明,在用户查询服从Zipf分布的环境下,PLC负载均衡方法可使系统达到较好的负载均衡。