计算机网络与通信 第2版 教学课件 作者 申普兵 第12章 网络设计基础.ppt

《计算机网络与通信 第2版 教学课件 作者 申普兵 第12章 网络设计基础.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、计算机网络与通信2第12章　网络设计基础排队论基本图论基础知识网络拓扑设计重点：M/M/l排队系统和图论基础3排队论基础排队论基本概念一、排队论与计算机通信网排队论就是利用概率论和随机过程理论，研究随机服务系统内服务机构与顾客需求之间的关系，以便合理地设计和控制排队系统。二、排队系统的一般表示排队服务机构顾客到达顾客离去输入输出排队规则服务规则顾客到达，排队等待，服务结构给予适当的服务以满足客户的需求，顾客离开服务机构，这四个环节组成一个排队模型。5三、排队系统的基本参数1、顾客到达率λ顾客到达率λ是单位时间内平均到达排队系统的顾客数量。λ反映了顾客到达系统的快慢速度。2、服务员数目m服务员数

2、目m是排队系统内可以同时提供服务的设备或窗口数，它表征服务机构的资源。6三、排队系统的基本参数3、服务员服务速率μ服务员服务速率μ是单位时间内由一个服务员进行服务后离开排队系统的平均顾客数。对于m＝1的单服务员系统，μ是系统的服务速率；对于m>1的多服务员系统，系统服务速率为mμ。μ的倒数τ＝1/μ是单个服务员对顾客的平均服务时间。7四、排队系统的三个特征排队系统在运行中的三个过程：顾客输入过程——说明顾客到达的规律。排队过程——与排队规则有关。顾客接受服务过程——取决于服务机构的效率和服务时间的长短。排队系统的特征就是排队系统三个过程的特征。81、顾客到达间隔时间的分布函数顾客的输入过程不同

3、，描述其特征的顾客到达间隔时间的分布函数也不同。我们学习最简单流分布，其顾客输入过程满足三个条件：平稳性：在指定时间间隔t内，到达k个顾客的概率只与t的长度有关。稀疏性：在Δt内到达两个以上顾客的概率为0无后效性（独立性）：在互不重叠的时间间隔中顾客到达的概率是相互独立的。1、顾客到达间隔时间的分布函数当输入过程为最简单流时，在给定时间间隔t内系统有k个顾客到达的概率服从泊松分布：Pk(t)=k=0，1，2，-------设T为顾客到达时间间隔，T的概率分布函数为FT(t)=P(T≤t)=1－P(T>t)=1－P0(t)=1－e－λtT的概率密度函数为fT(t)=λe－λt101、顾客到达间隔

4、时间的分布函数例1：计算机通信网中，分组到达率λ＝35分组/min，输入过程满足最简单流条件，求分组到达时间间隔在0.1min以内的概率和在0.1min~0.3min之间的概率。112、服务时间的分布函数假设顾客接受服务的过程满足最简单流的平稳性、稀疏性和独立性，则服务时间τ的概率分布函数为：Fτ(t)=1－e－μt其概率密度函数为fτ(t)=μe－μt平均服务时间为：τ=1/μ123、排队规则(1)损失制系统（即时拒绝方式）：顾客到达时如果所有服务窗口均被占满，则立即遭到拒绝，不允许顾客排队等待。(2)等待制系统（不拒绝方式）：顾客到达时如果所有服务窗口均被占满，允许顾客排队等待，且队列长度

5、没有限制。(3)混合制系统（延时拒绝方式）：顾客到达时如果所有服务窗口均被占满，允许顾客排队等待，但队列长度有所限制。13排队系统的服务规则先到先服务后到先服务随机服务优先制服务通信网中一般采取先到先服务规则，有时根据情况采用优先制服务方式。14五、排队系统的主要指标排队长度k：某时刻系统中的顾客数，包括正在被服务的顾客。等待时间ω：从顾客等待系统到开始接受服务的时间。服务时间τ：从顾客开始被服务到离开系统的时间间隔。系统时间s：从顾客等待系统至离开的时间，即每个顾客在系统中的停留时间。s=ω+τ15五、排队系统的主要指标系统效率η：即平均窗口占用率。若系统有m个窗口，某时刻有γ个窗口被占用，

6、则γ/m就是占用率。η=γ/m稳定性ρ：也叫排队强度。ρ=λ/mμ若ρ<1,顾客到达率小于系统的服务速率，系统是稳定的，可以采用不拒绝方式。若ρ≥1，平均等待系统的顾客数大于离开系统的顾客数，应当采取拒绝方式。16李特尔（Little）定律对于一个平均到达率为λ的排队系统有：N=k=λs其中N为平均队列长度，s为平均系统时间。此定律是在稳定状态下（t→∞）得出的，它适用于任何种类的排队系统。17六、排队系统的分类排队系统通常用符号X/Y/m/n表示。其中X是顾客到达间隔时间的分布，Y是服务时间的分布，m是服务员个数，n为排队系统中允许的顾客数，也称为截止队长。常用的分布符号：M——负指数时间分

7、布；D——定长时间分布；Ek——k阶爱尔兰时间分布；Hk——k阶超指数时间分布。18常见的排队系统1、M／M／m／n排队系统顾客到达间隔时间和服务时间的分布均为负指数分布。当n=∞时，队长不受限，为等待制排队系统(不拒绝方式)，表示为M／M／m。当n<∞时，为混合制排队系统(延时拒绝方式)。当n=m时，为损失制系统(即时拒绝方式)。当m=l且n=∞，为M／M／l系统，是最简单的排队系统。19常见的