基于Small-World网络的非结构化DHT算法

目前,非结构化的P2P路由算法面临着搜索效率低下的严峻问题,这严重影响了非结构算法的应用领域.提出一种基于关键字聚类的分布式哈希表算法,主要思路是将环状关键字空间分成上下两层,下层(AUT层)负责关键字管理,上层(HUB层)负责节点路由.每个节点用一个随机数值作为它的聚类中心,从过往的路由消息中本地节点将抽取文件关键字和节点聚类中心,以聚类原则将这些数据记录到本地路由表中.除了改进非结构化算法的数据组织无序性,另一个目标是提高搜索效率.于是,上述算法的增强算法利用了small-world理论,在HUB层中加入远距离节点的聚类中心,将确定性聚类转化为概率性聚类,故能保证路由长度为O(log2N).

利用非确定性DHT解决覆盖网络的非传递连通问题

为了解决网络中广泛存在的非传递连通(NTC)问题,提出了一种利用非确定分布式哈希表(DHT)解决覆盖网络的NTC问题的方法,通过解除底层节点ID与逻辑空间位置的对应关系,避免了NTC节点对网络结构的影响,同时利用重定向路由机制实现网络的消息路由。仿真结果表明,非确定DHT能够有效地解决覆盖网络的NTC问题。

面向异构DHT存储的数据与位置解耦算法

分布式哈希表(distributed hash table,DHT)由于其高效的数据寻址方式而被广泛应用于分布式存储.传统DHT必须将数据存放在指定节点中才能实现高效的数据分布式寻址,极大地限制了DHT技术的应用范围.例如,在异构存储网络中,节点的存储空间、带宽、稳定性等均有较大差异,结合数据特征和节点性能差异选择合适的数据存放节点可以很大程度上提高数据的访问效率,而传统DHT数据和存储位置紧耦合的特征导致其难以应用于异构的存储网络中.针对此问题,提出了vRoute算法以实现DHT中数据标识与其存储位置的解耦.通过构建基于Bloom Filter的分布式数据索引,vRoute算法可以在不降低数据寻址效率的基础上允许数据存储在网络中的任意节点.通过扩展Kademlia算法实现了vRoute,并从理论上证明了vRoute算法的有有效性.最后,模拟实验表明vRoute以较低的存储、网络开销实现了和传统的DHT算法接近的数据寻址效率.

基于DHT的层次式P2P资源定位模型

P2P系统的一个核心问题是如何高效定位所需资源。该文提出了一种基于DHT(distributedhashtable)的层次式资源定位模型,将层次式引入结构化P2P系统。模型将节点组织成一个多层网络,每层可以包含多个DHT子网。该模型有助于解决P2P网络的可扩展性和可管理性问题。模拟测试表明,模型在路径长度和访问延迟方面的性能优于原DHT。

基于DHT的P2P搜索定位技术研究

在P2P系统中,如何高效准确地对资源进行定位是衡量其性能的一个关键。通过对目前基于DHT的几个典型P2P系统搜索定位算法的介绍,分析了基于DHT搜索定位技术的优点和存在的问题,并对P2P发展进行了展望。

DHT算法基本统计特性及其应用

对分布式哈希表(DHT)分析与建模,首先面临的问题是需要了解DHT的基本统计规律。从节点间距服从几何分布这一结论出发,利用概率论相关知识讨论了离散与连续地址空间上DHT网络中间距的分布规律以及一段地址空间上节点出现个数的概率特性。通过对节点管理范围的分析,研究了两种DHT网络的平衡性,并通过测量一段地址空间上的平均节点个数来估计网络规模。结果表明:Chord网络中节点负载是不均衡的,Pastry网络由于节点管理范围定义的细微差别使得节点的负载均衡性有很大改善,而网络规模的估计问题等价于泊松过程的参数估计问题。

一种基于DHT的P2P搜索方法

在网络搜索技术中,P2P模式有C/S模式无可比拟的优势。P2P为非中心化结构中的网络用户赋予更多的权力,使网络应用的核心从中央服务器向网络边缘的终端设备扩散,因而可以全面改写当前的网络搜索技术。在各种P2P技术中,搜索技术是最有价值、最亟待解决的问题,其中分布式哈希表(DHT)协议将是对等网搜索的重要发展方向。本文首先概述P2P搜索技术现状,接着分析比较了当前几种典型的协议搜索方法,最后讨论一种基于分布式哈希表的协议搜索方法。

一类DHT算法中负载的概率分布

根据节点之间间距的概率,推导出Chord、Pastry和虚拟服务器(VS)平衡方案下节点负载的概率分布。分析表明在这些分布式哈希表(DHT)算法中,节点负载都服从相同形式的伽马分布。特别地,当一个物理节点上放置20个虚拟节点,以概率0.99保证节点之间的负载差异不超过两倍。仿真实验验证了以上结果。

DHT负载均衡的必要性

在分布式哈希表(DHT)中,节点ID通常随机选择,但这并不意味着DHT是负载均衡的。仿真结果表明,Chord网络中的负载是不均衡的。在总结对该问题相关工作的基础上,理论上证明了DHT算法本质上的不均衡性,并精确给出节点负载不均衡性的上界范围,仿真验证了分析结论。

P2P系统中基于DHT的文件存储与复制策略的设计

基于一个具有良好扩展性与通用性的DHT文件存储和共享系统,结合传统的数据复制技术,在充分考虑P2P网络的异构性前提下,设计了一种自组织的文档存储策略和一种结合节点综合性能的自适应的最多请求者与最近最少访问相结合的复制策略。这两种策略结合使用,能够保证文档存储的可靠性、共享信息的高效可用性,并可自动调整网络的负载平衡状况,保证网络的可扩展性与稳定性。

P2P网络中基于DHT的自适应Chord风险模型

针对Chord模型在节点加入或离开时产生大量消息,不适用于动态网络的问题,提出一种基于分布式哈希表(Distribute Hash Table,DHT)的自适应Chord模型,即Self-adaptive Chord。方法是该模型在节点加入或离开的时候暂不考虑整个网络逻辑拓扑的一致性,只简单更新其前驱节点和后继节点的路由表,而在节点转发消息时动态地调整各节点路由表,使得网络逻辑拓扑动态地趋向于一致。通过实验对比评估了自适应Chord和Chord性能,结果表明自适应Chord能有效降低由于网络动荡引发的消息数量,同时基本保留了Chord的高效率查询。结论为自适应Chord提供了一种在节点动荡频繁的环境下的候选解决方案。

一种基于DHT混合型对等发现服务的算法设计

提出一种新的发现服务算法ROAD,尝试采用混合策略来适应系统的不同变化程度;通过改善超级点的使用方式,构建加速路由表,加快发现服务的速度,降低消息转发的延时;并通过幂次序组播算法改善对超级点的依赖性。选择不同质量类型的超级点,ROAD可以扩展成满足不同服务需要的发现机制。

一种基于DHT的Web缓存共享方法

提出了一种基于DHT技术的Web缓存共享方法。该方法使得企业网络中所有节点能够相互共享浏览器中的本地缓存,从而形成一个高效的、大规模的分布式缓存共享系统。针对Web缓存共享的系统响应迅速的要求提出一种路由步长为O(2)的路由协议,保证Web查询请求最多只经过一次转发就可到达目标节点。性能分析和仿真实验的结果证明其在路由可靠性、命中率、系统响应和缓存代价方面均有满意的效果。

基于DHT-P2P新型的ONS解析机制

针对基于DNS技术的EPCglobal ONS系统存在负载不均衡,查询时延较大等缺点,提出基于改进DHT机制的层次化ONS解析系统,运用OverSim网络仿真平台进行仿真实验。实验结果表明基于DHT机制的ONS解析系统能够有效地应对单点失效,平均查询时延波动轻微,相比于EPCglobal ONS系统具有更好的负载均衡性能,这个特性极其适合地址空间急剧增长的物联网,对加快物联网的发展具有很重要的现实意义。

一种基于节点交换的DHT优化方法

分布式哈希表(DHT)存在逻辑拓扑与实际网络拓扑不匹配的问题,造成查询操作时延过大。针对该问题,提出一种基于节点交换的DHT优化方法,通过对DHT节点逻辑位置的调整,改善DHT的查找性能。使用地标聚类方法对节点进行分类,物理位置相近的节点属于同一个地标聚类区,采用地理布局的思想,使DHT覆盖网络逻辑拓扑与底层物理拓扑尽量匹配,从而达到缩短DHT查询操作的时延、提高DHT路由性能的目的。

动态DHT中基于目录的负载平衡技术

首先介绍了一种新的虚拟节点选择方法,该方法使虚拟节点在拓扑空间中具有群聚性,能减小节点的连接度,并且能考虑节点在存储能力上的差异,选择适量的虚拟节点。然后将该方法与基于目录的负载平衡方法相结合,将分布式负载平衡简化为目录中节点的负载平衡。模拟测试表明:该技术在动态的Chord中具有可靠的负载平衡功能。

IndexPeer：半结构化P2P系统资源发现模型及其DHT算法

提出了一种基于半结构化P2P系统的资源发现模型——IndexPeer模型。该模型采用三层索引结构,由下至上分别为virtual organization层、service peer层和indexpeer层。IndexPeer充分利用P2P系统中的节点性能差异,具有高效的查找功能,且对网络的高度动态性有良好的适应性。针对Index Peer模型的体系结构,对该模型的结构化层DHT算法进行了研究和设计。基于small-world的仿真实验表明,IndexPeer模型的体系结构及其结构化层DHT算法具有较好的鲁棒性和一定的可扩展性。

基于DHT的P2P网络负载平衡

P2P网络中节点在地址空间分布不均,负载能力大小不同,以及对Keys的访问量各异。这些特点导致了节点间负载分布极不均衡,需要引入平衡机制。针对结构化P2P网络特点提出的算法在搜集节点的负载信息过程中只消耗极少的额外网络资源,同时还通过重定位解决了虚拟节点带来的负面效果。

DHT网络基于债务关系的公平文件交换

P2P(peer to peer)网络中,节点的自私行为极大地降低了系统的可用性.基于债务关系的文件交换网络,构建了一种促进合作的激励机制.同时,该机制保证了文件交换的公平性.激励机制的关键在于DHT(distributed hash table)网络邻居有限的固有特征,因而节点间的交互易于形成重复博弈.DFFE(debt relationship based fair file exchange in DHT network)协议只需维护很少的本地节点交互信息,协议开销小、网络扩展性好.网络路由采用基于一跳信息的贪婪算法.理性节点间的博弈存在纳什均衡,其策略选择的近似算法具有渐进收敛性.仿真实验表明了激励机制的有效性和在动态网络中性能的稳定性.

E-SkipNet:一种支持多属性范围查询的DHT网络

传统DHT网络能支持高效的关键字精确查找,但无法直接支持多属性范围查询,提出一种新的DHT网络E-SkipNet,可支持高效的多属性范围查询.E-SkipNet对传统DHT网络SkipNet进行了扩展改进,将数据属性信息引入到节点双ID设置中,将节点组织成多个属性域负责存储各属性数据,从而支持多属性查询;进一步采用均匀位置保留哈希函数对数据进行映射存储,从而在各属性域中保留数据属性值的顺序关系,这是支持高效范围查询的关键.分析表明,E-SkipNet网络可以支持多属性范围查询,具有良好的负载均衡性和对数据模式的适应性,且比现有MAAN和Mercury等同类方法具有更少的查询路由跳数.