计算机网络与通信 申普兵 第11章 网络设计基础

《计算机网络与通信 申普兵 第11章 网络设计基础》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第11章网络设计基础排队论基础11.1图论基础知识11.2网络拓扑设计11.3【本章内容简介】本章首先介绍计算机通信网络设计的基础知识：排队论和图论。然后讨论计算机通信网络拓扑设计。【本章重点难点】学习本章时，应注重掌握有关排队论和图论的一些基本定义和基本分析方法，学会如何运用这些基础知识进行计算机通信网络的拓扑设计。11.1排队论基础排队论又称随机服务系统理论，它广泛应用于计算机通信领域，是计算机通信网的基础理论之一。1．排队论与计算机通信网排队是日常生活中常见的现象。由要求随机性服务的顾客和服务机构两方面构成的系统，称为随机服务系

2、统或排队系统。11.1.1排队论基本概念顾客需求的随机性和服务设施的有限性是产生排队现象的根本原因。排队论就是利用概率论和随机过程理论，研究随机服务系统内服务机构与顾客需求之间的关系。以便合理地设计和控制排队系统。计算机通信网就是一个大的排队系统。排队系统尽管千差万别，但都可以抽象为顾客到达服务机构，若服务员有空闲，便立刻得服务，若服务员不空闲，则需排队等待服务员有空闲时再接受服务，服务完后离开服务机构。2．排队系统的一般表示图11.1排队模型排队系统的基本参数包括：顾客到达率，服务员数目m和服务员服务速率。（1）顾客到达率顾客

3、到达率是单位时间内平均到达排队系统的顾客数量（具体到计算机通信网，就是单位时间内到达分组交换节点的分组数量）。反映了顾客到达系统的快慢速度，越大，说明系统的负载越重。3．排队系统的基本参数一般排队系统中顾客的到达是随机的，即任意相邻两顾客到的时间间隔Ti是一个随机变量。Ti的统计平均值就是顾客到达的平均时间间隔达，其倒数即为顾客到达率=若在观察时间t内有n（t）个顾客到达，在平稳条件下，有=（2）服务员数目m服务员数目m就是排队系统内可以同时提供服务的设备或窗口数，它表征服务机构的资源。在计算机通信网中，m常指分组交换节点

4、的输出信道数量。（3）服务员服务速率服务员服务速率指的是单位时间内由一个服务员进行服务所离开排队系统的平均顾客数，对于m=1的单服务员系统，就是系统的服务速率；对于m＞l的多服务员系统，则系统的服务速率为m，即单位时间内接受服务后离开系统的平均顾客数为m。假设每个服务员的服务速率均为，的倒数就是单个服务员对顾客的平均服务时间，也就是一个顾客在系统内接受服务的平均时间。4．排队系统的三个特征排队系统在运行中包括三个过程：顾客输入过程排队过程顾客接受服务（然后离去）的过程（1）顾客到达间隔时间的分布函数顾客的输入过程不同，用

5、以描述输入过程特征的顾客到达间隔时间的分布函数也就不同。如果顾客的输入过程满足下述三个条件，称该输入为最简单流。①平稳性。②稀疏性。③无后效性（或独立性）。根据推导得出，当输入过程为最简单流时，在给定时间间隔t内系统有k个顾客到达的概率为Pk(t)=k=0，1，2，…式（11-3）称为泊松分布。由此可见，最简单流在t时间内到达系统的顾客数量服从泊松分布。根据式（11-3）可进一步推导出顾客到达间隔时间的分布函数。设T为顾客到达时间间隔，它是一个随机变量，可以取0～的连续值。根据概率论中连续型随机变量的分布函数定义，T的概率分布函数为

6、FT(t)=P(T≤t)若T＞t，说明顾客到达间隔时间大于所选定的时间长度t，则P（T＞t）表示在t时间内没有顾客到达的概率，即P0(t)。根据式（11-3）有P(T＞t)=P0(t)=e−t由此可得出T的概率分布函数FT(t)=P(T≤t)=1−P(T＞t)=1−P0(t)=1−e−t相应地顾客到达间隔时间T的概率密度函数为fT(t)==e−式（11-5）和式（11-6）说明：最简单流的顾客到达时间间隔T服从负指数分布规律。具体到计算机通信网，就是分组到达交换节点的时间间隔T服从负指数分布[见式（11-6），分组的到达率为

7、]。（2）服务时间的分布函数设为一个顾客在系统内接受服务的时间，即服务时间。它也是一个随机变量。假设顾客接受服务的过程也满足最简单流的平稳性、稀疏性和独立性。利用上述的方法，同样可推导出服务时间的概率分布函数为Fτ(t)=1−e−t其概率密度函数为f(t)=e−t式中为服务员的服务速率，它的倒数是服务时间的期望值，即平均服务时间由式（11-7）和式（11-8）可见，服务时间也是负指数分布。计算机通信网中，由于发送分组的速率为C，所以分组发送时间的概率密度函数为f(t)=Ce−ct综上所述，无论是顾客输入过程

8、，还是服务过程，只要是最简单流，则所对应的概率分布函数（输入过程对应的是顾客到达间隔时间的分布函数，服务过程对应的是服务时间的分布函数）都为负指数分布，又称为M分布。称为M分布的原因是这种分布使排队过程具有马尔柯夫（Ma