不同网络拓扑模型对网络的影响
摘要：在计算机网络行为的分析与研究中，用不同的网络拓扑
结构模型模拟复杂网络是一种使用非常广泛的研究方法。对于这些
不同的网络拓扑模型对网络的影响到底是怎样的，如今还是个很难
回答的问题。在这篇文章中，我们比较了广泛使用的几种网络拓扑
结构模型对网络行为的影响，比如二维格子模型、cayley 树模型、
transit-stub模型、brite模型。我们发现不同的网络拓扑结构模
型在整体上存在着相同的网络行为和特征。
关键词：计算机网络模型，相变，网络行为
1． 简介
计算机网络飞速的发展引起来越来越多的研究者对其网络行为
特征的关注，而在研究的过程中网络模型又一个非常重要的研究方
式。不可置疑的是，对于研究网络来说最基本的是对网络特性（包
括拓扑和协议）合理的描述和模拟。现在已经提出来了很多网络模
型，比如，二维格子模型、二进制的cay-ley树模型，还有随机图
结构等等。事实上，这些模型很难完全反应整个大规模网络的结构
特征。为了很好的反映网络中非常重要的“域”这个概念，因此产
生了transit-stub结构，这个结构反映了网络分层次和域的思想。
最近的研究表明大规模网络存在着幂率现象。而幂率现象并不总在
transit-stub模型中存在，alberto medina等人在考虑了这个因
素之后提出了一个拓扑结构产生器brite [5]。通过这个产生器生
成的拓扑结构包含有幂率现象。
大多数关于计算机网络的研究主要集中在网络的动态规则上，
比如，路由规则和传输协议。不过，还是有越来越多关于网络整体
行为特征的研究，不仅有计算机方面的专家，还有数学家，统计物
理学家等。这些复杂的行为特征包括相变、数据包传输的幂率现象、
不规则行为和一些非线性现象。目前计算机网络可以被描述为一个
由大量的非线性单元组成的复杂非线性系统。这些非线性单元的相
互作用导致了网络系统的复杂动态行为。在90年代早期，leland 等
人通过研究网络通信的发送特性，指出了以太网数据包的到达时间
是自相似的，并且大范围内是相互依赖的。对于已经广泛使用在网
络通信研究中的泊松模型，这个结论的得出对它提出了挑战性。基
于二维格子模型和cayley树模型发现了网络中的相变现象，这个
发现意味着在计算机网络中至少存在着两个阶段，非拥塞阶段和拥
塞阶段。在更为复杂的计算机网络模型transit-stub模型中使用
udp协议时，同样发现了相似的相变现象。而统计分析真实的计算
机网络的实验数据进一步的得出了这些仿真结果所得出的结论。
然而，网络的拓扑结构是怎么影响网络整体行为却依然是一个
难以解释的问题。本文分析和比较了几种非常广泛使用的网络拓扑
模型来解释这个问题，包括二维格子模型、cayley 树模型、
transit-stub模型、brite模型。仿真结果显示网络拓扑结构对整
个网络的宏观演化没有很大的影响，但是对于局域网络却是非常重
要的。另外，在计算机网络动态演化规则中网络协议是一个非常重
要的组成部分，并却在动态演化的过程中起着非常重要的作用。
2． 各种网络拓扑结构比较
在这一节里，分析和比较了各种非常广泛使用的网络拓扑结构
模型，包括包括二维格子模型、cayley 树模型、transit-stub模
型、brite模型。
2.1 二维格子模型
在以上几种网络拓扑模型中，二维格子模型是最简单的网络拓
扑结构。在这个模型中，主机和路由器分布在二维格子的格点上。
每一个格点的位置可以描述为一个离散的二维空间变量p，如下
p=xi+yj,
这里的i和j都是笛卡尔单位向量。除了边界节点之外，每一
个节点都有四个邻居。对于边界节点邻居的不同选择，可以分为周
期性边界条件和非周期性边界条件。如果左（上）边界上的节点的
邻居定义为右（下）边界上的节点，这样的格子模型被称为周期性
边界条件格子模型。图1是周期性边界条件和非周期性边界条件的
格子模型。不过从二维格子模型的结构可以看出这个模型并不能表
示计算机网络的不规则性。但是这个模型由于它的结构和规则的简
单型却被广泛的使用。
图1：二维格子模型的非周期性边界与周期性边界
2.2 cayley 树模型
cayley 树是一个没有环的无限维的分层的格子网，并且每一个
节点含有固定数目的分支。cayley树生成的步骤如下：
（1）首先选一个中心节点作为生长节点，从这个节点生长出单
位长度的z个分支。每个分支的末端节点是另外一个生长点。
（2）一个组包含这些新的生长点的生成，从每一个组的每一个
节点的末端，z-1个分支生成。
（3）重复第二步直到这棵树足够大。
参数z被称为这个模型的调和数，例如z=2，这个树就是一个一
维链。图2表示了一个z=3的cayley树的拓扑结构。cayley树有
层次结构，这点可以反映真实计算机网络的结构。但是，它的这种
规则的生长规则并不能放映真实网络的灵活性。
图2：cayley树结构
2.3 transit-stub结构
以上两种的拓扑结构模型都只有非常简单的连接关系，反映包
含复杂内部结构的大规模真实网络的能力有限。大规模的计算机网
络经常都有地区域和分层的结构，因此在大规模网络中“域”这个
概念非常重要。在transit-stub拓扑结构中，大规模计算机网络
通常被描述为一些路由域的集合，在一个域中的节点共享相同的路
由信息。局部路由性在路由域中是非常重要的特性，这表示在一个
域中任意两个节点之间的通路都是包含在域中的。路由域可以被分
为stub域和transit域。定义如下：
（1）从节点u到v的通路经过路由域d，当且仅当节点u或v
在d中，这样的域d就被称为stub域。
（2）不是stub域的路由域就被称为transit域
transit域在transit-stub模型中对应计算机网络层中的顶层，
stub域对应其它的层。transit-stub的典型结构如图3所示。
图3：transit-stub结构
2.4 brite结构 [5]
最近的研究表明在因特网拓扑结构中存在幂率现象。这种幂率
现象存在在下列关系中：
（1）节点出度对层次
（2) 节点的数目对出度
（3）邻居内的节点对的数目与邻居的范围
然后，transit-stub结构并不能很好的反映这些对应的幂率关
系，因此它似乎并不能非常精确的描述因特网的拓扑结构。albert
medina 等人已经研究出这些幂率现象是怎么起作用的，并且产生
了brite结构。并把这个应用到因特网拓扑结构发生器上来生成网
络结构，称作brite结构。并且试验结果表明，brite结构确实能
真实地代表计算机网络的拓扑结构。
3． 实验结果以及结论
在计算机网络的仿真实验中，拓扑结构模型在网络行为的研究
上是非常重要的。他们代表了计算机网络的静态规则。然而，协议
主要是负责数据包的传输，可以看作是计算机网络的动态规则。这
些动态的规则在动态系统的复杂性现象中启着更重要的作用。我们
的实验是用了两种很常用的协议tcp和udp在上诉四种广泛使用的
拓扑结构上。仿真结果确认了网络协议在计算机网络的复杂性现象
中起着比拓扑结构更重要的作用。在包的平均生命周期与包的长生
速率的实验中我们应用udp协议，观察到了相变现象，但是在使用
tcp协议时，包的平均生命周期并没有放映网络的拥塞情况。另外
一个参数，发送速率是用来表示相变现象从非拥塞阶段到拥塞阶段
的。实验结果表明，相同的网络协议，不同的网络拓扑结构，观察
到的网络整体行为在本质上是一样的，而不同的网络协议，却观察
到不同的复杂性现象。因此我们得出结论，在复杂网络动态系统的
复杂性现象上，网络协议也就是动态的规则比网络拓扑结构起到了
更重要的作用。

注：文章内所有公式及图表请用pdf形式查看。