初步认识

  • 要充分开发 P2P 的优势，非常重要的一点就是妥善解决 P2P 网络中的资源搜索
  • 相较非结构化 P2P 网络，结构化 P2P 网络资源搜索协议比较成熟，且满足可扩展性、鲁棒性、负载均衡、高查询效率等，因而更适合云计算、物联网、移动互联网等应用。
  • 结构化 P2P 资源搜索算法基本上是基于DHT 技术的，如 Chord，CAN，Pastry，Tapestry
  • 基于结构化 P2P 资源搜索算法对网络中的资源进行搜索，能够在非常短的时间内以非常高的效率查找定位到目标资源所在节点，流量相对减少，由于累积效应而极大降低网络的能耗
  • 能够充分利用网络中的带宽资源，利用网络中闲置的节点计算能力，可以充分利用 P2P 的分布式、共享式的特点，并利用结构化 P2P 的资源搜索算法，从而让闲置的节点有效地加入整个的逻辑网络，实现资源的统筹运用

  • 从另外一个角度来讲，是用更少的资源来完成更多的计算，这样从宏观上极大地降低了网络中的能耗

    DHT算法原理

  • 基本组成

  • DHT 算法使用分布式哈希函数来解决结构化的分布式存储问题
  • 分布式哈希表可以看成是一张巨大的散列表，每个节点被分配以一个散列块并负责管理该散列块
  • DHT 存储和搜索技术为 P2P 中资源的存储和搜索提供了全新的思路

  • DHT 将整个搜索空间对应到一个 Hash 空间，然后对各个节点进行相应 Hash，每个节点负责部分哈希空间

  • 存放资源

  • 当某个节点发布一份资源时，即对该资源的特征值( 如文件名) 进行 Hash，得到一个哈希值
  • 根据此哈希值和相应协议的映射关系即可知道此哈希值存放的节点

  • 并把该资源或者该资源索引存放到相应节点上

  • 搜索资源

  • 当需要搜索某个资源时候，类似的，先对该资源特征值进行 Hash，得到一个 Hash值

  • 然后由相关协议可知道其存储节点，并完成路由查询

  • 技术优势

  • 基于 DHT 分布搜索和路由算法因其查找可确定性、简单性、分布性、高效性、快速性等特点

  • 成为结构化 P2P 网络中研究和应用的热点

  • 经典算法

  • Chord（美国麻省理工大学）
  • CAN、Tapestry（加州大学伯克利分校）

  • Pastry（微软研究院）

  • 4 种资源搜索算法都是基于 DHT 进行的，故而本质都是一样的

  • 资源的查询速度都较快、路由表都相对简单、具有鲁棒性( 即容错性强) 、可扩展性较强、负载比较平衡
  • 但是由于细节上的一些差异，使得它们在具有某些相近性能的同时也具有各自的特点

image.png

Chord算法

  • 麻省理工学院 2001 年设计的基于 DHT的可扩展的信息资源定位和路由协议
  • 是基于逻辑环的拓扑结构
  • Chord 中的文档和节点通过一致性哈希变换得到了唯一的标识符
  • 网络中所有的节点根据标识符的大小，从小到大以顺时针的方向构成一个圆环的拓扑结构
  • 文档被存储在顺时针第一个节点标识符大于或者等于文档标识符的节点里
  • 查找时，节点通过依次查找其后继节点便可以找到查询结果，非常适合大规模的 P2P 网络

image.png

  • Chord 算法的特点是简单且性能稳定
  • 较其它结构化 P2P 模型，Chord 有较好的扩展性、可靠性和较高的查询效率

  • 但是 Chord 路由表中有 1 /3 左右的表项重复，降低了查询效率

  • 算法改进

    ZHANG Hao，JIN Hainie，JIN Wu，et al． Dual-chord: a more effective distribute hash table［J］． Mini-Micro S-ystem，2006，27( 8) : 1450-1454

  • 提出了Dual-Chord

  • 提高路由表查询效率，进而减少平均的路由跳数
  • 为每个节点从顺时针和逆时针方向同时构造路由表
  • 但同时也使得每个节点要维护 2 倍于 Chord 的路由表数目，使得系统维护变复杂

CHE Gan，Wu Guoxing，YANG Wang． G-chord: an improved routing algorithm for Chord［J］． Journal of Southeast University ( Natural Science Edition ) ，2007，37( 1) : 9-12

  • 提出了 G-Chord
  • 通过对 Chord 环进行分组，实现组内节点自我管理
  • 由组代表管理组间的路由和查询，使路由表长度得到大幅度减少，同时保持总跳数和平均路径长度基本保持一致
  • 但这种方法显然牺牲了 Chord 的简单稳定特性

XU K，SONG J，SONG M． A P2P lookup pr-otocol model［J］． Cluster Computing，2010，13( 11) :199-211

  • 提出一种新的思路改进 Chord 路由表项
  • 在减少路由表冗余，提高查询效率同时还保证了节点的加入、查找复杂度基本不变

结构化P2P资源搜索算法及其在未来光网络中的应用_吴帅勇.pdf

  • 名址分离架构的资源搜索设计
  • 英特网最初的设计思想上的根本缺陷，造成 IP 地址的语义过载问题，从而带来移动性、多宿主、安全性、路由可扩展性等一系列问题
  • 以 Chord 算法为例，分析在名址分离未来网架构中的资源搜索算法设计，名址分离架构将原来的网络层拆分为网络层和身份标识层

image.png

  • Chord 系统提供的 Chord 协议应用一致性哈希函数将关键字和节点分别分配给一个 m 位的标识符
  • 关键字和节点就有了相同的名字空间，使得关键字大致均匀分配到节点上
  • 从而获得一个负载均衡的环形结构
  • 应用一致哈希函数 SHA-1 获得节点和关键字哈希值
    • 关键字一一对应关键字标识符( key identifier)
    • 节点一一对应节点标识符( node identifier)
    • 两类标识符都是 m 位二进制整数
    • 其中【P2P】DHT搜索算法 - 图4，N是Chord 中节点的数量，有以下的关系式:

【P2P】DHT搜索算法 - 图5

  • Chord 环算法中关键字被分配到它的后继节点上，关键字的后继节点是节点标识等于或者大于该关键字的节点
  • 也就是说，如果在 Chord 系统中有节点标识与关键字相等的节点，那么该关键字就存储在这个节点上
  • 否则，关键字存储在节点标识大于该关键字的最小的节点上

  • 用 successor(K) 表示关键字 K 的后继节点，按照节点标识符由大到小顺时针方向形成一个环，这就是 Chord 环

  • 新方案中，取 IP 地址的哈希值的前 m/2 位作为前 m/2 位，智能终端的身份标识的哈希值的前 m/2 位作为后m/2 位，这样组合得到一个 m 位的标识值就是节点标识 NID;

  • 而资源的标识还是对资源的文件名哈希获得，把〈key，value〉按照 Chord协议的方法存放到相应节点，即

【P2P】DHT搜索算法 - 图6
image.png

  • 新方案不仅在新的网络架构中解决了移动性和多宿主问题，还充分利用了 Chord 算法的优点。
  • 之所以能解决移动性，是因为如上的方法中，
  • 节点 node identifier 前半部分随着终端 IP 的变化而变化，后半部分只要是同一个终端，就保持不变。
  • 这样，终端发生移动的情况下，节点 node identifier 也相应变化，但同时其中保存了终端的 ID 信息，故而整体能够代表终端的 ID 属性又能反映终端对应的位置。
  • 对于多宿主，也能够保证几个宿主位置信息相近同时节点 node identifier 不同，不会导致现有网络中多个智能终端共用一个 NID 的问题。

  • 另外，新方案中，value 不再是 IP 地址，而是文件存储位置所在的智能终端的 ID，因为 IP 有可能是变化着的，而 ID 能准确对应信息存放位置，且名址分离架构中，知道ID 就能知道相应的智能终端的地址

    CAN算法

  • CAN 由美国加州伯克利分校于 2001 年提出

  • 基于虚拟的 d 维笛卡尔坐标空间实现其数据组织和路由查找功能
  • 该虚拟坐标空间由该网路中的节点动态的划分，每个节点负责一块独立的不相交的区域
  • 查找时，先确定目标节点的坐标，接着节点便将查询请求转发给当前节点的邻居节点中坐标最接近目标节点的节点，直到得到正确的搜索结果为止

image.png

  • 与 Chord 不一样的是，CAN 实际上是一种序列查找，所以它的复杂度为【P2P】DHT搜索算法 - 图9
  • 这样一来 CAN的优点和缺点都很明显
  • 由于每个节点只需要维护每个维度空间中的几个邻居，其它节点加入和退出对它的影响都很小
  • 这个优点使得它很适合大规模的动态网络应用

  • 但是，正是因为如此，当节点数目很多时，CAN 的平均搜索复杂度也会很大

    Pastry算法

  • Pastry 由美国微软学院提出

  • 在 Pastry 协议中，所有节点构成一个环形拓扑结构
  • 每个节点加入Pastry 网络时，经过哈希函数的计算获得一个 128 位的唯一标识 (nodeID)
  • 所有标识均按照大小顺序顺时针构成一个环形的拓扑结构
  • 在 Pastry 中，每个节点拥有一个路由表 R( routing table) ，一个邻居节点集 M( neighborhood set) 和一个叶节点集 L( leaf set)

  • 如何及时、准确地对 R，M，L 中信息进行动态维护，保证路由查找的高效性，是 Pastry 算法面临的难题

    Tapestry算法

  • Tapestry 是美国加州大学伯克利分校提出的一种新型 P2P 网络定位和路由算法

  • 同 Pastry 算法一样，Tapestry 给每个节点都分配一个唯一的 nodeID，每个资源对象也从同样一个空间获得一个资源 ID，也即 key
  • Tapestry 中的空间称作 GUID
  • 每个节点都维护一张路由表，表中每个条目项都是一个能够让查找更靠近目标节点的条目
  • 这样，查询就能沿着路由条目最终到达目标节点
  • Tapestry 采用基于地址前缀的路由机制，按照从左到右顺序，每次只改变一个位数
  • 与 Pastry 有很多相似之处，最大区别在于资源分配方式不同