计算机网络与通信申普兵第11章网络设计基础课件教学.pptVIP

第11章 网络设计基础 【本章内容简介】本章首先介绍计算机通信网络设计的基础知识：排队论和图论。然后讨论计算机通信网络拓扑设计。 【本章重点难点】学习本章时，应注重掌握有关排队论和图论的一些基本定义和基本分析方法，学会如何运用这些基础知识进行计算机通信网络的拓扑设计。 11.1 排队论基础 排队论又称随机服务系统理论，它广泛应用于计算机通信领域，是计算机通信网的基础理论之一。 11.1.1 排队论基本概念 1．排队论与计算机通信网 排队是日常生活中常见的现象。 由要求随机性服务的顾客和服务机构两方面构成的系统，称为随机服务系统或排队系统。 顾客需求的随机性和服务设施的有限性是产生排队现象的根本原因。排队论就是利用概率论和随机过程理论，研究随机服务系统内服务机构与顾客需求之间的关系。以便合理地设计和控制排队系统。 计算机通信网就是一个大的排队系统。 2．排队系统的一般表示 排队系统尽管千差万别，但都可以抽象为顾客到达服务机构，若服务员有空闲，便立刻得服务，若服务员不空闲，则需排队等待服务员有空闲时再接受服务，服务完后离开服务机构。 3．排队系统的基本参数 排队系统的基本参数包括：顾客到达率?，服务员数目m和服务员服务速率?。 （1）顾客到达率? 顾客到达率???是单位时间内平均到达排队系统的顾客数量（具体到计算机通信网，?就是单位时间内到达分组交换节点的分组数量）。?反映了顾客到达系统的快慢速度，?越大，说明系统的负载越重。 一般排队系统中顾客的到达是随机的，即任意相邻两顾客到的时间间隔Ti是一个随机变量。Ti的统计平均值就是顾客到达的平均时间间隔达，其倒数即为顾客到达率 ?= 若在观察时间t内有n（t）个顾客到达，在平稳条件下，有 ?= （2）服务员数目m 服务员数目m就是排队系统内可以同时提供服务的设备或窗口数，它表征服务机构的资源。在计算机通信网中，m常指分组交换节点的输出信道数量。 （3）服务员服务速率? 服务员服务速率?指的是单位时间内由一个服务员进行服务所离开排队系统的平均顾客数，对于m=1的单服务员系统，?就是系统的服务速率；对于m＞l的多服务员系统，则系统的服务速率为m?，即单位时间内接受服务后离开系统的平均顾客数为m?。 假设每个服务员的服务速率均为? ，?的倒数 就是单个服务员对顾客的平均服务时间，也就是一个顾客在系统内接受服务的平均时间。 4．排队系统的三个特征 排队系统在运行中包括三个过程： 顾客输入过程 排队过程 顾客接受服务（然后离去）的过程 （1）顾客到达间隔时间的分布函数 顾客的输入过程不同，用以描述输入过程特征的顾客到达间隔时间的分布函数也就不同。 如果顾客的输入过程满足下述三个条件，称该输入为最简单流。 ① 平稳性。 ② 稀疏性。 ③ 无后效性（或独立性）。 根据推导得出，当输入过程为最简单流时，在给定时间间隔t内系统有k个顾客到达的概率为 式（11-3）称为泊松分布。由此可见，最简单流在t时间内到达系统的顾客数量服从泊松分布。根据式（11-3）可进一步推导出顾客到达间隔时间的分布函数。 设T为顾客到达时间间隔，它是一个随机变量，可以取0～?的连续值。根据概率论中连续型随机变量的分布函数定义，T的概率分布函数为 FT (t)=P (T≤t) 若T＞t，说明顾客到达间隔时间大于所选定的时间长度t，则P（T＞t）表示在t时间内没有顾客到达的概率，即P0(t)。根据式（11-3）有 由此可得出T的概率分布函数 FT (t) = P(T≤t) = 1?P(T＞t) =1?P0(t)=1?e??t 相应地顾客到达间隔时间T的概率密度函数为 式（11-5）和式（11-6）说明：最简单流的顾客到达时间间隔T服从负指数分布规律。具体到计算机通信网，就是分组到达交换节点的时间间隔T服从负指数分布[见式（11-6），分组的到达率为?]。 （2）服务时间的分布函数 设?为一个顾客在系统内接受服务的时间，即服务时间。它也是一个随机变量。假设顾客接受服务的过程也满足最简单流的平稳性、稀疏性和独立性。利用上述的方法，同样可推导出服务时间?的概率分布函数