第三章Erlang拒绝和等待系统.ppt
第三章 Erlang拒绝和等待系统,通信网实验室http:/,2023/6/23,http:/,2,3.1 介绍,在本章中将要对不同的交换系统建立起排队系统模型，并进行性能分析。首先，需要定义电话网中的各种基本指标，电话交换系统如图3.1。,2023/6/23,http:/,3,定义3.1业务量：业务量描述了在一定时间内，该s条线路被占用的总时间。如果第r条信道被占用Qr秒，则s条信道上的业务量为：如果换一种角度，上述业务量Q的计算可以表达为：其中t0为观察起点,T为观察时长，R(t)为时刻t被占用的信道数，这是一个取值在0到S之间的随机变量。(T时长内被占用的中继数总数),业务量,2023/6/23,http:/,4,呼叫量的单位 erl,上述定义的业务量与观察时长T密切相关，下面定义的呼叫量或话务量与观察时长无关。呼叫量一般用来近似表达电话呼叫流的大小。定义3.2呼叫量 呼叫量的单位为erl，这是一个无量纲的单位。实际上，在图3.1中，在一段时间T内通过的呼叫量就是该时段内被占用的平均中继数。,2023/6/23,http:/,5,对于从外界到达交换系统的呼叫流有两种：一种为无限话源，这种系统被称为爱尔兰（Erlang）系统；另一种为有限话源，这种系统被称为恩格谢特（Engset）系统。,Erlang vs.Engset,2023/6/23,http:/,6,时间阻塞率 vs.呼叫阻塞率,现在来考虑电话网的时间阻塞率和呼损，这是两个重要的性能指标，当图3.1中的s条中继线全部繁忙时，系统处于阻塞状态。系统处于阻塞状态的时间和观察时间的比例称为时间阻塞率，即：定义3.3 时间阻塞率,2023/6/23,http:/,7,定义3.4 呼叫阻塞率或呼损 拒绝呼叫的次数占总呼叫次数的比例定义为呼叫阻塞率。一般，如果到达的呼叫流为Poisson过程，有。掌握计算局部的呼损的Erlang公式和Engset公式是本章的重要的目标。,呼叫阻塞率,2023/6/23,http:/,8,数据交换系统,下面对数据交换系统进行一些说明。,2023/6/23,http:/,9,数据交换系统,在图3.2中，有p条入线和q条出线。在数据网络中，信息一般被截为变长分组，在每条入线上，有不同的到达率。分组包在到达交换系统后，根据路由表完成交换到达相应的出口j。但是因为难以避免的出线冲突，会有不同的入口来的信息包希望同时去同一出线，产生竞争，这些包将在相应的出口排成一个队列，依照次序轮流得到服务。,2023/6/23,http:/,10,时延,数据包在穿越交换机时将经历一段延迟，其中包含交换时延，排队时延和服务时延。交换时延一般固定且较小排队时延可变服务时延与包长有关排队时延和服务时延是时延中最重要的部分，它们的和称为系统时间。对于数据网络，首先需要分析数据包穿越一个交换机的系统时间。,2023/6/23,http:/,11,对于数据网络，有不同的工作方式，包括面向连接和无连接两种主要方式。将对面向连接的数据网络，对其交换系统建立模型，分析其系统时间，进而计算网络任意端对端的时延，然后全网的平均系统时间或平均时延。,面向连接的数据网络,2023/6/23,http:/,12,全网性能分析,电话网络和面向连接的数据网络分别使用平均呼损和平均时延作为性能评估的重要指标。关于它们的计算可以做如下简单考虑：,2023/6/23,http:/,13,网络用图 表示，如果任意两点之间的呼叫量为它们之间的呼损为：,电话网全网平均呼损,2023/6/23,http:/,14,如果任意两点之间信息包的到达率为：它们之间的延迟为：,数据网全网平均延迟,2023/6/23,http:/,15,3.2 Erlang即时拒绝系统,2023/6/23,http:/,16,现在假设电话呼叫流的到来服从Poisson过程，每个呼叫的持续时间服从参数的负指数分布。系统有s条中继线，如果没有空闲的中继线，就拒绝新来的呼叫，并且该呼叫不再进入系统。在这样的情况下，该系统的排队系统模型为,2023/6/23,http:/,17,M/M/s(s)的 状态转移图,2023/6/23,http:/,18,这样该生灭过程的达到率和离去率分别如下:,2023/6/23,http:/,19,根据生灭过程的稳态分布 规律：令根据概率归一性，解得：,2023/6/23,http:/,20,Erlang公式,稳态分布为：特别，当ks 时，表达了中继线全忙的概率，这个概率为系统的时间阻塞率，记为 Erlang B公式,2023/6/23,http:/,21,例3.1 计算M/M/排队系统的平均队长。解：M/M/为一个虚拟系统，有个中继线。到达的呼叫流是参数的Poisson过程，呼叫持续时间服从参数为的负指数分布。由于有个服务员或中继线，系统一定有稳态分布，取系统中的呼叫数为状态变量，这个排队系统是一个生灭过程。状态转移图如图3.4所示。,例3.1,2023/6/23,http:/,22,各状态的到达率和离去率如下：,例3.1 状态转移图,2023/6/23,http:/,23,由生灭过程，设，则：根据概率归一性，则从而稳态分布为上式中的服从参数为a的泊松分布，如果为系统中的呼叫数，则其平均队长EN和方差VarN同为a。平均队长为a表明通过的呼叫量为a。,例3.1 求解过程,2023/6/23,http:/,24,例3.2 计算图3.1中的通过呼叫量。解：通过的呼叫量是被占用的平均中继线数。考虑到稳态分布为：通过的呼叫量：,例3.2 M/M/s(s)的通过呼叫量,2023/6/23,http:/,25,结果的直观意义，如图3.5。a为到达的总呼叫量，a为通过的呼叫量，a和a的关系可以由 来决定。每条中继线平均承载的呼叫量为,例3.2 结论,2023/6/23,http:/,26,根据Erlang公式计算得，。如果时间阻塞率为0.02，30条中继线可以承载21.9erl的呼叫量，而10条中继线可以承载5.08erl的呼叫量。显然后者承载的呼叫量远小于前者的1/3。在同样时间阻塞率下，分散的中继线群承载的总呼叫量小于中继线集中后承载的呼叫量。在实践中，将这种集中效应称为大群化效应,例3.3 大群化效应,2023/6/23,http:/,27,例3.3中的两种情况下，效率是不一样的。在同样的呼损下，小中继线群效率较低。效率高的中继线群对呼叫量的波动更加敏感习题3.3,例3.2 大群化效应效率,2023/6/23,http:/,28,在图3.1的中继线群中，如果将中继线依次编号为1，2，s，并且严格按顺序使用。请计算每条中继线的通过呼叫量。解：对任意k(1ks)，根据中继线的使用规则，在1，2，k这k条中继线上的溢出呼叫量将由k1，k2，s这些中继线来承载。,例3.4 M/M/S(S)顺序使用,2023/6/23,http:/,29,1，2，k1这k1条中继线通过的呼叫量为1，2，k这k条中继线上通过的呼叫量为 所以，第k条中继线通过的呼叫量 这样，第k条中继线通过的呼叫量,例3.4 求解,2023/6/23,http:/,30,例3.5 主备线即时拒绝系统,2023/6/23,http:/,31,3.3 Erlang等待制系统,假设呼叫流的到来服从参数为的Poisson过程每个呼叫的持续时间服从参数为的负指数分布。系统有s条中继线如果呼叫到来时系统中没有空闲的中继线，该呼叫并不被拒绝，而是等待。假设这个系统的等待位置可以是，则该系统的模型为M/M/s。,2023/6/23,http:/,32,3.3 等待制系统,对于这个系统的分析目标首先需要计算稳态分布然后计算一个呼叫到来时需要等待的概率再次需要了解等待时间的均值、分布等。,2023/6/23,http:/,33,等待制系统状态转移图,2023/6/23,http:/,34,该生灭过程各个状态的到达率和离去率如下,等待制系统分析,2023/6/23,http:/,35,假设 为稳态分布，则根据概率归一性，则,等待制系统分析-pk,2023/6/23,http:/,36,在a0。考虑呼叫到达系统的瞬间，不算该呼叫，系统的状态分布为。一般来说，与 是不同的，但是如果到达的呼叫流为Poisson过程，则,等待制系统分析-p0,2023/6/23,http:/,37,一个呼叫到来时，当系统处于状态 时，呼叫需要等待，需要等待的概率计算如下：上式一般被记为：这个公式一般被称为Erlang C公式，用来计算一个呼叫需要等待的概率,等待制系统分析-等待概率,2023/6/23,http:/,38,例3.5 M/M/s系统的通过呼叫量,例3.5 计算在as的条件下，M/M/s系统的通过呼叫量。解：通过呼叫量,2023/6/23,http:/,39,下面通过Little公式计算平均等待时间Ew。系统中的平均呼叫数,例3.5 M/M/s系统的Ew,EN为系统中的平均呼叫数，由被服务的平均呼叫数和等待的平均呼叫数组成,2023/6/23,http:/,40,E(N)结果的推导,2023/6/23,http:/,41,E(N)结果的推导(2),EN为系统中的平均呼叫数，由被服务的平均呼叫数和等待的平均呼叫数组成,2023/6/23,http:/,42,通过的呼叫量为a，即系统中忙的中继线的平均数为a，所以 为等待队列中的平均呼叫数。根据Little公式，平均等待时间,例3.5 M/M/s系统的Ew(续),2023/6/23,http:/,43,如果a25erl，呼损 需要多少中继线？平均每条线的通过呼叫量为多少？拒绝的呼叫量为多少？如果C（s，a）0.01，每个呼叫平均持续时间1/180秒，需要多少条中继线？平均每条线通过的呼叫量为多少？平均等待时间为多少？,例3.6 Erlang公式应用举例,2023/6/23,http:/,44,解：a25erl，计算或者查表得s36 拒绝的呼叫量250.010.25erl 平均每条线通过的呼叫量a/s25（10.01）/360.69。若a25erl，计算或者查表得s39平均每条线通过的呼叫量a/s25/390.64,例3.6 求解,2023/6/23,http:/,45,系统中的平均呼叫数为 平均等待时间为,例3.6 求解（续）,2023/6/23,http:/,46,例3.7 分组交换系统的时间分析,2023/6/23,http:/,47,数据分组流服从参数的泊松过程c表示线路速率数据包长度为变长，平均包长为b，假设包长度服从负指数分布服务时间也就服从负指数分布，且平均服务时间,2023/6/23,http:/,48,数据业务对语义透明性要求较高，在网络正常工作时，图3.8中的存储器溢出概率很小，可以近似认为存储器无限大。交换机的每个出线可以用一个M/M/1系统模拟。根据定理2.5，M/M/1的系统时间s，可以由下面公式计算,例3.7 求解,2023/6/23,http:/,49,包在穿过交换机时，上式中的s将是数据包经历的主要时间。需要注意的是在上式中，没有考虑包的开销对时间的影响。如果为了对数据包进行差错控制，要经历逐段反馈重发，包经历的时间延迟的计算会比较复杂。,例3.7 结果分析,2023/6/23,http:/,50,3.4.1 的稳态分布,现在考虑一般的排队系统，这个系统有s个服务员，但系统的容量为n。呼叫在到达系统时，如果有任何一个空闲的中继线，可以立刻得到服务，而系统如果已有n个呼叫，新到的呼叫会被拒绝。如果到达的呼叫流为参数的Poisson过程，服务时间服从参数为的负指数分布，这个系统是一个生灭过程。,2023/6/23,http:/,51,3.4.1 M/M/s(n)的状态转移图,2023/6/23,http:/,52,从而根据（2.7），稳态分布根据概率归一性，求得,M/M/s(n)分析-pk,2023/6/23,http:/,53,M/M/s(n)分析时间阻塞率pn,呼叫需要等待的概率：时间阻塞率为：,2023/6/23,http:/,54,当ns 时，。排队系统是一个混合系统，既可以允许呼叫等待，又有一定的容量限制，随着系统中s和n取不同的值，会得到不同的排队系统。,M/M/s(n)分析-结论,2023/6/23,http:/,55,M/M/s(n)等待时间的分布,表示呼叫到达时系统中有k个顾客的情况下等待时间的概率。在时间t内离开的呼叫数小于等于ks这个事件与事件 等价,2023/6/23,http:/,56,M/M/s(n)等待时间的分布（续）,2023/6/23,http:/,57,3.5*Engset系统,考虑图3.12中的Engset系统，系统中有s条中继线，系统的输入是n个同样的信源。假设每个信源的输入是参数为的Poisson过程。Engset系统的输入流的强度取决于空闲信源的个数，输入过程不是平稳的。,2023/6/23,http:/,58,2023/6/23,http:/,59,如果当s个中继线全满时，就拒绝新来的呼叫，这样的系统称为Engset拒绝系统；如果当s个中继线全满时，允许呼叫等待，这样的系统就称为Engset等待系统。下面考虑Engset拒绝系统。,2023/6/23,http:/,60,系统的中继线数目sn，每个呼叫的持续时间服从参数为的负指数分布，令 表示一个空闲信源所能提供的呼叫量。图3.13为Engset系统的状态转移图。状态变量,2023/6/23,http:/,61,Engset拒绝系统有 个状态，这是一个生灭过程，各个状态的到达率和离去率分别为：,2023/6/23,http:/,62,稳态分布为：根据概率归一性有,2023/6/23,http:/,63,令 则其中 表示了系统的时间阻塞率。,2023/6/23,http:/,64,Engset拒绝系统的稳态分布,是呼叫到来时，系统中有k个呼叫的概率；根据定义,2023/6/23,http:/,65,特别，当ks时，表示了Engset系统的呼损 这个公式称为Engset呼损公式，用于有限信源的情形。,2023/6/23,http:/,66,特别：例3.9 假设s2，n可以变化，但保持。计算 和。解：根据书上公式（3.36）和（3.37），有,2023/6/23,http:/,67,在n时，由恩格谢特系统变为爱尔兰系统。具体计算一些数值，如：在n10时，；在n12时，。一般认为，在n6s后，恩格谢特系统就可以近似认为是一个爱尔兰系统。在实际应用中，这个条件非常容易满足。另外由于恩格谢特系统相对比较复杂，所以一般不用恩格谢特系统。,2023/6/23,http:/,68,习题,3-1 3-2 3-3 3-43-63-12,
