《计算机网络与通信 教学课件 ppt 作者 申普兵 第11章 网络设计基础》由会员分享，可在线阅读，更多相关《计算机网络与通信 教学课件 ppt 作者 申普兵 第11章 网络设计基础（95页珍藏版）》请在金锄头文库上搜索。
1、第11章 网络设计基础,【本章内容简介】本章首先介绍计算机通信网络设计的基础知识：排队论和图论。然后讨论计算机通信网络拓扑设计。 【本章重点难点】学习本章时，应注重掌握有关排队论和图论的一些基本定义和基本分析方法，学会如何运用这些基础知识进行计算机通信网络的拓扑设计。,11.1 排队论基础,排队论又称随机服务系统理论，它广泛应用于计算机通信领域，是计算机通信网的基础理论之一。,1排队论与计算机通信网 排队是日常生活中常见的现象。 由要求随机服务的顾客和服务机构两方面构成的系统，称为随机服务系统或排队系统。,11.1.1 排队论基本概念,顾客需求的随机性和服务设施的有限性是产生排队现象的根本原因
2、。排队论就是利用概率论和随机过程理论，研究随机服务系统内服务机构与顾客需求之间的关系。以便合理地设计和控制排队系统。 计算机通信网就是一个大的排队系统。,排队系统尽管千差万别，但都可以抽象为顾客到达服务机构，若服务员有空闲，便立刻得服务，若服务员不空闲，则需排队等待服务员有空闲时再接受服务，服务完后离开服务机构。,2排队系统的一般表示,图11.1 排队模型,排队系统的基本参数包括：顾客到达率，服务员数目m和服务员服务速率。 （1）顾客到达率 顾客到达率 是单位时间内平均到达排队系统的顾客数量（具体到计算机通信网，就是单位时间内到达分组交换节点的分组数量）。反映了顾客到达系统的快慢速度，越大，说
3、明系统的负载越重。,3排队系统的基本参数,一般排队系统中顾客的到达是随机的，即任意相邻两顾客到的时间间隔Ti是一个随机变量。Ti的统计平均值就是顾客到达的平均时间间隔达，其倒数即为顾客到达率 =,若在观察时间t内有n（t）个顾客到达，在平稳条件下，有 =,（2）服务员数目m 服务员数目m就是排队系统内可以同时提供服务的设备或窗口数，它表征服务机构的资源。在计算机通信网中，m常指分组交换节点的输出信道数量。,（3）服务员服务速率 服务员服务速率指的是单位时间内由一个服务员进行服务所离开排队系统的平均顾客数，对于m=1的单服务员系统，就是系统的服务速率；对于ml的多服务员系统，则系统的服务速率为m
4、，即单位时间内接受服务后离开系统的平均顾客数为m。,假设每个服务员的服务速率均为 ，的倒数 就是单个服务员对顾客的平均服务时间，也就是一个顾客在系统内接受服务的平均时间。,4排队系统的三个特征,排队系统在运行中包括三个过程： 顾客输入过程 排队过程 顾客接受服务（然后离去）的过程,（1）顾客到达间隔时间的分布函数 顾客的输入过程不同，用以描述输入过程特征的顾客到达间隔时间的分布函数也就不同。,如果顾客的输入过程满足下述三个条件，称该输入为最简单流。 平稳性。 稀疏性。 无后效性（或独立性）。,根据推导得出，当输入过程为最简单流时，在给定时间间隔t内系统有k个顾客到达的概率为,Pk (t)=,k
5、=0，1，2，,式（11-3）称为泊松分布。由此可见，最简单流在t时间内到达系统的顾客数量服从泊松分布。根据式（11-3）可进一步推导出顾客到达间隔时间的分布函数。,设T为顾客到达时间间隔，它是一个随机变量，可以取0的连续值。根据概率论中连续型随机变量的分布函数定义，T的概率分布函数为 FT (t)=P (Tt),若Tt，说明顾客到达间隔时间大于所选定的时间长度t，则P（Tt）表示在t时间内没有顾客到达的概率，即P0(t)。根据式（11-3）有,P (Tt) = P0(t) =et,由此可得出T的概率分布函数 FT (t) = P(Tt) = 1P(Tt) =1P0(t)=1et,相应地顾客到
6、达间隔时间T的概率密度函数为,fT (t) =,=e,式（11-5）和式（11-6）说明：最简单流的顾客到达时间间隔T服从负指数分布规律。具体到计算机通信网，就是分组到达交换节点的时间间隔T服从负指数分布见式（11-6），分组的到达率为。,（2）服务时间的分布函数 设为一个顾客在系统内接受服务的时间，即服务时间。它也是一个随机变量。假设顾客接受服务的过程也满足最简单流的平稳性、稀疏性和独立性。利用上述的方法，同样可推导出服务时间的概率分布函数为,F (t) = 1et,其概率密度函数为 f (t) =et 式中为服务员的服务速率，它的倒数是服务时间的期望值，即平均服务时间,由式（11-7）和式
7、（11-8）可见，服务时间也是负指数分布。 计算机通信网中，由于发送分组的速率为C，所以分组发送时间的概率密度函数为,f (t) =Cect,综上所述，无论是顾客输入过程，还是服务过程，只要是最简单流，则所对应的概率分布函数（输入过程对应的是顾客到达间隔时间的分布函数，服务过程对应的是服务时间的分布函数）都为负指数分布，又称为M分布。,称为M分布的原因是这种分布使排队过程具有马尔柯夫（Markov）性，马尔柯夫最基本的性质是无记忆性。,（3）排队规则 排队系统通常分成下列三种情形。 损失制系统（即时拒绝方式）。 等待制系统（不拒绝方式）。 混合制系统（延时拒绝方式）。,具有等待性质的排队系统（
8、包括等待制系统和混合制系统）相应的服务规则主要有下列几种： 先到先服务 后到先服务 随机服务 优先制服务,以上介绍的几种服务规则，在通信网中一般采取的是先到先服务，但有时根据情况也采用优先制服务方式。,5排队系统的几个主要指标及李特尔（Little）定律,（1）排队系统的几个主要指标 排队长度k（简称队长） 等待时间 服务时间 系统时间s 系统效率 稳定定性,（2）李特尔（Little）定律 对于一个平均到达率为的排队系统，在平均的意义上有,N=,=,上式称为李特尔定律（推导过程从略），其中N为平均队长，为平均系统时间。这里需要说明两个问题：一是此定律是在稳定状态下（即t）得出的，二是它适用于
9、任何种类的排队系统。,排队系统通常使用符号 X/Y/ m/n 常见的排队系统有以下几种。 （1）M/M/m/n排队系统 （2）M/D/1排队系统 （3）M/Ek/l排队系统 （4）M/Hk/1排队系统,6排队系统的分类,1M/M/l排队系统模型,11.1.2 M/M/1排队系统,图11.2 M/M/1排队模型,M/M/1排队系统模型如图11.2所示。M/M/l排队系统有以下几个特点： 顾客到达间隔时间T服从参数为的负指数分布（即顾客流是参数为的泊松流），概率密度函数fT(t)=et (t0)，平均到达间隔时间为l/；,到达的顾客能全部进入系统排队，然后接受服务； 一个服务员（m=1）； 一个顾
10、客的服务时间 服从参数为 的负指数分布，概率密度函数为f (t) =et（t0），平均服务时间1/； 排队强度 =/。,根据推导可以得出M/M/1排队系统稳定时刻（t），队长为k（即系统里有k个顾客）的概率Pk为：,2M/M/l排队系统的指标,P0 =1 Pk = (1)k k1,由Pk 可以求出系统在稳定状态下的指标，包括平均队长、平均系统时间、平均等待时间、系统效率等。 （1）平均队长N 平均队长N 就是系统中的平均顾客数目，是系统内顾客数k的统计平均值（即期望值）。,也可写成,（2）平均系统时间 平均系统时间就是每个顾客在系统内停留的平均时间。,（3）平均等待时间W 平均等待时间是每个顾
11、客的平均排队等待时间。,（4）系统效率 由于M/M/1是单服务员系统，它的系统效率就是系统内有顾客的概率。因此有,由以上推导出的公式可以看出，M/M/1排队系统的主要指标均与排队强度有关，就此说明两个问题： 上述M/M/1排队系统指标的所有公式中的 均要满足1。否则系统将不能稳定工作；,M/M/1排队系统的系统效率为 ，为了提高系统效率，希望 大些；但是从式（11-19）可以推出， 的增大，则平均等待时间也增大，为了减小等待时间，有希望 小些，所以系统效率和平均等待时间之间有矛盾，那么 的取值就要兼顾一下系统效率和平均等待时间，以求获得最佳结果。,11.2.1 图的基本概念 1图的定义 这里所
12、说的图是点线图。点线图是由若干个点和点间的连线所组成，点（也叫端点）是任意设置的，连线则表示不同点之间的联系。严格地说，图的定义为,11.2 图论基础知识,设有点集V=v1，v2，vh和边集E=e1，e2，em，如果对任一边ekE，由V中的一个点对（vi，vj）与之对应，则图可用有序二元组（V，E）表示，记为G = (V，E),另外一个概念就是一个图只由它的点集V、边集E和点与边的关系所确定，而与点的位置、边的长度与形状无关，即一个图所对应的几何图形不是唯一的。,图11.3 图的概念（1）,图11.4 图的概念（2）,链路对于图G = (V，E)，其中k（k2）条边和与之关联的端点依次排成点和
13、边的交替序列，则称该序列为链路。边的数目k成为链路的长度。 路径无重复边和点的链路称为路径。 回路如果路径的起点和终点重合，则称为回路。,2链路、路径与回路,图11.5 有自环与并行边的图,另外还有两个概念： 自环两个端点重合为一点的边称为自环。例如图11.5中的e9。 并行边与同一对端点关联的两条或两条以上的边称为并行边。例如图11.5中的e4和e8为并行边。,（1）有限图和无限图 （2）简单图和复杂图 （3）有向图与无向图 （4）有权图与无权图 （5）连通图与非连通图,3图的分类,图11.6 有向图与无向图,图11.7 连通图与非连通图,任何图都是自己的子图。另外还有两种图： 真子图 生成
14、子图,4子图的概念,图11.8 子图的概念,1树的基本概念 （1）树的定义 一个无回路的连通图称为树。树中的边称为树枝。树枝有树干和树尖之分：若树枝的两个端点都至少与两条边关联，则称该树枝为树干；若树枝的一个端点仅与此边关联，则该树枝为树尖，并称该端点为树叶。,11.2.2 树,（2）树的分类 常见的树的种类有三种：图11.9所示的是一种典型的树，称为根树，通常指定树中某一个点为树根，例如图11.9中的v1为树根。另外还有两种树，就是星树和线树，如图11.10所示。,图11.9 根树,（3）树的性质 从树的定义可以推出，树有如下性质： 具有n个点的树共有n1个树枝； 树中任意两个点之间只存在一
15、条路径； 树是连通的，但去掉任一条边便不连通，即树是最小连通图；, 树无回路，但增加一条边便可得到一个回路； 任一棵树至少有两片树叶，也就是说树至少有两个端的度数为1。,图11.10 星树和线树,（1）支撑树的概念 如果一棵树T为一个连通图G的子图，且包括G中所有的点，则该树称为G的支撑树，也叫生成树。 支撑树有以下两个要点。,2图的支撑树,只有连通图才有支撑树。 一个连通图至少有一棵支撑树。,图11.11 图的支撑树,（2）图的阶和空度 连通图（即联结图）G的支撑树T的树枝数称为图G的阶，记为。若图G有n个端点，则它的阶为n1。 连通图G的连枝数称为图的空度，记为。 图的阶表示主树的大小，取决于图G中的端数。,图的空度的意义有两点： 表示主树覆盖该图的程度， 越小，覆盖程度越高， = 0表示图G就是一棵树； 空度反映图G的联结程度， 越大，连技数越多，图的联结性越好， = 0表示最低的联结性。,割是指图的某些子集，若图是连通的，去掉这种子集就使其成为非连通图；若图是非连通的（由几部分组成），去掉这种子集就使图的部分数增加。根据这种子集的元素不同，割分为割端集和割边集。,11.2.3 割,割端令v是图G的一个端。 割端集去掉几个端后，使非连通图的部分数增加，或使连通图变为非连通图，则这些端的集合称为割端集。,1割端和割端集,图11.12 割端和割
