浅析P2P系统的拓扑

宋静静

摘 要：Napster、Gnutella和Freenet等P2P系统的初始设计存在显著的可扩展性问题。近年来，一些研究小组独立地提出了新一代的感知拓扑P2P系统，以支持可扩展的路由和位置方案。随着P2P体系结构的流行和越来越多的系统引入，我们认为有必要提出一个抽象的、通用的拓扑模型来捕捉P2P体系结构的本质。这种模式应该有助于为更新颖的P2P系统开发新的设计空间。

关键词：P2P系统;覆盖网络;路由;定位算法

一、引言

互联网的普及使得一个通用的存储空间成为可能，它分布在互联网上参与的终端计算机（对等机）上。所有对等方都具有相同的角色，并且空间中没有集中式服务器。这种体系结构被统称为对等（P2P）系統。尽管P2P系统仅仅在几年前才被引入，但它现在已经成为最流行的互联网应用之一，并成为互联网流量的主要来源。它们的快速和广泛的预部署表明P2P系统有其优势。P2P文件共享可能会为软件分发、分布式文件系统、搜索网络和静态Web内容交付等应用带来新的内容分发模型，P2P系统最突出的初始设计包括Napster[1]、Gnutella[2]和freenet[3]。不幸的是，它们都有明显的缩放问题。例如，在Napster中心服务器存储Napster用户社区中所有可用文件的索引。要检索文件，用户使用所需文件的已知名称查询此中心服务器，并获取存储所需文件的用户计算机的IP地址。

一个可扩展的P2P文件分发系统可以做吗？已经认识到，任何对等系统的中心是用于将文件名映射到系统中的位置的索引方案。也就是说，P2P文件传输过程本质上是可扩展的，但最困难的部分是从谁到谁中找到对等方来检索文件。因此，一个可扩展的P2P系统至少需要一个查找索引机制。针对这些可扩展性问题，出现了支持可扩展路由和定位方案的第二代P2P系统。与前面的系统不同，它们保证在有限数量的网络跳数中对查询作出明确的回答，同时保持有限的路由信息量，其中包括Tapestry、Pastry、Chord和CAN。

通过进一步的研究，我们发现所有这些新一代P2P系统都有一个共同的特点，即节点在应用层上连接成一个有规则的网络，例如一个环、一个网格或一个通常被称为覆盖网络的超立方体。随着P2P体系结构的日益流行和系统的不断引入，我们认为需要一个抽象的、通用的拓扑模型来捕捉P2P体系结构的本质。这种模式应该反过来促进新的P2P系统设计空间的开发。

二、拓扑模型

在开发抽象模型时，我们做了两个观察。首先，在任何P2P系统中，我们可以看到有多个节点分布在整个互联网上，并将其部分本地存储贡献给全局存储空间。因特网可以被模拟成一个物理上连接这些节点的通用互连网络。其次，我们注意到P2P系统中节点的主要功能除了存储和缓存数据外，还包括消息路由和数据定位。路由功能在源节点和目标节点之间路由给定的请求/回复消息。数据定位试图在路由表的帮助下找到数据项的位置或主节点。所有对等节点都以某种规则的方式以逻辑方式连接为一个覆盖网络，从而显著地导出路由表大小和路由路径。在这样的系统中，路由表的条目（例如邻居的IP地址）充当到其他相邻节点的逻辑链路，因此被视为覆盖网络的边缘。

覆盖网络的复杂性常常决定了可以构建的P2P系统的大小。同样，P2P系统的可达到性能最终受到覆盖网络特性的限制。显然，选择覆盖网络是P2P系统设计的第一步，也是最关键的一步。

在我们定义并描述了以下术语之后，各组成部分将变得清晰：

数据ID和密钥空间：为每个文件或数据分配一个密钥或全局唯一标识，该标识对应于文件的文本名、所有者的公钥/随机的加密散列。注意，有序密钥空间是覆盖网络的第一个必要特性。

节点ID：节点的标识符与文件的密钥空间相同。它可以被计算为节点IP地址或公钥的加密散列。

数据放置：数据ID和节点ID属于同一空间。理想情况下，数据存储在与数据ID具有相同ID的节点上，但活动节点或对等节点的数量通常比数据的数量少很多。每个节点负责在密钥空间中存储一定范围的密钥。数据存储在最近的节点上，最近的ID为节点ID。

分布式哈希表：所有数据或节点通过哈希映射到同一个密钥空间中的一个点。Hash的功能应该保证密钥空间内数据或节点的均匀随机分布。

覆盖网络：所有的活动对等节点通过路由表在应用层进行逻辑连接，每个路由表条目包含一个邻居的IP地址，由于所有活动节点上的数据联合应该覆盖整个密钥空间，因此逻辑连接的网络称为覆盖网络。任何传统的互连网络，如环网、网格网和超立方体，都不能直接用作覆盖网络。

路由表：每个节点维护由系统中的一小部分节点组成的路由表。由于所有对等节点都以某种规则的拓扑结构连接，因此路由表可以显著缩小。路由表的大小（或条目数）相当于覆盖网络的传出程度。它是覆盖网络的空间复杂度。

基本操作：一个基本操作是查找（key），它返回存储该密钥的节点的标识（例如IP地址）。此操作允许节点根据其密钥放置和获取数据。

路由和定位算法：当发出或接收到查找（密钥）时，查找将通过覆盖网络路由到负责该密钥的主节点。每个跃点在解决查找方面都取得了最大的进展。不同算法的进程标记不同，但是任何路由算法都应该在每个跳的意义上收敛，使得当前节点ID和主节点ID之间的距离越来越小。注意，收敛路由算法是覆盖网络的第二个必要特征。

路由表大小：由于所有对等节点都以某种规则的拓扑结构连接，因此路由表可以显著减少。路由表的大小（或条目数）由规则网络的程度决定。它是覆盖网络的空间复杂度。

路径长度：是覆盖网络中消息需要经过的跃点数。它是覆盖网络的时间复杂度。

邻近性：实际距离性能不仅取决于路径长度，还取决于网络中每个跳的通信延迟。虽然互联网是完全自治的，但进一步的调查表明，互联网仍然具有一定的规律性。如果P2P系统的支持网络被限制在一个区域或校园范围内，这种规律性就更加明显。

容错性：首先，根据路由算法，如果下一个节点当前未加入网络，则应将路由消息发送到路由表中更新的另一个节点;其次，如果节点在没有通知的情况下突然崩溃，则活节点应能够检测并更新路由表。

自组织：为了使P2P系统完全分布式，当一个节点加入或离开系统时，路由表应该自动重新配置。节点可能由于崩溃而突然离开，或者通过通知邻居并提交密钥而优雅地离开，前一种情况通常称为节点失败。在这种情况下，节点应该有方法检测节点加入或节点离开以重新配置其路由表状态。在一些节点离开后，剩余的活动节点根据拓扑连接模式自组织。注意，自组织是覆盖网络的第三个必要特性。

数据可用性：存储同一数据的多个副本，以提高查找效率和容错性。当请求的数据发送到请求者时，它们通常沿着从目标到源的反向路径存储。

可扩展性：一般来说，P2P是可扩展的，前提是可以在不明显降低性能的情况下增加对等点的数量。目前，它主要是通过空间时间复杂度来评估的，即路由表大小乘以路径长度。显然，可扩展性并不是一个标准。实际上，它是由上面讨论的几乎每一个方面所决定的总体评估。例如，为了提高可扩展性，路由和自组织都应该只使用本地信息。

上述标准并非详尽无遗，而是与拓扑相关，其中包括一致哈希、智能代理、分布式数据结构、查询合成、安全性、匿名性和与拓扑无关的社会计量学。我们对拓扑分析的关注并不意味着这些其他问题是次要的。

三、总结

P2P系统最大的特点就是用户之间直接共享资源，其核心技术就是分布式对象的定位机制，这也是提高网络可扩展性、解决网络带宽被吞噬的关键所在。迄今为止，P2P网络已经历了不同网络模型，各种模型各有优缺点，有点还存在着本身难以克服的缺陷。因此在目前P2P技术还远未成熟的阶段，各种网络结构依然能够共存，甚至呈现相互借鉴的形式。

在结构化P2P系统中，每个节点只存储特定的信息或特定信息的索引。当用户需要在P2P系统中获取信息时，它们必须知道这些信息可能存在哪些节点中。由于用户预先知道应该搜索哪些节点，这就避免了非结构化P2P系统中使用的泛洪式查找，因此提高了信息搜索的效率。