通信网理论基础(修订版)第二章.ppt

第二章 网内业务分析,提纲,2.1 排队论基础2.2 通信网的业务模型与分析2.3 提高网效率的一些措施,2.1 排队论基础,由要求服务的顾客和提供服务的服务员双方构成的系统通常被称为排队系统。,节点,顾客,服务员,生活中的排队现象通信中的排队,研究这种系统的意义在于它的广泛性:信息流与信道；计算机的指令与总线数据与中央处理单元故障与维修等,资源的有限性和需求的随机性是排队现象存在的基础。,由于顾客到达和服务完毕的时间都是不确定的，绝大多数排队系统工作于随机状态。这种随机性造成有时顾客排队时间过长，有时服务员却闲着；前者是服务质量的损失，后者是服务资源的浪费。一个高效益的排队系统应能为顾客提供满意服务的同时，尽量提高资源的利用率。这既与排队系统的统计参数有关，又与所选择的工作方式有关。,排队论的概念,排队论：即利用概率论和随机过程理论，研究随机服务系统内服务机构与顾客需求之间的关系，以便合理地设计和控制排队系统。,排队论所研究的问题有:(1)等待时间的分布,平均等待时间;(2)系统时间(也称逗留时间)的分布,平均系统时 间及系统时间的方差(时延抖动);(3)在系统中的顾客数(也称系统占有数)的分布及 均值;(4)等待顾客数的分布及其均值;(5)服务器忙着(或空闲)的概率;(6)忙期长度的分布及其均值;(7)在忙期被服务的顾客数的分布以及它的均值。,任何排队系统都有3个参量m、l、m，称为排队模型三要素：服务员数目m顾客到达率服务员服务速率,2.1.1 基本概念,顾客,服务者,服务员数目m m称为窗口数或服务员数目，表征系统的资源量，它表示系统中有多少服务设备可同时向顾客提供服务在计算机通信网中，m常指分组交换节点的输出信道数量等当m=1，可称为单窗口排队系统；当m1，就称为多窗口排队系统,排队模型三要素,10,顾客到达率单位时间内平均到达排队系统的顾客数量单位时间内平均到达分组交换节点的分组数量反映了顾客到达系统的快慢程度，越大，说明系统的负载越重,节点,顾客,服务者,排队模型三要素,11,顾客到达率ti:任意相邻两顾客到达的时间间隔，是一个随机变量：ti的统计平均值，表示顾客到达的平均时间间隔,排队模型三要素,如1分钟（60秒）到达顾客数为4人，则平均顾客到达的时间间隔就是(1/4)分钟，即15秒。,12,顾客到达率,排队模型三要素,13,服务员服务速率单位时间内由一个服务员进行服务所离开排队系统的平均顾客数对于m1系统，就是系统的服务速率对于m 1系统，系统的服务速率为m:任意相邻两顾客离开的时间间隔，是一个随机变量，即第i个顾客的服务时间：单个服务员对顾客的平均服务时间，也就是一个顾客在系统内接受服务的平均时间如1分钟（60秒）由1个服务员服务离开顾客数为4人，则平均一个顾客服务的时间为(1/4)分钟，即15秒。,排队模型三要素,Wi:第i个顾客等待时间(下降沿与上升沿之差)Ci:第i个顾客到达或离去时间ti：第i+1与第i个顾客到达时间间隔,ti=(Ci+1-Ci)到达，上升沿之差i:第i个顾客与第i+1个顾客离去的时间间隔，即第i个顾客的服务时间，i=(Ci-Ci-1)离去，下降沿之差,窗口数m、顾客到达率l和服务率m虽是排队系统的3个基本参数，要充分描述排队系统并分析其运行状态还是不够的，因为排队系统的性能主要取决于顾客到达时间间隔ti与服务时间ti的统计分布和排队规则。对于一般的统计分布，迄今还不易得到解析结果。通常最常用的分布是指数分布，它能导致排队过程成为马尔可夫（Markov）过程，许多问题易于得到解析结果，而这种分布也是与实际排队问题中的一大类相近。,常见排队系统的一般假设平稳性：在时间间隔t内，到达k个顾客的概率只与t的长度有关，而与这间隔的起始时刻无关。无后效性：顾客到达时刻互相独立，即顾客各自独立地随机到达在互不重叠的时间段内，顾客到达的概率相互独立，即不同t内顾客到达的概率无关疏稀性：在无限小时间间隔t内，到达2个或2个以上顾客的概率为零，且在有限时间内到达的顾客数是有限的即：在t内只有一个顾客到达或没有顾客到达,满足以上三个条件的随机流称为简单流.简单流的到达间隔是负指数分布的且在一段时间内到达的顾客数是泊松分布.,证明简单流的到达间隔是负指数分布:,设为到达间隔为t,把t分成N等份,每份的长度 根据无后效性和稀疏性，在前面N个 内无顾客到达，再一个 内有一个顾客到达的概率为（其中，a(t)为概率密度）：,tt内到达1人的概率1-tt内到达无人到达的概率tt内离去1人的概率1-tt内无人离去的概率,证明简单流的到达间隔是负指数分布:,所以在上述三个假设下的简单流的顾客到达间隔是负指数分布，其概率密度为：,再证明当到达间隔是指数分布时,在时间间隔T内的到达数是普松分布:把时间间隔T分成N等份,在这N个小区间内,k个顾客可在N个中任意k个 中到达:,T:顾客到达时间间隔，0T,概率分布函数,表示在时间t内有顾客到达的概率,在时间t内没有顾客到达(k=0)的概率即为,如果将T看成是数轴上的随机点的坐标，那么，分布函数FT(t)在t处的函数值就表示T落在区间(-,t上的概率,因为概率密度 积分即为分布函数，所以也可以由下式得到分布函数：表示T落在区间(-,t上的概率是1-e-t,所以，对于最简单流有：,顾客到达时间间隔分布在T期间内有k个顾客到达的概率符合泊松（Poission）分布，即,顾客在T时间间隔内到达k个的概率,泊松分布参数，单位时间内顾客到达数,在T时间内顾客到达的个数,对于最简单流有：,在一段时间内,电话的呼叫是简单流,因为顾客的到达数与时间起点无关;顾客的到达时刻相互独立;在很短的时间间隔内到达两个以上顾客的概率可认为是0.,服务时间分布,把上述假设用于服务过程，有类似结果即假设服务相继两个顾客所需要的时间也是互不相关、平稳和稀疏的，则：服务时间t服从负指数分布，其概率密度为在T期间内有k个顾客被服务后离去的概率服从（Poission）分布，即,排队系统表示符号：ABm(N,n),A顾客到达时间间隔分布，分布a(t)B 服务时间分布，分布b()m窗口数N顾客源，潜在顾客数，省略为n截止队长，省略为，不拒绝,A和B可以分别填入M、Er、Hr、D和G等，其中G表示任意分布,M分布,输入过程对应的是顾客到达间隔时间的分布函数，服务过程对应的是服务时间的分布函数，如果为上述指数分布，称为M分布指数分布所导致的排队过程具有马尔可夫（Markov）性，所以可称为M分布。（马尔柯夫最基本的性质是无后效性，顾客之间的到达是随机的）,M指数分布,MMm(n)顾客到达时间间隔和服务时间都服从指数分布,m个服务窗口，截止队长为n,Er分布,Er分布是r阶厄朗分布，适用于成批处理的排队问题，如顾客到达积累成r个时作为一批，再进入排队系统，或处理r个任务后作为一批送出时。或每秒平均到达批，则前后两批之间的间隔时间t的概率密度函数为：,当r=1，就是前面的指数分布：,D分布,即在t=1/时为，其他时候为0，并且从-到+积分，结果为1.每隔1/秒来一个顾客（如分组交换）或每个顾客服务时间固定都可以用D分布描述 如包交换系统中，包长是常量，服务时间是固定值，则用D分布是恰当的。,Er分布中，当r时，为单元脉冲函数,说明时间间隔t是固定,的 值：常称为D分布或确定性分布：,成批处理r批人数，有r人一起进入排队系统，或处理后r个一批送出批到达率r-顾客到达率t 批间隔，a(t)批间隔t的概率密度函数（r=1，即为指数分布（EM）当r,a(t)=(t-1/),确定型分布,等间隔进入,称D分布,Er阶厄朗分布（Erlang）,Er、D分布,HR分布,当到达的顾客有R类，各类的平均到达率不相同，分别为1，2，,R，各类顾客所占的比例分别为1，2，,R，当这些顾客混合排队时，就可得到如下分布：,且有,R=1，则HRM,排队系统的工作方式,排队系统的运行性能不仅与上述的统计分布有关，还与系统预先规定的工作方式有关。排队规则是指服务机构是否允许排队服务规则是指在排队等待情形下服务的顺序是什么。,排队系统的工作方式,按服务规则划分有：先到先服务：按顾客到达先后，顺序服务，这是常见情况，无其他说明时，常按这种方式分析。后到先服务：这是不常见情况，也可能出现，如仓库中同品种的货物，出库时常是后进先出。优先制服务。对各类顾客分别事先赋予不同的优先级，优先级愈高，愈提前被服务。通信网中也较为常见。还有随机服务等。,n为顾客数，m为窗口数。顾客到达时，如果所有服务窗口m均被占满等待制系统（不拒绝方式）允许排队，且队长没有限制，但应满足稳定性要求，即排队强度：截止型，即时拒绝方式立即遭到拒绝，即服务机构不允许顾客排队等待（m=n,电话通信网常采用）即除了m个正在服务的人外，系统不允许有其他人排队截止型，延迟拒绝方式允许排队，但队长有限制。（mn,带缓冲存储的数据通信就属于这一类）即除了m个正在服务的人外，还允许n-m个人排队,排队系统的工作方式-排队规则,排队系统的主要性能指标（1）排队长度k（2）等待时间w（3）服务时间t（4）系统时间s（5）系统效率h（6）稳定性,排队系统的主要性能指标（1）排队长度k简称队长，是某时刻观察系统内滞留的顾客数，包括正在被服务的顾客。k是非负的离散随机变量，需用概率来描述，通常有以下3种观察方式：pk:随机地取t时刻来观察队长为k的概率。rk:顾客到达时刻所观察到的人数（不包括刚刚到达的顾客）为k的概率。dk:顾客被服务完毕将离开时所看到人数为k的概率。,排队长度k一般pk、rk、dk三者是不同的；对于顾客到达规律具有前述的马尔可夫性的系统，则pk=rk。此外，当每瞬间到达人数或离去人数只能是一人时，则rk=dk。满足疏稀性时，只要顾客到达是泊松流，就有pk=rk=dk。上述参数都是指队长为k的概率k的统计平均值 称为平均队长。,排队系统的主要性能指标,排队系统的主要性能指标,（2）等待时间w顾客到达至开始被服务的这段时间，是连续随机变量，其统计平均值 称为平均等待时间。越小越好在通信网中，是信息在网内的平均时延的主要部分，其他时延如传输时间、处理时间等一般均为常量，而且一般比较小。,排队系统的主要性能指标,（3）服务时间t顾客被服务的时间，即顾客从开始服务至离开系统的时间间隔，其统计平均值 称为平均服务时间。为单个窗口平均服务的顾客数（平均服务速率）,排队系统的主要性能指标,（4）系统时间s顾客从到达系统至离开系统的这段时间，又称为系统内停留时间，其统计平均值 称为平均系统时间。,系统时间=等待时间+服务时间,排队系统的主要性能指标,（4）系统时间s：列德尔（Little）公式,称为列德尔（Little）公式（适用于任何排队系统）,一个平均到达率为的排队系统，在平均意义上有：,Little,即：在排队系统中的平均顾客数=顾客的平均到达率平均逗留时间:,主要性能指标,（5）系统效率h定义为平均窗口占用率。某时刻t有rt个窗口被占用，若共有m个窗口，则rt/m就是占用率。显然，rt/m是一个随机变量，它的统计平均值就是系统效率，即h愈大，服务资源的利用率愈高。,主要性能指标,（6）稳定性对于不拒绝系统，当到达率与服务率之比大于窗口数时，平均顾客到达数将大于平均顾客离去数，顾客的队长将愈来愈长，平均等待时间趋于无限大，系统陷于混乱，将不能稳定工作。令排队系统的强度r为：对于截止型系统，因为队长被人为地限制，即使rm，系统仍能稳定地工作。,系统稳定,系统不稳定,主要性能指标,（6）稳定性有的资料中定义排队系统的强度r为：对于截止型系统，因为队长被人为地限制，即使r1，系统仍能稳定地工作。,系统稳定,系统不稳定,排队问题的求解方法,确定状态变量 画状态转移图 列状态转移方程 求解目标参量,2.1.2 M|M|1问题,排队问题的求解方法先确定状态变量，最常用的是队长k。取系统中随机时刻的k还是取顾客到达或离去时刻的k，要看问题的性质，以使数学上易于处理。画状态转移图列状态转移方程，建立pk(t)的差(对k)微分(对t)方程。性能参数求解（求解目标参量）若能解出pk(t)，则参数计算将易于进行。若难于求解pk(t)，可求解与t无关的稳态解。,2.1.2 M|M|1问题,2.1.2 M|M|1问题,M/M/1排队模型：顾客到达时间间隔为（负）指数分布，顾客到达率为服务时间为（负）指数分布，顾客服务率为单窗口（即m=1）不拒绝系统（n）先到先服务（顺序服务）潜在顾客数为无穷（即N）,排队系统的排队模型,图1 一般排队系统 排队模型,51,到达时间间隔负指数分布泊松输入流,服务时间负指数分布,图2 M/M/1排队模型,取队长k为状态变量来建立系统的差微分方程pk(t)-为时刻t，系统内有k个顾客或队长为k的概率（k=0,1,2,）取t为足够小的时间间隔则：tt内到达1人的概率 tt内离去1人的概率,系统的差微分方程,t时刻，k状态,由t到t+t时刻顾客数变为k的转移情况,pk(t),情况1：在t内来一人，离去一人,pk(t+t),情况2：无人来，无人离去,Pk-1(t),：在t内来一人，无人离去,Pk+1(t),：在t内无人来，离去一人,t：足够小的时间间隔,取队长k为状态变量,pk(t),情况1：在t内来一人，离去一人 pk(t)(lt m t),pk(t+t),情况2：无人来，无人离去 pk(t)(1-l t)(1-m t),Pk-1(t),：在t内来一人，无人离去 pk-1(t)l t(1-m t)pk-1(t)l t,Pk+1(t),：在t内无人来，离去一人pk+1(t)(1-l t)m t pk+1(t)m t,由t到t+t时刻顾客数变为k的转移情况,取队长k为状态变量,其状态转移图如下（省略高阶项（2t）,pk(t)(lt mt)（高阶项2t略）pk(t)(1-lt)(1-mt)pk(t)-pk(t)lt-pk(t)mt)pk-1(t)lt(1-mt)pk-1(t)ltpk+1(t)(1-lt)mt pk+1(t)mt,（1-l t）(1-m t),系统的差微分方程（队长k为状态变量）,综上所述，并忽略(t)2项，可得,移项整理得：,令t0，得：,p1(t),：在t内无人来，离去一人p1(t)(1-lt）m tp1(t)m t,p0(t+t),P0(t),：情况1：来1人，走1人p0(t)l tm t（2t 项，省略）情况2：在t内无人来，无人离去 p0(t)（1-l t）(1-m t)=p0(t)-p0(t)l t-p0(t)t-p0(t)2t p0(t)-p0(t)l t-p0(t)t=p0(t)-p0(t)l t,由t到t+t时刻顾客数变为0的转移情况,取队长k为状态变量,注：p0(t)t=0,所以：p0(t+t)=tp1(t)+p0(t)-t p0(t),系统的差微分方程（队长k为状态变量）M|M|1系统方程,上述系统方程只能适用于无后效的M|M问题，因为对于非M|M问题，转移概率不但与平均到达率或平均服务率有关，还可能与时刻或当时的状态有关。,上式是哥尔莫柯洛夫方程的特例。,至此，得M/M/1完整状态方程:,哥尔莫柯洛夫方程dpk(t)=(dt内进入k状态的概率)-(dt内离开k状态的概率)也就是pk(t)的增量应等于进入k状态的概率减去离开k状态的概率哥尔莫柯洛夫方程适用于各种排队系统。,M|M|1问题的状态转移图图中l、m分别表示转移概率ldt、mdt。,根据哥尔莫柯洛夫方程，由状态转移图可直接写出系统方程（注：此时已经不包括由k到k状态的转移，只有进或出k状态，但是因为左边已经是微分式子，所以不影响结果）。,状态转移图的变化,根据哥尔莫柯洛夫方程，状态转移图此时已经不包括由k到k状态的转移，只有进k或出k状态，但是因为左边已经是微分式子，所以不影响结果）。,dpk(t)=(dt内进入k状态的概率)-(dt内离开k状态的概率),(1-l t)(1-m t),状态方程的不同,(1-l t)(1-m t),只看进，不看出，有保持,只看进出，无保持,稳态方程及稳态解,分析排队系统，就是解这些系统方程，有稳态解和暂态解。排队系统的运行经过暂态进入稳态，在数学上说，就是当t，pk(t)已稳定，即与t无关，可记为pk。,系统方程求解,M|M|1,稳态解：,物理意义：到达与离去平衡，pk(t)与t无关,M|M|1,M|M|1的稳态解,物理意义：到达与离去平衡，pk(t)与t无关 数学描述：,M|M|1,M|M|1,求p0:用归一化条件,p0系统无人概率（空闲率）1-p0=系统有人概率（忙概率）,越大表示越忙，太大不稳得通解：,M|M|1,稳态方程概率的归一性,稳态解,平均队长队长方差,M|M|1,数学期望或均值,离散型随机变量X的数学期望或均值,连续型随机变量X的数学期望或均值：,其中，为连续型随机变量X的概率密度,方差,方差：度量随机变量X与其均值E(X)的偏离程度,对于离散型随机变量：,对于连续型随机变量：,随机变量X的方差可按下列公式计算：,平均队长队长方差,M|M|1：,等待时间当一顾客到达时，系统处于k状态，此顾客需等待k个顾客被服务完毕后方能开始被服务，因此要等待的时间wk是k个服务时间之和。可以直接用以下公式求：也可用特征函数法求w的 概率密度函数，从而求平均值。,M|M|1的等待时间w,用特征函数法求等待时间w的概率密度函数,若系统已有k人,来一人的等待时间w为k人的服务时间之和，即:,i的特征函数:(b()的付氏变换),k个i和的特征函数,特征函数作用：可简化很多运算，尤其是可以简化样本各阶矩和独立随机变量和的分布的运算,i的特征函数,若系统已有k人,来一人的等待时间w为k人的服务时间 即:,i的特征函数:(b()的付氏变换),k个i和的特征函数,用特征函数法求等待时间w的概率密度函数,因为k为离散变量,故w的特征函数:,用特征函数法求等待时间w的概率密度函数,w k的特征函数w的特征函数w的概率密度函数,M|M|1的等待时间w,由连续型随机变量平均值或数学期望公式：有平均等待时间,M|M|1的等待时间w,平均等待时间方差,系统时间概率密度注：系统时间s=等待时间w+服务时间t,两个独立的统计变量X和Y的和的概率密度函数是X 与Y的概率密度函数的卷积,M|M|1的系统时间s,卷积公式如下，直接求积分麻烦，可用其拉普拉氏变换求，再求反变换,为了避免跟拉氏中的s混淆，将上式中的s换成变量t,所以，第二部分卷积的结果为：,总的卷积的结果为两部分之和，即：,系统时间系统时间概率密度平均系统内停留时间和方差,平均系统内停留时间和方差也可从w和t的数字特征直接求得。还可验证M|M|1的稳态解满足列德尔公式，即,M|M|1的系统时间s,M|M|1问题的主要参量均取决于排队强度r由于r=1-p0是系统内有顾客的概率，亦即窗口忙的概率，对于单窗口情况，r就是排队系统的效率h。为了提高服务资源的利用率，就希望r选择得大一些。其次，由于平均等待时间和方差可看出，r的增大，将使平均等时间及方差均增大，这就意味着顾客将等候较久才能被服务，亦即排队系统的服务质量下降。从顾客的观点来看，常希望r小一些。此外，当r1时，以上公式都不适用，此时系统已不能稳定地工作(因为MM1是不拒绝工作方式)。,M|M|1闲期与忙期的统计特性,闲期与忙期的统计特性闲期I为系统中无顾客的持续时间，忙期T为系统中有顾客的持续时间，二者均为连续非负随机变量。闲期I的分布是易于求得的。由于闲期为系统处于无顾客状态后有一个顾客到达之间的时间间隔，因而其与顾客到达规律相同。,M|M|1闲期与忙期,在M|M1系统中，闲期也是指数分布，即其概率密度函数和闲期的统计平均值分别为：,M|M|1闲期与忙期,忙期统计特性,忙期的分布则是较为困难。顾客到达时刻与服务完毕时刻要满足一定条件，方能形成一个顾客数为n的忙期T。,形成一个顾客数为n的忙期T的条件：,形成一个顾客数为n的忙期T的条件：则n和T的联合概率如下，其中B为上述条件。,n和T的联合概率密度忙期T的概率密度函数其中I1(x)为第一类一阶修正贝塞尔函数,忙期的平均长度忙期的平均长度可根据平稳性求得,忙期内的平均顾客数每个忙期内有n个顾客的概率为平均顾客数忙期中的平均人数也就是忙的条件下的平均队长（即），而忙的概率为r，从而排队队长：,忙期中的平均人数也就是忙的条件下的平均队长（即），而忙的概率为r：,平均队长随时间变化，当1，平均队长将不断增大当队长达到某值时，再采取措施，如增大值或减小值，使 排队系统进入另一种状态，或开始另一暂态过程，对于提高系统效率是有益处的。,M/M/1暂态解,至此,得M/M/1结论如下:,系统效率,计算机通信网中的分组发送,1/就是单个服务员对顾客的平均服务时间，也就是一个顾客在系统内接受服务的平均时间计算机通信网中，分组的平均长度通常表示为1/(bit)若信道容量为C bit/s，则分组平均发送时间为1/(C)(s)则每个输出信道发送分组的速率为C(对应服务员的服务速率)若有m条信道，则整个系统发送分组的速率为mC。所以，在计算机通信网中，C对应着排队论中的笼统说顾客时，其服务员的服务速率用，具体说分组时，输出信道发送分组的速率用C,103,计算机通信网中的M/M/1系统指标将以下所有的换成C：,系统稳定时队长为k的概率,平均队长,或,平均系统时间,平均等待时间,系统效率,/(C),例 在以M/M/1为模型的分组传输系统中，设分组的平均到达率=1.25分组/s(秒)，分组长度服从指数分布，平均长度为1/=960bit/分组，输出链路的传输速率C=2400(bit/s).求:（1）每一分组在系统中所经过的平均时延；（2）系统中平均分组数；（3）系统效率,105,例 在以M/M/1为模型的分组传输系统中，设分组的平均到达率=1.25分组/s(秒)，分组长度服从指数分布，平均长度为1/=960bit/分组，输出链路的传输速率C=2400(bit/s).求:（1）每一分组在系统中所经过的平均时延；（2）系统中平均分组数；（3）系统效率,M|M|1,2.1.3 M|M|m(n)问题,M|M|1系统的主要缺点M|M|1系统的主要缺点是服务质量与系统效率的矛盾不易解决。要使排队系统在保证稳定性运行的情况下提高效率，必须采取措施减小等待时间，以达到一定的质量要求。问题主要是如何压缩排队队长。,2.1.3 M|M|m(n)问题,压缩排队长度的措施增加窗口数分析表明，对于一定的顾客到达率，增加窗口数显然能减小等待时间，这是一种积极的措施。当然，增加窗口数意味着投资加大。截止排队长度也就是采用拒绝型系统。这是一种消极措施。为保障已排队的顾客不过长时间等待，当系统内顾客数已达到规定值时，新来顾客即被拒绝。有顾客被拒绝当然也降低系统质量，但这种代价可换取系统效率和稳定性，并能保证已排队的顾客不等得太久，仍不失为一种可行的措施。,以上2种措施可兼用，成为截止型多窗口排队系统。多窗口情况下一般有2种排队方式：其一为混合排队方式，即顾客排成一个队，依次接受m个窗口的服务；另一种为分别排m个队，分别接受m个窗口的服务。,M|M|m(n)问题有m个窗口排1个队，即任一窗口有空即被服务顾客到达率为l，顾客到达间隔时间为指数分布单窗口的服务率为m，服务时间为指数分布截止队长为mn，当队长（包括正在被服务的顾客）为n时，新来顾客被拒绝而离去窗口未占满时，顾客到达后立即接受服务窗口占满时，顾客依先到先服务规则接受服务,M|M|m(n)问题状态转移图令系统内顾客数k作为系统的状态变量，此时只有n+1种状态。当km时，有k个窗口在被占用，服务率为km。当m k n时，m个窗口均被占用，服务率为mm。,系统方程,稳态方程归一性,方程的稳态解令r=l/(mm)，利用递推易得其中,几种特例m=1，为M|M|1(n)问题m=1，n，即前述M|M|1问题m=n，为即时拒绝系统,拒绝概率,a=l/m称为呼叫量,n，是多窗口不拒绝系统,m=n，为即时拒绝系统,拒绝概率,a=l/m称为呼叫量,是通信系统常用的厄朗（Erlang）或爱尔兰公式，a称为呼叫量。,爱尔兰公式,爱尔兰公式,爱尔兰分布条件下(N，m,N m）,爱尔兰公式在交换设备计算中非常有用，为了书写方便，常用Em(a)表示。Em(a)的含义：线束容量为m的线束流入话务量为a（单位为e）时，按爱尔兰呼损公式计算的呼损为Em(a)。,业务量业务量是在指定时间内线路被占用的总时间。若某线路有m条信道，第r条信道被占用Qr秒，则m条信道或该线路上的业务量为另一种表达业务量的方式是,在时刻t被占用的信道数。T是观察时间,业务量和呼叫量,业务量的量纲是时间。若一个信道代表一个电话话路，则业务量或话务量的单位是秒话路。观察时间可以是1小时或1天等。,基于排队论的话务量,基于排队论的话务量Y：Y=ST话务量三要素呼叫强度：（单位时间内平均发生的呼叫次数）占用时长：S（听拨号音、拨号、振铃、通话）考察时间：T注意：各变量的时间单位要相同。话务量的大小与用户通话的频繁程度和通话占用的时间长度以及统计观察的时间长度有关。,呼叫量业务的强度通常称为呼叫量。它可定义为线路占用时间与观察时间之比，单位是厄朗，即,根据前述定义，呼叫量可写成,通常T为1小时，所得的平均值a称为小时呼叫量或小时厄朗。,基于排队论的话务量强度（呼叫量）,基于排队论的话务量强度a单位时间内的话务量，称为话务量强度，用A表示。同时为了称呼方便，将话务量强度简称为话务量，它是度量通信系统繁忙程度的指标。因此话务量强度的定义为：上述的S是平均占用时间大小，即是平均服务时间大小，也即排队论中的话务量的大小与单位时间内用户通话的频繁程度和通话占用的时间长度有关。,作为网设计依据的呼叫量有下列两种1天中最忙1小时内的呼叫量称为日呼叫量，也就是1天中最大的小时呼叫量；1年内取30天，取这些天的日呼叫量的平均值称为年呼叫量，亦称基准呼叫量。有的网一年四季的日呼叫量变化不大，就可用日呼叫量作为网设计的依据。有的网日呼叫量变化较大，就取年呼叫量作为设计依据。一般而论，小网多属于前者，而大网往往属于后者。,局间中继线的计算,例：有三个程控交换局需要设立数字中继，要求的呼损E0.005。通过调查统计得到各局之间的话务量要求分别是2-3局之间的流入话务量为a2361.74e2-4局之间的流入话务量为a2457.81e请计算各局之间应该设置多少条中继电路？,解：由公式可算得，也可查表：2-3局，a2361.74e，E0.005，查表得m79；2-4局，a2457.81e，E0.005，查表得m75；,124,例某商店有3个服务员,每个服务员在每一时刻只能服务一个顾客,服务时间为负指数分布,均值为2.5分钟.顾客到达为普松分布,平均每分钟到达1.2人.设无等待,（1）求顾客到达而未被服务所占的百分比;（2）若要求到达而未被服务所占的比例小于5%,问需几个服务员?解:排队系统类型:M/M/3.（1）顾客到达而未被服务所占的百分比即系统中有顾客数n=m=3的概率，即,125,（2）设需n个服务员,则,所以，需要设7个服务员。,平均等待时间到达顾客的等待时间与到达时刻系统状态k有关:当km时，顾客不需等待即被服务；kn时，顾客被拒绝而离去，也无等待时间；所以只有当mkn时，才存在等待问题,M/M/m(n)的平均等待时间,只算,情况即可,k=m 等1人k=m+1 等2对k 等k-m+1人,mkn时，k个顾客中，有m个顾客正在被服务，k-m个在排队等待，因此新到的顾客要等待k-m+1个顾客被服务完毕才能开始被服务。由于m个窗口都在工作，所以平均服务率是mm，系统平均顾客离去间隔时间（即系统平均服务时间）为1/mm。,新到顾客的平均等待时间,mkn,新到顾客的平均等待顾客数,（顾客离去的时间间隔都为1/，对某一个新到顾客来说，其前面平均正在服务或）等待的顾客数为,1)当m=1,为单窗口。M/M/1(n),新到顾客的平均等待顾客数,2）当n,为非拒绝系统,数学的M/M/m问题平均等待数:,新到顾客的平均等待顾客数,d)当m=1,n为M/M/1 平均顾客数与平均队长就相等,新到顾客的平均等待顾客数,M|M|m(n)平均队长,离去的顾客中有一部分顾客是被拒绝的，没有得到服务,M|M|m(n)平均停留时间,系统效率：当km时，系统的效率亦即窗口的占用率k/m。当km时，系统的效率为1。,M|M|m(n)系统效率,M|M|m(n)系统效率,n时为多窗口不拒绝系统，其效率为,根据前述结果，可得出如下结论（参照书中图2-6和图2-7）对于一定的r值，增大截止队长n可以提高效率，但等待时间w将增长。这是说延迟可以换取效率。只要平均延迟是允许的，采用较大的n是合理的。对于不拒绝系统，r必须小于1，才能使系统稳定；当r1，等待时间将无限增大。对于拒绝系统，在r1，系统仍能稳定工作。这就是说，以拒绝顾客为代价可取得稳定性。只要拒绝概率被控制在一定限度内，增加r可提高系统效率。,n一定时，增加r将使等待时间上升；但当r大于一定值时，大部分顾客被拒绝，参加排队的顾客反而可少等待一些时间。这是以拒绝概率的增大为代价而得到的，其实综合服务质量是下降的。在不拒绝系统中，效率等于排队强度=/(m)m个M|M|1系统与一个M|M|m系统相比，在同样的系统效率下，后者的服务质量将高于前者；反之，在同样的平均等待人数时，后者的效率将高于前者。,2.2 通信网的业务模型与分析,2.2.1 各种测度和指标2.2.2 业务分析举例,2.2.1 各种测度和指标,业务量和呼叫量业务量业务量是在指定时间内线路被占用的总时间。若某线路有m条信道，第r条信道被占用Qr秒，则m条信道或该线路上的业务量为另一种表达业务量的方式是,在时刻t被占用的信道数。T是观察时间,业务量的量纲是时间。若一个信道代表一个电话话路，则业务量或话务量的单位是秒话路。观察时间可以是1小时或1天等。,呼叫量业务的强度通常称为呼叫量。它可定义为线路占用时间与观察时间之比，单位是厄朗，即,根据前述定义，呼叫量可写成,通常T为1小时，所得的平均值a称为小时呼叫量或小时厄朗。,作为网设计依据的呼叫量有下列两种1天中最忙1小时内的呼叫量称为日呼叫量，也就是1天中最大的小时呼叫量；1年内取30天，取这些天的日呼叫量的平均值称为年呼叫量，亦称基准呼叫量。有的网一年四季的日呼叫量变化不大，就可用日呼叫量作为网设计的依据。有的网日呼叫量变化较大，就取年呼叫量作为设计依据。一般而论，小网多属于前者，而大网往往属于后者。,基于排队论的呼叫量信道数m相当窗口数，单位时间内的平均呼叫数是到达率l。每次呼叫占用线路的平均时间相当于平均服务时间。当am时，相当于r=l/(mm)1，这对于不拒绝系统将是不稳定的。对于拒绝系统当然还是稳定的，只是有拒绝情况出现而已。,阻塞率和呼损实际的通信网及其子系统中，为了工作的稳定性，多为截止型的排队系统。阻塞率和呼损都指拒绝状态占全部状态的百分比。当系统处于拒绝状态时，系统是阻塞的，即从用户角度看将出现呼损。阻塞率可有两种定义，即时间阻塞率和呼叫阻塞率。,时间阻塞率是总观察时间内阻塞时间所占的百分比，即这个时间阻塞率就是排队系统中截止队长为n时的拒绝概率，也就是系统处于n状态，或已排满队而不容许再排入的状态占全部时间的百分比。,呼叫阻塞率（呼损）定义为被拒绝的呼叫次数占总呼叫次数的百分比，即通常称为呼损的就是这个呼叫阻塞率。,Pc有呼叫，统计（用户角度）,不呼叫不统计，但不呼叫时可能已阻塞。Pn时间统计，客观统计（客观角度）阻塞时间内可能无呼叫发生,即,纯随机呼叫时，,纯随机呼叫：潜在呼叫源（用户）为无限多；准随机：有限用户数N，相互独立，但N很大；令l0为每个用户单位时间内平均呼叫次数，截止队长为n。当r个用户已被接受排队服务时，则到达率将为(N-r)l0，则呼叫阻塞率为,队长为r的概率,分子是被阻塞的呼叫次数，而分母是总呼叫次数。,用户数为有限值N的准随机呼叫,当N时，所有r与N相比均可忽略，则,N有限时，pcpn，当Nn时，pc和pn相差不大，从统计测量来说，pc比用pn方便，因而在Nn时，通常不区分。,呼损与转接次数有关转接次数愈多，呼损愈高。设源宿端间其有向径上有r条边，边上的呼损各为，则该径上源宿端之间的呼损将为,时延时延是通信网的另一重要指标。一般地说，时延指消息进入网内后直到被利用完毕所需的时间。这包括等待时间、服务时间、传输时间和传播时间。从排队论来说，时延的主要部分是系统时间，即等待时间和服务时间。在延迟拒绝系统中尤其是如此。对于实时性业务如电话通信，常采用即时拒绝方式，则等待时间几乎为零，呼损就会出现得较多。,通过量和信道利用率-通过量在所要求的呼叫中，有一部分被拒绝，其他的才实际通过网而被利用。通常以单位时间通过的业务量为通过量，即,pc是呼损,有时也用单位时间内通过的呼叫次数作为通过量,信道利用率若线路的容量为Cr，则信道利用率为若某线路可通m路电话，其容量可定为m，则信道利用率相当于排队模型中的窗口占用率或系统效率，得,通信网中若有M条边，相当于M条线路，则全网效率可用各线路通过量之和与各线路的容量之和表示，即应指出，全网的通过量并不是各线路的通过量之和，因为有些信息流要经过几条边才能从源端到宿端。为了说明全网的通过量，应计算从各端进入网内而能达到宿端的业务量，即总通过量为,其中，ar是从第r端进入网的呼叫量，而Pc是这些呼叫量在网中被阻塞的百分比。,2.2.2 业务分析举例,用排队论分析通信网业务问题步骤:规定模型定义状态变量列出状态方程求解稳态方程，并计算所需的目标参量，以得到网的质量指标和有效性指标,2.2.2 业务分析举例,用排队论分析通信网业务问题步骤首先规定模型选择适当的排队模型，使之与实际问题近似。通信网中常见的模型有M|M|m(n)、M|D|1和M|Er|1等。如果某种排队模型与实际问题有较理想的符合，可直接引用相应结果。不然就应作具体分析，尤其是考虑某些排队规则如优先制等，必须建立相应的模型，再按以下步骤进行分析。,其次是定义状态变量这是求解难易的关键。所选择的状态变量要便于计算，并使结果具有可用性。有时要选用多维的变量。维数愈大，计算的将愈复杂，所以应尽量用维数少的变量来描述问题。常用的变量是队长，占用线数等。第三步就是列出状态方程。对于M|M问题，可先画出状态转移图，直接用柯氏方程列出稳态方程，即进入某状态的概率等于离开该状态的概率最后是求解稳态方程，并计算所需的目标参量，以得到网的质量指标和有效性指标。,几个例子,（1）有限用户即时拒绝系统设交换站用N个用户，每个用户的呼叫率为l0，有m条中继线，用户占线时间服从均值为1/m的指数分布，截止队长为n=m。电话交换系统属于此类。,当用户之间相互独立，总呼叫率为Nl0，相当于M|M|m(N,m)排队系统。选用占线数k作为状态变量，则状态转移图如下,由状态转移图可列出系统稳态方程,归一化条件,方程求解令r=l0/m，用递推法可解出用归一化条件解出p0，即,时间阻塞率或拒绝概率（表示同时呼叫用户数有m个，将中继线m条完全占用，产生阻塞）代入公式（2-107）：得呼叫阻塞率或呼损为：,有,线路利用率h,上述线路利用率h分子的变化：,令m=2，Nr=1代入作数值计算,对各种N值得如下表,由图可见，呼损pc常小于时间阻塞率p2。当N=2时，pc=0，这是必然的，因为两个用户两条信道，相当于专用线，当然不会有呼损。此时p2=0.11，即时间阻塞率还是存在的。当N，pc=p2，此时已为纯随机呼叫。其实当N10时，两者差别已不大。一般地说，当N5m时，这种近似已不成问题。当N时，Nr=Nl0/mm=l/mm=1就是呼叫量，除了呼损0.2外，通过量将为0.8；线路利用率为0.8/2=0.4，这与曲线中的值一致。但当N为有限值时，这个关系并不成立。,（2）主备线即时拒绝系统设在交换站有2种输出线，A是主用线，B为备用线。当A线被占用时再有呼叫才用B线传输。到达和服务率分别为均值l和m的指数分布。,主备线即时拒绝系统,在这里，一个状态变量已不能表达系统的状态。令二维矢量（x,