结构化P2P网络的核心机制研究

2022-09-10

对等网络 (peer-to-peer network, 简称P 2 P网络) 是分布式系统与计算机网络相结合的产物, 是采用对等模式工作的计算机网络。在P 2 P网络中, 每个网络结点在行为上是自由的, 在功能上是平等的, 在连接上是互联的, 所有结点分布式地自组织成一个整体网络。因此, 它打破了传统的客户/服务器 (C/S) 模式, 克服了C/S模式中服务器的瓶颈, 极大程度地提高了网络效率。

1 P2P网络的三种形式

对于现有的各种P 2 P网络, 可以从设计思想出发, 兼顾体系结构和出现时间两个方面的考虑, 将其分成三代:

第一代, 混合式P 2 P网络, 它是C/S和P 2 P两种模式的混合。

第二代, 无结构P 2 P网络, 它以分布、松散的结构来组织网络, 故称“无结构”。

第三代, 结构化P 2 P网络, 它以准确、严格的结构来组织网络, 并能高效地定位结点和数据。最经典的结构化P 2 P网络有Chord、CAN、Tapestry、Pastry等。

其中, 结构化P 2 P网络因为其高效快速的资源定位方式成为P 2 P网络发展的方向。

2 结构化P2P网络核心机制分析

P 2 P网络是建立在层次化的网络结构上, 其核心机制是一个构建在底层物理网上的覆盖网, 所以第一个要考虑的就是覆盖网的拓扑结构。它对P 2 P网络本身的工作性能和其他方面的设计机制起着决定性的作用。具体说明如下。

(1) 覆盖网拓扑结构。

结构化P 2 P网络最大的特点即在于它们都有一个严格的覆盖网拓扑结构。结构化P 2 P网络的几种主要拓扑结构有带弦环、多维空间、超立方体、蝴蝶形、de Bruijn图、C C C及其他形状 (如跳表) 等。

(2) 分布式散列表。

分布式散列表 (D H T) 是P 2 P网络中的一个核心设施, 提供对于任何一个结点、数据对象在覆盖网中的位置映射。为了使这种映射唯一、均匀、随机, 分布式散列表都使用安全的一致性散列函数, 主要采用S H A-1 (安全散列算法) , 它能产生均匀、随机、与输入无关的1 6 0位散列值, 并且散列值冲突的概率极小。在P 2 P覆盖网上依靠D H T通常能准确、快速地路由消息和定位数据对象, 这正是P 2 P查询的优势所在。但是, 这里引入的模糊查询的困难的问题也急需解决。

(3) 路由和定位。

所谓“定位”, 是指确定位置的过程, P 2 P网络的定位都是通过一步一步的“路由”来完成的。路由和定位的方式通常取决于覆盖网拓扑结构和路由表结构。基于这两个因素, 结构化P 2 P网络通常都维护一个比较小的路由表 (可变度或者常数度) , 采用分布式、局部性的贪心路由算法, 逐步缩小当前结点与目的结点之间的I D差异, 通常定位效率为O (l o g N) 跳, 并且能保证定位成功, 单就覆盖网而言此定位效率接近最优。

在结构化P 2 P网络中, 主要的几种路由方法是:数值邻近路由、逐位匹配路由、位置邻近路由、层次路由和混合式路由等。

其中, 最典型的是数值邻近路由, 这里的“数值”通常指结点I D值。路由过程中每一步, 当前结点都在自己的路由表中选择与目的I D最邻近的结点作为下一跳, 因此, 路由路径中每一跳的结点I D与目的I D的差距会越来越小, 直至最接近目的I D的结点为止。C h o r d是最典型的数值邻近路由。

逐位匹配路由出自P l a x t o n, 其后继Tapestry、Pastry继承并扩展了它, 前者采用后缀匹配, 后者采用前缀匹配, 两者差异并不大。

C A N是最典型的位置邻近路由, 每个结点的路由表记录自己在多维空间中的邻居, 每次选择离目的结点最近的邻居作为下一跳, 其定位效率等价于多维空间的直径。

V i c e r o y采用了蝴蝶网层次路由, 路由过程常常是先从低层爬到高层, 再从高层爬到底层。

Cycloid是一个典型的混合式路由的例子, 它使用了类似P a s t r y的超立方体路由 (属于逐位匹配路由) , 又结合了两种环形路由:一是主环上的环形路由, 二是每个小环上的环形路由。

(4) 动态结点算法。

P 2 P网络的最大特点和难点, 在于它极大的动态性:不断地有新结点加入、旧结点离开、结点失效等情况发生。面对这样一个动态环境, P 2 P网络需要一套健全、可行的方法来处理各种动态问题, 在新结点加入时通知其他结点新成员的到来, 在旧结点离开时通知其他结点老成员的离去, 而最难的是需要高效、合理地检测到结点失效并及时修复P 2 P网络。对于这三者的处理, 我们统称其为“动态结点算法”。

新结点的加入和旧结点的离开都比较简单, 因为它们是主动发生并且通知他人的, 而结点失效则不同, 它是被动发生、不可预料的。通常情况下, 处理失效的第一步是检测失效。目前比较实用的方法是周期性地联系路由表中的邻居, 看是否可达, 如果不可达, 再进行第二步路由表修复。对结点失效的处理是结构化P 2 P网络最大的开销所在。

(5) 容错性和安全性。

为了实现高效的路由, P 2 P网络中每个结点会保存一个路由表和其他辅助性的信息, 记录它的网络邻居、远程指针等, 这些信息称作“结点状态”, 它在结点加入网络时被初始化。但是, 由于网络环境的动态性, 网络结点不断地加入、离开、失效, 数据对象也被不断地插入、删除和废弃, 结点状态变得陈旧、与实际网络不一致, 这种不一致会影响到网络工作的效率和正确性, 需要进行容错处理。最典型的容错机制是冗余方法和周期性检测:前者通过保存适当的冗余信息, 提供有效的代替, 以空间换取容错;后者通过每个结点的周期性检测来及时纠正错误, 以时间换取容错。

结构化P 2 P网络的安全性是一个很复杂的问题。现有的系统通常利用散列方法来保证数据的完整性, 从而实现了某个方面的安全机制, 但这些通常是不够的, 并不能达到完全的安全、匿名。

3 结语

P 2 P网络是建立在层次化的网络结构上, 其核心机制是在应用层建立逻辑上的覆盖网络, 并且在P 2 P覆盖网上依靠分布式散列表进行准确、快速地路由消息和定位数据对象。本文系统的探讨了结构化P 2 P网络的核心机制, 并重点讨论了路由与定位的方法。可以预见结构化P 2 P网络在未来的发展道路上会进行得更好。

摘要：P2P技术强烈的冲击着传统的媒体、电信和互联网等众多行业, 它将成为下一代互联网的核心技术和最显著的特征之一。本文分析了P2P网络的特点及三种形式, 同时对结构化P2P网络的几种核心机制进行了初步研究。

关键词：结构化P2P网络,路由和定位,动态结点算法