基于网络延迟的P2P路由算法的研究

近年来,P2P计算应用已经超过Web应用而成为占用互联网带宽最多的网络应用.针对目前P2P系统中采用的随机选择邻居节点的方法会降低路由效率以及增大网络开销方面的问题,在分析Chord方法特点的基础上,提出一种改进的Chord构建算法DeChord.从逻辑上相邻的点在物理上也相邻这一原则出发,DeChord采用Chord数据定位算法;利用全局网络定位系统计算节点坐标并以此为依据计算节点间的物理距离,节点加入时充分考虑节点之间的逻辑距离与物理距离的一致性,系统节点总是选择距离自己物理距离较近的节点作为邻居节点;DeChord算法使得节点的路由表的信息能得到及时的更新.DeChord中的邻居节点选择方式可以降低消息路由过程中每一跳的网络延时,从而降低整个消息路由的开销.模拟实验表明,利用该算法建立的P2P系统能大幅度降低数据定位的延时.     

PSON: A scalable P2P file sharing system with efficient complex query support

A desired P2P file sharing system is expected to achieve the following design goals: scalability, routing efficiency and complex query support. In this paper, we propose a powerful P2P file sharing system, PSON, which can satisfy all the three desired properties. PSON is essentially a semantic overlay network of logical nodes. Each logical node represents a cluster of peers that are close to each other. A powerful peer is selected in each cluster to support query routing on the overlay network while the less powerful peers are responsible for the maintenance of shared contents. To facilitate query routing, super peers are organized in form of a balanced binary search tree. By exploiting the concept of semantics, PSON can support complex queries in a scalable and efficient way. In this paper, we present the basic system design such as the semantic overlay construction, query routing and system dynamics. A load balancing scheme is proposed to further enhance the system performance. By simulation experiments, we show that PSON is scalable, efficient and is able to support complex queries.     

基于兴趣挖掘的纯P2P搜索机制研究与实现

在纯P2P环境下，搜索机制是影响信息检索的关键因素之一。本文提出一种基于兴趣索引表的搜索机制，并在此基础上实现纯P2P信息检索原型系统Isearch。该机制首先利用向量空间模型将文件内容向量化，然后对向量空间进行聚类，得到节点的兴趣度，再计算节点之间的兴趣相似度，在本地建立兴趣索引表。在搜索时，根据兴趣索引表直接将查询请求转发到有相似兴趣的节点。实验结果表明，该机制既不影响查询结果，又能减少访问节点的数量，提高查询效率。     

A new and effective hierarchical overlay structure for Peer-to-Peer networks

The tremendous growth of public interest in Peer-to-Peer (P2P) networks in recent years has initiated a lot of research work on how to design efficient overlay structures for P2P systems. Scalable overlay networks such as Chord, CAN, Pastry, and Tapestry provide no control over where data is stored and the location of the peers and resources is determined by the hash values of their identifiers and keys respectively. As a result, these overlays cannot support range queries and other proximity-aware complex queries directly.In this paper, we present a hierarchical P2P overlay network called SkipCluster, which is capable of supporting both exact-match and multi-dimensional range queries efficiently without consumption of extra memory space. SkipCluster is derived from skip graphs and SkipNet, but it has a two-tier hierarchical architecture.In both tiers, peers are connected in sequence according to the order of their peer IDs, and related resources are stored near each other without hashing of their resource keys. We design a novel data structure called Triple Linked List (TLL) to store each super-peer’s pointers in the higher tier, which can be used to find the longest prefix and speed up query routing of inter-cluster. In the lower tier, each intra-cluster peer’s routing table contains pointers with exponentially incremental distance. Experimental results show that SkipCluster can speed up both exact-match and range queries in different network sizes.     

A self-similar super-peer overlay construction scheme for super large-scale P2P applications

Unstructured peer-to-peer (P2P) overlay networks with two-layer hierarchy, comprising an upper layer of super-peers and an underlying layer of ordinary peers, are used to improve the performance of large-scale P2P applications like content distribution and storage. In order to deal with continuous growth of participating peers, a scalable and efficient super-peer overlay topology is essential. However, there is relatively little research conducted on constructing such super-peer overlay topology. In the existed solutions, the number of connections required to be maintained by a super-peer is in direct proportion to the total number of super-peers. For super large-scale P2P applications, i.e. the number of participating peer is over 1,000,000, these solutions are not scalable and impractical. Therefore, in this paper, we propose a scalable hierarchical unstructured P2P system in which a self-similar square network graph (SSNG) is proposed to construct and maintain the super-peer overlay topology adaptively. The SSNG topology is a constant-degree topology in which each node maintains a constant number of neighbor nodes. Moreover, a simple and efficient message forwarding algorithm is presented to ensure each super-peer to receive just one flooding message. The analytical results showed that the proposed SSNG-based overlay is more scalable and efficient than the perfect difference graph (PDG)-based overlay proposed in the literature.     

InstantLeap: an architecture for fast neighbor discovery in large-scale P2P VoD streaming

In large-scale peer-to-peer (P2P) video-on-demand (VoD) streaming applications, a fundamental challenge is to quickly locate new supplying peers whenever a VCR command is issued, in order to achieve smooth viewing experiences. For many existing commercial systems which use tracker servers for neighbor discovery, the increasing scale of P2P VoD systems has overloaded the dedicated servers to the point where they cannot accurately identify the suppliers with the desired content and bandwidth. To avoid overloading the servers and achieve instant neighbor discovery over the self-organizing P2P overlay, we design a novel method of organizing peers watching a video. The method features a light-weight indexing architecture to support efficient streaming and fast neighbor discovery at the same time. InstantLeap separates the neighbors at each peer into a streaming neighbor list and a shortcut neighbor list, for streaming and neighbor discovery respectively, which are maintained loosely but effectively based on random neighbor list exchanges. Our analysis shows that InstantLeap achieves an O(1) neighbor discovery efficiency upon any playback “leap” across the media stream in streaming overlays of any size, and low messaging costs for overlay maintenance upon peer join, departure, and VCR operations. We also verify our design with large-scale simulation studies of dynamic P2P VoD systems based on real-world settings.     

P2P流媒体直播系统覆盖网拓扑优化算法

针对对等(P2P)流媒体直播系统中节点的异构性问题,将系统节点分为不同级别,基于随机行走算法选择邻居节点,采用Metropolis- Hastings算法计算随机行走的转移矩阵,从而保证节点能以较大的概率选择到系统中级别较高的节点,并进一步描述覆盖网拓扑优化算法。仿真实验结果表明,该算法能促进节点协作,降低系统延时,在动态网络环境下具有良好的鲁棒性。     

无结构P2P系统的重叠网拓扑优化

无结构P2P（Peer-to-Peer）系统的自身结构特征表现着良好的自治性和扩展性。然而,由于自身松散的重叠网拓扑结构以及对等节点可以自由地加入和离开的特点,系统十分容易产生重叠层与底层物理网络的拓扑结构不匹配的问题。另一方面,由于无结构P2P系统大多数采用泛洪式转发,大量的消息会通过低效地重叠网连接占用带宽,产生不必要的数据冗余,从而影响网络的性能,降低整个网络的利用率。提出一种动态拓扑优化模型机制,该机制通过节点在消息转发过程中获取实时的网络拓扑信息,进而通过一系列优化策略对低效的拓扑结构实施优化。     

P2P VOD系统邻居节点查找算法

P2P流媒体点播系统中,由于用户的VCR操作存在不确定性,在查找合作节点时存在一定困难。针对该问题,提出了一种基于预测的邻居节点选择算法。描述了基于虚拟直播频道的点播系统覆盖网构建方式,将系统中的节点通过DHT协议的方式组织起来。提出了一种基于用户行为的学习预测策略模型,根据该模型预测结果提前查找所需邻居节点。仿真实验表明,该算法能改善用户跳转响应延时,促进节点协作。     

以访问频率为路由方向感的无结构P2P搜索

在全分布无结构P2P中,节点通常组织成为覆盖网络,通过查询消息在网络中广泛转发实现盲目搜索。由于数据存放位置独立于数据内容,一个节点并不清楚哪些节点更容易命中查询,因此发现路由方向感,提高查询消息转发有效性,对全分布无结构P2P搜索具有重要意义。在相关工作中,主要从用户兴趣、本体论等语义角度聚类用户,减小搜索范围。但当前语义获取和语义描述等工作还不甚成熟,因此这些方法并没有得到广泛采用。提出了一种以访问频率为路由方向感的新型搜索方法QRRO。在QRRO中,每个节点被分配一权重标识;节点仅仅为访问频率与节点权重接近的数据建立索引;基于访问频率建立存储内容和存储位置之间的藕合关系,形成路由方向感。模拟实验表明,QRRO在提高搜索成功率、降低搜索路径长度方面是有效的。而且,由于访问频率是每个文件都具有的非语义属性,因此QRRO具有通用性。     

一种高效的P2P环境中的窗口查询算法

随着多媒体以及P2P网络的发展,针对高维数据基于属性的窗口查询已经成为一个重要研究课题.提出了一种在超级节点P2P网络中有效解决高维数据的窗口查询算法,在每个单独的网络节点上,数据通过一种降维算法映射到一维空间,在超级节点上,构造数据的统计信息表以及构造网络查询树,算法在每次查询时,按照查询树的规则来访问整个网络,并利用统计信息剪枝网络中的节点查询,避免网络的泛洪.实验中使用了不同的数据集来评测算法的查询效率,结果表明该算法具有很高的查询效率.     

JXTA P2P分布式事件路由改进算法研究

在分布式信息资源网络环境中,信息资源路由转发机制是分布式计算核心功能之一,P2P网络作为分布式计算采用最广泛的应用逻辑覆盖网络.将网络的小世界特性引入到JXTA P2P网络中,对其资源路由算法进行研究,从动态选取聚集节点、自适应选择种子聚集节点、设定对等体组等3方面进行改进.最后,通过模拟实验,表明改进算法的合理性和可行性.改进算法对分布式环境下自适应路由提供了一种可借鉴事件路由策略.     

一种基于多重覆盖的结构化P2P搜索

本文提出了一种基于多重覆盖的结构化P2P搜索策略,mDOS(multi-Dimensional Overlays based Search).mDOS模拟社会网络中的小世界模型,根据结点的多重属性将结点组织成为多维树型结构.每一维上的任意两个结点根据其在树型结构中的位置形成语义距离.按照覆盖网络中实际距离与语义距离之间的一定函数关系构造多重覆盖网络.邻居结点和目标结点之间在网络中的实际距离可以通过他们的语义距离估计得到,形成基于结点属性的路由方向感.两个结点的有效距离取值多维中的最短语义距离.多重覆盖中的一个结点可以桥接在不同维上的邻居结点,缩小结点之间的平均有效距离,进而缩短搜索路径长度.mDOS还引入索引内容"懒惰维护"机制和路由表"被动修改"机制以克服结点动态性带来的覆盖网络维护代价.最后的实验表明mDOS可以降低搜索路径长度,降低维护代价,提高可用性.     

一种支持多维资源描述的高效P2P路由算法

在分析现有P2P(peer to peer)路由算法的基础上,提出了一种基于二阶矩定位、支持多维资源数据描述的高效资源路由算法--FAN(flabellate addressable network)路由算法.FAN算法将节点映射到统一的多维笛卡尔空间,并以节点相对空间原点的二阶矩作为子空间管理和资源搜索的依据.FAN路由算法具有O(log(N/k))的高路由效率,在节点加入和退出FAN网络时,更新路由信息的代价为O(klog(N/k)).实验结果表明,FAN路由算法具有路由效率高、维护代价小的优点,是一种P2P环境中支持多维资源数据描述的高效结构化资源路由算法.而且,目前部分基于CAN(content-addressable network)网络的改进算法也可以在FAN网络中适用,并获得更好的路由效率和更低的维护代价.     

An optimal inherently stabilizing routing algorithm for star P2P overlay networks

Star graphs possess many desirable properties such as scalable node degrees and diameters, which are essential to facilitate reduced routing table sizes and low maximum path length for routing in large P2P networks. In addition, because a large number of disjoint paths are available and each data/replica in an n‐star can be placed in an (n − 1)‐star, load balancing and alleviation of network bottlenecks can be implemented in star P2P overlay networks. Therefore, star networks have been proposed as viable alternatives to existing overlay topologies for large P2P networks. In this paper, we propose an optimal stabilizing and inherently stabilizing algorithm for routing messages over all disjoint paths between two peers in a star P2P overlay network. The algorithm is optimal in terms of its time complexity in rounds and the length of the longest path traversed by the messages, and fault tolerant due to being stabilizing and inherently stabilizing, allowing the system to withstand transient faults. The algorithm can be used to increase network reliability and survivability in P2P networks. In addition, the usage of all disjoint paths to route messages between two peers leads to increased network bandwidth while distributing the communication overhead across the network and eliminating network bottlenecks in P2P networks. Copyright © 2016 John Wiley & Sons, Ltd.     

一种分阶段的P2P流媒体数据调度算法

针对当前P2P流媒体中各节点数据调度时独立获取数据而对提高节点间数据协作性考虑不足,导致服务器负载较重的问题,提出一种分阶段的数据调度算法。当多个节点将请求的数据中含有相同数据块时,各节点将分两个阶段合作的获取这些数据。第1阶段按照带宽相对大小各节点以合作的方式先各自获取数据的一个子集,第2阶段节点间再充分共享上一阶段已经获得的子集数据,协作地完成该轮调度的数据传输。仿真实验表明该算法可以提高节点间数据协作性,充分利用节点带宽资源传输媒体数据,提高系统可扩展性。     

基于模糊逻辑的资源感知P2P重叠网及其应用研究

P2P重叠网以其系统高效性和有效性被广泛应用于分布式网络管理系统中。但是,传统P2P重叠网络的设计往往只关注其P2P特性,忽略了重叠网自身的管理问题;另外,P2P网络强调的是参与者的平等性,忽略了各参与节点自身性能的差异,从而极大影响了系统的整体性能。本文提出一种基于模糊逻辑的资源感知P2P重叠网,系统中的每个参与节点负责管理一部分网元设备,并充分考虑各节点所管理资源的可用性及其所处环境的时变特性,同时利用基于策略的网络管理方式,构建了一种动态和自主的P2P重叠网网络管理系统。仿真结果证明了该方案在网络管理中的可行性和有效性。     

基于改进DHT算法的分布式资源发现模型的研究*

为了解决大型分布式系统由集中管理导致的扩展性和鲁棒性差的问题,利用改进的结构化对等网组织分布式计算资源,构造一个SRDM（scalable resource discovery model,可扩展资源发现模型）。SRDM将逻辑空间中的节点分为主机节点和资源节点。主机节点对应分布式环境中的计算节点,用于存储peer关联信息,通过相容性hash映射到逻辑空间上;资源节点对应分布式环境中资源属性信息,其与逻辑空间的映射通过分段hash再合并的方法得到。通过对属性值采用位置保留hash方法,使改进后的DHT算法支持有效的资源节点范围查询和多属性范围查询。最后通过实验证明,基于改进DHT算法的资源发现方法比集中式的方法有更好的扩展性,更适用于大规模分布式系统下的资源发现。     

P2P环境中基于信任度的服务路由系统的研究*

随着网络的飞速发展,基于P2P结构的分布式应用越来越多。P2P系统节点之间的资源高度共享,节点之间的信息搜索和交换往往需要第三方节点进行信息中转,这为信息窃取和信息窜改类型的网络攻击带来了便利。为了提高P2P应用的可用性,提出了在P2P环境下一种新的以可信度为标准的服务路由系统的模型,阐述了模型的设计思想,并详细介绍了其实现机制。对仿真系统进行了性能测试,并对测试结果进行了分析。该模型对于信息窜改、信息窃听及路由功能失效等类型的恶意攻击有较好的抑制作用。