第三章Erlang拒绝和等待系统.ppt

《第三章Erlang拒绝和等待系统.ppt》由会员分享，可在线阅读，更多相关《第三章Erlang拒绝和等待系统.ppt（68页珍藏版）》请在三一文库上搜索。

1、第三章 Erlang拒绝和等待系统,通信网实验室 http:/ 介绍,在本章中将要对不同的交换系统建立起排队系统模型，并进行性能分析。 首先，需要定义电话网中的各种基本指标，电话交换系统如图3.1。,2019/7/16,http:/ 。 如果第r条信道被占用Qr秒，则s条信道上的业务量为： 如果换一种角度，上述业务量Q的计算可以表达为： 其中t0为观察起点,T为观察时长，R(t)为时刻t被占用的信道数，这是一个取值在0到S之间的随机变量。(T时长内被占用的中继数总数),业务量,2019/7/16,http:/ erl,上述定义的业务量与观察时长T密切相关，下面定义的呼叫量或话务量与观察时长无关

2、。呼叫量一般用来近似表达电话呼叫流的大小。 定义3.2呼叫量 呼叫量的单位为erl，这是一个无量纲的单位。 实际上，在图3.1中，在一段时间T内通过的呼叫量就是该时段内被占用的平均中继数。,2019/7/16,http:/ 一种为无限话源，这种系统被称为爱尔兰（Erlang）系统； 另一种为有限话源，这种系统被称为恩格谢特（Engset）系统。,Erlang vs. Engset,2019/7/16,http:/ vs. 呼叫阻塞率,现在来考虑电话网的时间阻塞率和呼损，这是两个重要的性能指标，当图3.1中的s条中继线全部繁忙时，系统处于阻塞状态。 系统处于阻塞状态的时间和观察时间的比例称为时间

3、阻塞率，即： 定义3.3 时间阻塞率,2019/7/16,http:/ 呼叫阻塞率或呼损 拒绝呼叫的次数占总呼叫次数的比例定义为呼叫阻塞率。 一般 ，如果到达的呼叫流为Poisson过程，有 。 掌握计算局部的呼损的Erlang公式和Engset公式是本章的重要的目标。,呼叫阻塞率,2019/7/16,http:/ 2中，有p条入线和q条出线。 在数据网络中，信息一般被截为变长分组，在每条入线上，有不同的到达率。 分组包在到达交换系统后，根据路由表完成交换到达相应的出口j。 但是因为难以避免的出线冲突，会有不同的入口来的信息包希望同时去同一出线，产生竞争，这些包将在相应的出口排成一个队列，依照

4、次序轮流得到服务。,2019/7/16,http:/ 交换时延一般固定且较小 排队时延可变 服务时延与包长有关 排队时延和服务时延是时延中最重要的部分，它们的和称为系统时间。 对于数据网络，首先需要分析数据包穿越一个交换机的系统时间。,2019/7/16,http:/ 将对面向连接的数据网络，对其交换系统建立模型，分析其系统时间，进而计算网络任意端对端的时延，然后全网的平均系统时间或平均时延。,面向连接的数据网络,2019/7/16,http:/ 关于它们的计算可以做如下简单考虑：,2019/7/16,http:/ 表示， 如果任意两点之间的呼叫量为 它们之间的呼损为：,电话网全网平均呼损,2

5、019/7/16,http:/ 它们之间的延迟为：,数据网全网平均延迟,2019/7/16,http:/ Erlang即时拒绝系统,2019/7/16,http:/ 系统有s条中继线，如果没有空闲的中继线，就拒绝新来的呼叫，并且该呼叫不再进入系统。 在这样的情况下，该系统的排队系统模型为,2019/7/16,http:/ 的 状态转移图,2019/7/16,http:/ :,2019/7/16,http:/ 规律： 令 根据概率归一性， ，解得：,2019/7/16,http:/ 特别，当ks 时， 表达了中继线全忙的概率，这个概率为系统的时间阻塞率，记为 Erlang B公式,2019/7/

6、16,http:/ 计算M/M/排队系统的平均队长。 解：M/M/为一个虚拟系统，有个中继线。到达的呼叫流是参数的Poisson过程，呼叫持续时间服从参数为的负指数分布。 由于有个服务员或中继线，系统一定有稳态分布，取系统中的呼叫数为状态变量，这个排队系统是一个生灭过程。状态转移图如图3.4所示。,例3.1,2019/7/16,http:/ 状态转移图,2019/7/16,http:/ ，则： 根据概率归一性， ，则 从而稳态分布为 上式中的服从参数为a的泊松分布，如果为系统中的呼叫数，则其平均队长EN和方差VarN同为a。 平均队长为a表明通过的呼叫量为a。,例3.1 求解过程,2019/7

7、/16,http:/ 计算图3.1中的通过呼叫量。 解：通过的呼叫量是被占用的平均中继线数。 考虑到稳态分布为： 通过的呼叫量：,例3.2 M/M/s(s)的通过呼叫量,2019/7/16,http:/ a为到达的总呼叫量，a为通过的呼叫量，a和a的关系可以由 来决定。 每条中继线平均承载的呼叫量为,例3.2 结论,2019/7/16,http:/ ， 。 如果时间阻塞率为0.02，30条中继线可以承载21.9erl的呼叫量，而10条中继线可以承载5.08erl的呼叫量。显然后者承载的呼叫量远小于前者的1/3。 在同样时间阻塞率下，分散的中继线群承载的总呼叫量小于中继线集中后承载的呼叫量。 在

8、实践中，将这种集中效应称为大群化效应,例3.3 大群化效应,2019/7/16,http:/ 在同样的呼损下，小中继线群效率较低。 效率高的中继线群对呼叫量的波动更加敏感习题3.3,例3.2 大群化效应效率,2019/7/16,http:/ 解：对任意k(1ks)，根据中继线的使用规则，在1，2，k这k条中继线上的溢出呼叫量将由k1，k2，s这些中继线来承载。,例3.4 M/M/S(S)顺序使用,2019/7/16,http:/ 1，2，k这k条中继线上通过的呼叫量为 所以，第k条中继线通过的呼叫量 这样，第k条中继线通过的呼叫量,例3.4 求解,2019/7/16,http:/ 主备线即时拒

9、绝系统,2019/7/16,http:/ Erlang等待制系统,假设呼叫流的到来服从参数为的Poisson过程 每个呼叫的持续时间服从参数为的负指数分布。 系统有s条中继线 如果呼叫到来时系统中没有空闲的中继线，该呼叫并不被拒绝，而是等待。 假设这个系统的等待位置可以是，则该系统的模型为M/M/s。,2019/7/16,http:/ 等待制系统,对于这个系统的分析目标 首先需要计算稳态分布 然后计算一个呼叫到来时需要等待的概率 再次需要了解等待时间的均值、分布等。,2019/7/16,http:/ 为稳态分布， ，则 根据概率归一性，则,等待制系统分析-pk,2019/7/16,http:/

10、 考虑呼叫到达系统的瞬间，不算该呼叫，系统的状态分布为 。一般来说， 与 是不同的，但是如果到达的呼叫流为Poisson过程，则,等待制系统分析-p0,2019/7/16,http:/ 时，呼叫需要等待，需要等待的概率计算如下： 上式一般被记为： 这个公式一般被称为Erlang C公式，用来计算一个呼叫需要等待的概率,等待制系统分析-等待概率,2019/7/16,http:/ M/M/s系统的通过呼叫量,例3.5 计算在as的条件下，M/M/s系统的通过呼叫量。 解：通过呼叫量,2019/7/16,http:/ 。 系统中的平均呼叫数,例3.5 M/M/s系统的Ew,EN为系统中的平均呼叫数，

11、由被服务的平均呼叫数和等待的平均呼叫数组成,2019/7/16,http:/ 为等待队列中的平均呼叫数。 根据Little公式，平均等待时间,例3.5 M/M/s系统的Ew(续),2019/7/16,http:/ 需要多少中继线？平均每条线的通过呼叫量为多少？拒绝的呼叫量为多少？ 如果C（s，a）0.01，每个呼叫平均持续时间1/180秒，需要多少条中继线？平均每条线通过的呼叫量为多少？平均等待时间为多少？,例3.6 Erlang公式应用举例,2019/7/16,http:/ a25erl， 计算或者查表得s36 拒绝的呼叫量250.010.25erl 平均每条线通过的呼叫量 a/s25（10

12、.01）/360.69。 若a25erl， 计算或者查表得s39 平均每条线通过的呼叫量 a/s25/390.64,例3.6 求解,2019/7/16,http:/ 平均等待时间为,例3.6 求解（续）,2019/7/16,http:/ 分组交换系统的时间分析,2019/7/16,http:/ c表示线路速率 数据包长度为变长，平均包长为b，假设包长度服从负指数分布 服务时间也就服从负指数分布，且平均服务时间,2019/7/16,http:/ 交换机的每个出线可以用一个M/M/1系统模拟。根据定理2.5，M/M/1的系统时间s，可以由下面公式计算,例3.7 求解,2019/7/16,http:

13、/ 如果为了对数据包进行差错控制，要经历逐段反馈重发，包经历的时间延迟的计算会比较复杂。,例3.7 结果分析,2019/7/16,http:/ 的稳态分布,现在考虑一般的排队系统，这个系统有s个服务员，但系统的容量为n。 呼叫在到达系统时，如果有任何一个空闲的中继线，可以立刻得到服务，而系统如果已有n个呼叫，新到的呼叫会被拒绝。 如果到达的呼叫流为参数的Poisson过程，服务时间服从参数为的负指数分布，这个系统是一个生灭过程。,2019/7/16,http:/ M/M/s(n) 的状态转移图,2019/7/16,http:/ 根据概率归一性，求得,M/M/s(n)分析-pk,2019/7/1

14、6,http:/ 时间阻塞率为：,2019/7/16,http:/ 时， 。 排队系统是一个混合系统，既可以允许呼叫等待，又有一定的容量限制，随着系统中s和n取不同的值，会得到不同的排队系统。,M/M/s(n)分析-结论,2019/7/16,http:/ 等待时间的分布,表示呼叫到达时系统中有k个顾客的情况下等待时间的概率。 在时间t内离开的呼叫数小于等于ks这个事件与事件 等价,2019/7/16,http:/ 等待时间的分布（续）,2019/7/16,http:/ Engset系统,考虑图3.12中的Engset系统，系统中有s条中继线，系统的输入是n个同样的信源。假设每个信源的输入是参数

15、为的Poisson过程。 Engset系统的输入流的强度取决于空闲信源的个数，输入过程不是平稳的。,2019/7/16,http:/ 下面考虑Engset拒绝系统 。,2019/7/16,http:/ 表示一个空闲信源所能提供的呼叫量。图3.13为Engset系统的状态转移图。 状态变量,2019/7/16,http:/ 个状态，这是一个生灭过程，各个状态的到达率和离去率分别为：,2019/7/16,http:/ 根据概率归一性有,2019/7/16,http:/ 则 其中 表示了系统的时间阻塞率 。,2019/7/16,http:/ 根据定义,2019/7/16,http:/ 表示了Engset系统的呼损 这个公式称为Engset呼损公式，用于有限信源的情形。,2019/7/16,http:/ 例3.9 假设s2，n可以变化，但保持 。计算 和 。 解：根据书上公式（3.36）和（3.37），有,2019/7/16,http:/ 在n10时， ， ； 在n12时， ， 。 一般认为，在n6s后，恩格谢特系统就可以近似认为是一个爱尔兰系统。在实际应用中，这个条件非常容易满足。另外由于恩格谢特系统相对比较复杂，所以一般不用恩格谢特系统。,2019/7/16,http:/ 3-2 3-3 3-4 3-6 3-12,