结构化P2P网络中的负载均衡技术研究

发布时间：2018-08-28 07:48

【摘要】：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:基于PushPull模式的Gossip算法实现状态信息的传播;给出了一种新颖的算法对全局状态进行压缩以减小传输和存储开销。理论分析和实验结果表明,在N个节点的网络中只需要log N-2个周期就可以将任意节点上的状态传播到整个网络中;如果节点负载符合Zipf分布,只需要很小的存储空间就可以存储大规模网络的全局状态信息;在节点状态变化率不高的情况下,通信开销较小,同时可以保证全局状态较高的准确性。
[Abstract]:I DHT-based structured P2P networks have a lot of research and applications, both in traditional distributed systems and in new computing models. After more than 10 years of development, its basic theory and core technology tend to be stable. Researchers have also turned their attention to practical application problems, load balancing is one of them. One important aspect is that the "hot spot" problem in traditional applications exists in structured P2P networks as well. At the same time, the ability of nodes is so different from that of traditional servers that load balancing in structured P2P networks becomes more important. It is more difficult to achieve load balancing in structured P2P networks. This paper focuses on the load balancing problem caused by uneven query distribution in structured P2P networks. The main work includes the following aspects: (1) serious skewed queries easily lead to the load of nodes maintaining hot data in the system is much higher than that of other nodes. Replication/caching technology can effectively balance the load of nodes.The application of replication/caching technology in structured P2P networks has a long history.In order to improve system reliability and data availability,researchers have proposed a large number of replication schemes,and made theoretical analysis from the aspects of efficiency,data retention,data consistency,etc. In view of this problem, the relationship between replica placement strategy and query hit rate in structured P2P networks is analyzed creatively by using the relative position of the replica and the source data. It is found that the hit probability is exponential with the decrease of the distance between the replica and the source data. (2) In DHT-based SOA, search engines and other systems, on the one hand, the "hot spots" caused by high skewness of user access will seriously affect the availability of the system; on the other hand, multi-attribute resource location based on single keyword will inevitably seriously affect the efficiency of the system. Balanced multi-attribute resource location method QFMA: Based on MAAN, the description information of the same resource is stored on multiple nodes; the state information of the node where the "hot" keyword is located is "piggybacked" by copying along the route; other queries switch targets according to these states during the route, and the "hot" keyword is "piggybacked". In structured P2P networks, the logical structure and physical structure of the network are often inconsistent, that is, there are topologies. On the one hand, topological mismatch will lead to high latency of query location; on the other hand, it will increase routing and data transmission between autonomous systems. Replication/caching in structured P2P networks is an effective means to eliminate "hot spots" and achieve load balancing. However, replica creation, replica maintenance, query scheduling and other operations will inevitably lead to additional operations. Routing and data transmission overhead. In order to reduce the overhead of replication/caching and the routing between autonomous systems, a load balancing algorithm PB-Chord based on replication of neighboring nodes is proposed. Any node has the load status information of all nodes in the cluster. The data object information can be used to improve the efficiency of routing and positioning in the process of query. At the same time, the information can be used for centrless query scheduling to achieve load balancing of nodes in the cluster. Theoretical analysis and experimental results show that PB-Chord can achieve load balancing in the cluster. (4) It is a challenging task to obtain global load state in large-scale, dynamic P2P networks. In view of this situation, this paper proposes an efficient way to obtain global load state in large-scale structured P2P networks. Hermes: A Gossip algorithm based on PushPull mode is proposed to transmit state information. A novel algorithm is presented to compress the global state to reduce the transmission and storage overhead. Theoretical analysis and experimental results show that in N-node networks, only log N-2 cycles are needed to propagate the state of any node to the whole. If the node load conforms to the Zipf distribution, only a small storage space is needed to store the global state information of the large-scale network.
【学位授予单位】：国防科学技术大学
【学位级别】：博士
【学位授予年份】：2013
【分类号】：TP393.02

【相似文献】