论文研究-DHT算法及其应用研究 .pdf

所需积分/C币:7 2019-08-19 11:09:43 237KB .PDF
9
收藏 收藏
举报

DHT算法及其应用研究,米爱莲,王洪波,当前,全分布式P2P结构应用越来越广泛,而DHT是其核心算法,本文对DHT进行了原理分析和应用研究。首先,在对DHT算法原理分析基础上,
国武技论文在线 算法 是一种经典算法,其度数类型为 它是在年由麻省理工学 院提出,其核心思想就是要解决在应用中遇到的基本问题:如何在网络中找到存 有特定数据的节点。其使用一致性哈希作为哈希算法。在一致性哈希协议中并没有定义具体 的算法,在 协议中将其规定为 采用了一致性哈希的一种变体计算方法为节点分配关键字,改善了一致性哈希的 可扩展性。一鈫性哈希函数为每个节点和关键宇分配位宇节的标识符,把节点和键值映 射到一个大小为坏形空问上。此标识符可以用 等散列函数产生。节点的标识符 可以通过散列节点的地址产生,而关键字的标识符可以直接散列此关键字。标识符长度 必须足够长,这样才能保证两个节点或者关键字散列到同个标识符上的概率小到可以忽 略不计 在一致性哈希中,每个关键字都保存在它的后继 节点中,后继节点是节点标 识符大于或等于关键字标识符的第一个节点,可表示为 如果标识符采用 位二进制数表示,并用将从到的数排列成一个圆圈,那么 就是从开 始顺时针方向距离最近的节点。如图所示 2+=sor03 EUEGEEsOr(6》=3 图 环的结构 在一致性哈希的基础上提供了优化的路由算法:在中,每个节点同样需要 存储个其他节点的信息,这些信息的集合被称为查询表( )。一致性哈希中 的节点同样具有这样的表格,但在中,表格中的节点不再是直接相邻的节点,它们的 间距(间隔)将成的关系排列(表示表中的数组下标)。这样形成的节点之间路由 关系实际上就是折半查找算法需要的排列关系 算法 算法可被看作的一个变种,但它是一个度数为常数的经典算法 它利用了小世界现象,于年提出。它是常数度( )的,因为每个节点仅 建立到其他节点常数数量的链接。相比而言,如其它类似算法所要求的链接数 量依赖」系统中的节点总数。当重叠网拓扑变化时: 的这个基木属性显著地降低 了每节点状态和网络流量的总量。但是,随着节点数量的增加,它不如 的规模扩展性 好。如图所示为一个 网络 国武技论文在线 ■rade long link short ink 图 网络 同样采用一致性哈希作为哈希算法。与相比,在 中, 的指针表被替换为个常数但可配置的大小为的长距离连接衣。与其他系统相比,这些链 接是依据调和分布(因此名为 )而随机地选择的。实际上,长距离链接的调和分 布对于少量节点的一个系统,在标识符空间中倾向于大距离,但随着系统增长减少到更小的 距离。 这种配置环境中的基本路由是直接的,即将请求转发到离目的关键字最短距离的节点。 迸过利用到其他节点的双向特性,顺时针和逆时针两个方向都路由导致平均高达 路由跳的减少。另外 使用了一种预查( )方法。每个节点的预查表 记录如下节点,他们通过后继、先驱和长距离链接是可达的,即节点的邻居的邻居。它们不 采用贪婪路由,一个节点将消息转发到其直接邻居(不是邻居的邻居),该邻居承诺到目的 地有最优的前进方向。在管理负担的代价之下,当节点加入或离廾系统时,将平均路由眺数 降低 和其他系统相比, 的主要贡献是其常数节点度拓扑,它户生在每节点状态和 节点加入及离开两个方向非常低的开销。它也利用了节点间的双向链接和双向路由。 的路由性能( 和其他系统( )相比是有竞争力的, 但对于非常巨大的节点数量其扩展性不好。在运行时,基于节点们的能力,节点能够调整到 系统其他部分的所维护链接数量,这是不被 和的原始设计所允许的。 算法 是常数跳算法的典型代表,它在的基础上引入集中式组管理,每个节 点的占用空间是√,路由需要时间。与现有系纨相比,有很好的负载均衡 在节点失效与丢包的情况下, 能维护很好的稳定性,因此,在节点人范闱频繁加入与 退出的情况下能减小抖动。 是松散结构的,它不需要维护结构与不变量(如环、路由 表等)。 也采用一致性哈希作为其哈希算法。 在 中节点和资源的命名算法与 相同。 将系统中节点分成个 组,每个节点通过哈希函数分配到果个组中。各个资源对象也通过哈希函数发布到某个 组中,以使得各组中的节点和资源对象分布均匀 各节点维护的软状态包括:关系组视图 ):同组中所有节点 的视图;连接( ):其它各组中常量个数节点的信息;文件数组( 国武技论文在线 同组节点上的全部资源对象的索引信息。 路由过程为:査询节点通过哈希函数找到文件所在的关系组,然后将搜索请求转发到相 应的组中;在组内查找文件数组找到相应的文件,并将节点信息返回。 的路由延迟 为,但节点度数和维护开销为 。网络更新消息通过 协议来传播。不过, 在超大规模的系统里,这种组维护开销可能过大 由于是基于协议的,因此能够很好的处理抖动问题。其次,具有 灵活性,能够根据值动态的选择距离更近的连接 的路由延时低, 为,并且具有很好的负载均衡。 节点状态的开销为 ,这比其它算 如 等的状态维护开销要大,但是在大部分中型的系统中,这种开销 也算得上是相对较小、且在合理范围内的。 算法的应用及发展趋势 目前在互联网的实际应用当中,业务在全球范闱内都应用得相当广泛,网络的使用 者大量地使用技术来达到共享数据的日的,这便是当下应用最为热门的文件共享 服务,而这其中最耳熟能详,乜是人们日常都在使用的便是和 这两项服务。 现在人们普遍地利用和 下载工具从网络中卜载或是为别人共亨各种各样的 数据,我们甚至可以说互联网现在的繁荣景象与这些技术的应用有很大的关系。而在这两种 主流的文件共享技术中,都对技术加以了利用,并且收到了非常好的效果。 现在的主流下载工具中几乎都使用了作为其中一项重要的功能,因为以目前 的用户规模与发展速度来看,已经很难靠工具提供的索引服务器,或者称之为 来达到预期的服务效果了,此时算法便发挥了其强大的作用,在不需要服务器的情况 下,通过算法的组织,每个客户端在完成自己文件共享的目的之余,还可以负责一个 小范围的路由,从而实现整个网络的寻址和存储。使用支持该技术的下载软件, 用户无需连上 就可以下载,因为软件会在网络中寻找下载同一文件的其他用 户并与之通讯,开始共享任务。 些软件还可以自动通过搜索神子資源,构成所谓的种子市场。所谓种子,但是 在作用过程中非常重要的一种文件,称之为 文件,该文件中记载了需要被共亨 的目标文件相关的 或者是相关信息,在用户互连过程中它是必不可少的。而 种子市场便是通过的技术手段,记录下的一系列与具体工具无关的各种和子信息, 用户可以通过种子市场得到想要的种子信息而不必通过具体的工具,这使得种子的利用 率大大提高。在 中也得到了类似的应用。在文件共享服务中使用算法的 好处非常明显,它大人降低了 的负扫,甚至在理想状态下完全不需要仟何 便能完成其预想的功能,用户之间也可以更快地建立起通信。 日前应用在不同工具当中的算法不尽相同,但最主流的,同时应用在一些主流 或是 工只中的算法叫做 它是由美国纽约大学在年左右提出 的一种比较复杂但效率非常高的算法。虽然在两种不同的文件共亨协议中都采用了相 同的算法,但它们各自的具体实现却各有不同,以适应其各自的特定需求,在 中实现的该算法被称之为算法 然而单纯从技术上算法给各种实际应用带来了巨大的便利,但是由于技术 的引入,使得本来就备受争议的互联网文件共享业务受到了更多的关注,因为在技术 国武技论文在线 卜,定位盜版信息或是恶意信息将更加困难与不可控,因为算法提倡的完全平等的节 点关系导致査找到各种信息的源头比以往更加困难。除此之外,在异构的网络环境中,网络 中节点所处的网络环境差別非常大,单纯地依靠算法在有的时候达不到预期的效果而 常常失效,这也是算法要进一步实用所需面临的问题。 结论 算法作为种成熟的算法,其学术价值已经得到了广泛的认同,并且已经衍生出 大量的不同类型、不同侧重点的算法,而且针对算法的实际应用也越米越多,应用范 围也越来越广¨,特别是在应用领域,算法以其稳定的性能,极髙的可扩展性很妤 的解决了其面佡的一个很大的难题:用户规模膨胀导致的性能瓶颈。各种不同类型的 算法被引入到不同的应用当中,使得系统的服务能力随着用户规模的增长而可以 自行增长,即与用户规模达到自适应的状态,这一特点极人的推动了技术的发展。 同时, 算法也面临着可控性不足、应付网终异质性能力不够等问题,但是随着技 术的演进与发展,不仅仅对于技术 算法必将发挥出更大的能量 参考文献

...展开详情
试读 6P 论文研究-DHT算法及其应用研究 .pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_39840924 欢迎大家使用并留下宝贵意见
2019-08-19
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

    成功上传501个资源即可获取
关注 私信
上传资源赚积分or赚钱
最新推荐
论文研究-DHT算法及其应用研究 .pdf 7积分/C币 立即下载
1/6
论文研究-DHT算法及其应用研究 .pdf第1页
论文研究-DHT算法及其应用研究 .pdf第2页

试读结束, 可继续阅读

7积分/C币 立即下载 >