论文部分内容阅读
摘要：在计算机网络行为的分析与研究中，用不同的网络拓扑结构模型模拟复杂网络是一种使用非常广泛的研究方法。对于这些不同的网络拓扑模型对网络的影响到底是怎样的，如今还是个很难回答的问题。在这篇文章中，我们比较了广泛使用的几种网络拓扑结构模型对网络行为的影响，比如二维格子模型、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形式查看。
关键词：计算机网络模型，相变，网络行为
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形式查看。