P2P网络的拓扑结构（精选十篇）
P2P网络的拓扑结构 篇1
1 集中式拓扑
集中式内容路由是提供路由查询最直观和简单的方法。在P2P网络中设置一个节点, 称为中心节点, 所有其他节点和中心节点建立相应的连接关系, 并把自身所拥有的资源索引信息都保存到中心节点上, 从而使中心节点拥有全网的资源索引信息。当某个节点需要进行路由查询时, 向中心节点提交查询关键字, 中心节点遍历资源索引表格, 就可以很容易查询全网是否拥有请求节点感兴趣的资源。集中式只是针对路由查询机制而言, 在内容传送上仍然是对等服务思想。也就是请求节点通过集中式的路由查询机制定位出能够提供内容服务的节点后, 与这些节点分别建立传输通道实现并行传送, 而不是完全从中心服务器获得内容。中心化拓扑结构的最大优点是维护容易、资源比较的发现效率较高且实现相对简单。但是这种拓扑结构存在一些问题。集中式结构最明显的缺点是中心节点连接其他节点过多时, 需要存储大量的资源索引信息, 并且要保持资源索引信息的准确性和通信及时性, 就必须不断和其他节点保持信息的同步。当节点规模扩展时, 中心节点很容易出现性能瓶颈。代表系统有Napster。
2 全分布式非结构化拓扑
打破集中式结构的最简单办法是在P2P节点之间建立随机拓扑, 也就是在一个新加入节点和P2P网络中的某个节点间随机建立连接通道, 从而形成一个随机拓扑结构。当一个节点需要进行内容路由时, 节点向全网广播查询请求, 每个节点收到查询消息后搜索资源列表, 查看自己是否有资源可以为请求节点提供服务。如果有, 则向请求节点返回搜索结果, 否则直接忽略请求。这种机制不需要中心节点存在, 是一种纯分布式的机制, 但是网络拓扑结构是随机的, 没有典型的结构特征, 因此这种机制称为纯分布式路由查询技术。但是, 随着节点数目的不断增多, 网络规模不断扩大, 无结构化的纯分布网络进行内容路由时, 有很多致命的问题难以解决。特别是大规模节点消息响应风暴问题, 在网络规模过大时, 当前没有一个完善的机制可以解决, 这也导致其超大规模应用面临挑战。采用这种拓扑结构最典型的案例有Gnutella。
3 全分布式结构化拓扑
全分布式结构化拓扑的基本思想是将所有节点按照某种结构 (比如形成一种环状网络或树状网络) 进行有序组织, 从而在路由消息的传递上避免广播风暴, 典型的算法有DHT和Chord。分布式散列表 (Distributed Hash Table, 简称DHT) 是将一个关键值 (key) 的有限集合合理的分散到所有在分布式系统中的节点上, 并且能够将信息有效地转送到唯一拥有查询者提供具有关键值的节点。而Chord的组织结构式环网络, 该算法的核心思想是在资源空间和节点空间之间寻找一种匹配关系, 使得请求节点能够利用有序的网络结构快速定位到相关索引所在的节点。由于P2P网络中的节点较多, 且具有不稳定性, 这就要求DHT算法必须具有增量的维护能力。在面临急剧的网络膨胀和节点不稳定断开时, 节点的路由表能够进行增量更新, 节点的加入或离开不能让网络的路由表产生急剧的变化, 而只需要维护少量的更新即可。
4 半分布式拓扑
半分布式拓扑结构, 也称作混杂模式 (Hybrid Structure) , 它主要是吸取了全分布式非结构化拓扑结构和中心化结构的优点, 其将主要节点分为为两类。一类是所谓超级节点 (Super Node, 简称SN) , 另一类是普通节点 (Ordinary Node, 简称ON) 。整个网络可以看成是两级结构, 第一级是超级节点组成的一个类似随机的拓扑网络, 每个SN下面由若干个普通节点组成, 每个ON与SN建立邻居关系, 它们之间形成星型结构, 但ON与ON之间没有直接的邻居关系。一个节点成功的加入P2P网络, 是作为SN还是ON, 主要根据节点的CPU、内存、网络带宽等资源决定的。如果一个节点是普通节点, 加入P2P网络以后, 会选择一个SN进行通信, 选中的SN节点随后将推送包含多达SN的列表发给新加的节点, 加入节点将会根据列表中SN的状态决定选择哪个具体的SN作为其父节点。采用这种结构的最典型的案例就是Ka Zaa。
5 总结
网络拓扑结构 篇2
计算机网络拓扑主要是指通信子网的拓扑构型。
计算机网络拓扑根据通信子网中通信信道类型分为两类：
点到点线路通信子网的拓扑：星型、树型、环型和网型。
广播信道通信子网的拓扑：总线型、环型、树型、无线通信与卫星通信型。
三种主要的拓扑结构：
星型拓扑结构
星型拓扑中各节点都与中心节点连接，呈辐射状排列在中心节点周围。网络中任意两个节点的通信都要通过中心节点转接。星型结构的优点是控制简单，单个节点的故障不会影响到网络的其它部分，但中心节点的任务重，形成广系统的瓶颈、另外中心节点的故障会导致整个网络的瘫痪，
总线型拓扑结构
总线型拓扑通过一根传输线路将网络中所有节点连接起来，这根线路称为总线。网络中各节点都通过总线进行通信，在同一时刻只能允许一对节点占用总线通信。总线型拓扑所需电缆数量少，结构简单有较高的可靠性，另外易于扩充，增减用户方便。缺点是传输距离有限.通信范围受到限制;故障诊断和隔离困难;分布式协议不保证信息及时传送.不具实时功能。
环型拓扑结构
环型拓扑中各节点首尾相连形成—个闭合的环，环中的数据沿着一个方向绕环逐站传输 。环型拓扑的优点是抗故障性能好，电缆长度短;缺点是一但网络中的任意一个节点或一条传输介质出现故障都将导致整个网络的故障，因此故障难以检测。
计算机网络拓扑结构模式 篇3
韩昊（1994.08-），男，汉族，黑龙江塔河人。本科，黑龙江科技大学，研究方向：采矿。
摘要：研究空间系和图表以及不变量的属性的数学领域就是拓扑学。如果地址有拓扑属性，就可能创建地址，这些地址是位置相关的地址而不是路由相关地址。
关键词：拓扑；逻辑地址；空间地址
一、引言
我们发下早期的网络开发通常从操作系统中寻求指导，并由此产生了寻址（甚至许多os设计，包括NUIX无法理解IPC的重要性）。Shoch从操作系统中发现，网络也需要分离逻辑名称和物理地址，这种分离在操作系统中非常有用，Saltzer扩充了这种类推，他的观点包含虚拟地址和物理地址之间的区别，从而产生了位置独立的应用程序名称、位置相关的节点地址和附着点地址和路由，并声称这些都是网络结构必不可少的组件。我们还知道Saltzer遗漏了路由选择是两步骤进程这一点，这两步是（从节点地址序列中）选择下一跳，然后选择到下一跳的具体路径。我们知道，确定路径（例如节点地址到最近邻居的PoA地址的映射）所需要的信息是映射，并且这个映射与应用程序名到节点地址或者上层目录的映射相同。这证实了我们的发现，网络体系结构由单个递归层组成。它进一步暗示（N-1）-层的地址是（N）-层的附着点，使用（N）-层的某些应用程序可能是（N+1）-层的成员，因为（N）-层是附着点。节点和附着点之间的关系式相对的。
二、让地址拓扑化
1.在操作系统中位置相关是一个非常简单的概念
应用程序名和逻辑地址空间之间-的关系也很好理解。内存地址空间有很规则的结构。按照这样的类推，假设节点地址和PoA地址对应于逻辑地址空间和物理地址空间。但我们如何能让地址变的相关呢？在其他类推中，相关位置很好理解，例如街道寻地址。街道寻地址非常的相似：给定一个地址，很容易获得达到的目的地的许多路由，但网络很少有像城市街道那样的规则结构。凭直觉我们知道这是什么意思，但将其转换为我们能够实现的东西就是另一回事。提到位置相关通常的反应时建议用经纬网这类的。但其实他忽略啦一点：我们要在网络中而不是在地球表面上差找地址。
很明显上述方式并不合适网络，网络中的链路按某个频率不停变换，将寻地址与这么不稳定的东西结合在一起是无效的。另外，图与“如何”而不是与“在哪里”绑定的太紧。我们需要一种抽象的图表，这种抽象的图表中的变更保持相对不变。
研究空间关系和图表以及不变量属性的数学领域就是拓扑学。如果地址有拓扑性，就可以创建地址，这些地址是位置相关的地址而不是路由相关的地址。
2.寻址的拓扑
寻址的拓扑任何使用过汉语字典的人都可以验证，命名不会变。语言的校勘序列这种属性可用来确定单词在地址空间拓扑中的什么位置。当路由器选择算法的本质让我们综合考虑路由选择和成本最优化。因为我们要考虑多种情况，所以我们要单独确定连接性和成本最优化路由选择。其实最好的类比是辞典，辞典保持两个名称空间之间的映射，每个都有不同的拓扑。一张放在语言核对序列（例如字母表）中，另一张表放在某种语义拓扑中，这种拓扑尝试将含义相似的单词放在一起，表示某种“接近”概念。第一张表有指示针指向第二张表
应用程序命名和IPC寻址之间的主要不同就是拓扑的本质不同，IPC寻址拓扑用来定位DIF内IPC进程相对于其他的进程位置，因此是位置相关的。这就是它们通常建立在空间拓扑上的原因，应用程序命名拓扑用来定位语义空间（或者一组语义属性）内的应用程序。例如，我们以某种方法结构建文件目录，帮助定位文件，而不是物理设备，因此它可能是位置独特的。可能创建位置的相关的应用程序命名，就像可能创建路由相关的网络地址一样再有些情况下，甚至必须这样。因此，应用程序包含来自拓扑空间的地址，虽然在有些情况下，它不是可度量化的空间，然而IPC的地址空间很可能能够度量，如果不能，至少它还有方向。因为地址空间的文职不同，所以从应用程序地址空间到分布式IPC，它们的地址空间映射不可能同胚。路由器要确定两件事：具有不同地址的给定PDU，它们的地址彼此“接近”，这样它可以再同方向发送PDU，约定地址，发送它的“方向”。我们希望层之间的映射在打多数情况下是同胚的。
3.层的层次结构
网络结构被组织为层的分层堆栈。在传统的网络体系结构中，它们是专用不同函数的层。因此，层的这种堆栈图无法说明我们所关心的显著属性。常见的“塔”图表示有一组层，一层堆在另一层上面，所有层在网络的所有系统中都有相同的作用域。层的“沙漏”图用来表示顶部协议的多样性；中间较窄，包含的协议比较少，通常只有一个到两个；底部比较宽，反应了媒介的多样性。这些与层关联的分类，但没有说明运行网络中的层。层有不同的函数，这些与我们的这种思路紧密相关。既然我们认为层都有相同的函数，那么我们感兴趣的是层的作用域、它们分析和解决问题的能力，层有两个主要属性：抽象化和缩放。层对机制的用户隐藏啦内部机制的运行、隔离和通信量。但最重要的是，它们是创建这种抽象化的有效工具。
層次结构中下层的作用域较小。通常，作用域随着层的上升而增加。这就像树形图，它包含更多的叶子而不是分枝。这提供啦一种机制，通过这种机制我们能够“分治”层处理的问题。在下层，通过少数对象使用好的粒度处理；而在上层，通过更多的元素使用较小的粒度处理，这样实现着些函数的工作量在层之间保持相对不变。
这些层允许提高路由选择和资源分配的效率。如果在相同中间点之间有多个流程，就可以将这些流程组合为单个低层流程，在低层封装，其中“相同位置”可能是主机或者某个中间路由器。后者更有可能。与上层相比，下层的作用域和地址空间相对较小。下层较小的作用域说明PCI系统开销随着层的降低而减少，同时也减少啦路由选择的复杂性。（例如，对较少流程的较少路由决定需要较少的路由计算和路由通信量）分层是适用于抽象化和缩放的主要工具。
4.层的多个层次结构的寻址拓扑
虽然将一层的拓扑与下面的地址拓扑结合在一起会有所帮助，但这个不必要的条件。在这些子网边缘的边界路由器可能连接到其他子网或者一个或者更多支持提供商。公司数据由边界路由器封装，并通过其中某一个提供商发送。只有公司边界路由知道公司的寻址结构。它实际上是VPN。主机不能访问提供商的地址空间，提供商是个人所有者，完全控制这地址空间。
三、总结
P2P网络拓扑模型分析 篇4
P2P网络拓扑模式的发展经历了三个阶段:集中式P2P、分布式P2P和混合式P2P,目前主要采用混合式P2P。
1 集中式P2P
集中式P2P结构是最早的P2P应用模式,因其仍具有中心化的特点也被称为非纯粹的P2P结构。集中式P2P模式的拓扑结构类似于B/S,需要一个中心服务器来进行连接,但服务器作用只限于记录各对等体共享资源的相关信息及响应对等体并生成共享资源的索引信息,与传统的网络模式不同的是,真正的共享资源保存在每个对等体上而不是在服务器上。当某个对等体要访问其他对等体的共享文件时,只需服务器提供对方对等体的相关信息就可以建立一条直接互连的通道,无需服务器的干预(见图1),代表性网络为Napster。
当某节点希望搜索一个不知道位置的资源时,该节点向目录服务器发送请求,目录服务器在数据库中查询到匹配的资源后将其定位信息返回该节点,然后在两个节点之间执行交互。
集中式P2P具有维护简单、检索效率高的特点。但中心目录服务器却成为脆弱的瓶颈,如果该服务器失效,整个系统都会瘫痪。而且,不同等级的用户连接速度也会使系统性能大大降低,容易出现单点故障。
2 分布式P2P
分布式P2P没有中心服务器,各对等体随机接入网络,通过与其相邻的对等体直接连接形成整个网络体系,每个对等体的功能相似、地位平等。采用随机图的组织方式,利用TTL(Time-to-Live),洪泛(Flooding),随机漫步或有选择转发等方式搜索网络资源。当节点度数服从幂率(power—law)规律时,该方式能够较快发现目标结点,而且面对网络的动态变化体现了较好的容错能力。代表性网络是Gnutella。其拓扑如图2所示。
由于没有中心服务器记录共享资源的索引信息等,对等体通过转发请求共享资源的查询包遍历整个网络获取共享资源。
分布式P2P无中心化的特点避免了单点失效的问题,一个对等体失效并不影响整个网络的正常运行,并且不容易受到网络攻击。但是由于没有中央服务器保存对等体共享资源的索引信息,当对等体要获取网络资源时,必须使请求包遍历整个网络才能得到结果,由此产生许多无效的数据包,因此这种模式占用带宽较大,而且需要花费很长时间才能有返回结果。
随着P2P网络规模的逐渐扩大,网络开销成指数级上升。因此准确性和可扩展性是非结构化网络面临的两个重要问题。
3 混合式P2P
混合式P2P网络结合了集中式结构和分布式拓扑的优点,网络中存在着中间服务器,文件目录是分布的。混合式P2P模式引入了超级对等体的概念,按其功能可将超级对等体分成索引对等体和搜索对等体等。混合式P2P将各对等体按性能分成普通对等体和超级对等体两类,超级对等体保存其他对等体的共享资源的索引信息,若干普通对等体以超级对等体为中心形成一个类似集中式P2P模式的小型网络,各小型网络再通过其超级对等体相连形成一个大的混合P2P(见图3)。
混合式P2P中的超级对等体即充当了集中式P2P的中心服务器,又起到了分布式P2P中普通对等体的作用,任何一个普通对等体搜索共享资源时都要通过超级对等体,其搜索步骤如下:
1)对等体首先将请求查询发送到所属小型网络的超级对等体中,在超级对等体中搜索共享相关信息。
2)若超级节点能在其管辖区域查询到共享资源的索引信息,则返回查询信息。
3)超级节点查询不到共享资源,则将请求查询包发送给相邻的超级对等体。
混合式网络结构综合了分布式P2P和集中式P2P两种P2P模式的特点,保留了分布式P2P无中心化和集中式P2P快速查找的优势。既能在一定程度上有效避免单点化的问题,又能在不占用大量带宽的基础上较快速的完成搜索。混合式P2P模式是目前最为流行的P2P模式,其代表软件如Bit Torrent.
P2P并不是一个新概念,早在1969年ARPANET出现的时候,网络应用的模式就是P2P。如今,P2P又回到了人们视线。尽管P2P技术现在还不成熟,但为我们提供了前所未有的自由和便利。随着P2P研究的进一步深入,P2P技术将为信息社会带来更多的机遇与挑战。
参考文献
[1]林宇,程时端,李琦.对等网络[J].中兴通讯技术,2006,12(1):57-60.
[2]任浩.网格研究[EB/OL].http://grid.cs.tsinghua.edu.cn.
[3]万焱,郑振华.P2P技术与应用研究综述[J].软件导刊,2006,(1).
P2P网络的拓扑结构 篇5
上海市加权公交站点网络拓扑结构分析
构建上海公交站点的加权网络模型,研究加权网络静态统计性质,包括节点强度分布、加权群聚系数和相关性.研究发现:一个停靠站点上的饱和运输量和该站点的连接密度之间是一种超线性的关系,该发现为分析公交客流量分布提供了重要的借鉴.研究还比较了加权前后集聚系数和节点相关性的.变化,发现运输量大的节点之间建立公交线路的可能性也较大,而且这些连接强度较大的节点之间的公交路段交通压力也偏大.文末提出了一些改善这类公交状况的建议.
作 者：秦艳 张宁 李季明 QIN Yan ZHANG Ning LI Ji-ming 作者单位：上海理工大学,管理学院,系统工程研究所,上海93刊 名：广西师范大学学报(自然科学版) ISTIC PKU英文刊名：JOURNAL OF GUANGXI NORMAL UNIVERSITY(NATURAL SCIENCE EDITION)年，卷(期)：26(2)分类号：O157关键词：复杂网络 公交网络 力权网络 拓扑分析
网络拓扑结构的仿真建模 篇6
尽管研究网络拓扑的方法有多种, 如理论分析、实验测试、仿真建模等, 但仿真建模以其高效性、灵活性、低费用等优点而成为网络拓扑研究的最重要手段。网络拓扑建模是对真实的网络元素进行抽象, 保留其基本特征, 并运用等效描述的方法来建立网络拓扑模型的。建模是仿真的理论依据和方法保证。
1 拓扑特征的表示
通常用一个加权有向连通图来表示网络拓扑, 图中的节点和边分别表示网络中的路由器 (或交换机) 和链路, 而网络中的主机则不被考虑。这里假设图中的有向边具有对称特性, 即链路的带宽、延迟和代价在两个方向上都相等, 而且边的代价就是其欧几里得长度。
设一拓扑图中有个n节点、m条边, 为了量化拓扑的特征, 使之便于测量和比较, 这里定义以下三种特征度量:
(1) 节点的度。特别是节点的平均度, 定义为2m/n, 叶节点的度为1。
(2) 网络直径。拓扑图中任意两节点之间最短路径的最大跳数或长度。
(3) 双向元素。拓扑图中有向边的数量。
2 随机拓扑的仿真建模
2.1 随机拓扑模型
建立随机拓扑模型的基本思想是:全部节点随机地 (或按heavy-tailed分布) 放置在一个平面内;考虑每对节点, 用某一概率P (u, v) (也称为边概率) 在节点对 (u, v) 之间加上一条边。这就是标准的随机拓扑建模方法, 我们称此模型为纯随机模型或者简单随机模型。纯随机模型并不能明显地反映真实的网络结构, 因而仅用于拓扑建模的参照与研究;其它的随机模型都是以它为基础演变而来, 它们之间的不同之处在于所用的概率P (u, v) 不同。
为了能更好地反映真实的网络拓扑, 几种随机拓扑模型随即出现。最常见的随机拓扑模型是B.M.Waxman提出的Waxman模型, 该模型所用的概率P (u, v) 按下式计算:
式中, α>0, αβ≤1为模型参数, d为节点u到v的欧几里得距离, L是整个平面内任意两节点间的最大距离。其中, 增加!的值可以增加拓扑图中边的总数, 增加"的值会增加拓扑图中长边相对于短边的比率。
Waxman模型也有几种变化: (1) 用[0, L]间的一个随机数来替代节点u到v的几何距离d; (2) 将P (u, v) 乘一比例因子k#/n, 这里的#是所期望的节点平均度, n是节点数, k是依赖于α和β的常数; (3) 允许α>1.0。第二种变化实际上是M.B.Doar和I.Leslie提出的Doar-Leslie模型, 该模型所用的边概率为:
此模型不同于Waxman模型, 因为Waxman模型中的参数相当于此模型中的$k#/n, 这里的比例因子k#/n可以更加直接地控制拓扑图中边的数量。
E.W.Zegura与K.L.Calvert等人提出了另外两种随机拓扑模型:指数模型和位置模型。这两种模型强调节点间的距离对于边概率的影响, 在指数模型中:
该模型中的边概率随节点间距离的增加而呈指数减少。在位置模型中, 边按其长度进行分类, 并对每个类别分配不同的边概率:
式中的r为长度类别的边界参数。
2.2 模型参数的选择
为了分析模型参数对拓扑结构的影响, 需要事先固定三个拓扑特征:节点数n、边数m和节点间的最大距离L作为比较的基准, 通常取。对于上述的每种拓扑模型, 在n、m和L固定的情况下, 首先通过实验 (或理论分析) 探测几个参数的不同组合, 然后为每种拓扑模型选择一个特定的参数集。
(1) 纯随机模型中的节点平均度 (也就是数学期望) 可以表示为P (u, v) * (n-1) , 则有:
将n=100、m=175代入, 可求得P (u, v) =0.035。
(2) 在指数模型中, 节点的平均度可表示为E (nαe-d/ (L-d) ) =nαE (e-d/ (L-d) ) , 这里的!为比例因子。实验结果显示, 当n=100、m=175、L=141时, !=0.06。
(3) Waxman模型中的参数与边概率之间的关系有些复杂。实验证明, 当!、!固定时, L的变化对边概率没有太大的影响, 因为在公式 (1) 中, d/L的值基本上可以保持不变, 因此只需要考查β、α与边数m之间的变化关系。参照文献[4], 可以作出α、β与边数m之间的关系图, 如图1所示。当。
(4) 实验结果表明:在Doar-Leslie模型中, 取α=0.1、β=0.3、k≈27、ε=3.5可满足n=100、m=175和L=141的条件。
(5) 位置模型中的节点平均度可以近似地表示为:
上式等号左边的第一部分表示当d
2.3 模型特征的比较
为了比较以上五种随机拓扑模型的特征, 对每种模型都生成100个拓扑图。通过对实验数据 (即每个拓扑图的特征值) 进行分析和比较, 容易得出如下结论:
(1) 不同类型拓扑图之间的最大区别在于它们的基于几何长度的网络直径不同。其中, 纯随机模型的网络直径远大于其它模型的网络直径, 这种模型对加入边的长度不敏感, 因而才会有更多的长边和长路径。
仅次于纯随机模型的是Doar-Leslie模型和指数模型。对于指数模型, 尽管在边概率的计算公式中包含了边的长度, 但是随着边长度的增加, 边概率下降得要比它们的模型慢;DoarLeslie模型有一个较高的!值, 因此边的长度也较大。
在Waxman模型和位置模型中, 虽然边概率的计算公式完全不同, 但由于模型参数的选择不同导致了边长度分布的类似性。
(2) 在这100个拓扑图中, 所有节点的度都在2到5之间, 节点的平均度全部约为3.5, 而且, 几乎所有拓扑图中的叶子节点数都在5到15之间。
(3) 所有拓扑图中双向元素的数量比较接近, 大约都在10至20之间。
3 规则拓扑的仿真建模
规则拓扑的结构有十分明显的规律, 如环状、树状、星型、线形链、Mesh图等, 根据这些规律布置节点和链路的位置及连接性就可以建立它们的拓扑模型。表1给出了一些常见规则拓扑图的特征标量, 其中的n表示节点数。
为了便于考查拓扑的不同特征对某些网络消息或算法性能的影响, 经常用到一种特殊的规则拓扑模型-矩阵模型, 该模型允许用一个可控的方式去改变网络尺寸、直径以及节点的度等拓扑特征。矩阵模型的拓扑实际上是一个多维的节点阵列图, 如图2所示, 图中的虚线表示曲线链路 (为了使图形清晰, (b) 中的虚线部分被去掉) , 每条边表示两条无向的链路。
此阵列图可以用二元组 (k, n) 表示, 其中k表示每维的节点数, n为维数。因此, 一个 (k, n) 拓扑图中有kn个节点, 2nkn条链路, 节点的平均度为2n, 网络直径为[k/z]n。
4 Internet拓扑的仿真建模
4.1 Internet的拓扑结构
从历史的观点上讲, 大型网络如PSTN (Public Switched Telephone Networks) 的拓扑结构通常按照设计的方案增长和变化, 并采用集中式的授权和管理。相反, Internet的异构性 (由IP协议结构实现各种异构网络的互连) 、大规模和快速变化这些特征使得我们不可能对Internet进行集中式的管理和控制, 谁也不知道有关Internet拓扑的细节, 因而难以对它进行描述、建模和仿真。
尽管如此, IP地址的分配计划和政府的资助建设使得Internet的拓扑结构也具有一定的规律。今天的Internet可以看作是由一些网络域或AS (Autonomous System) 通过各自的边界网关节点连接而成的、具有层次化结构的网络。每个域中包含了路由器、交换机和主机等网络元素, 同时存在一些相对简单的、关于路由计算和信息管理的控制策略。
如图3所示, Internet中的域可以分为Stub和Transit两类:Stub域中的流量只在本域中产生或终止, 而Transit域则没有此项限制, 即Transit域常作为流量的传输网络。Stub域一般只与一个Transit域相连 (Stub域也可以与多个Transit域相连, 这种域称为多穴Stub) , 而Transit域则作为多个Stub域的连接网络。Stub域通常是校园网、LAN等, 而Transit域则是WAN、MAN (Metropolitan Area Networks) 等。
最后需要说明的是:Stub域也可以与另一个Stub域通过各自的边界网关直接相连, Transit域也可以进一步地被分层, 例如, 一个WAN可以看成是由多个MAN组成的层次结构。
4.2 混合建模方法
前面所介绍的拓扑建模方法 (包括随机拓扑和规则拓扑的建模方法) 并不适用于Internet, 主要有以下原因: (1) 它们不能够描述Internet拓扑的层次化结构; (2) 也不能确保Internet所需的连接性; (3) 在Internet拓扑中, 链路数并不一定随节点数一起增加或减少。
建立Internet的拓扑模型通常采用混合建模方法 (又称为层次建模法) :首先把Internet拓扑分成三个层次, 即Transit层、Stub层和主机层;然后对每一个层次进行分别建模;并对域内和域间的连接性分开进行处理。
4.2.1 模型参数
为了便于描述和控制Internet拓扑模型的特征, 这里定义两类模型参数:整体性参数和连接性参数。如表2 (a) 和 (b) 所示。
4.2.2 建模过程
Internet拓扑的建模过程可能在不同的模型中会有所不同, 但基本的建模过程如下:
(1) 把每个Transit域看作是一个节点, 这时可以选择一种随机拓扑的建模方法, 在整个网络平面内建立包含这些特殊节点的拓扑模型。这里, 节点数为T, 边数为ETT。
(2) 对于每一个Transit域, 也可以选用一种随机拓扑的建模方法在一个平面子区域内建立它的拓扑模型, 并选择一些特殊的节点作为它的边界网关。这里, 节点数为NT, 边数为ET。
(3) 对于Transit域中的每个节点, 在该Transit域的周围划分出一个平面子区域, 并选用一种随机拓扑的建模方法在此子区域内建立它所对应的Stub域的拓扑模型。在每个Stub域中选取一个节点作为连接该Transit域的边界网关, 如果EST>1 (多穴Stub) , 则一个Stub域可以与多个Transit域相连, 当然, 也可以在Stub域与Stub域之间加上一些附加边 (链路) 。
(4) 将NL个主机节点放置在一个平面子区域内, 呈Star布置。Star的中心节点是与一个Stub域相连的路由器, 作为该LAN的网关。如果ELS>1, 那么该路由器也可以与多个Stub域相连。值得注意是:整个建模过程都在一个平面内进行。
4.3 Internet拓扑模型
4.3.1 Transit-Stub模型
Transit-Stub是GT-ITM (Georgia Tech Internetwork Topology Models) 拓扑仿真软件所采用的模型。目前的Transit-Stub模型并不支持主机系统的描述和建模, 因此该模型中的NL=0。Transit-Stub的建模过程与上述的基本建模过程相同, 这里仅介绍Transit-Stub模型中节点和链路属性的分配。
Transit-Stub模型中的每个节点都带上一个标识其位置的标记, 此标记的结构为:L1:L2:L3。其中, L1表示该节点是一个Transit节点还是一个Stub节点, 是一个布尔类型的变量;L2表示该节点所属的Transit域的编号;L3表示该节点所属的Stub域的编号。
当我们对Transit-Stub拓扑图中的边分配代价时, 应考虑不同类型边的代价的不同性。这里定义了几个有关代价分配的参数, 如表3所示, 在构造Transit-Stub模型时, 拓扑图中边的代价推荐按照下列公式进行分配:
需要说明的是, 表3和公式 (7) 中的代价和网络直径都用跳数来度量, 这与用几何长度表示边代价的随机拓扑模型有些不同。
4.3.2 Tiers模型
Tiers模型能够描述包括Transit域、Stub域和LAN三层结构的拓扑, 但Transit域的个数必须为1, 即T=1。生成Tiers拓扑图的过程如下:
(1) 整个平面被分割成一个个小区域 (grid) , 每个网络节点根据它所处的物理位置和类型被放置在这些grid的中心。这里的节点类型是指:WAN的路由器或交换机、MAN的路由器或交换机以及LAN的主机。不同类型的节点形成了不同的拓扑层次, 例如, WAN节点形成Transit域, MAN节点形成Stub域, LAN节点形成LAN。
(2) 对于每一层的每个域中的全部节点, 采用最小生成树 (MST, Minimum Spanning Tree) 的方法将它们连接起来。这里LAN除外, 因为LAN中的节点采用的是Star连接。冗余的边应加到几何距离最短的两节点之间。
(3) 根据不同类型节点间的几何距离为最短的原则在不同层的域之间加上边。
最后需要说明的是:在Tiers模型中, 边的代价采用节点间的欧几里得距离来度量;Tiers建模的时间计算复杂度为O (N2H) 。
4.3.3 Transit-Stub与Tiers的比较
Transit-Stub和Tiers都明显地采用了分层建模的方法, 但Tiers引入了MST的方法来连接网络中的节点。MST的使用保证了节点的连接性, 减少了建模时间, 而且生成的拓扑图更加接近真实的WAN拓扑。
另外, Tiers将LAN布置成Star, 这有利于减少拓扑图的边数以及仿真所需的时间。Tiers把连接两个不同类型节点的一个节点作为两个节点来看待, 这种处理有利于描述不同网络层次之间传输数据的延迟。
Transit-Stub大量地使用了随机拓扑的建模方法, 而且不能对LAN进行描述和建模。
还有一种Internet的拓扑模型是Inet, 这里并不展开说明。该模型根据初始节点度的分布, 采用最小生成树算法连接度大于2的节点, 这些节点用一个度连接到最小生成树, 其余的度用于与其它节点的匹配。Inet是一种基于测度的建模方法, 即生成的拓扑图结构在很大程度上取决于节点度的分布。
5 结束语
本文阐明了网络建模在网络仿真中的重要意义, 全面论述了网络拓扑的类型及各种拓扑的仿真建模方法, 为广大网络工作者提供了一种研究网络拓扑及构造拓扑仿真模型的参考。
参考文献
[1]Waxman B M.Routing of multiple connections.IEEE Journal onSelected Areas in Communications, 1998, 6 (9) :1617￣1622.
[2]Doar M, Leslie I.How bad is naive multicast routing?In:Proceed-ings of the Twelfth Annual Joint Conference of the IEEE Computerand Communications Societies (IEEE INFOCOM’93) , San Fran-cisco, CA, 1993, vol.1, 82￣89.
[3]Wei Liming, Estrin D.Multicast routing in dense and sparsemodes:simulation study of tradeoffs and dynamics.In:Proceedingsof the Fourth International Conference on Computer Communica-tions and Networks (ICCCN’95) , Las Vegas, NV, 1995, 150￣157
[4]Zegura E W, Calvert K L, Bhattacharjee S.How to model an inter-network.In:Proceedings of the Fifteenth Annual Joint Conferenceof the IEEE Computer Societies (IEEE INFOCOM’96) , San Fran-cisco, CA, 1996, vol.2, 594￣602.
[5]Floyd S, Paxson V.Difficulties in simulating the Internet.IEEE/ACM Transactions on Networking, 2001, 9 (4) :392￣403.
[6]Calvert K L, Doar M B, Zegura E W.Modeling Internet topology.IEEE Transactions on Communications, 1997, 35 (6) :160￣163.
[7]Doar M B.A better model for generating test networks.In:Proceed-ings of Global Telecommunications Conference (GLOBECOM’96) , London, 1996, 86￣93.
同学网络的拓扑结构研究 篇7
复杂网络是一种描述自然科学、社会和工程技术等复杂系统中个体间相互作用关系的模型, 自20世纪80年代末开始, 已经成为国际上许多学科最为前沿的研究热点问题之一[1,2,3,4,5,6,7]。目前在数学、物理学、生物学、计算机学、社会经济科学、系统科学等领域广泛应用[6];其中, 社会网络作为一种典型的复杂网络, 也得到人们越来越多的关注。
在现实生活中, 每个人都有各自的人际关系网。人与人之间的关系构成了社会网络, 网络中的节点是人, 边则是人们之间的关系。人是社会的主体, 人际关系与人们日常生活息息相关, 对人们工作和学习有显著影响。1967年, 哈佛大学心理学教授Stanley Milgram提出的“六度分离”理论, 是对现实社会网络最早的一次实证研究[8]。社会网络分析成为研究个体行为与群体动力学的重要工具, 研究和分析社会网络也有着非常重要的实际意义。
互联网的产生与发展很大程度上改变了人们的思维和交流方式。在线社交网络OSN (Online Socia Network) 迅速兴起并成为主流, 吸引了全球很多人的关注和参与。目前, 国内外不断涌现出各种社交网站, 如表1所示。
显而易见, 在线社交网络是一类特殊的社会网络, 又拥有如此庞大的用户群体, 完全可以看作一种复杂的巨系统。国内外也有很多学者开始利用复杂网络理论来研究在线社交网络的复杂性, 并取得了一定成果[9,10,11,12]。众所周知, 结构决定功能, 想要认识并利用这类网络的功能, 首先就需要对网络的结构就有清晰的了解, 这些研究既有重大的社会价值, 又有很大的经济意义。本文基于真实用户数据构建了一个在线社交网络, 对该网络的底层拓扑结构进行了研究。
1 网络拓扑结构的统计指标
1.1 度分布
度是节点属性中简单但很重要的概念, 节点的度定义为与该点连接的其他节点的数目。有向网络中, 节点的出度指从该节点指向其他节点的边的数目;入度是指从其他节点指向该节点的边的数目[4]。直观上看, 一个节点的度越大就意味着这个节点在某种意义上越“重要”。网络中所有节点i的度i的平均值称为网络的平均度, 记
(1) 度分布函数P (k) 。P (k) 表示的是一个随机选定的节点度恰好为k的概率。
(2) 累积度分布函数Pk。Pk表示度不小于k的节点的概率。
有研究表明, 许多现实社会网络的节点度分布符合幂律分布[14], 可用公式 (2) 函数表示。
这表明在现实社会网络中, 绝大多数节点的度相对较低, 但也存在少数节点的度相对较高。式 (2) 说明社交网络具有无尺度特性。
Golder S[15]等人对Facebook中用户的朋友数量进行了研究, 数据包含了从2004年2月到2006年3月之间用户的好友列表。网络的好友数分布如图1所示, x轴表示朋友数, y轴表示拥有对用好友数的用户数量。可以看出, Facebook的好友数分布服从两段近似幂律关系。临界好友数约为250处, 超过之后用户数量下降。该网络的平均度
关于双段幂律分布的数学细节和物理意义, 可以从文献[17-18]中找到, 此处不再赘述。
1.2 群聚系数
群聚系数是网络的一个局部参数, 用以表示网络集团化的程度[4]。在社交网络中, 即刻画了某个节点的两个朋友节点也是朋友的可能性。假设网络中某一节点i的度为ki, 即节点i有ki个邻居节点。ki个邻居节点之间实际存在的边数为ki, 可能存在的总边数为ki (ki-1) /2, 则节点i的群聚系数Ci定义为:
整个网络的群聚系数C则为所有节点群聚系数的平均值, 也称平均群聚系数。实证研究表明, 大量现实中复杂网络的群聚系数比同等规模的随机网络大得多, 表现出较强的聚集性[13]。
一般地, 度值大的节点具有较小的群聚系数;而度值小的节点则相反。定义C (k) 为度值为k的节点群聚系数的平均值, 若两者之间的相关性满C (k) ~k-α, 则表明网络存在明显的层次结构[19], 即小的节点群以层次化的方式组织成较大的节点群, 并维持无尺度特性不变[20]。在Fu[16]等人研究的连通集团 (connected component) 和胡海波[21]等人研究的若邻网中, 群聚系数与度的关系都反映网络具有一定程度的层次化结构, 如图3所示。
1.3 平均最短路径长度
网络的平均路径长度 (average path length) 定义为任意两个节点之间距离的平均值[4], 即:
其中, n为网络节点数, dij表示节点i到节点j的最短距离。网络中任意两个节点之间距离的最大值称为网络的直径 (diameter) , 记为D=maxi, jdij。
平均最短路径长度
1.4 度相关性
节点度的相关性表示一个节点的度值与其邻居节点度值之间的相关性。在一个网络中, 如果度大 (小) 的节点倾向于连接度大 (小) 的节点, 则该网络了是正相关的;反之, 网络则是负相关的。常用来表示度相关性的指标有联合度分布、无尺度指标和同配系数。本文采用的是同配系数, 也称为度相关系数:即连在一起的节点对应度值的Pearson相关系数r[22]。
其中, ji, ki为第i条边对应两个节点的度值 (i=1, 2, …, M为总边数) , -1
大量实证研究[19]表明:生物和技术网络呈现异配模式, 如Web和Internet的度相关系数分别为-0.067和-0.189[23];而大多数现实社会网络则具有同配特性, 如科学家合作网、电影演员合作网和商业合作网等。然而, 很多在线社交网络往往相反[23], 比如Cyworld的度相关系数为-0.13[24], 若邻网中r=-0.082[21], 人人网某连通集团中r=-0.0036[16], 这都表明了在线社交网络与现实社会网络的一个重大区别。
1.5 介数
介数分为节点介数 (vertex betweenness) 和边介数 (edge betweenness) [5]。一般采用的是节点介数:即在网络的所有最短路径中, 通过该节点的最短路径的条数。假设节点s和t之间的最短路径数为δst, 两节点间过i的最短路径条数为δst (i) , 则节点的介数为:
它刻画了一个节点担当连接两个节点的中介 (或“桥梁”) 的能力, 反映节点在网络中枢纽性和影响力。节点的介数越大, 表明这个节点的枢纽性越强, 删除这样的节点会使大量的节点对之间的最短路径变长。Goh[25]等人对网络中节点介数的分析进行了统计学研究, 发现介数遵循幂律分布。
2 同学关系网络拓扑结构分析
2.1 数据收集
本文研究的同学关系网络, 是在人人网 (www.renren.com) 所有用户中选择一个用户, 由该用户所有好友以及好友之间的关系构造而成。根据网站的规则, 一个用户申请另一个用户“加为好友”, 通过后则互相成为好友;最后得到一个由404个节点, 8435条边构成的无向无权网络, 如图4所示。
2.2 拓扑结构分析
对该同学关系网络节点度分布的描述, 本文采用的是累积度分布函数Pk, 如图5所示。与现实中大部分的幂律分布具有单一度指数不同, 该同学关系网络的累积度分布Pk也服从两段近似幂律分布, 即在特定的临界度值时两边分为两段。在好友数约为45处, 用户数开始急剧下降。当k
对数据进行统计分析, 同学关系网络节点度所占比例分布情况如表2所示。表的左半部分表示比例排在前10位的单一度值, 其中前5位节点度k≤5, 由此可见网络中大部分节点连接边数较少, 即连通性比较低。表的右半部分表示各度区间分布情况, 其中度在1~10之间的节点所占比例高达30.4%, 与左表结论符合。度很大的节点所占的比例很小, 表明只有少数个体拥有大量的连边, 即认识很多朋友。
值得注意到是, 该网络中等度值的节点也占有一定比例, 其中度在51~80之间的节点占了总体的30%左右。这是由于该网络是由人人网中一个普通用户的所有好友构成, 而大多数好友是该用户的同学;在同学群体中, 根据人人网的机制和规则容易知道, 人与人之间认识的可能性会更大, 反映到网络中即节点之间倾向于彼此连接。因此, 该用户的高中同学 (相同班) 之间连接较多, 形成高中同学群体;大学同学 (相同班或相同系) 之间彼此联系, 形成大学同学群体。两个群体中的节点 (同学) 分别构成了两个明显的社团 (community) , 如图5所示。图中一些节点同时连接了高中群和大学, 则代表这些节点既是该用户的高中同学, 也是大学同学。在社团内部, 节点连接几率较大, 从而节点的度也会较大, 这解释了为什么中等度值节点也占有一定的比例。
网络中大部分节点度比较小, 只和该用户或其他几个个体连接。这些节点可能是该用户在其他学校的同学, 或是在网站活动中结识, 与该网络中同学没有关联。网络中存在极少数度较大的节点, 度最大的为该用户本身, 和其他403个节点都有连边。结合实际情况发现, 这几个度很大的节点 (该用户除外) 在现实生活中并不是社交广泛的人, 但在在线社交网络很“活跃”。说明在线社交网络为现实中不“活跃”的人提供了“社交”机会, 并有可能成为人气很高 (度大) 的节点, 这也可能是在线社交网络日益流行的原因之一。
该同学关系网络的群聚系数C=0.65, 比同等规模随机网络的群聚系数要大很多, 说明该网络具有强聚集性。群聚系数与度值关系如图6所示, 当节点度较小时, 群聚系数和度之间没有明显的关系。C (k) 的拟合值近似一个常数 (0.6) , 近似于平均群聚系数C=0.65;随着度值的增加, 群聚系数会逐渐变小。表明该网络的群聚系数符合一般规律, 但不具有明显的层次或社团结构。
计算可得该网络的平均最短路径长度,
网络的度相关系数r=-0.13, 与其他很多在线社交网络相同, 呈现出异配模式。在网络中, 度小的节点倾向于连接度大的节点, 即好友数量少的用户和好友数量多的用户连接的可能性更大。这一现象与现实社会网络有很大不同。现实生活中, 虽然普通人都希望能跟知名人士或业界精英建立联系, 但这些往往更倾向于跟同等地位的人交往。在线社交网络则不同, 它打破了社会阶层间无形的壁垒, 个体有机会跟那些人气很高的个体建立联系[26], 于是才能呈现度的异配模式。
该同学关系网络中节点介数的均值为2.22×10-3, 节点介数与度值的相关性如图7所示。可以看出, 随着度值的增加, 介数的值也逐渐增大。这与实际情况一致, 当一个人在某个社交圈内认识很多人的时候, 一般情况下, 他在这个圈内的“影响力”就比较大。
3 结束语
本文研究并分析了在线社交网中一个同学关系网络的结构。较大的群聚系数 (C=0.65) 和较小的平均最短路径长度 (
在线社交网络日益流行, 并逐渐成为人们日常生活的一部分, 在线社交网络的研究具有潜在的理论和应用价值。这类网络的建立多是基于共同的兴趣爱好、业务背景和信任关系;反之, 网络连接的建立也可影响个人的兴趣和相互之间的信任。深入理解在线社交网络的底层拓扑结构, 有助于了解信息在网络中的传播过程和个人间信任关系的建立、巩固或消除, 并有助于对网络流量进行合理的优化或配置[27]。在线社交网络的研究也为社会学家和心理学家研究大规模社会网络提供了前所未有的机会, 有助于他们在这些网络中寻求新形势的个人或集群行为和相关人类动力学行为。在线社交网络对政治选举也能产生一定的影响[28];同时, 销售人员也能利用这种网络推销他们的商品。
P2P网络的拓扑结构 篇8
自新中国成立以来, 中国的航空网络逐步发展壮大, 特别是改革开放以来, 随着全国工作重点转移到经济建设上, 以及对外开放政策的实施, 中国航空网络的各项建设也进入了改革和发展时期, 以持续十多年高出国际民航组织缔约国年均增长率约3倍的速度发展成为世界航空大国。中国航空网络发展的这一历史性跨越, 令世界航空界瞩目[1]。
回顾新中国民航事业的发展历程, 我们看到, 今日的中国航空网络, 以其所组织规模、基础设施、技术装备, 以及所具有的运行质量, 已经成为中国交通运输体系的重要组成部分, 成为中国实现现代化和加快国际化进程的重要生力军。
中国的航空网络近年的发展速度是惊人的, 因此, 我们将通过1989年-2004年 (缺1991年) 国内主要航空港及主要航线构成的中国航空网络数据[2], 来探讨中国航空网络结构上的变化以及未来的发展。
1 中国航空网络的演化
1.1 边数目变化
航空网络中的边, 就是两航空港间的直航航线。如图1所示, 在1989年-1998年之间, 中国航空网络的边数目维持稳定的增长, 年增长率基本保持在10%-20%左右。因此, 短短10年间, 中国航空网络的边数目从仅有的65条增加到了250条, 增加了接近3倍的数量。而在1998年-1999年, 边数目则经历了一段爆发式的增长——随着主要航空港的不断增加, 在各航空港之间建立更多的直航航线显得更加必要, 因此1998年-1999年间, 边数目从250条飞跃上升到了接近500条, 足足翻了一翻。但在1999年以后, 中国航空网络的边数目发展却出现了相对稳定甚至轻微下滑的趋势。纵观全局, 出现这种现象的主要原因是国内的航空网络已经发展到了一个相对成熟的阶段, 并开始进入优化结构的阶段。因此, 部分创造经济效益较低, 或因其他交通运输方式发展而能被替代的航线开始退出历史舞台, 而部分因应需求而产生的航线则被建立。
总的而言, 中国航空网络的边数目发展与国家开放民航市场的政策, 以及因国家经济发展而增加的航空运输需求有着必然的联系。但随着航空网络的结构优化调整, 中国航空网络的边数目近期内应该会保持在一种相对稳定的状态。
1.2 节点数目变化
航空网络中的节点, 就是航空网络中实际存在的主要航空港。如图2所示, 和边数目的发展变化状态相类似, 在1989年-1998年这10年间, 中国航空网络的主要节点数从32个增加到了66个, 增加了一倍;而且在这10年内每年均保持增长的趋势, 但增长速度较边数目略慢, 增长速度维持在5%-15%左右。而1998年-1999年间, 节点数目出现了近50%的高增长。但此后的节点数目基本上维持在了90个左右的稳定态势, 时多时少。产生此现象的主要原因是部分航空港人流及货运量减少而不再扮演主要航空港的角色, 部分地区则因经济发展而增加了对航空运输的需求, 从而使该地航空港承担起了国内主要航空港的职务。
从这十几年节点数的发展变化来看, 国家加大对航空港等航空基础设施建设的投入, 改扩建支线航空港, 发展加强枢纽航空港, 都是中国航空网络节点数变化发展的原因。而随着经济的进一步发展, 中国航空网络的节点必然会在调整的基础上不断增加。
2 无权重的中国航空网络拓扑结构特征
自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。一个典型的网络是由许多节点与连接两个节点之间的一些边组成的, 其中节点用来代表真实系统中不同的个体, 而边则用来表示个体间的关系, 往往是两个节点之间具有某种特定的关系则连一条边, 反之则不连边, 有边相连的两个节点在网络中被看作是相邻的。例如, 神经系统可以看作大量神经细胞通过神经纤维相互连接形成的网络, 计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络。类似的还有电力网络、社会关系网络、交通网络等等。这些后来都能被归类为复杂网络的网络宏观性质一直备受各种科学研究活动的关注, 并且绝大部分该类型网络都展示出了小世界特性[3]等性质。
毫无疑问, 中国航空网络和这些复杂网络具有极大的相似之处, 也具有一些复杂网络所具有的特性。因此, 下面将以2004年的数据[2]对无权重中国航空网络的复杂网络拓扑结构特性进行分析。
2.1 描述复杂网络拓扑结构的主要性质
2.1.1 小世界效应
小世界效应是复杂网络最有代表性的性质。简单地说, 小世界现象指的是, 尽管许多网络具有相当大的规模 (节点多, 跨度远) , 如果把节点间的距离定义为连接它们最少沿途的边数 (相隔的边数) , 则其任何两个节点之间却存在相对很短的“快捷距离”。美国哈佛大学社会心理学家米尔格兰在1967年做过一项有趣的实验[4], 即著名的“六度分隔”理论实验, 一般称为“小世界” (small-world) 的模式由此诞生。这说明, 若将个人作为节点, 人的相识关系作为连接, 则构成的网络是小世界的。另外, Erdos和Renyi己经证明, 经典的随机网络其任何两个节点的典型距离为网络节点数之对数数量级, 所以也具有小世界的特点。对于一个无向的节点数为N的全连通网络, 其平均最短距离可以定义为[5]:
网络的平均最短距离反映了网络中节点对之间的平均分离, 同时也反映了网络的尺寸, 因此也常叫它作网络直径。今天人们对小世界网络的定义, 除了小的平均最短距离以外, 还意味着下面的高聚集性。同时具有两个方面特性的网络才可以被称为是小世界的。
2.1.2 网络的聚集性
如果一个网络节点有数个直接连接的紧邻节点, 那么这些紧邻节点之间有可能也是紧邻的。而聚集性用于描述这种可能性程度, 从而实际表达了网络连接的聚集程度。定量地来说, 可以用簇系数 (Clustering coefficient) 来表达。假定考虑一个网络的节点i具有ki个紧邻, 其簇系数可以定义为[5]:
其中Ei是节点i的ki个紧邻间实际存在的连接。这个定义被广泛使用, 尤其在社会学领域常被称为网络密度。显然簇系数表示了节点的紧邻之间也是紧邻的程度。整个网络的簇系数C则定义为ci对全部节点的平均。对于随机网络, 则有C=p, p为节点间的连接概率。Watts和Strogatz首先指出[6], 许多实际网络的簇系数远大于相同节点规模的随机网络。也就是说, 许多实际网络具有趋于集团的特性, 就像人的社会关系网络一样。
2.1.3 度和度分布
网络中节点具有的连接数称为该节点的度。度分布描述复杂网络节点连接数目的分布特性。当前人们用分布函数P (k) 表示任意选择一个网络节点其连接数为k的概率, 实际上就是具有k个连接的节点占全部网络节点的比例。对于随机网络, 因为连接的随机性, 所有节点的连接数 (度) 应该接近网络的平均连接度
但人们通过经验研究发现, 实际网络的度分布远非泊松分布。显然, 这是因为实际网络的连接并不是随机的。令人惊奇的是许多实际的网络, 像WWW、Internet、代谢网络、电话呼叫网络等, 其度分布都服从幂率P (k) ∝k-r。这样的网络有一个统一的名称, 即Scale-Free (SF) 网络或者无标度网络。
2.2 无权重航空网络拓扑数据分析
2.2.1 度分布
从统计得到的数据, 我们知道中国航空网络的主要节点数目为N=92, 存在的主要边数目为E=454, 因此计算得到中国航空网络的平均度值为
其中幂率指数=0.8±0.1, f (k/kx) 为取决于航空港的最大连接数处理能力的指数截断函数。而根据此函数, 我们可以得知中国航空网络的度分布服从幂率P (k) ∝k-r, 具有无标度特性。
通过上述数据考虑中国航空网络的实际情况, 我们可以发现目前国内航空网络中, 直航航线较少的支线机场仍然占有主要地位, 而拥有大量直航航线的枢纽机场数量则略显不足。
2.2.2 平均簇系数分布
由公式 (2) 及平均簇系数计算公式C=N-1∑ici我们计算出无权重中国航空网络的平均簇系数C=0.718。而在图4中所示的平均簇系数C (k) , 则定义为对所有k相同的簇系数ci (k) 所取的平均值。如图4所示, 我们可以看到平均簇系数C (k) 随着k的增大而不断衰减, 即连接数小的节点拥有更大的聚集性, 而连接数大的节点其紧邻节点之间的直接连接反而更少。此外, 我们还能发现平均簇系数C (k) 的分布在度值较小时, 衰减速度较慢;而当度值增大至一定程度时, 其衰减速度突然加快。而其衰减分布符合幂率衰减:
其中α的值按k在不同区间取值的不同而发生变化:当k≦20时, α=0.12;当k>20时, α=1.1±0.1。
根据整个航空网络平均簇系数的值及平均簇系数C (k) 的分布, 我们知道我国航空网络的聚集程度相对较高。国内的航空港特别是支线航空港, 其紧邻往往会形成一个紧密的集群。
2.2.3 平均距离分布
由图5, 我们可以知道中国航空网络各节点的平均最短距离di随着节点的度值增加而不断减小;而且当节点度值较小 (k<10) 时, 度值相同的节点平均距离分布并不集中, 而是相对平均地分布于一个值域区间2
结合实际的航空运输网络进行考虑, 相对较小平均距离d=2.26意味着在中国国内, 平均只要通过2.26条直航航线就能到达目的地, 符合航空运输便捷高效的特性。但是, 从统计资料中我们也发现了航空网络的最大距离为dmax=4, 即某些城市之间的航空运输仍然要经过4条航线才能到达, 仍然存在一定的不便之处, 需要对现有的航空网络作出进一步的优化设计。
3 结语
本文已经表明, 中国的航空网络正在不断地发展壮大, 特别是航空港与航线的数量都呈现着不断上升的趋势。而对中国航空网络的统计数据进行分析, 则使其展示出了复杂网络的多样性分布及各种幂律趋势。本文的研究仅提供了一种定量的、一般性的复杂网络拓扑机构理解方法, 为中国航空网络的机构优化提供了一定的技术基础。但限于篇幅, 未能对带权重的航空网络进行探讨, 诸如航空网络的稳健性等进一步的问题也并未进行更深入的相关研究。但纵观现今民航的发展和网络研究趋势, 对航空网络的深入研究和优化工作势在必行, 我们必须迎合潮流, 做好相关的研究工作。
参考文献
[1]杨国庆.中国民航发展展望[J].交通运输工程学报, 2001, 1 (4) :1-8
[2]中国交通年鉴社.中国交通年鉴1989-2004[M].北京:中国交通年鉴社, 1990-2005
[3]Watts J.S., Strogatz S.H., Collective dynamics of‘small-world'networks, Nature393:440-442, 1998
[4]S.Milgram., The small world problem., Psychology Today, 2:60-67, 1967
[5]李勇.复杂网络理论与应用研究[D].华南理工大学博士论文, 2007
探讨国际贸易网络拓扑结构的演化 篇9
关键词：国际贸易,国际贸易网络,拓扑结构
国际贸易网络系统由全球100多个国家和地区构成, 在经济全球化的背景下, 世界贸易已经发展成为互惠、共赢的贸易网络。随着经济全球化发展, 各个国家之间的依赖性加强, 这种影响也逐渐延伸到了各个国家之间的国际贸易网络。如2008年爆发的全球范围内的金融危机, 对世界各国的经济均造成了极大的冲击, 因此, 必须从全球化的范围内对国际贸易系统展开研究。本文通过复杂的网络方法, 分析了2003年至2013年的国际贸易网络拓扑结构的演化规律。
1 国际贸易网络的构建
在国际贸易系统中, 用顶点代表每个国家, 用商品和服务流动方向的有向边代表各个国家之间的贸易关系, 这样设计的目的是为了能够使用有向网络说明国际贸易系统。在一般情况下, 网络的拓扑性质是指网络不依赖于顶点的具体位置、边的具体形态而单独体现出来的性质, 在网络拓扑性质的基础上网络的拓扑结构得以发展。本文构建的贸易网络包含了193个顶点及21186条边。
在构建国际贸易网络时, 需要按照商品及服务的流向来明确国际贸易网络中边的指向, 贸易出口意味着商品及服务的流出, 贸易进口意味着商品及服务的流入, 若在T年, A国向B国出口了商品及服务, 则在T年的网络快照上勾勒一条由A至B的边, 其对应的邻接矩形存在非零元素θA B (T) =1, 反之, 若A至B没有边时, θAB (T) =0。各个国际贸易网络快照由每年度的国际贸易网络拓扑结构组合而成, 因此, 每国际贸易网络快照都具有其特殊的拓扑结构和拓扑性质, 能够直接影响到贸易网络的连通性。由于国际贸易网络的大部分拓扑结构和拓扑性质难以运用随机图范式加以解释, 在这种情况下, 必须运用合适的测度标准来分析和研究国际贸易网络的拓扑结构、拓扑特性及其演变规律[1]。
2 国际贸易网络拓扑结构的顶点度分布
国际贸易网络拓扑结构的顶点度主要代表与顶点存在关联的边数, 在有向网络中, 各个顶点均存在对应的出度和入度, n (T) 表示T年全球进行贸易的国家总数, A国在T年的出度与入度则等于从A国进口以及向A国出口的各个国家的总数。
有关学者将贸易网络中具有某种幂指数形式的度分布称作无标度网络, 即BA模型, 并将真实系统运用自组织建立起无标度网络归结为两个重要因素——增长性与择优连接。在BA模型中, 于整个贸易网络中找寻连通度最大的顶点视为择优顶点, 从而使中枢顶点可以获得优势连接, 使之变得更加强大;若贸易网络中的顶点数量达到一个特定的数值时, 贸易网络中的顶点连接数量就会出现一些顶点存在大规模连接的情况, 然而, 大部分顶点只存在少量连接[2]。
在国际贸易网络中, 具有较强经济实力的国家在国际贸易关系中存在很大的优势, 一个国家的国内生产总值与其国际贸易关系数量成正比。在本文的研究对象中, 选用一部分经济发展规模相对较小的国家作为表示国际贸易网络发展中新增顶点的国家, 这些国家的贸易产品主要是某些基本商品, 考虑到空间地理位置具有差异性, 运输成本将有所增加, 因此无标度网络中的择优选择难以在国际贸易网络中得以展现。
对于经济规模相对较小的国家而言, 其在一般情况下是与周边邻国发展贸易关系, 难以在世界性的贸易网络中实现择优连接。由此可见, 尽管择优选择能够在国际贸易网络中发挥一定的积极影响, 然而, 完整的国际贸易网络并非典型的无标度网络。
从本质上看, 复杂的贸易网络无标度性可以视为异质性, 贸易网络中存在少数的顶点拥有大规模连接、大部分顶点拥有少量连接的情况, 因此, 为了进一步描述国际贸易网络异质性的演化特征, 本文采用网络结构熵与标准网络结构熵进行分析。通过运用标准网络结构熵, 能够对比不同年度国际贸易网络快照的异质性, 本文对2003年至2013年的国际贸易网络进行计算, 对国际贸易网络快照顶点存在相同、边数相同的某个随机网络情况进行分析[3]。实验表明, 国际贸易网络与随机网络的网络结构熵差异并不明显, 二者的增长趋势均相同, 不存在无标度网络异质性的情况。国际贸易网络从2003年至2013年的演化过程中, 标准网络结构熵与随机网络趋近, 说明国际贸易网络顶点度的异质性特征在不断消失, 国际贸易网络的拓扑结构出现随机化趋势。
所得研究表明, 随着现代交通运输和通信技术的发展, 国际贸易中的运输与通信费用得到了极大的降低, 在此情况下, 国际贸易自由化的领域得到进一步的拓展延伸, 从而使得各个国家之间有条件自行开展直接贸易, 极大地促使了国际贸易趋向全球化发展的局面, 在一定程度上削弱了发达国家在发展国际贸易关系中的主导地位, 使世界贸易呈现多元化发展的趋势。
3 国际贸易网络拓扑结构的群聚性
群聚系数的一般含义为对于存在kA条边的顶点A, 群聚系数表示为:
在上述公式中, nA是A的kA个邻边的数量, 若CA=0, 则顶点A的邻边不存在连通情况;若CA=1, 则顶点A的所有邻边都存在连通的情况, 群聚性越高则说明顶点周边的邻边连通性越好。
通过计算得知, 2003年至2013年国际贸易网络快照C (k) 和k存在一定的关系, 在每个网络快照中, C (k) 的总体趋势与k呈负相关, 即C (k) 随着k的增加而不断下降[4]。顶点度k能够反映一个国家贸易联系范围的广泛性, 顶点度数低的国家通常为经济发展规模相对较小的国家, 因其受本国经济规模的制约, 只能在国与国之间的周边区域内开展贸易关系, 其国际贸易伙伴在区域上相对集中, 贸易往来的机会也随之增高;顶点度数高的国家通常为世界性的贸易强国, 其贸易伙伴数量多且分布的范围广, 然而这些贸易伙伴之间能够直接开展贸易往来的概率较小。
从网络快照的对比中可以看出, 2003年一部分国家的顶点度数很低, 与周边国家的贸易联系相对较少, 由网络快照的顶点分布情况可知, 2003年的国际贸易系统还未形成有序的结构;而在2013年的网络快照中, 各个顶点数分布得更为集中, 表现出极强的统一性和一致性, 这就意味着2013年世界各国在国际贸易格局中的地位与贸易分工更为明细, 此时国际贸易网络趋于协调、有序的方向发展。
4 国际贸易网络的拓扑结构度相关性
在一般情况下, 顶点之间的有边连接存在的情况往往由顶点类型决定, 在复杂网络中, 根据顶点度的选择性关联, 被称作顶点的度相关性, 并可以分为同类混合和非同类混合两类。同类混合就是指度数高的顶点更倾向于和度数高的顶点相连接。非同类混合就是指度数高的顶点更倾向于与度数低的顶点相连接。
本文将同类混合网络度相关数值设置为正, 非同类混合网络度相关数值设置为负, 结合国际贸易度相关数值的变化情况, 度相关<0则说明国际贸易网络为非同类混合网络, 顶点度低的国家更倾向于与周边中枢国家发展贸易关系, 并形成以区域中枢国家为中心的区域经济合作组织, 诸如东盟、欧盟等。
另外, 在经济全球化的背景下, 各区域经济合作组织不能与其他地区断绝经济关系, 在此基础上, 区域经济大国成为连接各个地区贸易沟通的桥梁, 因此, 国际贸易网络系统已经形成全球化经济发展、区域经济发展并存的局面, 当度相关系数数值越低, 这一趋势也随之加强[5]。
5 国际贸易网络的拓扑结构的互惠性
在国际贸易网络拓扑结构中, 当中的贸易关系并非全部呈现双向性特征, 换言之, A国与B国存在贸易出口关系, 但B国对A国不一定也存在贸易出口关系, 因此, 这就牵扯到了国际贸易网络的互惠性。国际贸易网络的互惠性, 主要就是指贸易网络中两个国家之间存在双向贸易关系的具体程度, 互惠性是国际贸易网络拓扑结构中的一个关键测量指标, 其重要性不仅在于互惠性能够对国际贸易网络存在的威胁传播机制与传播速度产生相当重要的作用, 还在于其能够对世界各国国际贸易网络参与程度进行全面的衡量。
从2003~2013年各个年度国际贸易网络互惠系数的变化可知, 2003年的互惠系数为1.03, 2013年的互惠系数为1.57。由此可见, 国际贸易网络的互惠性在逐渐增长, 并不断呈现上升趋势, 说明世界各国都存在双向贸易关系, 世界各国之间的经济互补性日益增强, 使得更多的国家能够建立本国的比较优势, 并积极投入到国际贸易分工的全球化贸易体系之中。
6 结语
综上所述, 国际贸易网络是一个典型的、复杂的经济网络, 对国际贸易网络的拓扑结构发展演化进行描述, 有助于更好地理解国际贸易系统的运作规律, 还有助于各个国家制定科学合理的贸易政策。本文通过对国际贸易网络拓扑结构的发展演化进行分析, 由度分布性得知一个完整的国际贸易网络并非典型的无标度网络, 随着世界贸易交易成本的逐渐降低, 越来越多的国家开始发展本国的直接贸易关系, 国际贸易网络不断向随机网络趋同。对国际贸易网络拓扑结构的群聚性分析, 说明国际贸易网络中各个国家之间的分工合作变得更为有序。国际贸易网络的度相关性表明国际贸易网络非同类混合网络, 更多的小国更青睐于同区域大国开展贸易合作, 国际贸易已经趋向全球化发展。国际贸易网络的互惠性逐渐增长, 表面国际贸易中双向贸易呈现不断上升的发展趋势, 世界各国之间的经济互补合作得到进一步加强。
参考文献
[1]王哲, 吴松弟.中国近代港口贸易网络的空间结构——基于旧海关对外—埠际贸易数据的分析 (1877-1947) [J].地理学报, 2010, 16 (10) .
[2]崔卫杰.入世十周年中国高新产品贸易的国际地位分析[J].国际贸易, 2011, 05 (12) .
[3]陈银飞.2000-2009年世界贸易格局的社会网络分析[J].国际贸易问题, 2011, 10 (11) .
[4]王火灿.融入·共赢·转变——中国加入WTO十周年回顾与展望[J].世界贸易组织动态与研究, 2011, 19 (06) .
计算机网络多层拓扑结构的自动发现 篇10
2009年8月3日收到随着网络技术的迅速发展, 网络规模的不断扩大, 网络结构的日益复杂, 网络管理已成为网络系统运行好坏的关键。而网络拓扑发现是网络管理的基本工作, 是其他管理功能的基础。因此, 自动发现网络的物理拓扑结构具有非常重要的意义, 是网络管理系统的发展趋势[1]。
自动发现网络物理拓扑是指由程序自动识别和发现指定范围内的计算机网络中的路由器、交换机、主机等设备, 并建立所发现的网络设备之间的连接关系, 形成整个网络的拓扑结构[1] 。
分析国内外的相关研究, 发现目前的不足主要有以下几点:①搜索过程冗余信息过多, 耗时太长②搜索出的图只包含部分节点, 不够完整[2]。本文综合考虑了多种拓扑结构搜索方法, 提出了基于SNMP协议发现网络的逻辑层结构、结合STP协议确定网络链路层结构的方法。这个方法结合了逻辑层和链路层的搜索, 实行单次搜索并行发起, 多次搜索结果合并的机制, 在搜索时间上占一定优势, 并且经多次搜索可以获取接近完整的网络拓扑结构。本文还提出在搜索前, 对不进行搜索的设备进行规避的思想, 以缩短搜索时间。
1 基于SNMP协议的网络层拓扑发现
1.1 SNMP简介[2]
目前的网络连接设备基本上都是属于可网管型的, 即它们都支持SNMP协议。网络的拓扑信息可以从MIB库中获得, 因此可以通过使用SNMP的方式获取MIB信息, 从而得到计算机网络的拓扑连接关系。使用SNMP的优势在于只要针对少量设备发送探测报文, 探测速度快, 探测流量小。
SNMP的基本思想是:所有的网络设备都维护一个MIB库, 它保存该设备上所有与网络运行相关的信息, 并对管理工作站发出SNMP查询进行响应, 管理工作站通过从这些网络设备中获取的SNMP响应报解析出与网络拓扑相关的信息, 就可以得到整个网络的拓扑结构。
1.2 MIB信息
网络层拓扑发现所用的MIB信息库为RFC1213所定义的MIBII, 其结构如图1所示。
根据sysServices和ipForwarding值可以判断设备是否支持网络层服务, 是否具有IP路由功能, 从而判断设备的类型。
ipAddrTable中记录了该设备的所有端口地址等信息。ipRouteTable是网络层拓扑发现的关键, 它存储的是该设备的路由信息。ipNetToMediaTable即ARP表, 其ipNetToMediaPhysAddress、ipNetToMediaNetAddress分别代表与子网中设备的物理地址和网络地址。
1.3 基于SNMP的网络层拓扑发现过程
读取种子路由器 (开始搜索的节点) 的ipRouteTable, 由于路由表中的ipRouteNextHop所标识的必然是具有路由功能的网络节点, 因此可以从种子节点采用广度优先遍历算法由内向外发现网络中所有具有路由功能的设备[4,5]。
ipRouteTable中的ipRouteType有四种取值:other (1) , invalid (2) , direct (3) , indirect (4) 。其中direct (3) 表示ipRouteDest与该路由器直接相连, 其ipRouteNextHop为该路由器的一个端口地址;indirect (4) 表示ipRouteDest不与该路由器直接相连, 其ipRouteNextHop为另一个路由器端口地址, 要达到这个目的子网至少还需经过下一跳。
ipAddrTable的ipAdEntAddr表示路由器接口的ip地址, ipAdEntNetMask表示该接口所在子网的子网掩码, ipAdEntIfIndex表示ip地址所对应的端口索引。所有的ipAdEntAddr与ipAdEntNetMask进行“与”操作, 可以得到与该路由设备相连的所有子网地址。在ifTable中, 根据ipAdEntIfIndex可获取相应端口的ifDescr、ifType, 从而得到该端口所连子网的类型。
这样通过分析设备的MIB信息我们就可以获得网络中的子网信息和路由器信息, 以及它们之间的连接关系。同时通过路由表的ipRouteIfIndex, 可以得到转发该数据包所要投向的端口号, 再由接口表得到端口的类型就可以了解所在子网的类型, 从而构建出整个网络的拓扑关系图。
1.4 存在问题及解决方案
基于SNMP的拓扑发现主要用于反映网络的整体拓扑状况, 该方法发现过程和算法简单, 发现效率高, 系统和网络的开销小, 由于从路由表可以获得下一跳地址信息, 因此对于受到访问限制的网络, 还是可以发现第一级路由器, 得到相对比较完整的网络拓扑关系。但该方法存在以下不足: (1) 路由表中含有大量的冗余信息; (2) 虽然可以根据ipNetToMediaTable得到一些无路由功能的网络设备 (交换机、主机等) , 但是一个主机存入这个表中的记录会在20 min后自动删除, 所以其保存的信息不够完整, 而且不能确定它们间的连接关系; (3) 由于路由器可以连接多个子网, 具有多个接口, 不同的ipRouteNextHop 地址可能表示同一台路由器, 因此发现过程中会造成对同一路由器的多次搜索, 搜索结果中也会出现路由器重复。
本文针对如上问题的解决方案为: (1) 对路由表的各表项信息进行过滤, 只读搜索过程所需的信息, 避免信息冗余; (2) 对ipNetToMediaTable的信息进行多次读取, 并合并读取结果, 以获得尽可能完整的信息, 用STP协议判断无路由功能设备的连接关系, (3) 读取路由器的ipAddrTable以获得该路由器所有端口所对应的ip地址, 选取一个地址 (本文选取loopback地址) 唯一标识这个路由器, 其他所有地址均用这个地址替换, 这样就消除了发现过程及结果中的重复。
2 基于STP协议的链路层拓扑分析
2.1 STP简介[6]
IP网络主干由路由器-路由器、路由器-子网组成, 路由器将IP网分解为多个子网或逻辑网段。子网通常由交换机-交换机、交换机-主机构成, 由于子网内大量分布交换机, 同时在网络设计中, 为了保证网络的可靠性, 一般在网络中增加几条冗余备份线路, 这样在实际的网络拓扑图中会出现环, 为了解决它可能会打来的桥接循环和子网内广播风暴问题, 在交换机间运行STP协议来阻塞一些端口以使交换机间的闭合回路断开, 只有生成树上的交换机端口才能转发数据帧, 从而避免循环和广播风暴, 支持冗余拓扑[4]。
本文所讨论的交换机之间的连接关系都是指有效的链路连接, 不包含被阻塞的端口, 拓扑发现得到的端口之间的连接均是当前生成树的一个快照。
STP算法的基本思想是:交换机之间定期发送BPDU包, 交换生成树配置信息, 以便能够对网络的拓扑、花费或优先级的变化做出及时的响应, 而BPDU包的数据可以从BRIDGE-MIB库中得到, 因此同样可以分析SNMP的响应报来得到二层交换机的连接关系。
2.2 MIB信息
链路层设备连接关系的判断所用的MIB信息库为RFC1493所定义的BRIDGE-MIB, 其结构如图2所示。
2.3 基于STP的链路层分析
链路层拓扑发现的目标是发现子网内部的拓扑结构。数据链路层的通信以MAC地址为标志, BRIDGE-MIB中提供了交换机或网桥的端口转发MAC地址表, 并且提供了一个生成树协议信息表, 通过读取交换机设备上的这些信息, 可以准确的获取链路层拓扑结构。
dot1dStpPort:包含生成树协议信息的端口号;dot1dStpPortPriority:优先级;dot1dStpPortState:端口状态;dot1dStpPortEnable:端口的enabled/disabled状态;dot1dStpPortPathCost:路径费用;dot1dStpPortDesignated Root:根交换机;dot1dStpPortDesignatedCost:指定端口的路径花费;dot1dStpPortDesignatedBridge:指定交换机;dot1dStpPortDesignatedPort:指定端口;dot1dStpPortForwardTransitions:端口转换次数。
首先从Designated Root字段很容易地得到了生成树的根交换机, 同时, 对于每个交换机上的端口, 其指定交换机都能通过Designated Bridge字段获取。其次, Port字段表示了本交换机的根端口, 而Designated Port字段表示连接到指定交换机的指定端口[8,9]。
2.4 存在问题及解决方案
获取生成树信息构造交换机连接拓扑与通过获取分析交换机设备地址转发表信息构造连接拓扑相比, 所用时间短, 给网络造成的流量负担小, 并且算法简单容易实现。不足之处是要求网络中的交换机都支持生成树协议, 但是这在校园网络中通常是满足的。
由于链路层中的网络信息传递是以MAC地址为源地址和目的地址, 而一台交换机往往具有多个MAC地址, 所以在拓扑发现中需要用一个MAC地址来唯一标识一台交换机设备, 根据RFC 1493文档的建议, 在本文的拓扑发现中, 用交换机所有端口的MAC地址中最小的MAC地址来唯一标识这台交换机, 这个最小的MAC地址可以通过读取BRIDGE-MIB中的dot1dBaseBridgeAddress得到。
3 算法设计
单次搜索的流程图如图3所示。
搜索开始设置规避数据和种子节点。其中规避数据可以为没有权限搜索的ip段, 也可以为已经得到拓扑结构的ip段等, 搜索时将自动回避对规避数据的搜索, 从而节省拓扑搜索时间。
种子节点为拓扑搜索发起的点, 设置的数据包括必选和可选两部分。其中必选数据有发起搜索点ip, 搜索过程所需的community, retryTime, timeOut;可选的有要进行搜索的ip地址段, 搜索的最大深度, 搜索的最大广度等。
单次搜索结束后可以得到一个全新的网络拓扑结构, 此时可以选择将新的数据与以前搜索得到数据进行合并, 以得到尽可能完整的拓扑结构。
4 结束语
网络拓扑发现是网络管理中一个难点, 受限于网络的复杂性和网络协议的多样性, 做到对网络中所有设备完整准确地发现是非常困难的。
本文结合了网络二层和三层的搜索方法, 首先基于SNMP协议发现网络的逻辑层结构 (路由器及其连接关系) 及在线的二层设备 (包括交换机、主机等) , 其优点在于发现速度快, 但前提是被发现的网络设备需要支持SNMP协议。然后利用STP协议判定网络二层设备的连接关系。在实现方法上引入了数据规避、并行搜索、结果合并等机制。
实验证明, 本方法在搜索时间上占一定的优势, 并且经过多次搜索可以得到一张接近完整的网络拓扑结构图。
参考文献
[1]庄锁法, 龚俭.网络拓扑发现综述.计算机技术与发展, 2007; (10) :80—83, 91
[2] Case J, Fedor M, Schoffstall M, et al.RFC 1157-A simple networkmanagement protocol (SNMP) , http://www.faqs.org/rfcs/rfc1157.html, 1990—5
[3] McCloghrie K, Rose M.RFC 1213-Management Information Base forNetwork Management of TCP/IP-based internets:MIB-II, http://www.faqs.org/rfcs/rfc1213.html, 1991—3
[4] Mansfield G, Ouchi M, Jayanthi K.Techniques for automated networkmap generation using SNMP.IEEE INFOCOM, 1996; (2) :473—480
[5]曲朝阳, 胡绪超.基于SNMP的网络拓扑发现与拓扑生成树的绘制.网络安全技术与应用, 2007; (03) :23—24, 27
[6] Inst.Electr.&Electron.Eng, New York, 802.1DTM IEEE stand-ard for Local and metropolitan Area networks:media access control (MAC) bridges.IEEE-SA Standards Boards, 2004
[7] Decker E, Langille P, Rijsinghani A, et al.RFC 1493-Definitions ofManaged Objects for Bridges.http://www.faqs.org/rfcs/rfc1493.ht-ml, 1993—7
[8] Gobjuka H, Breitbart Y.Discovering network topology of large multi-subnet ethernet networks.IEEE INFOCOM, 2007:428—435
【P2P网络的拓扑结构】相关文章：
网络拓扑设计05-25
网络拓扑模型07-08
SDH网络拓扑05-06
计算机网络拓扑论文04-18
计算机网络拓扑论文提纲11-15
复杂网络理论下计算机网络拓扑研究论文09-04
新型拓扑结构06-02
网拓扑结构08-26