刘凯 张华

摘要：P2P（Peer-to-Peer）是现今广泛使用的一种网络模型，非结构化P2P模型和结构化P2P模型是其中两种基本拓扑结构。非结构化模型一般使用洪泛方法实现，结构化P2P网络一般使用分布式哈希表构建。该文在分析两种P2P网络的基础上，对比了结构化P2P模型和非结构化P2P模型中的典型案例的实现过程，并对其优缺点进行了总结。

关键词：P2P；洪泛；分布式哈希表

中图分类号：TP393文献标识码：A文章编号：1009-3044（2012）36-8631-03

1研究背景

二十一世纪以来，信息技术迅速发展，互联网上的信息量快速增长，根据Google公司的报道，到2005年，Google已经索引了80.6亿个页面和10亿以上的图片，如何有效管理这些信息是一个热点和难点问题。当前，互联网程序主要使用客户机/服务器（C/S）和浏览器/服务器（B/S）模式，这两种模式都以服务器为中心，由服务器负责存储资源和提供服务。但随着互联网的发展，两种模式中服务器的负载越来越重，服务器成了发展的瓶颈，同时应用程序对服务器依赖性较大，一旦服务器出现故障，整个系统都面临崩溃。

P2P的出现，使得消除服务器为中心的网络瓶颈成为了可能。最近几年，P2P计算已称为计算机中的热门话题之一。P2P网络是一种分布式的网络，它打破了传统的C/S和B/S模式，在网络中每个计算机的功能和地位都是对等的，每个计算机既为其他用户提供服务，也想用其他用户所提供的服务，在P2P中，所有的运算、存储等都分布在各个计算机上，这样就减少了对服务器的依赖，减轻了服务器的负载。

2P2P网络结构

P2P系统一般要构造一个拓扑结构，在这个结构中需要解决节点命名，出错恢复和数据查询等问题，现有的P2P网络结构有以下几种：

2.1混合型的P2P结构

这种结构并不是完全的分布式P2P，这种结构中仍然有服务器的存在，不过服务器的作用发生了改变，和传统的C/S相比，此时服务器仅祈祷促成各种节点协调和扩展的功能，一般这种服务器我们称为索引服务器。在这种结构下，资源并不存储在服务器上，而是存储在各个计算机上，这样一来可以大大降低服务器的负载压力，但是对服务器的依赖性依然存在。比如著名的MP3共享软件Napster就是使用混合型的P2P结构。

2.2纯分布式的P2P结构

纯分布式的P2P结构又分为非结构模型和结构化模型两种，其中非结构模型采用随机图的组织方式，各个计算机间的关系以及数据的放置方式没有严格的控制，才用洪返的方式来定位数据，该模型的主要优点是稳定性好，主要缺点是查询效率比较低；结构化模型中主要基于分布式哈希表来控制计算机的分布和数据的放置，该模型的优点是查询效率高，主要缺点是稳定性比较低。

3非结构化P2P模型

非结构化P2P模型采用了基于完全随机图的洪泛发现和随机转发机制。解决了网络结构中心化的问题，扩展性和容错性较好，但是它采用应用程广播的协议导致消息量过大，网络负担过重，无法得知整个网络的拓扑结构或组成网络的各计算机的身份，另外这类系统更容易受到垃圾信息甚至是病毒的恶意攻击，而且由于采用洪泛方法，查询的直径也不可控，查询效率比较低下。下面我们来看一种典型的使用非结构模型的软件，Gnutella。

4结构化P2P模型

非结构化P2P系统中存在着缺乏有效的可扩展的查找机制的问题。近年很多研究人员在设计可扩展的查找机制方面做了很多工作，重要成果就是分布式哈希表（DHT，DistributedHashTable），基于分布式哈希表的P2P是结构化的P2P。与一般的哈希表累死，分布式哈希表提供三个基本操作：插入，查找和删除，操作对象仍然是键值对，与传统哈希表不同的是，分布式哈希表的各项是分布在网络的各个计算机上，因此每个计算机都要具备这样的功能：给定一个键，消息必须能够被传递到保存该键的计算机上。典型的DHT协议有：Chord，CAN等。

Chord在2001年由麻省理工学院提出，其核心思想就是要解决在P2P应用中遇到的基本问题：如何在P2P网络中找到存有特定数据的节点。Chord实现了这样的一种操作：给定一个关键词Key，将其映射到某个计算机上。为此，Chord中使用了DHT为每个计算机和关键词产生了一个n位的标识，并按照标识大小形成环形结构。标识的长度n必须足够长，这样可以忽略不同计算机或关键词哈希结果相同的情况。在Chord中，每个关键词都保存在它的后继中，后继指的是计算机标示大于等于关键词标示的第一个计算机在Chord中，如果n表示关键词和计算机标识的位数（二进制），那么每个计算机需要存储n个其他计算机的信息，这些信息叫做查询表（FingerTable），或者叫做指针表，而且这些表格中存储的不再是直接相邻的计算机。在查询的时候，查询计算机将请求发送到与所查询关键词的标识最接近的计算机上。收到查询请求的计算机如果发现自身存储了被查询的关键词，可以直接回应查询计算机；如果被查询的关键词不在本地，就根据查询表将请求转发到与标识最接近的计算机上。这样的过程一直持续到找到相应的计算机为止。不难看出，查询过程实际上就是折半查找的过程。

5两种模型的对比

而在负载平衡方面，首先Gnutella中的计算机之间的关系是随机的，未考虑负载平衡，Chord中使用了相容哈希，可以在全网范围内实现负载平衡；在稳定性方面，Gnutella中的计算机的加入和退出只对邻近计算机有影响，所以计算机的加入退出对整个网络影响不大，所以其稳定性较高，Chord中计算机的加入退出时间复杂度较高，如果计算机频繁加入退出可能引起整个网络的瘫痪，所以其稳定性比较差；在可扩展性方面，Gnutella中计算机加入退出方面，但由于Gnutella使用洪泛的方式通信，大量的带宽占用使得一些带宽少性能差的计算机被孤立，导致网络可用性降低，因此Guntella的可扩展性一般，Chord中因为具有O（logN）的空间和时间复杂度，所以能够容纳大量的计算机，所以其可扩展性很好。

6小结

该文主要介绍了P2P的概念、特点和分类，其中重点介绍了纯分布式P2P中的两个典型：非结构化的Chord和结构化的Gnutella，并对比了两种模型的在时间复杂度、空间复杂度度、稳定性、可扩展性等方面的优缺点，扬长避短，以便于读者选择合适的P2P模型进行开发和使用。

参考文献：

[1]GallaugherJM，RamanathanSC.ChoosingaClient/ServerArchitecture[J].InformationSystemsManagement，1996，13（2）：7-13.

[2]ClayShirky.WhatisP2Pandwhatisn't[C].O'Reilly'sEmergingTechnologyConference，2002.

[3]Gnutella[EB/OL].Http：//www.Gnutella.com.

[4]PEER-TO-PEER.ORG[EB/OL].http：//www.peer-to-peer.org/.

[5]徐玉.P2P网络中资源搜索算法的研究[D].南京：南京邮电大学，2011.