加载中…
正文 字体大小:

结构化P2P网络——DHT网络原理

(2011-04-16 20:52:05)
标签:

哈希

节点

dht网络

路由表

拓扑

分类: 计算机网络

    P2P系统的应用越来越广泛,在文件共享、流媒体服务、即时通讯交流、计算和存储能力共享以及协同处理与服务等方面都能看到P2P的存在,一些P2P应用如Napster、eMule、BitTorrent等早已是家喻户晓了。

    P2P按其拓扑关系大致可以分为两类四种形式:

       1.非结构化拓扑。包括中心化拓扑、分布式拓扑、半分布式拓扑,其分别对应着Napster、BitTorrent、Kazaa这三种知名的应用。

       2.结构化拓扑。主要形式为分布式结构化拓扑,也就是所谓的DHT网络。

    DHT——Distributed Hash Table 分布式哈希表:

       1.哈希表被分割成不连续的块,每个节点被分配给一个属于自己的哈希块,并成为这个哈希块的管理者。

       2.通过加密哈希函数,一个对象的名字或关键词被映射为128位或160位的散列值。

         DHT网络的基本思想如下:

       1.每一份资源都由一组关键字进行标识。

       2.系统对其中的每一个关键字进行Hash,根据Hash的结果决定此关键字对应的那条信息(即资源索引中的一项)由哪个用户负责储存。

       3.用户搜索的时候,用同样的算法计算每个关键字的Hash,从而获得该关键字对应的信息存储位置,并迅速定位资源。

   

    DHT关键字定位:

       1.DHT通过分布式散列函数,将输入的关键字唯一映射到某个节点上,然后通过某些路由算法同该节点建立连接。

       2.每个节点并不需要保存整个系统的节点视图信息,只在节点中存储其邻近的几个后继节点信息,当一个节点收到一个查询操作时,如果它发现所查询的标识不在自己关联的区间内,那么该节点将会把该查询发送给其存储节点信息表中它认为最靠近目标的邻居。

       3.每次转发都能更进一步地接近数据源。因此较少的路由信息就可以有效地实现到达目标节点。

 

    DHT的具体算法实现过程:

    (1)对每个节点的一定特征(如IP地址)进行Hash,使得到的每个节点的节点值唯一。将节点按照节点值的从小到大构成一个环(Chord环)。(此处节点值可以看作是新环中的IP地址)

    (2)通过节点值,获取每个节点与下一个临近节点之间的距离,从而获得每个节点所需负责的值区间。(此过程类似于建立路由表)

    (3)对每个节点上的资源提取关键字,并对关键字进行Hash,得到的Hash值按照(2)中的每个节点负责的区间进行分配,从而使每一项资源的存储信息都被存储在一个节点上。(此步骤获得了资源的索引列表)

    (4)当搜索一项资源时,对其关键字进行Hash,得到的值与当前节点的值区间表相比较,从而获得资源的索引信息最有可能存在的节点。查询该节点,获取资源的索引,根据索引,即可找到资源所在的节点,并建立通信。

 

   具体示例:image

                                           图一

    如图一所示,节点Hash结果为1、8、14、2、32、42、48、51、56,由此建立一个环。

 

image

                                         图二

    如图二所示,建立“路由表”——Finger Table,节点值为8的N8节点,与其距离为1,2,4这些Hash值对应的索引都被存储在节点N14上,距离为8的Hash值对应的索引存储在节点N21上,依次类推。对于节点N8而言,只需要存储相邻的几个后继节点(N14,N21,N32,N42)对应的“路由表”就可以,而不需要存储全部网络节点。

    在建立完“路由表”后,对每个节点的资源关键字进行Hash,所得的关键值k被存储在一个节点值等于k的节点上,如果不存在这样的节点则存储在节点值大于k的第一个节点上。如图一中,K10对应的关键字存储在N14节点。

 

image

                                         图三

    当需要搜索资源时,对待搜索的资源关键字进行Hash,如图三所示,Hash结果为54,则从当前节点N8的“路由表”中查找,因为N8的路由表,最多只保存到了N42节点的值,所以路由到N42节点,再从N42节点的“路由表”中查询,以此类推,直到最终找到54所存储的节点N56,则关键字54所对应的资源的索引信息就存储在N56节点上,在该节点上查询到此索引信息,就可以根据索引信息中指示的资源所在节点去进行通讯传输了。

 

    基于DHT的算法

    -优点:

      •能够自适应结点的动态加入/退出,有着良好的可扩展性、鲁棒性、结点ID分配均匀具有自组织能力。

    -缺点:

      •DHT的维护机制较为复杂,尤其是结点频繁加入退出造成的网络波动(Churn)会极大增加DHT的维护代价。

      •DHT仅支持精确关键词匹配查询,无法支持内容/语义等复杂查询。

 

    以上便是对DHT网络的一点总结。

0

阅读 评论 收藏 禁止转载 喜欢 打印举报
已投稿到:
前一篇:安家在此
后一篇:清明雨上
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    < 前一篇安家在此
    后一篇 >清明雨上
      

    新浪BLOG意见反馈留言板 不良信息反馈 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有