再谈P2P技术：网络拓扑结构、核心技术分析

随着P2P应用的蓬勃发展，作为P2P应用中核心问题的发现技术除了遵循技术本身的逻辑以外，也受到某些技术的发展趋势、需求趋势的深刻影响。　

P2P协议概述

P2P打破了传统的Client/Server (C/S)模式，在网络中的每个结点的地位都是对等的。每个结点既充当服务器，为其他结点提供服务，同时也享用其他结点提供的服务。P2P与C/S模式的对比如下图所示:

P2P技术的特点体现在以下几个方面：

• 非中心化（Decentralization）：网络中的资源和服务分散在所有结点上，信息的传输和服务的实现都直接在结点之间进行，可以无需中间环节和服务器的介入，避免了可能的瓶颈。P2P的非中心化基本特点，带来了其在可扩展性、健壮性等方面的优势。

• 可扩展性：在P2P网络中，随着用户的加入，不仅服务的需求增加了，系统整体的资源和服务能力也在同步地扩充，始终能较容易地满足用户的需要。整个体系是全分布的，不存在瓶颈。理论上其可扩展性几乎可以认为是无限的。

• 健壮性：P2P架构天生具有耐攻击、高容错的优点。由于服务是分散在各个结点之间进行的，部分结点或网络遭到破坏对其它部分的影响很小。P2P网络一般在部分结点失效时能够自动调整整体拓扑，保持其它结点的连通性。P2P网络通常都是以自组织的方式建立起来的，并允许结点自由地加入和离开。P2P网络还能够根据网络带宽、结点数、负载等变化不断地做自适应式的调整。

• 高性能/价格比：性能优势是P2P被广泛关注的一个重要原因。随着硬件技术的发展，个人计算机的计算和存储能力以及网络带宽等性能依照摩尔定理高速增长。采用P2P架构可以有效地利用互联网中散布的大量普通结点，将计算任务或存储资料分布到所有结点上。利用其中闲置的计算能力或存储空间，达到高性能计算和海量存储的目的。通过利用网络中的大量空闲资源，可以用更低的成本提供更高的计算和存储能力。

• 隐私保护: 在P2P网络中，由于信息的传输分散在各节点之间进行而无需经过某个集中环节，用户的隐私信息被窃听和泄漏的可能性大大缩小。此外，目前解决 Internet隐私问题主要采用中继转发的技术方法，从而将通信的参与者隐藏在众多的网络实体之中。在传统的一些匿名通信系统中，实现这一机制依赖于某些中继服务器节点。而在P2P中，所有参与者都可以提供中继转发的功能，因而大大提高了匿名通讯的灵活性和可靠性，能够为用户提供更好的隐私保护。

• 负载均衡: P2P 网络环境下由于每个节点既是服务器又是客户机，减少了对传统C/S结构服务器计算能力、存储能力的要求，同时因为资源分布在多个节点，更好的实现了整个网络的负载均衡。

根据具体应用不同，可以把P2P分为以下这些类型：

• 提供文件和其它内容共享的P2P网络，例如Napster、Gnutella、eDonkey、emule、BitTorrent等；

• 挖掘P2P对等计算能力和存储共享能力，例如SETI@home 、Avaki、Popular Power等；

• 基于P2P方式的协同处理与服务共享平台，例如JXTA、Magi、Groove、.NET My Service等；

• 即时通讯交流，包括ICQ、OICQ、Yahoo Messenger等；

• 安全的P2P通讯与信息共享，例如Skype、Crowds、Onion Routing等。

P2P网络中的拓扑结构研究

拓扑结构是指分布式系统中各个计算单元之间的物理或逻辑的互联关系，结点之间的拓扑结构一直是确定系统类型的重要依据。目前互联网络中广泛使用集中式、层次式等拓扑结构，Interne本身是世界上最大的非集中式的互联网络，但是九十年代所建立的一些网络应用系统却是完全的集中式的系统、很多Web应用都是运行在集中式的服务器系统上。集中式拓扑结构系统目前面临着过量存储负载、Dos攻击等一些难以解决的问题。

P2P系统一般要构造一个非集中式的拓扑结构，在构造过程中需要解决系统中所包含的大量结点如何命名、组织以及确定结点的加入/离开方式、出错恢复等问题。

根据拓扑结构的关系可以将P2P研究分为4种形式：

• 中心化拓扑（Centralized Topology）

• 全分布式非结构化拓扑（Decentralized Unstructured Topology）

• 全分布式结构化拓扑（Decentralized Structured Topology，也称作DHT网络）

• 半分布式拓扑（Partially Decentralized Topology）

中心化拓扑

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

Napster实质上并非是纯粹的P2P系统，它通过一个中央服务器保存所有Napster用户上传的音乐文件索引和存放位置的信息。当某个用户需要某个音乐文件时，首先连接到Napster服务器，在服务器进行检索，并由服务器返回存有该文件的用户信息；再由请求者直接连到文件的所有者传输文件。

Napster首先实现了文件查询与文件传输的分离，有效地节省了中央服务器的带宽消耗，减少了系统的文件传输延时。这种方式最大的隐患在中央服务器上，如果该服务器失效，整个系统都会瘫痪。当用户数量增加到105或者更高时，Napster的系统性能会大大下降。另一个问题在于安全性上，Napster并没有提供有效的安全机制。

在Napster 模型中，一群高性能的中央服务器保存着网络中所有活动对等计算机共享资源的目录信息。当需要查询某个文件时，对等机会向一台中央服务器发出文件查询请求。中央服务器进行相应的检索和查询后，会返回符合查询要求的对等机地址信息列表。查询发起对等机接收到应答后，会根据网络流量和延迟等信息进行选择，和合适的对等机建立连接，并开始文件传输。Napster的工作原理如图1所示。

这种对等网络模型存在很多问题，主要表现为：

• 中央服务器的瘫痪容易导致整个网络的崩馈，可靠性和安全性较低。

• 随着网络规模的扩大，对中央索引服务器进行维护和更新的费用将急剧增加，所需成本过高。

• 中央服务器的存在引起共享资源在版权问题上的纠纷，并因此被攻击为非纯粹意义上的P2P网络模型。对小型网络而言，集中目录式模型在管理和控制方面占一定优势。但鉴于其存在的种种缺陷，该模型并不适合大型网络应用。

全分布非结构化网络

全分布非结构化网络在重叠网络（overlay）采用了随机图的组织方式，结点度数服从”Power-law”[a][b]规律，从而能够较快发现目的结点，面对网络的动态变化体现了较好的容错能力，因此具有较好的可用性。同时可以支持复杂查询，如带有规则表达式的多关键词查询，模糊查询等，最典型的案例是Gnutella。

Gnutella是一个P2P文件共享系统，它和Napster最大的区别在于Gnutella是纯粹的P2P系统，没有索引服务器，它采用了基于完全随机图的洪泛（Flooding）发现和随机转发（Random Walker）机制。为了控制搜索消息的传输，通过TTL (Time To Live)的减值来实现。具体协议参照［Gnutella协议中文版］

在Gnutella分布式对等网络模型N中，每一个联网计算机在功能上都是对等的，既是客户机同时又是服务器，所以被称为对等机(Servent，Server+Client的组合)。

随着联网节点的不断增多，网络规模不断扩大，通过这种洪泛方式定位对等点的方法将造成网络流量急剧增加，从而导致网络中部分低带宽节点因网络资源过载而失效。所以在初期的Gnutella网络中，存在比较严重的分区，断链现象。也就是说，一个查询访问只能在网络的很小一部分进行，因此网络的可扩展性不好。所以，解决Gnutella网络的可扩展性对该网络的进一步发展至关重要。

由于没有确定拓扑结构的支持，非结构化网络无法保证资源发现的效率。即使需要查找的目的结点存在发现也有可能失败。由于采用TTL（Time-to-Live）、洪泛（Flooding）、随机漫步或有选择转发算法，因此直径不可控，可扩展性较差。

因此发现的准确性和可扩展性是非结构化网络面临的两个重要问题。目前对此类结构的研究主要集中于改进发现算法和复制策略以提高发现的准确率和性能。

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

另外，由于非结构化系统中的随机搜索造成的不可扩展性，大量的研究集中在如何构造一个高度结构化的系统。目前研究的重点放在了如何有效地查找信息上，最新的成果都是基于DHT的分布式发现和路由算法。这些算法都避免了类似Napster的中央服务器，也不是像Gnutella那样基于广播进行查找，而是通过分布式散列函数，将输入的关键字惟一映射到某个结点上，然后通过某些路由算法同该结点建立连接。

最新的研究成果体现在采用分布式散列表（DHT）[a]的完全分布式结构化拓扑网络。

分布式散列表（DHT）

DHT分布式散列表实际上是一个由广域范围大量结点共同维护的巨大散列表。散列表被分割成不连续的块，每个结点被分配给一个属于自己的散列块，并成为这个散列块的管理者。DHT的结点既是动态的结点数量也是巨大的，因此非中心化和原子自组织成为两个设计的重要目标。通过加密散列函数，一个对象的名字或关键词被映射为128位或160位的散列值。一个采用DHT的系统内所有结点被映射到一个空间，如果散列函数映射一个位的名字到一个散列值，则有。

分布式散列表起源于SDDS（Scalable Distribute Data Structures）[a]研究，Gribble等实现了一个高度可扩展，容错的SDDS集群。

最近的研究集中在采用新的拓扑图构建重叠路由网络，以减少路由表容量和路由延时。这些新的拓扑关系的基本原理是在DHT表一维空间的基础上引入更多的拓扑结构图来反映底层网络的结构。

DHT类结构能够自适应结点的动态加入/退出，有着良好的可扩展性、鲁棒性、结点ID分配的均匀性和自组织能力。由于重叠网络采用了确定性拓扑结构，DHT可以提供精确的发现。只要目的结点存在于网络中DHT总能发现它，发现的准确性得到了保证，最经典的案例是Tapestry，Chord,CAN,和Pastry。

Tapestry提供了一个分布式容错查找和路由基础平台，在此平台基础之上，可以开发各种P2P应用(OceanStore即是此平台上的一个应用) 。Tapestry的思想来源于Plaxton。在Plaxton中，结点使用自己所知道的邻近结点表，按照目的ID来逐步传递消息。Tapestry基于Plaxtion的思想，加入了容错机制，从而可适应P2P的动态变化的特点。

在DHT技术中，网络结点按照一定的方式分配一个唯一结点标识符(Node ID) ，资源对象通过散列运算产生一个唯一的资源标识符(Object ID) ，且该资源将存储在结点ID与之相等或者相近的结点上。需要查找该资源时，采用同样的方法可定位到存储该资源的结点。因此，Chord的主要贡献是提出了一个分布式查找协议，该协议可将指定的关键字(Key) 映射到对应的结点(Node) 。从算法来看，Chord是相容散列算法的变体。MIT的GRID和RON项目则提出了在分布式广域网中实施查找资源的系统框架。

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

DHT类结构最大的问题是DHT的维护机制较为复杂，尤其是结点频繁加入退出造成的网络波动（Churn）会极大增加DHT的维护代价。DHT所面临的另外一个问题是DHT仅支持精确关键词匹配查询，无法支持内容/语义等复杂查询。

半分布式结构

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

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

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

P2P中的核心技术

度数和直径的折衷关系（tradeoff）对发现算法的影响

DHT发现技术完全建立在确定性拓扑结构的基础上，从而表现出对网络中路由的指导性和网络中结点与数据管理的较强控制力。但是，对确定性结构的认识又限制了发现算法效率的提升。研究分析了目前基于DHT的发现算法，发现衡量发现算法的两个重要参数度数（表示邻居关系数、路由表的容量）和链路长度（发现算法的平均路径长度）之间存在渐进曲线的关系。

研究者采用图论中度数(Degree)和直径(Diameter)两个参数研究DHT发现算法，发现这些DHT发现算法在度数和直径之间存在渐进曲线关系，如下图所示。在N个结点网络中，图中直观显示出当度数为N时，发现算法的直径为O(1)；当每个结点仅维护一个邻居时，发现算法的直径为O(N)。这是度数和直径关系的2种极端情况。同时，研究以图论的理论分析了O(d)的度和O(d)的直径的算法是不可能的。

从渐进曲线关系可以看出，如果想获得更短的路径长度，必然导致度数的增加；而网络实际连接状态的变化造成大度数邻居关系的维护复杂程度增加。另外，研究者证明O(logN)甚至O(logN/loglogN)的平均路径长度也不能满足状态变化剧烈的网络应用的需求。新的发现算法受到这种折衷关系制约的根本原因在于DHT对网络拓扑结构的确定性认识。

Small world 理论对P2P发现技术的影响

Small-world模型的特性：网络拓扑具有高聚集度和短链的特性。在符合small world特性的网络模型中，可以根据结点的聚集度将结点划分为若干簇(Cluster)，在每个簇中至少存在一个度最高的结点为中心结点。大量研究证明了以Gnutella为代表的P2P网络符合small world特征，也就是网络中存在大量高连通结点，部分结点之间存在“短链”现象。

因此，P2P发现算法中如何缩短路径长度的问题变成了如何找到这些“短链”的问题。尤其是在DHT发现算法中，如何产生和找到“短链”是发现算法设计的一个新的思路。small world特征的引入会对P2P发现算法产生重大影响。

非结构化P2P系统中发现技术一直采用洪泛转发的方式，与DHT的启发式发现算法相比，可靠性差，对网络资源的消耗较大。最新的研究从提高发现算法的可靠性和寻找随机图中的最短路径两个方面展开。也就是对重叠网络的重新认识。其中，small world特征和幂规律证明实际网络的拓扑结构既不是非结构化系统所认识的一个完全随机图，也不是DHT发现算法采用的确定性拓扑结构。

实际网络体现的幂规律分布的含义可以简单解释为在网络中有少数结点有较高的“度”，多数结点的“度”较低。度较高的结点同其他结点的联系比较多，通过它找到待查信息的概率较高。

语义查询和DHT的矛盾

现有DHT算法由于采用分布式散列函数，所以只适合于准确的查找，如果要支持目前Web上搜索引擎具有的多关键字查找的功能，还要引入新的方法。主要的原因在于DHT的工作方式。

基于DHT的P2P系统采用相容散列函数根据精确关键词进行对象的定位与发现。散列函数总是试图保证生成的散列值均匀随机分布，结果两个内容相似度很高但不完全相同的对象被生成了完全不同的散列值，存放到了完全随机的两个结点上。因此，DHT可以提供精确匹配查询，但是支持语义是非常困难的。

目前在DHT基础上开展带有语义的资源管理技术的研究还非常少。由于DHT的精确关键词映射的特性决定了无法和信息检索等领域的研究成果结合，阻碍了基于DHT的P2P系统的大规模应用。[a]

P2P发现技术研究的成果与不足

P2P发现技术中最重要的研究成果应该是基于small world理论的非结构化发现算法和基于DHT的结构化发现算法。尤其是DHT及其发现技术为资源的组织与查找提供了一种新的方法。

随着P2P系统实际应用的发展，物理网络中影响路由的一些因素开始影响P2P发现算法的效率。一方面，实际网络中结点之间体现出较大的差异，即异质性。由于客户机/服务器模式在Internet和分布式领域十几年的应用和大量种类的电子设备的普及，如手提电脑、移动电话或PDA。这些设备在计算能力、存储空间和电池容量上差别很大。另外，实际网络被路由器和交换机分割成不同的自治区域，体现出严密的层次性。

另一方面，网络波动的程度严重影响发现算法的效率。网络波动（Churn、fluctuation of network）包括结点的加入、退出、失败、迁移、并发加入过程、网络分割等。DHT的发现算法如Chord、CAN、Koorde等都是考虑网络波动的最差情况下的设计与实现。由于每个结点的度数尽量保持最小，这样需要响应的成员关系变化的维护可以比较小，从而可以快速恢复网络波动造成的影响。但是每个结点仅有少量路由状态的代价是发现算法的高延时，因为每一次查找需要联系多个结点，在稳定的网络中这种思路是不必要的。

同时，作为一种资源组织与发现技术必然要支持复杂的查询，如关键词、内容查询等。尽管信息检索和数据挖掘领域提供了大量成熟的语义查询技术，由于DHT精确关键词映射的特性阻碍了DHT在复杂查询方面的应用。

P2P网络拓扑模型

Internet作为当今人类社会信息化的标志,其规模正以指数速度高速增长.如今Internet的“面貌”已与其原型ARPANET大相径庭,依其高度的复杂性,可以将其看作一个由计算机构成的“生态系统”.虽然Internet是人类亲手建造的,但却没有人能说出这个庞然大物看上去到底是个什么样子,运作得如何.Internet拓扑建模研究就是探求在这个看似混乱的网络之中蕴含着哪些还不为我们所知的规律.发现Internet拓扑的内在机制是认识Internet的必然过程,是在更高层次上开发利用Internet的基础.然而,Internet与生俱来的异构性动态性发展的非集中性以及如今庞大的规模都给拓扑建模带来巨大挑战.Internet拓扑建模至今仍然是一个开放性问题,在计算机网络研究中占有重要地位.

Internet拓扑作为Internet这个自组织系统的“骨骼”,与流量协议共同构成模拟Internet的3个组成部分,即在拓扑网络中节点间执行协议,形成流量.Internet拓扑模型是建立Internet系统模型的基础,由此而体现的拓扑建模意义也可以说就是Internet建模的意义,即作为一种工具,人们用其来对Internet进行分析预报决策或控制.Internet模型中的拓扑部分刻画的是Internet在宏观上的特征,反映一种总体趋势,所以其应用也都是在大尺度上展开的.对Internet拓扑模型的需求主要来自以下几个方面:

• 许多新应用或实验不适合直接应用于Internet,其中一些具有危害性,如蠕虫病毒在大规模网络上的传播模拟;

• 对于一些依赖于网络拓扑的协议(如多播协议),在其研发阶段,当前Internet拓扑只能提供一份测试样本,无法对协议进行全面评估,需要提供多个模拟拓扑环境来进行实验;

• 从国家安全角度考虑,需要在线控制网络行为,如美国国防高级研究计划局(DARPA)的NMS(network modeling and simulation)项目.

1、随机网络与拓扑模型

随机网络是由N个顶点构成的图中，可以存在条边，我们从中随机连接M条边所构成的网络。还有一种生成随机网络的方法是，给一个概率p，对于中任何一个可能连接，我们都尝试一遍以概率p的连接。如果我们选择M = p，这两种随机网络模型就可以联系起来。对于如此简单的随机网络模型，其几何性质的研究却不是同样的简单。随机网络几何性质的研究是由Paul，Alfréd Rényi和Béla Bollobás在五十年代到六十年代之间完成的。随机网络在Internet的拓扑中占有很重要的位置。

2、随机网络参数

描述随机网络有一些重要的参数。一个节点所拥有的度是该节点与其他节点相关联的边数，度是描述网络局部特性的基本参数。网络中并不是所有节点都具有相同的度，系统中节点度的分布情况，可以用分布函数描述，度分布函数反映了网络系统的宏观统计特征。理论上利用度分布可以计算出其他表征全局特性参数的量化数值。

聚集系数是描述与第三个节点连接的一对节点被连接的概率。从连接节点的边的意义上，若为第i个节点的度，在由k.个近邻节点构成的子网中，实际存在的边数E(i)与全部k.个节点完全连接时的总边数充的比值定义为节点i的聚集系数

3、拓扑模型

Internet拓扑模型可分为两类:

1. 描述Internet拓扑特征,包括Waxman模型,Tiers,Transit -Stub和幂律;

2. 描述拓扑特征形成的机理,包括Barabási与Albert提出的BA和ESF以及一种改进模型GLP.

由于第二类模型对Internet幂律形成机理的描述还不成熟,更多的是作为一种产生幂律的图生成算法。对于第1类模型来说,Internet拓扑特征的发现,实际上就是刻画该特征的度量(metric)的发现.一个属于第一类的拓扑模型就是包含若干已存在的或新发现的度量,然后根据实际的Internet拓扑数据求出这些度量的值.因此,对这类模型进行评价需要从两方面入手:

1. 对它所采用的拓扑数据进行评价;

2. 对其度量进行评价.

在所有已经发现的Internet拓扑度量中,最为基本的就是节点出度频率fd.其分布是判断一幅拓扑图是否与Internet拓扑相类似的最重要的依据.在研究早期,研究人员或者认为Internet节点出度是完全随机的(如Waxman模型),或者认为节点出度是正规的(如Tiers模型).而幂律的发现证明了Internet拓扑结构介于两者之间,呈幂率分布.根据对出度频率分布的刻画,可将Internet拓扑模型分为以下3类:

1. 随机型,即认为Internet拓扑图处于一个完全无序的状态,在大尺度上是均一的.Waxman模型，是一种类似于Erds-Rényi模型的随机模型,出度频率呈泊松分布.这个模型有两个版本:RG1,先将节点随机布置在直角坐标网格中,节点间的距离就是其欧几里德距离;RG2,依据(0,L)均匀随机分布为节点对指定距离.两个版本中,节点间相接的概率P(u,v)与其距离相关,服从泊松分布,距离越近,概率越大.

   其中,d(u,v)表示节点u与v之间的距离,L为节点间最长距离,á与a取值范围是(0,1).

2.  层次型,来自对Internet结构所具有的层次特征的认识,在同一层上的节点出度接近,不同层间节点出度差别很大.对同一层上的节点布置借用Waxman模型方法.Tiers(等级)模型将Internet划分为LAN(局域网),MAN(城域网)和WAN(广域网)3个层次.在该模型中,WAN只有一个,通过指定LAN和MAN数量以及各自内部所包含节点的数量来构造拓扑图.Transit-Stub模型将AS域划分为Transit类和Stub类.在该模型中,Transit节点彼此互联构成一个节点群,一个或多个Transit节点群构成拓扑图的核心,而Stub节点分布在Transit节点群四周与Transit节点相连.Transit -Stub是GT-ITM(georgia tech Internetwork topology models)软件包的一部分,有时GT-ITM也就是指Transit-Stub模型.

3. 幂率型.1999年,Faloutsos等人对NLANR(National Lab for Applied Network Research)在1997~1998年间的3份BGP数据以及1995年的一份traceroute测量数据进行分析,发现Internet拓扑中存在着4条幂律.

   幂律是指形如的方程,对于两个变量X和Y,存在一个常数C,使得Y与X的C次幂成比例.有两个声明:(1) 节点v的等级为,v是在按出度降序排列序列中的索引值;(2) 邻接矩阵特征值按降序排列,第i个特征值为li.幂律1(等级指数R):节点出度dv与该节点等级rv的R次幂成比例.幂律2(出度指数O):出度频率fd与该出度d的O次幂成比例.

近似幂律(hop-plot指数H):h跳内节点对(pairs of nodes)的数量与h的H次幂成比例.幂律3(特征指数E):特征值li与其次序i的E次幂成比例.

Small World网络

在现实的Internet环境中，网络拓扑并不完全满足随机网络拓扑。Watt和Strogatz发现，只需要在规则网络上稍作随机改动就可以同时具备以上两个性质。改动的方法是，对于规则网络的每一个顶点的所有边，以概率p断开一个端点，并重新连接，连接的新的端点从网络中的其他顶点里随机选择，如果所选的顶点已经与此顶点相连，则再随机选择别的顶点来重连。当p = 0时就是规则网络，p = 1则为随机网络，对于0 < p < 1的情况，存在一个很大的p的区域，同时拥有较大的集聚程度和较小的最小距离。Small World网络的几何性质如图所示

• 平均路径。图中被随机选择又重新连结后的线称为捷径，它对整个网络的平均路径有着很大影响，分析表明:当p>=21(NK)，即在保证系统中至少出现一条捷径的情况下，系统的平均路径开始下降。即使是相当少的捷径也能够显著地减小网络的平均路径长度。这是因为每出现一条捷径，它对整个系统的影响是非线性的，它不仅影响到被这条线直接连着的两点，也影响到了这两点的最近邻、次近邻，以及次次近邻等。

• WS网络的集团系数。r1初始固定的节点数可计算t1{ p=0时规则网络的聚集系数为C(0), C(0)取决于网络结构而与尺寸N无关，因此有相对较大的值。随着边按一定的概率p随机化，聚集系数在CYO}的附近变化。

• 度分布。WS模型是介于规则网络和随机网络

来源文章：

P2P协议概述 www.jouypub.com/2019/8f7e24e90c9f563030fa55be2957365d/

P2P中的核心技术 www.jouypub.com/2019/8d6820c66a1b868b668b837d9ee3f6f2/

转载本站文章《再谈P2P技术：网络拓扑结构、核心技术分析》,
请注明出处：https://www.zhoulujun.cn/html/theory/ComputerScienceTechnology/network/2020_0125_8253.html