P2P网络的拓扑结构

拓扑结构是指分布式系统中各个计算单元之间的物理或逻辑的互联关系，结点之间的拓扑结构一直是确定系统类型的重要依据。目前互联网络中广泛使用集中式、层次式等拓扑结构。Internet本身是世界上最大的非集中式的互联网络，但是九十年代所建立的一些网络应用系统却是完全的集中式的系统，许多Web应用都是运行在集中式的服务器系统上。集中式拓扑结构系统目前面临着过量存储负载、DOS（Denial of Service，拒绝服务）攻击，网络带宽限制等一些难以解决的问题。Peer-to-Peer (简称P2P) 系统主要采用非集中式的拓扑结构，一般来说不存在上述这些难题。根据结构关系可以将P2P系统细分为四种拓扑形式：

• 中心化拓扑（Centralized Topology）；
• 全分布式非结构化拓扑（Decentralized Unstructured Topology）；
• 全分布式结构化拓扑（Decentralized Structured Topology，也称作DHT网络）；
• 半分布式拓扑（Partially Decentralized Topology）。

其中，中心化拓扑最大的优点是维护简单，资源发现效率高。由于资源的发现依赖中心化的目录系统，发现算法灵活高效并能够实现复杂查询。最大的问题与传统客户机/服务器结构类似，容易造成单点故障，访问的“热点”现象和版权纠纷等相关问题，这是第一代P2P网络采用的结构模式，经典案例就是著名的MP3共享软件Napster[1].

Napster是最早出现的P2P系统之一，并在短期内迅速成长起来。它实质上并非是纯粹的P2P系统，而是通过一个中央索引服务器保存所有Napster用户上传的音乐文件索引和存放位置的信息。它的工作原理如图1所示。当某个用户需要某个音乐文件时，首先连接到Napster中央索引服务器，在服务器上进行检索，服务器返回存有该文件的用户信息，再由请求者直接连到文件的所有者传输文件。Napster首先实现了文件查询与文件传输的分离，有效地节省了中央服务器的带宽消耗，减少了系统的文件传输延时。

图1 Napster的拓扑结构

然而，这种对等网络模型存在以下这些问题：

• 中央索引服务器的瘫痪容易导致整个网络的崩溃，因此可靠性和安全性较低。
• 随着网络规模的扩大，对中央索引服务器进行维护和更新的费用将急剧增加，所需成本较高。
• 中央索引服务器的存在常引起版权问题上的纠纷，服务提供商容易被追究法律责任。

综合上述优缺点，对小型网络而言，中心化拓扑模型在管理和控制方面占一定优势。但鉴于其存在的上述缺陷，该模型并不适合大型网络应用。

全分布式非结构化拓扑的P2P网络是在重叠网络（Overlay Network）(见标注1)采用了随机图的组织方式，结点度数服从Power-law规律（幂次法则）[2]，从而能够较快发现目的结点，面对网络的动态变化体现了较好的容错能力，因此具有较好的可用性。同时可以支持复杂查询，如带有规则表达式的多关键词查询，模糊查询等，采用这种拓扑结构最典型的案例便是Gnutella（音译：纽特拉）。准确地说，Gnutella不是特指某一款软件，而是指遵守Gnutella协议[3]的网络以及客户端软件的统称。目前基于Gnutella网络的客户端软件非常多，著名的有Shareaza、LimeWire和BearShare等。

图2Gnutella的拓扑结构和文件检索方法

Gnutella和Napster最大的区别在于Gnutella是更加纯粹的P2P系统，因为它没有中央索引服务器，每台机器在Gnutella网络中是真正的对等关系，既是客户机同时又是服务器，所以被称为对等机(Servent，Server+Client的组合)。在文件检索方面，它与Napster也不相同。在Gnutella网络的发展初期，它主要采用基于完全随机图的Flooding搜索算法。图2 显示了Flooding的工作流程：当一台计算机要下载一个文件，它首先以文件名或者关键字生成一个查询，并把这个查询发送给与它相连的所有计算机，这些计算机如果存在这个文件，则与查询的机器建立连接，如果不存在这个文件，则继续在自己相邻的计算机之间转发这个查询，直到找到文件为止。为了控制搜索消息不至于永远这样传递下去，一般通过TTL (Time To Live)的减值来控制查询的深度。

但是，随着联网节点的不断增多，网络规模不断扩大，通过这种Flooding方式定位对等点的方法将造成网络流量急剧增加，从而导致网络中部分低带宽节点因网络资源过载而失效。所以在初期的Gnutella网络中，存在比较严重的分区，断链现象。也就是说，一个查询访问只能在网络的很小一部分进行，因此网络的可扩展性不好。所以，后来许多研究人员在Flooding的基础上作了许多改进，例如采用Random work [4]、Dynamic Query[5]等方法。

由于非结构化网络将重叠网络认为是一个完全随机图，结点之间的链路没有遵循某些预先定义的拓扑来构建。这些系统一般不提供性能保证，但容错性好，支持复杂的查询，并受结点频繁加入和退出系统的影响小。但是查询的结果可能不完全，查询速度较慢，采用Flooding查询的系统对网络带宽的消耗非常大，并由此带来可扩展性差等问题。

全分布式结构化拓扑的P2P网络主要是采用分布式散列表（Distributed Hash Table, 简写成DHT）技术来组织网络中的结点。DHT是一个由广域范围大量结点共同维护的巨大散列表。散列表被分割成不连续的块，每个结点被分配给一个属于自己的散列块，并成为这个散列块的管理者。通过加密散列函数，一个对象的名字或关键词被映射为128位或160位的散列值。分布式散列表起源于SDDS（Scalable Distribute Data Structures）[6]研究，Gribble等实现了一个高度可扩展，容错的SDDS集群。DHT类结构能够自适应结点的动态加入/退出，有着良好的可扩展性、鲁棒性、结点ID分配的均匀性和自组织能力。由于重叠网络采用了确定性拓扑结构，DHT可以提供精确的发现。只要目的结点存在于网络中DHT总能发现它，发现的准确性得到了保证，最经典的案例是Tapestry，Pastry，Chord和CAN。

Tapestry [7]提供了一个分布式容错查找和路由基础平台，在此平台基础之上，可以开发各种P2P应用(OceanStore[8]即是此平台上的一个应用)。Tapestry的思想来源于Plaxton。在Plaxton中，结点使用自己所知道的邻近结点表，按照目的ID来逐步传递消息。Tapestry基于Plaxton的思想，加入了容错机制，从而可适应P2P的动态变化的特点。OceanStore是以Tapestry为路由和查找基础设施的P2P平台。它是一个适合于全球数据存储的P2P应用系统。任何用户均可以加入OceanStore系统，或者共享自己的存储空间，或者使用该系统中的资源。通过使用复制和缓存技术，OceanStore可提高查找的效率。最近，Tapestry为适应P2P网络的动态特性，作了很多改进，增加了额外的机制实现了网络的软状态（soft state），并提供了自组织、鲁棒性、可扩展性和动态适应性，当网络高负载且有失效结点时候性能有限降低，消除了对全局信息的依赖、根结点易失效和弹性差的问题。

Pastry 是微软研究院提出的可扩展的分布式对象定位和路由协议，可用于构建大规模的P2P系统。如图3 所示，在Pastry中，每个结点分配一个128位的结点标识符号(nodeID) ，所有的结点标识符形成了一个环形的nodeID空间，范围从0到2128 - 1 ，结点加入系统时通过散列结点IP地址在128位nodeID空间中随机分配。网络结点的加入与退出，资源查询的过程可以参考文献[9]。

图3Pastry的消息路由

Chord [10]项目诞生于美国的麻省理工学院。它的目标是提供一个适合于P2P环境的分布式资源发现服务，它通过使用DHT技术使得发现指定对象只需要维护O(logN)长度的路由表。在DHT技术中，网络结点按照一定的方式分配一个唯一结点标识符(Node ID) ，资源对象通过散列运算产生一个唯一的资源标识符(Object ID) ，且该资源将存储在结点ID与之相等或者相近的结点上。需要查找该资源时，采用同样的方法可定位到存储该资源的结点。因此，Chord的主要贡献是提出了一个分布式查找协议，该协议可将指定的关键字(Key) 映射到对应的结点(Node) 。从算法来看，Chord是相容散列算法的变体。

图4 Chord的拓扑形状

CAN(Content Addressable Networks)[11] 项目采用多维的标识符空间来实现分布式散列算法。CAN将所有结点映射到一个n维的笛卡尔空间中，并为每个结点尽可能均匀的分配一块区域。CAN采用的散列函数通过对(key, value) 对中的key进行散列运算，得到笛卡尔空间中的一个点，并将(key, value) 对存储在拥有该点所在区域的结点内。CAN采用的路由算法相当直接和简单，知道目标点的坐标后，就将请求传给当前结点四邻中坐标最接近目标点的结点。CAN是一个具有良好可扩展性的系统，给定N个结点，系统维数为d，则路由路径长度为O(n1/d) ，每结点维护的路由表信息和网络规模无关为O(d) 。

上述四种基于DHT的P2P系统的性能比较可以参照[12]。DHT这类结构最大的问题是DHT的维护机制较为复杂，尤其是结点频繁加入退出造成的网络波动（Churn）会极大增加DHT的维护代价。DHT所面临的另外一个问题是DHT仅支持精确关键词匹配查询，无法支持内容/语义等复杂查询。

半分布式拓扑结构（有的文献亦称作混杂模式，英文表达为Hybrid Structure）吸取了中心化结构和全分布式非结构化拓扑的优点，选择性能较高（处理、存储、带宽等方面性能）的结点作为超级结点（英文表达为SuperNodes或者Hubs），在各个超级结点上存储了系统中其他部分结点的信息，发现算法仅在超级结点之间转发，超级结点再将查询请求转发给适当的叶子结点。半分布式结构也是一个层次式结构，超级结点之间构成一个高速转发层，超级结点和所负责的普通结点构成若干层次。采用这种结构的最典型的案例就是KaZaa。

图5 半分布式拓扑结构（网络中包含Super Node）

KaZaa是当前世界最流行的几款P2P文件共享软件之一。根据CA公司统计，全球KaZaa的下载量超过2.5亿次。使用KaZaa软件进行文件传输消耗了互联网40%的带宽。之所以它如此的成功，是因为它结合了Napster和Gnutella共同的优点。从结构上来说，它使用了Gnutella的全分布式的结构，这样可以是系统更好的扩展，因为它无需中央索引服务器存储文件名，它是自动的把性能好的机器成为SuperNode，它存储着离它最近的叶子节点的文件信息，这些SuperNode,再连通起来形成一个Overlay Network. 由于SuperNode的索引功能，使搜索效率大大提高。

图6 KaZaa的软件界面

半分布式结构的优点是性能、可扩展性较好，较容易管理，但对超级点依赖性大，易于受到攻击，容错性也受到影响。

在实际应用中，每种拓扑结构的P2P网络都有其优缺点，下表从可扩展性、可靠性、可维护性、发现算法的效率、复杂查询等方面比较了这四种拓扑结构的综合性能。

比较标准／拓扑结构	中心化拓扑	全分布式非结构化拓扑	全分布式结构化拓扑	半分布式拓扑
可扩展性	差	差	好	中
可靠性	差	好	好	中
可维护性	最好	最好	好	中
发现算法效率	最高	中	高	中
复杂查询	支持	支持	不支持	支持

我还是比较看好chord...虽然目前还有不少问题没有解决....
顺便附上一篇经典的chord论文: Chord: A Scalable Peertopeer Lookup Service for Internet Applications
http://www.blogjava.net/Files/heiyuchuanxia/chord_sigcomm.rar