经典排队论课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,排队论的发展史,初期,(10,s-40,s):,主要研究应用于电话网和远程通信系统等无队列的排队系统,(,损失制,),中期,(40,s-60,s):,推广应用到军事、运输、生产、社会服务等领域，主要研究有队列,(,等待制,),的排队系统和排队网络,近期,(60,s-,今,):,主要研究大规模复杂排队系统的理论分析、数值分析和近似分析，尤其注重对业务突发性和带有各种网络控制的排队系统的研究,1,1909: Erlang,发表他的有关排队论的第一篇论文,;,1917: Erlang,发表著名的论文,“Solution of Some Problems in the Theory of Probability of Significance in Automatic Telephone Exchanges”,1936-47: Palm,发表论文 “,Repairmen in Serving,Automatic Machines”,1951: Kendall,发表论文,”,排队论中的某些问题,”,在,1953,年提出使用,Kendall,记号,;,1953-57: Kendall, Lindley, Pollaczek & Khinchin,用嵌入,Markov,链的方法研究,M/G/1,排队模型,;,􀂙,2,1961: Little,提出,Little,公式,;,1975/6: Kleinrock,著的两卷,”Queueing Systems”,出版,;,1982: Wolff,提出和推广和,PASTA (,Poisson,Arrivals,See Time Averages,),准则,1981: Neuts,引进矩阵分析方法,;,在以后的时间里,有大量的描述突发和具有,相关性通信业务的模型,(,如流体模型,MMPP,模型等,),发表,;,1990,后,:,提出长相关自相似的业务量模型,.,3,Kleinrock,Wolff,4,内容:,1. 基本概念和预备知识,2,.,Poisson,到达指数服务的排队系统(,M/M/1),3,.,M/,M/m(n),问题,4.,各种测度和指标,5.,提高网效率的一些措施,6.,优先权服务系统,只涉及上世纪,60,年代以前的成果,此后的成果将在,”,现代通信中的排队论,”,课程中介绍,5,以上内容只是排队论的很少的一部分,也是最初等,的一部分,.,除了从,理论分析、数值分析和近似分析,各方向,(,这些是从数学学科的角度,),发展外,近二十,年来，在技术学科特别是通信学科的激励下,尤其,注重对排队输入流,(,通信业务流,),业务突发性和带,有各种网络控制的排队系统的研究,.,可以毫不夸张地说,通信理论的发展,离不开排队论,.,6,排队论所研究的问题有,:,(1),等待时间的,分布,平均,等待时间;,(2),系统时间(也称逗留时间)的,分布,平均,系统时,间及系统时间的,方差,(,时延抖动,);,(3),在系统中的顾客数(也称系统占有数)的,分布,及,均值,;,(4),等待顾客数的,分布,及其,均值,;,(5),服务器忙着(或空闲)的,概率,;,(6),忙期长度的,分布,及其,均值,;,(7),在忙期被服务的顾客数的,分布,以及它的,均值,。,7,1. 基本概念和预备知识,概率知识：,事件,A，B,它可推广到无穷多个事件的情形：,(,概率加法定理,),8,事件,A，B,该公式称,全概率公式,若对事件,A，B,有,则称,A,与,B,相互独立,。,9,随机变量,X,的分布函数,概率分布的,母函数,概率分布密度的,Laplace,变换,X,1,X,2,相互独立,则在离散时,和的母函数等,于母函数的乘积;在连续时,和的,Laplace,变,换,等于,Laplace,变换,的乘积,.,10,Erlang,Kendall,其中,:,X-,到达分布,;Y-,服务时间分布,;Z-,服务员个数,A-,等待空间大小,B-,顾客源的限制,;C-,服务规则,Kendall,记号,:X/Y/Z/A/B/C,11,2,.,Poisson,到达指数服务的排队系统,指数分布,指数分布和普松过程在排队论中有着特殊的地位。,这是因为,一方面指数分布在连续型概率分布中是,唯一的具有无记忆性质的分布,普松分布又和指数,分布有着紧密的关系。另一方面,实验证明普松分,布是电话呼叫数概率分布的一种比较好的近似,而,指数分布又是电话通话时间概率分布的一种好的近,似,它们在排队论的发展历史中起了很大的作用并继续起着重要的作用。,12,定义,一个随机变量,x,当且仅当对任意的,满足条件,时，则称,x,的分布是,无记忆,的。无记忆性的直观理解是:一个物体的使用寿命是指被使用的时间，它是一个随机变量。如果该物体不论被使用了多久，其剩余寿命的分布与总寿命的分布完全相同，那么这种寿命分布是无记忆的，体现了永远年轻。,13,按条件概率定义，我们有,如果随机变量,x,是无记忆的，那么,反之，如果随机变量的分布满足(*)，则该分布是无记忆的。,14,因为指数分布的余分布函数为,而,故指数分布是无记忆的。当服务时间是指数分,布时，则不论顾客占用服务台多久，其剩余的,服务时间仍为指数分布的随机变量。,在连续型,随机变量中指数分布是唯一的具有无记忆分布,的随机变量,。在离散随机变量中，,几何分布,是,唯一的具有无记忆性质的随机变量,。,15,Poisson,过程,定义,若用,n,(t),表示从0开始到时刻,t,为止已经发生的事件的数目，则称随机过程,n,(t),t,0,为计数过程。,一般地说,在计数过程的记号上还应标以计数的起始时刻,如果过程的统计特性与起始时刻无关,则称过程为平稳的,.,下面我们讨论的,除非特别指明都是平稳过程。显然,计数过程,n,(t),取非负的整数值,并且,n,(t),是,t,的非降函数。,对于 是在区间(,s,t,内发生的事件数,量,称为,n,(t),在区间(,s,t,的增量。如当,独立,则称有独立增量,.,16,Poisson,过程定义(1):一计数过程,n,(t),如果满足,1.,n,(0)=0;,2.,n,(t),t,0,有独立增量;,3.发生在任何长为,t,的区间中的事件数服从参数为,的,Poisson,分布:,P,n,(t+s)-,n,(s)=n=,则称计数过程,n,(t),是率(参数)为,(0),的,Poisson,过,程。,17,Poisson,过程定义(2):一计数过程,n,(t),如果满足,1.,n,(0)=0;,2.,n,(t),t,0,是平稳的，且有独立增量;,3.,P,n,(h)=1= h+o(h);,4.P,n,(h),2=o(h)。,则称计数过程,n,(t),是参数为,( 0),的,Poisson,过程,。,18,在一个时间区间内的顾客的到达数与时间起点无关叫,平稳性,;,顾客的到达时刻相互独立称,无后效性,;在很短的时间间隔内到达两个以上顾客的概率可认为是0,这叫,稀疏性,.满足以上三个条件的随机流称为,简单流,.简单流的,到达间隔是负指数分布,的,且在一段时间内到达的顾客数是,普松分布,.,现证明,简单流的到达间隔是负指数分布,:设到达间隔为,t,把0,t),分成,N,等份,每份的长度为,在,0,t),都未到达,而在时刻,t,有顾客到达了的概率为,19,再证明,当到达间隔是指数分布时,在时间间隔,T,内的,到达数是普松分布,:,把,时间间隔,T,分成,N,等份,在这,N,个小区间内,有,k,个顾客顾客:,20,现已证明,:,简单流的到达间隔是负指数分布,;,当到达间隔是指数分布时,在时间间隔,T,内,的到达数是普松分布,.,在一段时间内,电话的呼叫是简单流,因为,顾客的到达数与时间起点无关,;,顾客的到达,时刻相互独立,;,在很短的时间间隔内到达两,个以上顾客的概率可认为是0,.,21,Poisson,过程的,性质,如下:,1.令 和 分别是具有参,数,和,的独立,Poisson,过程,则,N,(t),t,0,是率为,+,的,Poisson,过程。,证明:,Poisson,过程的分布母函数：,的分布母函数=,22,2.对于参数为,的,Poisson,过程，假设发生的,每个事件独立地以概率,p,做了记录，未做记,录的概率为1-,p。,令,n,1,(t),是到,t,为止被做了记,录的事件数，而,n,2,(t),是未被记录的事件数,则 和 分别是参数,为 和 的,Poisson,分布且相互独立.,23,证明,:,24,这两条性质说的是:,(1)独立,Poisson,过程的和仍是,Poisson,过程,而,且“和过程”的参数为加项过程的参数之和;,(2),Poisson,过程的分支也是,Poisson,过程,而且,各分支过程的参数是分支概率乘以原过程,的参数.,25,Little,定理:,在排队系统中的平均,顾客数=顾客的平均到达率,平均逗留时间,:,E,N,=,E,s,证明,:,Little,26,A(t)=,(0,t),内顾客的到达数,则在(0,t),内的平均到达率为,。,D(t)=,在(0,t),内离开系统的顾客数。,N(t)=,在时刻,t，,系统中的顾客数,于是,N(t)=A(t)-D(t)。,图中两条折线之间的面积表示在,(0,t),内所有顾客花费在系统中的总,时间,记为,(t)。,Tt=,在(0,t),内每一个顾客在系统中的平均逗留时间(对(0,t),内,全部顾客取平均)，于是,.,ENt=,在(0,t),内,系统中的平均顾客数,于是,令,t,取极限,得 这里,EN,是排队系统中的平均顾客数,T,是一个顾客在系统中的平均逗留时间,是顾客的平均到达率。,27,这个结论与,到达间隔分布,服务时间分布,服务员个数以及,排队规则,都无关。,28,排队系统(,M/M/1),是指到达间隔,(,到达数,),服从负指数,(,普松,),分布,服务时间服从负指数,分布,服务窗口数为,1,的排队系统,.,设到达分布的参数为,服务时间,分布的参数为,时间间隔,t(,不失一般性,可设为,(0,t,区间,),内有,n,个顾客到达的概率记为,.,现考察区间,它可看成,于是在内到达,n,个顾客这个事件可分解为以下事件的并,:,在 内到达,n+1,个顾客,在 内离开一个顾客,在 内到达,n-1,个顾客,在 内又到,因为 的概率= ; 的概率=,的概率= ;,的概率=,Markov,29,因为 的概率= ; 的概率=,的概率= ;,的概率=,到达一个顾客,在 内到达,n,个顾客,在 内,顾客的到达数和离开数相等,.,故而可列出以下瞬态,方程,:,30,在时刻 系统中有,n,个顾客是由以下三个事件组成,:,1),在时刻,t,有,N+1,个顾客,在 的时间里没有到达但离开一个顾客,;,2),在时刻,t,有,N-1,个顾客,在 的时间里到达一个顾客但没有离开的顾客,;,2),在时刻,t,有,N,个顾客,在 的时间里到达和离去的顾客数相等,(,包括未到和未离去,).,31,在 内到达一个顾客的概率为,没有到达的概率为,在 内离开一个顾客的概率为,没有顾客离开的概率为,32,为,m,阶,Bessel,函数方程,瞬态方程的解为,33,下面我们考察随机稳态解。我们定义,于是有,这是一个递推公式,经逐次递推得,再由归一化条件求得 ,当然这一切必须在,=/n=,(1-) =,34,M/M/1,的稳态解是,那么平均队长是,由,Little,定理,时延为,35,在稳定状态下指数系统的平衡方程法,设所有到达间隔和服务时间都是指数分布的,那么从任何时刻直到状态变化的这段时间也是指数分布的。以前我们写出,P(t),的微分方程并让,而得到稳态方程,我们也可以直接列出方程。在稳定情况下,进入状态的率必须等于从同一个状态离开的率,即进入和离开的率必须平衡。对于,M/M/1，,以下的表是平衡的概念。,36,状态 离开率 进入率,0,P,0,= P,1,1 (+)P,1,= P,0,+P,2,2 (+)P,2,= P1+P,3,3 (+)P,3,= P2+P,4, ,n (+)P,n,= P,n-1,+P,n+1, ,这些方程称为“,平衡方程,”,。,37,生灭过程,:,它也是一种马尔科夫过程,只是状态,只向相邻的状态转移,.,在连续时间的情况下,状,态有以下转移率矩阵,:,38,更一般地,对于生-灭过程,我们有,n,=,系统处在,n,时的到达率,n,=,系统处在,n,时的,服务率.那么由生-灭平衡概念,得,状态 离开率 进入,0,0,P,0,= ,1,P,1,1 (,1,+,1,)P,1,= ,0,P,0,+,2,P,2,2 (,2,+,2,)P,2,= ,1,P,1,+,3,P,3,3 (,3,+,3,)P,3,= ,2,P,2,+4P,4, ,n (,n,+,n,)P,n,= ,n-1,P,n-1+,n+1,P,n+1, ,39,在这情形,我们有,如此递推得,得,40,为使稳定解存在,必须要有,否则,P0=0,P1=0,P2=0,等等。,41,3.,M/,M/m(n),问题(,话务工程中的计算方法),在话务工程中,经典排队论被广泛地应用,其中爱尔兰(,Erlang)-B,公式和恩格塞特(,Engset),公式在计算中起着重要的作用。在较长的时间内,使用这两个公式进行某种定量分析时依靠查表。国外的有些大学和研究机构早已把话务工程中涉及的数学计算编成软件,如波兰波兹南大学的,J.Kubasik(1985),AT&T,的,D.L.Jagerman(1984,年)编了有关软件。,现在我们将介绍这方面的内容。,42,有限源,设总的用户数为,N，,中继线数为,n，,为每个用户呼叫的到达率, 为服务率,如果总的话务量为,A，,则,a.,损失制,如果没有缓冲器,那麽一旦系统的中继线全被占用,来到的呼叫将被拒绝,这就是损失制(式)。在损失制中我们总是假定,N,n(,不然就无损失可言)。按设定我们有,43,系统的状态分布为,44,下面介绍呼损概率。,应当说明,在有限源损失制中,有两种意义的损失率,其一为按时间计算的损失率,那就是全部,服务台被占的概率 另一种意义的损失率是按呼叫计算的损失率,那就是的,Engset,公式,它的意义是单位时间损失的平均呼叫数 与单位时间到达的平均呼叫数 之比:,45,46,b.,等待制,设系统的缓冲器容量为,N,也就是说,如果系统的中继线全被占用,再来的呼叫总可以等待到有线路空出而得到通信。在这种制式下无损失而只有时延。按定义有,47,48,需要等待的概率为,PW0=,系统中的平均顾客数(平均占有数)为,平均等待数为,49,无限源,设到达率=,，,服务率=,，,中继线数=,n。,a.,损失制,状态分布为,50,阻塞(损失)概率 定义为顾客被拒绝进入队列的概率。因为按顾客计算的阻塞率是损失的顾客数与要求服务的顾客数之比,假定等待空间容量为,K，,当系统已达到稳定时,在长为,的时间内能进入系统的平均顾客数为,因为当系统在状态,K,时顾客的到达将被阻塞,顾客被阻塞的平均数为,所以,在,M/M/n,的情况下,51,b.,等待制,52,53,54,c.,混合制(,M/M/n/m),55,特别对于单服务损失制排队,M/M/1/K，,56,下面我们推导一个比上式更一般的式子的递推计算公式。对于有限容量的,(,参数依赖状态的,)M/M/1/K,系统,57,以上利用了关系式,:,当,时,记,则有,58,按时间计算的阻塞率,因为在这个系统中到达率不变,所以两种意义,的阻塞率是相同的。,59,例,1,某商店有,3,个服务员,每个服务员在每一时刻只能服务一个顾客,服务时间为负指数分布,均值为,2.5,分钟,.,顾客到达为普松分布,平均每分钟到达,1.2,人,.,设无等待,求顾客到达而未被服务所占的百分比,;,若,要求到达而未被服务所占的比例小于,5%,问需几个服务员,?,解,:,排队系统类型,:M/M/3.,60,设需,n,个服务员,则,61,例,2,某厂有,N=20,台机床,每台机床平均每隔,1,小时,就要损坏,维修人员修复一台机床的平均时间为,0.1,小时,.,如一台机床由于等待维修不能开工造成的损,失为,C1=180,元,/,时,.,维修工的工资为,C2=6,元,/,小时,.,问,最好保留几位维修工可使费用,(,损失加工资,),最少,?,解,:,系统是,M/M/n/N/N.,排队系统的状态是损坏的机器数,.,上述公式里的,62,如果发生故障的机床数为,j,等待维修的机床数为,(j-n),平均数为,由此造成的损失为,:,如果损坏的机床数少于修理工的数目,则就有空闲,的修理工,他们空闲着但工资照拿,对老板来说有损,失,:,总损失,=,这里都指每小时的损失,.,63,总损失,n=3,0.3389,1.2126,68.2696,n=4,0.0683,2.188,25.4287,n=5*,0.0129,3.183,21.4237,n=6,0.0022,4.182,25.4799,n=7,0.0003,5.16,31.1466,64,例,3,某维修站有,2,名工人,站内可放,5,台机器,.,设待修,机器的到达间隔与维修时间皆负指数分布,平均每隔,5,分钟就有一部机器送来,每部机器的修理时间平均,为,10,分钟,.,求,1),维修站里没有机器的概率,;2),维修站,里场地有空的概率,;3),进入维修站的平均机器数,;,4),机器在维修站内的平均等待时间,.,解,:,这是,M/M/2/5/FCFS,问题,.,65,66,例,4,售票处有三个窗口,顾客以每分钟,4,人的平均速,度按普松规律到达,服务时间按指数分布,均值为,0.5,分钟,.,求,1),售票处空闲的概率,;2),平均队长,;3),平均等,待时间和逗留时间,.,解,:,为,M/M/3/,67,68,平均逗留时间,:,平均等待时间,69,例,5,有一洗车间,服务速率为,60,辆,/,小时,洗车间外可,停,4,辆车,汽车到达的速率为,40,辆,/,小时,.,求,1),汽车冲洗间无车的概率,;2),停满车的概率,;,3),汽车到达此冲洗处的平均数目,;,4),平均等待数目,;5),平均逗留时间,;6),平均等待时间,.,解,:M/M/1/5,类型,.,70,71,例,6,某商店每天开,10,个小时,一天平均有,90,个顾客,到达商店,商店的服务是平均每小时服务,10,个顾客,若假定顾客到达服从普松规律,服务时间服从负指,数分布,.,求,1),在商店等待服务的顾客平均数,;2),在队,长中多于,2,个顾客的概率,;3),在商店中的平均顾客数,;,4),若希望商店的平均顾客数少到,2,人,平均服务速度,需提高到多少,?,解,:M/M/1/,问题,队长分布为,72,4.,各种测度和指标,业务量,是指在指定时间内线路被占用的总时间.若某线路有,m,条信道,第,r,条信道被占 秒,则,m,条信道(或该线路)的业务量为,.,业务的强度,通常指,呼叫量,是线路占用时间与观察时间之比,单位是,Erlang.,一天内最忙的一小时内的呼叫量称日呼叫量.一年内取三十天,取这些天的日呼叫量的平均值称为年呼叫量或,基准呼叫量,.,73,时间阻塞率,是在总观察时间内阻塞时间所占的百 分比,它也就是截止队长为,n,时的拒绝概率,记为,p,n,.,呼叫阻塞率,是被拒绝的呼叫次数占总呼叫次数的百分比,通常称为呼损的就是这个呼叫阻塞率,记为,p,c,.,从排队论看,p,n,相当于随机时刻观察系统处于状态,n,的概率,p,c,相当于顾客到达时刻观察系统处于状态,n,的概率.(,顾客到达时,系统处于状态n将被拒绝进入系统,其概率就是拒绝的百分比.),一般说来,由于阻塞期间可能没有顾客到达,故,p,c,p,n,.,74,时延,指消息进入网内后直到被利用完毕所需的时间,这包括等待时间,服务时间,传输时延和处理时间.,在所要求的呼叫中,有一部分被拒绝,通常以单位时间通过的业务量为,通过量,即,(Erlang),其中,a,是呼叫量,p,c,是呼损.也有把单位时间内通过的呼叫次数作为通过量,即,(,次/秒).,信道的利用率:,其中 是线路的容量.,75,今考虑用户数为有限值,N,的准随机呼叫,令 为每个用户在单位时间内的平均呼叫次数，截止队长为,n.,当,r,个用户已被接受排队服务时,到达率为(,N-r) ,则呼叫阻塞率为,其中分子是被阻塞的呼叫次数,分母是总呼叫次数.当,N,时,所有,r,与,N,相比均可忽略,且,则上式成为,在,N,有限时,p,c,p,n,.,当,N n,时,p,c,和,p,n,差别不大.从统计测量来说,用,p,c,比用,p,n,方便.在,Nn,的情况下,准随机呼叫可近似成随机呼叫.,76,设网内的源宿端间某有向径上有,r,条边,边上呼损,(i=1,2,r),源宿端间的呼损将为,对于数字线路,其容量也可用路数,m,来表示,它是,线路上传输速率,R,与信息传输速率,r,之比:,通信网中有,M,条边,相当于,M,条线路,则全网效率,为,总通过量为,77,业务分析步骤:,1)建立模型;,2)定义状态变量;,3)列出状态方程;,4)求解状态方程;,最后计算所需的性能指标,.,78,业务分析举例,1）,主叫线即时拒绝系统,79,80,系统的线路利用率,换个角度,(0,1),(1,0)时通过一个,(1,1)时通过2个.对于,M/M/2/2,系统,81,2,）公共备线即时拒绝系统,82,83,84,85,86,87,88,A,端用户的呼损,B,端用户的呼损,简化：,线路的利用率：,若 得近似式,：,89,3）,两次排队问题,输入为普松流，到达率 包/秒。每包平均比,特数为,a，,信包长为指数分布。,r,和,s,分别为在,C,1,和,C,2,前的队长，信道,C,1,和,C,2,的服务率分别是,90,91,平均时延,效率,92,5.,提高网效率的一些措施,(1) 大群化效应,(2) 延迟效应,(3) 综合效应,(4) 迂回效应,93,大群化效应,:,资源集中利用优于分散经营.,从,及,(,其中,a=,是呼叫量,m,为信道数)可算出:,大群化效应之例,94,阻塞率 值,要求,0.1,时,可得,当,a=1(Erlang),时,需,m=3,此时,=0.0625,=(1- )/3=31%,当,a=10(Erlang),时,需,m=13,此时,=0.0843,=10(1-0.0843)/13=70.5%,当,a=100(Erlang),时,需,m=96,此,=0.1017,=100,.,系统业务量愈大节省愈明显.,ma,1,10,100,1,0.5,0.91,0.99,3,0.0625,0.75,0.97,10,0.215,0.90,30,0.70,100,0.076,95,A=100,A=10,A=5,A=1,P,m,3,13,96,96,在信息交换网中主要关心时延.已知系统时间,(,时延,),为,信道效率为,=,.,若把,n,个到达率为,的业务集中到一个大容量的线路中去,若要保持,或效率,不变,则信道容量,C,也要增到,n,倍,使,和,都增到,n,倍,此时时延可减小到,1/,n:,不变,而,成了,n,.,97,反之若保持 不变,例如10个分别排队的业务,各,自的,=,=0.5,则 =2/,集中在一起时,总到达,率,=10,服务率,则,即容量只要增到5.5倍就可使时延不变.集中后,的效率为,98,延迟效应,利用混合制,可降低呼损.例如,M/M/m/n,排队模型,其中,n=m+1,即只设一个等待位置.由,计算得下表,99,阻塞率,p,c,值(,n=m+1),括号内数字是,M/M/m,时的相应值.,ma,1,10,1,0.33(0.5),0.90(0.909,2,0.09(0.2),0.8039(0.8197),3,0.02(0.0625),0.7093(0.7321),10,0.1717(0.2141),12,0.09,100,101,由此可见只要容许一个呼叫等待,呼损,就明显下降,付出的代价是有的顾客须,等待的时间,当,m,很大时,等待时间是很,短的.并且在保证,Pc,0.1,的条件下,以,a=1(Erlang),为例,延迟拒绝比瞬时拒绝,可少用一条信道,而效率从31%提高到45.6%.,102,综合效应,综合是指不同性质的业务综合起来在一条线路上传输.例如数字与模拟,宽带与窄带,实时的与非实时的,高速与低速业务等.以宽带与窄带综合为例:,设一条线路能容纳,m,路窄带,信号或,s,路宽带,信号,而一条宽带信号占,n,条窄带信道,并令,s=m/n=,整数.再设窄带与宽带业务的到达率分别为,服务率分别为,则呼叫量分别为,.,取损失制,(,r1,r2),为系统的状态,其中,r1,为系统中窄带业务数,r2,为宽带业务数.0,r1,m,0,r2,s.,103,104,系统的稳态状态方程为,未占满,留下空位小于等于一路宽带,105,窄带信号呼损的条件是,m,条信道都占满,即,r1+nr2=m,则呼损为,宽带信号呼损的条件是空闲信道不足,n,条,即,r1+nr2m-n,则呼损为,信道利用率是,106,总呼叫量为,宽带所占的比例为,R=1全是宽带,R=0 全是窄,带。,在,A,一定的条件下呼损是,R,的函数.,以,m=12,n=3,为例计算,A=3,6,12,时的,p,c1,和,p,c2,得下图：,107,迂回效应,最短路径一般作为站间业务传输的主路由,可用径可作为迂回路由.今举下例来说明迂回效应.设站间业务量都是1(,Erlang),各边均两条链路.当无迂回路由时,由,Erlang,公式,所有呼叫的呼损皆为,迂回效应举例,108,若按以下路由表选择迂回电路,12,142 23,243 34,324,21,231 32,312 43,413,41,421 13,123 24,214,14,134 31,341 42,432,由于对称,各边的阻塞都相同,记为,B.,从路由表知,3-2与1-3间的溢出业务,将经过边,e,12,.,这些业务实际通过,e,12,的将各为,(3-2,间阻塞,3-1和1-2未阻塞或1-3阻塞,1-2和2-3均未阻塞).1-2间的直通业务实际通过,e,12,的为(1-,B),共计(1-,B)+2 (Erlang),相当于需求的呼叫量是,a=1+2B(1-B)(Erlang),其它边上也是如此.,109,因,m=2,由,Erlang,公式,阻塞率应为,算得,B=0.28.,因此,若允许作二次迂回,例如以下路由表,110,若允许作二次迂回,例如以下路由表,12,142,132 23,243,213,34,324,314 41,421,431,13,123,143 24,214,234,21,231,241 32,312,342,43,413,423 14,134,124,31,341,321 42,432,412,用同样方法,先算得,B=0.3,各站间呼叫的呼损为,p,c2,=0.078.,111,上面只是说明如果允许有迂回路由,那末端-端的阻塞率将降低,从,无迂回的0.2,到,一次迂回的0.11,到,二次迂回的0.078,.然而以上计算是建立在溢出业务量也是普松分布的假定下的.,112,更,严格,的算法将是:,设(,r,s),是状态,其中,r,是主路由的占线数,s,是溢出而在迂回路由上的占线数.再设主路由有,m,条信道,迂回路由的信道无限.记,P,状态(,r,s)= ,主路由中有,r,条信道被占的概率为,迂回信道上有,s,条信道被占的概率为,113,溢出呼叫的状态转移图,溢,出,呼,叫,状,态,转,移,图,114,稳态方程,解出,p,r,s,是困难的,今求溢出量,s,的均值与方,差.状态方程对,s,求和得,115,116,对,r,求和得,由递推得,最后有,117,现求,s,的方差.令,则,则方差为,因此需求,f(m),从状态方程的第一式两边乘,s,再相加,可得,它的解为(可代入验证),118,119,6.,优先权服务系统,强占优先制,:新到的顾客有优先权时,如遇服务台忙(全占)他可以强占无优先权顾客的服务台,使之中断服务,退到队列中去等待.,非强占优先制,:新到来的具有优先权顾客,不能去打断正在服务的任何顾客的服务,只能排在无优先权顾客之前等待服务.,.,120,这里只介绍求,非强占优先制中,任意一级顾客的,平均等待时间,设优先权有,M,级,高低次序从1到,M.,各,级顾客的到达率为,各级顾客的平均服务时间为,则系统的平均服务时间,为,h=/,其中,是系统的业务量.,121,在系统稳定时,假定新到的顾客属于第,P,级优,先权,他的等待时间将由三部分组成:,1.,等待服务台空出,的平均时间,:,设占用服务台的 顾客的平均剩余时间是,则等待服务台空出的平均时间是,(,因为服务台非空的概率是,).,2.,已,经在队列中,等待,的第,1-,P,级顾客的平均总占用时间,:,设每一级顾客的平均排队等待人数为,则每级顾客占用总时间是,i=1,2,P,由此可知,122,3.在,P,级新到的顾客排队等待期间,高优先级第1到(,P-1),级新到客,(,他们比,P,级新到顾客迟,但因优先级高故要往前排,),平均总占用时间,:,新到,P,级顾客平均等待时间,W,P,此间新到的1至(,P-1),级顾客的平均数为,这些顾客平均总占用时间为,123,移项整理后得,上式中,以(,P-1),代替,P,得,经整理最后得,124,如果新到的顾客是最高优先级的,那么上述推导中没有,其中,Z,为服务时间,是,M,个服务时间的加权平均,:,125,126,其中,如果对各业务的服务时间相同,则,127,P,级优先权顾客的平均等待时间,主要决定于优先,权较高的业务量,而于优先权较低的业务量无关;,如果顾客中大部分顾客有优先权,而只有少数没,有优先权,则有优先权的顾客的平均等待时间并,不会缩小多少,反而没有优先权股客的平均等待,时间要大为延长;,当各级顾客的平均服务时间不相等时,各级顾客,的业务量要受的影响,平均服务时间较长者为优,先时将延长全体顾客的平均等待时间,反之平均,服务时间较短的顾客列为优先级时全体顾客的,平均等待时间将缩短.,(,体现在某个 上,.),128,7.,一般排队问题,1),M/G/1,排队系统,令 是第,n,个顾客离开时所看到的系统中的顾客数,(其中 是第,n,个顾客的离开时刻,)这是一个马氏链,称为嵌入在顾客离开时刻的嵌入,Markov,链.,令 是在第,n,个顾客服务时间内到达的顾客数.于是有关系,129,引理1,设 是随机变量,X,的分布函数,是 的,Laplace-Stieljes,变换.,是参数为 的,Poisson,过程,Y,是在长为,X,的时间内,由 发生的事件数,则,其中 表示,Y,的母函数.,130,证明:,131,引理2,设,q,是取非负整数值的随机变量,其母函数为,则,132,证明:,133,定理,134,证明:,135,136,定理:,在,M/G/1,系统中当系统稳定时,在一个离开的顾客看来留在系统中有,n,个顾客的概率与一个顾客到达时发现在系统中有,n,个顾客的概率是相同的.,证明:,记一个到达者看到系统内有,k,个顾客的概率为,一个离开者看到系统内有,k,个顾客的概率为,137,假定在起始时刻,t=0,系统中有,i,个顾客.系统中顾,客数,N(t),增加一个的时刻记为,减少一个顾,客的时刻为,.,并记,和,.,若,第,n+1,个离开者看到系统内的,顾客数不大于,k.,那麽,此时系统中的顾客应是第,n+2,n+3, ,至多是第,n+1+k,个到达者,这也,就是说,由尚未进入而即将进入系统的第,n+1+k,个到达者看来系统中的顾客数(连同他自己)不,会超过,k,个,即,.,138,若,也就是说,由尚未进入而,即将进入系统的第,n+1+k,个到达者看来系统,中的顾客数不会超过,k,个,此时系统中至多曾有,n+k,个顾客进入,加上在起始时刻的,i,个顾客,应,至多曾有过,n+i+k,个顾客.那麽第,n+i,个离开者,看系统顾客数不大于,k,即,.,于是,139,队长的,Pollaczek-Khintchine,公式,应用以上结论,我们有,q,是离开者看系统的顾客数, 是到达者看系统的顾客数,N,是任意时刻看系统时的顾客数.,140,平方变异系数,: 对任意非负随机变量,X,它的平方变异系数定义为,队长的,Pollaczek-Khintchine,平均值公式.,141,142,143,M/G/1,系统的逗留时间,其中,令 是任意顾客在系统中所化费的,总时间,那么,是系统的逗留时间分布的,Laplace-Stieltjes,变换.,144,任一顾客化费在系统中的总时间内的到达顾客数的母函数为,.,对,FCFS,系统而言,在一个顾客在系统中逗留这段时间内的到达数与他离开时留下的顾客数相同的,145,逗留时间的,Pollaczek-Khintchine,变换公式,经代数运算,得到,146,逗留时间的,Pollaczek-Khintchine,平均值公式,M/G/1,系统的等待时间,147,用(2.11)和,Laplace,变换,的性质可证明,(,这是关于等待时间的,Pollaczek-Khintchine,平均值公式.),148,有两个常用的分布:,1)爱尔兰分布;,2)超指数分布.,爱尔兰分布:,r,个独立同分布的指数分布之和是,r,阶爱尔兰分布.其分布密度为,此时对应的指数分布的参数是,.,149,当指数分布的参数是 时,相应的,r,阶,爱尔兰分布的分布密度为,其拉氏变换为,当 称为伽马,(Gamma),分布,.,它的密度函数写为,下面仍讨论,r,阶爱尔兰分布,150,对指数分布,151,对,超指数分布,:,152,例如二阶超指数分布,:,153,154,例,7:,某维修点有一维修工人,平均每小时有,4,台机器送来,假定待修机器的到达是普松分布,每台机器的修理分两个阶段,假定这两阶段修理时间是独立的负,指数分布,平均服务时间皆,5,分钟,.,求,1),没有修理活,的概率,;2),平均等待修理的机器数,;3),机器的平均等待修理的时间,.,解,:,155,例,8:,银行,ATM,顾客按普松规律到达,平均每小时,40,人,ATM,办理一笔取款所需时间为,36,秒,求,1),顾客的平均等待时间,;,2),顾客的平均逗留时间,;3),等候取款的人数,.,解,:M/D/1,型,平均逗留时间,:,平均等待数,=,平均占有数,- :,156,2.2,G/M/1,排队系统,G/M/1,系统可以用在正好先于顾客到达时刻的点上的嵌入,Markov,链 来分析.,Markov,链的状态是第,n,个到达顾客所看到的在系统中的顾客数.,( 第,n,个到达间隔期间所完成的服务数),157,G/M/1,系统的嵌入,Markov,链的平稳概率的解有非常简单的形式:,其中 是以下方程在单位圆内的唯一实根:,的值可用叠代法得到:,158,由于 是第,n+1,个到达间隔期间所完成的服务数,事件 的概率分两种情况,:,1),当,j=0,此时,如到达间隔的长为,t,则,2),当,j0,此时,159,其中,t,表示到达间隔时间,.,160,G/M/1,的嵌入,Markov,链的一步转移概率矩阵是,161,和,M/G/1,的情形一样,若定义,记,即,162,验证.,163,G/M/1,等待时间分布为:,164,例,9,求排队系统 的占有分布和等待时间的分布,其中 的分布密度为,服务时间的负指数参数为,解,:,取,165,另,于是同样得到,分布,:,等待时间分布为,166,3) G/G/1,问题,(,求平均等待时间,),令,X,为服务时间,T,是到达间隔,167,补,168,169,Q(s),在左半,平面解析,W(s),在右半,平面解析,170,讨论,该式左边在左半,平面解析,右边在,右半平面解析.,171,172,173,174,175,176,177,若干简化,1.,(,无共享,),时,2.,完全共享存储器情形,(B=Mi):,因,B,甚大故可把,项忽略,此时有,则,$,C(B)=A_0+sumN_i=1A_irhoB_i,$,上式限于各$,rho_i$,都不相等时,否则计算留数时稍繁些.,178,其中,则,上式限于各 都不相等时,否则计算留数时稍繁些.,179,呼损,第,i,种业务的丢失率(呼损)为,其中,和,该式可用来选择某一链路上所需的存储容量,B,和各种业务的截止队长,Mi,也就是依照公平性决定,B,和,Mi,以使各丢失率,Li,小于某容许值,.,180,S1,集表明第,i,个缓冲器已满；,S2,集表明虽第,i,个缓冲器未满，但总的缓冲器,已满；,181,S1,集表明第,i,个缓冲器已满；,S2,集表明虽第,i,个缓冲器未满，但总的缓冲器已满；,当各种业务的队长 已接近 时,可以通知前面一些节点不要再把这些业务送来,而在前面链路存储器中停留一段时间.这是利用缓冲器来缓和本链路上的丢失,此时可用最前面的时延公式.,182,