Ca-Chord：基于主从环的Chord路由算法

提出基于主从结构的Chord路由算法。该算法根据区域组成多个子环,在子环中推选出处理能力强的节点为超节点彼此相连构成主环。每次路由都从子环开始,然后进入主环,确定路由跳节点后,再在该节点对应的子环查找目标节点,使得大部分路由都在子环执行,避免在整个P2P环上往复跨区域查找,减少路由跳数,提高路由延时性能。     

Chord协议的改进双向路由表结构

在结构化P2P网络中有效快速地定位节点非常重要。Chord是结构化网络中一种比较成功的路由算法。但是Chord的路由表存在着一定的信息冗余,且只能从环的一个方向查询,对于后半环节点信息的查询支持不足,由此导致查询定位的效率不高。基于这种不足,本文提出了一种改进后的Chord路由表结构,将路由表中的冗余信息替换为反向环中部分节点信息,同时在路由表中增加剩余反向环的节点信息,由于利用了原表的冗余项,因此在不至于增加过多路由表项数的情况下实现了路由表的双向查找。仿真实验表明,改进后的路由表结构提高了查询效率。     

基于分布式编程语言的Chord协议和算法

P2P分布式哈希表(DHT)协议本身简洁并且易于理解,但是命令式语言与分布式架构的不匹配使得实现和部署一个拥有全部功能的类似Chord的组件相当困难和复杂。针对这些问题,提出一种基于Bloom系统来设计P2P分布式哈希表协议的方法。首先,阐述了Bloom系统的分布式逻辑编程语言要素;其次,设计了一个最小分布式系统;再次,通过定义永久、暂时、异步通信和周期集合,设计了指表维护算法、后继列表算法以及维持稳定算法等,实现一个Chord原型系统。实验结果证明,原型系统能完成Chord所有功能,并且与传统语言相比,代码量减少60%。分析表明最终的算法代码和分布式哈希表协议规范高度一致,不仅增强了代码的可读性和重用性,而且加深了对协议本身及其应用的理解。     

基于对等结点指针表优化的Chord算法改进

对等网络需要解决的一个关键性问题是如何有效地查找存储所需资源的结点。文中在研究分布式查找算法Chord的基础上,介绍了分布式哈希表（DHT）的主要思想,阐述了资源关键字查找方式,重点分析结点指针表的特性及其表中冗余信息对查找资源的影响,进而提出了覆盖冗余信息的方法（uRFchord）改进结点指针表。URFChord方法首先要计算指针表的冗余量R（N）,然后在不增大指针表存储空间的情况下,删除指针表冗余信息再添加R（N）个新的路由信息。通过性能分析及仿真实验,证实了这种改进方法的可行性和有效性,减少了平均查找路径长度,提高了查询效率。     

基于IPv6地址聚类特性的Chord协议改进方法

从IPv6地址的层次分配所体现出的网络聚类特性出发,创造性地提出了分段构造节点标识符的思想,将节点标识符分成两部分,分别通过哈希IP地址的前缀和剩余部分来获得,使具有相同标识符前缀的节点被映射到邻近逻辑空间中,实现了逻辑网络和物理网络的有效吻合,进而在Chord协议基础上巧妙地设计了改进系统Chord6。从仿真分析结果可以看出,Chord6的寻路性能较Chord有了显著的改善。     

S-Chord：一种层次式Chord路由模型

结构化P2P网络Chord的路由表只能覆盖一半标识符空间,只要目标节点落入路由表没有覆盖的半环,就必须通过至少一个中间节点即2跳才能找到,导致其查找效率不高。由此提出一种层次式Chord路由模型——S-Chord,通过构建位于Chord环上的域间转发网,使与发起查找节点不在同一半环内的目标节点有可能只需1跳就能查找到,较好地解决了路由表覆盖面不足的问题。仿真实验表明, S-Chord能够减少平均查找跳数,提高查找效率。     

H-Chord:基于层次划分的Chord路由模型及算法实现

Chord是一种结构化的P2P网络,但是存在路由表信息冗余、查找效率不高的问题。为此,提出了一种基于层次划分的Chord路由模型(H-Chord)及其算法实现。仿真实验表明,H-Chord将大多数节点的路由表长度压缩到只有一项,消除了重复表项,降低了信息冗余,减少了平均查找跳数,提高了查找效率,使控制路由表长度和提高查找效率得到很好的统一。     

基于位置的层次式Chord模型

P2P网络中逻辑网络与底层物理网络拓扑不匹配以及路由表冗余问题导致路由效率低下,节点的异构性产生节点瓶颈。针对上述问题,在Chord的基础上利用节点的位置信息提出一种基于位置的层次式模型ALHChord。模拟实验表明,该模型可以有效提高路由效率,解决节点异构性问题,减少整个系统的维护开销。     

Evolvable agents,a fine grained approach for distributed evolutionary computing: walking towards the peer-to-peer computing frontiers

In this work we propose a fine grained approach with self-adaptive migration rate for distributed evolutionary computation. Our target is to gain some insights on the effects caused by communication when the algorithm scales. To this end, we consider a set of basic topologies in order to avoid the overlapping of algorithmic effects between communication and topological structures. We analyse the approach viability by comparing how solution quality and algorithm speed change when the number of processors increases and compare it with an Island model based implementation. A finer-grained approach implies a better chance of achieving a larger scalable system; such a feature is crucial concerning large-scale parallel architectures such as peer-to-peer systems. In order to check scalability, we perform a threefold experimental evaluation of this model: first, we concentrate on the algorithmic results when the problem scales up to eight nodes in comparison with how it does following the Island model. Second, we analyse the computing time speedup of the approach while scaling. Finally, we analyse the network performance with the proposed self-adaptive migration rate policy that depends on the link latency and bandwidth. With this experimental setup, our approach shows better scalability than the Island model and a equivalent robustness on the average of the three test functions under study.     

基于聚类金字塔的Chord超矩形范围查询

针对超球体查询方式不能将查询范围细化到每一维上的问题,提出一种基于聚类金字塔的超矩形范围查询方法。采用聚类金字塔技术对高维数据建立一维索引值,利用位置保持哈希函数为每个索引值赋予一个唯一的标识,从而构建P-Chord系统,在此基础上,给出范围查询过程。实验结果验证了P-Chord系统在减少距离计算代价与误中点个数、提高查全率等方面的有效性。     

基于Chord算法的物联网信息查询机制

针对物联网中现有物件名称服务查询机制的查询时延大、查找效率低等缺点,提出一种基于Chord算法的物联网信息查询机制。应用OMNET++网络平台进行仿真实验,结果表明,该机制在网络负载均衡、查询效率等方面有所改善,使网络时延由1.5 s左右降低到0~0.025 s之间,适用于地址空间急剧增长的物联网。     

Improved Chord Routing Algorithm Based on the Finger Table

Chord as one kind of structured P2P network＇s protocol, mainly used for network resource locator, and the efficiency of the routing algorithm influence the entire network performance. Study found that when the actual number of nodes in the network is much smaller than the size of the network, each node＇s finger table will contains multiple redundant routing information which is not conducive to the resource discovery and location. To address this problem, this paper presents an improved Chord routing algorithm based on the finger table： CA-Chord （continuous arc chord）, and simulation results confirmed that the improved algorithm can effectively eliminate redundant information in the finger table, and replace the redundant information with nodes information on an arc which are adjacent to each other on the logical position in the network, thereby improving the utilization of the finger table, then reduced the average query step, and greatly improved the efficiency of query.     

Chord路由表结构的改进与优化

如何高效定位所需资源是P2P网络和网格计算中的一个核心问题。P2P资源定位协议Chord的路由表结构含有一定的冗余信息,导致查询效率不高。针对该缺陷,文章对其进行改进与优化,使平均查询路径长度由(1/2)logN缩短到(1/2)logN-(1/4)logR(N),查询效率明显提高。     

Squid: Enabling search in DHT-based systems

A fundamental problem in large scale, decentralized distributed systems is the efficient discovery of information. This paper presents Squid, a peer-to-peer information discovery system that supports flexible searches and provides search guarantees. The fundamental concept underlying the approach is the definition of multi-dimensional information spaces and the maintenance of locality in these spaces. The key innovation is a dimensionality reducing indexing scheme that effectively maps the multi-dimensional information space to physical peers while preserving lexical locality. Squid supports complex queries containing partial keywords, wildcards and ranges. Analytical and simulation results show that Squid is scalable and efficient.     

基于DHT的分布式索引技术研究与实现

针对索引创建和维护效率不高的问题,设计了一种基于DHT(Distributed Hash Table)的分布式倒排索引构建算法。该算法利用基于改进的Chord网络的分布式哈希表技术,将分词后的结果分散到多个索引服务器上并行构建索引,同时采用前驱列表定位和减少服务器定位延迟的技术,大大缩短了索引构建时间。通过采用统一调度的基于分块的增量式倒排索引更新策略,索引更新时不再需要移动已有的索引文件,提高了索引更新效率。利用周期性稳定算法和前驱列表定位提高了系统的稳定性、容错性和索引的一致性。     

Scalable Bloom Filters

Bloom filters provide space-efficient storage of sets at the cost of a probability of false positives on membership queries. The size of the filter must be defined a priori based on the number of elements to store and the desired false positive probability, being impossible to store extra elements without increasing the false positive probability. This leads typically to a conservative assumption regarding maximum set size, possibly by orders of magnitude, and a consequent space waste. This paper proposes Scalable Bloom Filters, a variant of Bloom filters that can adapt dynamically to the number of elements stored, while assuring a maximum false positive probability.     

Building a tuple space on structured peer-to-peer networks

Research on peer-to-peer (P2P) networks has attracted much attention recently. A key factor is their ability to handle dynamics in the system in a distributed fashion, including ad hoc and dynamic join and departure of the peers and dynamic changes in the underlying network environment. As more and more innovating P2P applications appear, the need to support intuitive communication and synchronization among the peers in the P2P system becomes imperative. In this paper, we discuss how to build a tuple space on top of P2P systems and use on-line games as a target application. A simple API is supported for accessing the data stored in the tuple space and communicating between the peers. Through experiments and a demonstration game, we show that our system can facilitate the development of network games in a fully distributed environment.

基于语义路由的P2P信息检索

高效、稳定的P2P信息检索机制已经成为了研究的热点。现有的搜索方法包括使用广播方式或者分布式哈希表。基于分布式哈希表的方法虽然可以获得很好的查询性能,但是不支持近似查询,区间查询、而使用广播方式效率又低,引入语义路由,能很好地解决这些问题。语义路由是一种对广播搜索进行修剪的方法,将查询请求有选择的发送给能响应请求的节点。论文中介绍了语义路由机制,提出了基于该机制的P2P检索系统体系结构,最后使用NeuroGrid进行了仿真,实验结果显示使用语义路由可以提高查询效率。     

Solution for the broadcasting in the Kademlia peer-to-peer overlay

Structured peer-to-peer networks are capable of fast and efficient lookup operations as a distributed hash table. The topology of these networks makes it possible to send broadcast messages among nodes, either for the purpose of providing a complex query service for participants, or to disseminate information valuable for all nodes. In this article a broadcast algorithm for the Kademlia XOR topology is presented. The algorithm, which was developed specifically for Kademlia, uses replication mechanisms similar to that of the storage and retrieval service of this overlay topology. This allows for increased reliability and speed of the broadcast, and also efficient operation, as the routing table for lookups are already available and can be used. An analytical model is presented, which can be used to calculate the required level of replication for any desired reliability at runtime, and is validated with simulation as well.     

基于历史信息的对等网络负载均衡算法

针对当前对等网络中存在的负载不均衡问题,提出了基于历史信息查询的负载均衡算法(HILBA),以提高系统的整体心?实验结果表明,此算法在节点同构和异构环境下都提高了系统的负载均衡能力.