计算机网络建模数学工具的分析与比较

摘 要：论述了目前用于计算机网络建模的几种主要的数学工具，并且从网络建模和模型求解之间存在的矛盾角度出发对这几种数学工具进行了分析和比较。对研究计算机网络建模有一定的指导作用。

关键词：计算机网络；网络建模；数学模型；随机变量；概率

中图分类号：TP39文献标识码：A文章编号：1672-3198（2008）06-0321-01

1 计算机网络的性能分析建模特点

计算机网络研究与应用的重要理论基础和支撑技术是性能分析。要对网络进行性能分析必须先对要分析的网络建立一个适当的模型，然后求出模型的各项性能指标，以便对系统进行性能分析。但是由于计算机网络具有下列特点:首先，计算机网络内部的任何一点上，基本数据单元的到达时间均为随机变量。其次，组成网络的各个单元之间相互作用，使得网络中的数据流存在很强的相关性。因此既随机又相关是计算机网络中的数据流具有的特点。而网络中数据流的本质和特点又是我们在对计算机网络进行性能分析时所关心的。

在以往的性能分析工作中，一般都采用先建立网络的分析模型，通过模型求解得出精确解或者是数值解;然后，再用模拟或者采用构造系统测量的方法来验证得出的结果。但是在通过分析进行性能评价的过程中，给系统建模和对模型求解一直是一对相互矛盾的过程。建立的系统模型越精确，则模型必然就越复杂，相应的求解就越困难;反之，模型越简单，则求解就越容易，但结果的精确性也就越差。因此，我们在对计算机网络进行性能分析的过程中，始终考虑系统建模和模型求解之间的矛盾，兼顾建模的精确性和求解的可行性。因此，也将从这个角度来比较计算机网络建模的各种数学工具。

2 建立随机模型分析的方法

2.1随机过程概述

随机过程是定义在给定的概率空间上的一族随机变量{X(t)，t T}，T表示参数空间。随机变量x(t)是定义在概率空间上的实函数，x(t)所取的值表示随机过程在时刻t的状态，函数所有可能值的集合构成了随机过程的状态空间。随机变量的概率描述可以由概率分布函数F(X；t)=P{X（t ）＜x}和概率密度函数f（x；t）=F（x;t）x来表示。若考虑离散状态的随机过程，则概率分布函数为:Px(t)（k）=P{ X（t）=k}，∑allkPx(t)（k）=1 。包含n个随机变量Xi（i=1，2.....，n）的随机变量X的概率模型可由如下的单个随机变量的联随机变量的概率特征的重要性在于它是一种将包含随机变量本身的问题形式化的工具，可以通过在任意时刻抽取任意数目的随机变量组成的任何随机向量来刻画一个随机过程的完整概率特征。但是从求解的角度来说这是不可能实现的。

马尔可夫过程(Markovproeess)是一类重要的随机过程。它的状态空间是有限的或是可数有限的，经过一段时间系统从一个状态转移到另一个状态的这种进程只依赖于当前出发时的状态而与以前的历史无关。这种特性称为马尔可夫特性，也就是也就是说马尔可夫过程具有无记忆的特点。马尔可夫过程广泛的应用于离散事件系统，具有离散状态空间的马尔可夫过程叫做马尔可夫链，如果时间是连续的，则称为连续时间马尔可夫链。

如何恰当的定义系统的状态是直接在连续时间马尔可夫链的层次上建模存在的主要困难。为了解决这个问题，又有一些更为抽象的概率模型被提了出来。

2.2排队模型理论

排队模型作为运筹学研究的一种有力手段，在计算机网络性能分析中占有相当重要的地位，它是在随机过程基础之上发展起来的一种数学方法。

在现实生活中，排队现象是随处可见的。因为资源总是有限的，而对资源的需求则是随机的，因此从排队现象中得到抽象的物理模型，并继而建立数学模型的一整套理论就是所谓的排队论了。典型的排队系统如图所示:

从上面的图中可以看出队列和服务员是组成排队系统的两个基本要素。使用排队模型对计算机网络进行建模时，服务员通常是由现实对象系统中的某一个独立的功能部件(如:节点机、终端、线路或者是某一层次上的通信协议)所抽象出来的;而队列所描述的是在现实对象系统中所有待处理的对象(通常称为顾客)之间的序列关系。由于在现实系统中待处理对象是随机发生的，因此它们到达队列的分布可以用概率分布来刻画，通常假定顾客到达或到达时间的间隔为相互独立的且遵从同一分布的随机变量。

排队模型和马尔可夫链之间存在着密切的联系。通常的系统并不是孤立的排队，实际上我们经常遇到多个互连排队的问题如顾客流的分开与合并等。而单个的排队模型则是通过采用较为复杂的到达时间间隔和服务时间分布的概率密度函数来刻画现实对象系统，这样就需要引入多个服务员或者引入依赖于负载的服务率，分析求解超过了连续时间马尔可夫链的能力。这一缺点的根本原因在于将特定系统的特征隐含在概率密度函数中所造成的模型复杂化。而排队网络正是解决这个问题而引入的。

排队网络是对现实对象系统的一个直接映射。典型的排队网络是一个有向图G=(V，E)，其中v代表节点集合，而E=v x v代表一组弧。其中的每个节点代表一个服务站，表示实际系统中的某些主动的资源，如:节点可以模拟通信系统中的交换机或者路由器等网络节点。服务站包含一个队列和一个或者多个服务员。E所代表的弧的集合则定义了网络的拓扑结构，表示顾客流的可能通路。因而排队网络模型和单个的排队模型相比更能够刻画系统对单个资源的共享。而在求解时就可以把网络中的每个队列都看成是一个独立的因子，因而就可以通过这些独立因子的乘积求出整个系统的性能。通常情况下，采用排队模型的方法对计算机网络进行性能分析时所求解的都是信息穿过网络的平均延迟时间。为了方便分析就需要引入独立性假设。只有在此基础上分析过程才能十分直接，否则求解过程将变得非常困难。

Jackson在1957年和1963年的发表的论文中给出了Jackson网络模型，它给排队网络分析带来了突破。Jackson网络的稳定状态概率具有乘积形式的解，非常完美。但是Jackson网络的结论是基于这样的假设: 首先，在任何网络节点中的顾客的数量与其它任何节点中顾客的数量无关；其次，在任何网络节点中顾客所经历的服务时间独立于任何其它节点中顾客所经历的服务时间。而实际上这一假设并不成立。尽管在许多特定环境下的模拟和测量结果表明根据这一假设求解有很高的近似程度。

通过前面的分析我们可以看出，采用排队模型的方法来进行计算机网络的性能分析只能刻画网络的基本行为，无法精确的刻画网络中的某些既随机又相关的特性。

2.3petri网(PNs)理论

petri网(PNs)理论是1962年CarlAdamPetri博士在他的博士论文中首先提出来的。Petri网能够对具有并行、并发、同步、资源共享等特性的系统建立模型，并且使之形象化。Petri网作为一种图形化和形式化的建模工具，它包括位置(plaee，也称为库所、状态)元素、变迁(Transition)元素和连接它们的弧(arc)。把基本的Petri网模型中的变迁元素和时间随机变量关联起来就形成了随机Petri网模型。总的来说，随机Petri网具有下列特点:

(1)基本的随机Petri网模型可以很方便的描述网络中的相关时间，描述网络中的同步、竞争、碰撞和拥塞等行为。

(2)随机Petri网中的时间变迁元素和时间随机变量相关联，可以很好的描述计算机网络事件的随机性。

(3)随机Petri网可以同构于相应的马尔可夫随机过程，从而可以在随机过程的层次上进行模型求解。

3 结束语

综上所述，我们介绍了目前用于计算机网络性能分析的数学工具，并且从系统建模和模型求解之间存在的相互矛盾角度出发对各种模型工具进行了分析和比较。

随机过程是各种性能分析工具的基础，也就是计算机网络性能分析的基础。但是，对于计算机网络来说，在随机过程层次上直接建立网络模型的主要困难在于怎样恰当的对网络系统的状态进行定义。排队论是在随机过程基础之上发展起来的一种数学建模工具，在实际中有着广泛的应用。但使用排队模型只能描述网络系统的基本行为，难以精确的分析和描述网络的既随机又相关的特性。

近年来，随着Petri网理论的不断发展，其应用范围也越来越广，它是计算机网络系统性能分析中一个很有吸引力的数学工具。它在一定程度上可以缓解系统建模和模型求解之间存在的矛盾。在未来它将成为研究的主流方向。

参考文献

［1］施仁杰.马尔可夫链基础及应用［M］.西安：电子科技大学出版社，1992.

［2］唐应辉，唐小我.排队论一基础与应用［M］.西安：电子科技大学出版社，2000.

注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”