i基于DHT的结构化P2P网络,无论是在传统的分布式系统中还是在新的计算模式中都有着大量的研究和应用。经过10多年的发展,其基础理论和核心技术趋于稳定,研究者关注的重点也转向了实际应用中面临的问题,负载均衡问题是其中很重要的一个方面。传统应用中的“热点”问题,在结构化P2P网络中同样存在,同时由于节点的能力与传统服务器有着天壤之别,使得在结构化P2P网络中实现负载均衡变得更为重要;节点的动态性、异构性以及拓扑失配等因素使得在结构化P2P网络中实现负载均衡难度更大。本文围绕结构化P2P网络中由于查询分布不均匀带来的负载均衡问题展开深入研究。主要工作包括以下几个方面:(1)严重偏斜的查询容易导致系统中维护热门数据的节点的负载远远高于其它节点,采用复制/缓存技术能有效地平衡节点的负载。结构化P2P网络中复制/缓存技术的应用由来已久,为了提高系统可靠性和数据可用性研究者提出了大量的复制方案,并从效率、数据保持、数据一致性等方面进行了理论分析,但缺乏从负载均衡的角度对相关方法进行理论分析的研究。针对该问题,以Chord网络为例,创新地用与源数据的相对位置对结构化P2P网络中副本放置策略与查询命中率之间的关系进行了深入分析,发现了随着副本到源数据距离的减少命中概率呈指数性增长等规律。(2)在基于DHT的SOA、搜索引擎等系统中,一方面由于用户访问高度偏斜产生的“热点”会严重影响系统的可用性;另一方面,基于单关键字进行多属性资源的定位必然会严重影响系统的效率。针对上述问题,提出一种支持负载均衡的多属性资源定位方法 QFMA:以MAAN为基础,将同一资源的描述信息存储到多个节点上;采用沿路复制的方法在路由路径上“捎带”发布“热门”关键字所在节点的状态信息;其它查询根据这些状态在路由过程中进行目标切换,将“热门”关键字所在节点的负载分流到负载较轻的节点上,从而实现系统的负载均衡。QFMA在支持多关键字查询的同时,能够有效平衡热点的负载,且副本管理开销较小。(3)结构化P2P网路中,网络的逻辑结构和物理结构往往不一致,即存在拓扑失配现象。拓扑失配一方面会导致查询定位延时较高;另一方面会增加自治系统间的路由和数据传输。结构化P2P网络中复制/缓存是消除“热点”实现负载均衡的有效手段,然而副本创建、副本维护、查询调度等操作必然会带来额外的路由和数据传输开销。针对如何降低复制/缓存的开销、减少自治系统间路由等问题,提出了一种基于邻近节点复制的负载均衡算法PB-Chord:以网络中公共的DNS服务器为参照点,位置临近的节点在加入网络时进行聚簇,热门数据在本簇空闲节点上复制,任意节点都拥有本簇所有节点的负载状态信息、数据对象信息,在查询过程中利用这些信息提高路由定位效率,同时利用这些信息进行无中心的查询调度,实现簇内节点的负载均衡。理论分析和实验结果表明PB-Chord能够在实现系统负载均衡的同时,有效减小系统的通信开销,提高系统的路由定位效率。(4)在大规模、动态的P2P网络中获取全局负载状态是一项极具挑战的工作。针对这一现状,提出了一种能够在大规模结构化P2P网络中有效获取全局负载状态的算法Hermes:基于Push&Pull模式的Gossip算法实现状态信息的传播;给出了一种新颖的算法对全局状态进行压缩以减小传输和存储开销。理论分析和实验结果表明,在N个节点的网络中只需要log N-2个周期就可以将任意节点上的状态传播到整个网络中;如果节点负载符合Zipf分布,只需要很小的存储空间就可以存储大规模网络的全局状态信息;在节点状态变化率不高的情况下,通信开销较小,同时可以保证全局状态较高的准确性。