爱尔兰拒绝和等待系统.ppt

通信网基础,第三章 爱尔兰拒绝与等待系统,无线通信与网络研究室李屹 博士,拒绝系统、等待系统,通信网络中信息流有不确定性没有有规律；大量终端的信息流有统计规律性。实际系统中，呼叫遇到无可用资源时：立即拒绝该呼叫 如电话交换系统；让该呼叫等待，有可用资源再处理，如数据交换系统。,通信网与排队论中术语对应关系,电话网中基本指标中继线，s 条电话呼叫流的到达率 一个呼叫，在中继线有空闲时，占用中继线，完成接续；系统中s 条中继线全部忙时，呼叫被拒绝。,电话交换系统,业务量、呼叫量（话务量）,业务量：在一定时间内，线路（s 条）被占用的总时间。第r 条信道被占用Qr 秒，则s 条信道上的业务量为：t0 为观察起点，T 为观察时长，R（t）为时刻t 被占用的信道数，则,业务量、呼叫量（话务量）,呼叫量用来近似表达电话呼叫流的大小。单位为erl，无量纲在电话交换系统中，一段时间T 内通过的话务量就是该时段内被占用的平均中继数。实际网络中，R（t）是非平稳的。通常称一天中最忙的一小时内的呼叫量为日呼叫量；在一年内取30 天，这些天日呼叫量的平均值为年呼叫量。,爱尔兰系统、恩格谢特系统,对于从外界到达交换系统的呼叫流，一种为无限话源，这种系统被称为爱尔兰（Erlang）系统；另一种为有限话源，这种系统被称为恩格谢特（Engset）系统。,电话和分组交换系统的基本模型,对应两种目前主要应用的交换方式,电话交换系统,时间阻塞率、呼叫阻塞率（呼损）,系统处于阻塞状态的时间和观察时间的比例称为时间阻塞率拒绝呼叫的次数占总呼叫次数的比例定义为呼叫阻塞率，在实际应用中，呼叫阻塞率也被称为呼损,时延、时延的分析,对数据交换系统，数据包在穿越交换机时将经历一段延迟，其中包含交换时延，排队时延和服务时延。交换时延一般固定且较小，排队时延可变，排队时延和服务时延是时延中最重要的部分，它们和称为系统时间。对于数据网络，首先需要分析数据包穿越一个交换机的系统时间。,全网平均呼损、全网平均延迟,电话网络和面向连接的数据网络分别用平均呼损和平均时延作为性能评估的重要指标。假设网络用图G=(V,E)表示，端点和边集合的大小分别为：|V|=n,|E|=m。全网平均呼损如果任意两点之间的呼叫量为ai j,1 i,j n它们之间的呼损为：pi j,1 i,j n,全网平均呼损、全网平均延迟,如果任意两点之间信息包的到达率为：ij，1 i,j n它们之间的时延为：Ti j,1 i,j n在电话网中，仅需要描述两个端之间的呼叫量，不需要区别方向；但是数据网络中，需要在计算时区分端点的方向。网络的平均呼损和平均时延，是评价网络性能的重要指标，为网络规划和优化建立基础。,爱尔兰即时拒绝系统,爱尔兰即时拒绝系统的假设，排队模型为M/M/s(s)基于状态转移图进行稳态分析，得到爱尔兰B公式（系统的时间阻塞率、到达交换机的总呼叫量）全利用度系统、部分利用度系统例：M/M/系统的平均队长（为了说明爱尔兰公式中的总呼叫量含义）例：M/M/s(s)系统的通过呼叫量、溢出话务量、利用率（效率）的计算例：大群化效应（正面、负面影响，对呼叫量波动的敏感性）例：中继线使用顺序有限制时的每条中继线通过呼叫量分析例：主备线即时拒绝系统的稳态分析,爱尔兰即时拒绝系统-M/M/s(s),对电话交换系统如果为呼叫的到达率，每个呼叫可到达任意一个空闲中继线。假设电话呼叫流的到来服从Poisson 过程，每个呼叫的持续时间服从参数 的负指数分布。系统有s 条中继线，呼叫到来时，如果没有空闲的中继线，就拒绝该呼叫。该交换系统的排队系统模型为M/M/s(s)。,状态转移图,用系统中的呼叫数表示状态，这个排队系统是一个生灭过程的达到率和离去率分别为：,稳态分析,根据生灭过程的稳态分布令a=，并根据概率归一性解得从而稳态分布为：,爱尔兰B公式,当ks 时，ps 表达了中继线全忙的概率，即为系统时间阻塞率。为了强调a，s，ps也用B（s，a）表达即著名的Erlang 公式，1917 年得到。公式中a=的意义是到达交换机的总呼叫量,全利用度系统、部分利用度系统,虽然这个公式的推导需要假设呼叫持续时间服从负指数分布，但证明公式对服务时间的分布没有要求。在Erlang 公式的推导中，假设每个呼叫可以到达任意一个空闲的中继线，这种系统被称为全利用度系统。而Erlang 公式仅能应用于全利用度系统。如果呼叫不能到达任意一个空闲的中继线，而只能到达部分中继线，这个系统称为部分利用度系统。其时间阻塞率或呼损的计算比较复杂，由于部分利用度系统利用率低，部分利用度系统的呼损会大于相应全利用度系统的呼损。Erlang 公式计算出交换系统的时间阻塞率，考虑到a 为客观值，Erlang 公式表达了B(s,a)和s 的关系，为电话网络的规划和中继线容量配置奠定了基础。,例1：M/M/系统的平均队长,M/M/系统有个中继线，到达的呼叫流是参数 的Poisson过程，呼叫持续时间服从参数为 负指数分布。系统一定有稳态分布，取系统中的呼叫数为状态变量，这个排队系统是一个生灭过程。状态转移图为：,例1：M/M/系统的平均队长,各状态的到达率和离去率k=，k 0k=k，k 1由生灭过程，设a=，则根据概率归一性，稳态分布为,例1：M/M/系统的平均队长,上式中的pk 服从参数为a 的Poisson 分布，如果N为系统中的呼叫数，则其平均队长EN和方差VarN同为a。平均队长为a 表明通过的呼叫量为a，由于没有拒绝，说明到达的总呼叫量为a。,例2：M/M/s(s)系统的通过呼叫量,通过的呼叫量是被占用的平均中继线数。考虑到稳态分布为：通过的呼叫量：,例2：M/M/s(s)系统的通过呼叫量,a为到达的总呼叫量，a 为通过的呼叫量，a 和a的关系为：a=a 1 B(s,a)。同时被拒绝的呼叫量：a a=a B(s,a)被拒绝的呼叫量有时也被称为溢出话务量。每条中继线平均承载的呼叫量为：=s=a s。值也度量了s 条中继线的利用率或效率。,例3：大群化效应,一般来说，社会服务资源在一定范围内统一利用要优于分散经营，通信网中的信道资源也有类似的规律。在保障一定通信质量指标的前提下，变分散利用的信道为集中利用的信道，有效提高网络效率，这就是所谓通信线路大群化。,例3：大群化效应,根据Erlang 公式计算得，B(30,21.9)=0.02，B(10,5.08)=0.02 如果要求时间阻塞率小于0.02，30 条中继线可以承载21.9erl 的呼叫量；而10 条中继线可以承载5.08erl 的呼叫量。这种集中也有负面影响，因为呼叫量可能会波动，在同样的波动水平下，大容量的中继线群上的呼损将上升较多。,例3：大群化效应,这两种情况下，效率是不一样的，效率高的中继线群对呼叫量的波动更加敏感。同样的呼损下，小中继线群效率较低。,补充：综合效应,一般指不同性质的业务综合起来在一条线路上传输。例如：把数字和模拟、宽带和窄带、实时与非实时、高速和低速的业务等综合处理，以实现大容量信道的大群化效应。信道综合可以提高信道利用率，降低呼损。信源处也可以综合。例如在话音间隙或者图像扫描的逆程中插入数据，这属于在实时业务的间隙时间传输非实时业务。,例4：中继线顺序限制,在中继线群中，如果将中继线依次编号为1，2，s，并且严格按顺序使用。请计算每条中继线的通过呼叫量。解：对任意k，1ks，根据中继线的使用规则，在1，2，k 这k 条中继线上的溢出呼叫量将由k1，k2，s 这些中继线来承载。根据例2，1，2，k1 这k1 条中继线通过的呼叫量为：a1 B(k 1,a)1，2，k 这k 条中继线上通过的呼叫量为：a1 B(k,a),例4：中继线顺序限制,所以，第k 条中继线通过的呼叫量第k 条中继线通过的呼叫量：a k=aB(k 1,a)B(k,a)，1 k s，且B(0,a)=1对比：前面计算的s为随机占用中继线的情况下，每条线的效率或通过的呼叫。,例5：主备线即时拒绝系统,二种输出线路A：主用线B：备用线（A溢出时B）并非A故障时用 B,目标与假设：分析呼损，为方便可假设为无限用户定义状态：（a，b）=00，01，10，11 01有，AB占，A先毕，B尚有状态图:00：（1）01：（2）11：（3）10：（4）,例5：主备线即时拒绝系统,因 即 令解得:系统利用率:此时利用率同M/M/2(2),例5：主备线即时拒绝系统,爱尔兰等待制系统,爱尔兰等待制系统在假设呼叫流的到来服从参数为的Poisson过程，每个呼叫的持续时间服从参数为的负指数分布。系统有s条中继线，如果呼叫到来时系统中没有空闲的中继线，该呼叫并不被拒绝，而是等待。如果假设这个系统的等待位置可以是，则该系统的模型为M/M/s。,爱尔兰等待制系统,爱尔兰等待制系统图3.6 等待制系统 呼叫流的到达率 中继线的数目,爱尔兰等待制系统,爱尔兰等待制系统图3.6 等待制系统 呼叫流的到达率 中继线的数目,爱尔兰等待制系统,爱尔兰等待制系统图3.6 等待制系统 呼叫流的到达率 中继线的数目,可以呼叫任意一个空闲的中继线,爱尔兰等待制系统,爱尔兰等待制系统图3.6 等待制系统 呼叫流的到达率 中继线的数目,爱尔兰等待制系统,爱尔兰等待制系统图3.6 等待制系统 呼叫流的到达率 中继线的数目,可以呼叫任意一个空闲的中继线,爱尔兰等待制系统,爱尔兰等待制系统图3.6 等待制系统 呼叫流的到达率 中继线的数目,可以呼叫任意一个空闲的中继线,爱尔兰等待制系统,爱尔兰等待制系统的假设,爱尔兰等待制系统,爱尔兰等待制系统的假设,爱尔兰等待制系统,爱尔兰等待制系统的假设,爱尔兰等待制系统,爱尔兰等待制系统的假设,每个呼叫的持续时间服从参数为 的负指数分布,爱尔兰等待制系统,爱尔兰等待制系统的假设,每个呼叫的持续时间服从参数为 的负指数分布,爱尔兰等待制系统,爱尔兰等待制系统的假设,每个呼叫的持续时间服从参数为 的负指数分布,爱尔兰等待制系统,爱尔兰等待制系统的假设,爱尔兰等待制系统M/M/S模型,M/M/S模型M/M/S/?,表示呼叫流的到达系统这一本质特征。M示呼叫流的到来服从参数为 的泊松分布，每个呼叫的持续时间服从参数为 的负指数分布。,爱尔兰等待制系统M/M/S模型,M/M/S模型M/M/S/?,爱尔兰等待制系统M/M/S模型,M/M/S模型M/M/S/?,爱尔兰等待制系统M/M/S模型,M/M/S模型M/M/S/?,呼叫需要的服务时间的概率分布特性。M表示负指数分布。,爱尔兰等待制系统M/M/S模型,M/M/S模型M/M/S/?,爱尔兰等待制系统M/M/S模型,M/M/S模型M/M/S/?,中继线的个数,爱尔兰等待制系统M/M/S模型,M/M/S模型M/M/S/?,爱尔兰等待制系统M/M/S模型,M/M/S模型M/M/S/?,表示存储器的记忆量，一般认为存储器的记忆量无限大，省略掉此项。,爱尔兰等待制系统系统分析,等待制系统的分析计算稳态分布,爱尔兰等待制系统系统分析,等待制系统的分析计算稳态分布计算一个呼叫到来时需要等待的概率,爱尔兰等待制系统系统分析,等待制系统的分析计算稳态分布计算一个呼叫到来时需要等待的概率了解等待时间的分布与均值,爱尔兰等待制系统状态转移图,M/M/S状态转移图,爱尔兰等待制系统状态转移图,M/M/S状态转移图,爱尔兰等待制系统状态转移图,M/M/S状态转移图,爱尔兰等待制系统系统分析,系统是一个生灭过程该生灭过程各个状态的到达率和离去率如下：,爱尔兰等待制系统系统分析,假设 为稳态分布，为平均数目，则：,根据Little定理，平均延迟为：,爱尔兰等待制系统系统分析,根据概率归一性，则：,爱尔兰等待制系统系统分析,在 的条件下，该系统有稳定状态，且以上给出了M/M/S系统的稳态分布,爱尔兰等待制系统系统分析,爱尔兰C公式（Erlang C）用来计算一个呼叫等待的概率计算概率，为需要等待的时间呼叫到达系统的瞬间，不算该呼叫系统状态分布为一般 与 不同，如果到达的呼叫流为泊松过程，则：,爱尔兰等待制系统系统分析,一个呼叫到来且系统状态处于 时，呼叫需要等待，需要等待的概率计算如下：,爱尔兰等待制系统系统分析,一般被记为：在 的条件下，M/M/S系统有稳态，图3.6中通过的呼叫量，由于该系统不拒绝呼叫，应该为,爱尔兰等待制系统系统分析,例3.5 计算在 条件下，M/M/S系统的通过呼 叫量。解：通过的呼叫量,爱尔兰等待制系统系统分析,下面通过Little公式计算平均等待时间首先，求系统的平均呼叫数,爱尔兰等待制系统系统分析,经整理，得：其中：,爱尔兰等待制系统系统分析,根据例3.5，通过的呼叫量为，这也是系统中忙的中继线的平均数，所以，上式中 为等待队列中的平均呼叫数。根据Little公式，平均等待时间：,爱尔兰等待制系统分析举例,例3.6 如果，呼损，每个呼叫平均持续时间 秒，需要多少中继线？平均每条线的通过呼叫量为多少？拒绝的呼叫量为多少？如果，需要多少条中继线、平均每条线通过的呼叫量为多少？平均等待时间为多少？解：，计算或查表得：,爱尔兰等待制系统分析举例,拒绝的呼叫量=平均每条线通过的呼叫量=如果：计算或查表得：平均每条线通过的呼叫量=,爱尔兰等待制系统分析举例,系统中的平均呼叫数：平均等待时间：秒,爱尔兰等待制系统分析举例,例3.7 考察一个负载为m个数据流的通信链路，假设这m个数据流相互独立，它们的总到达速率等于，将这个链路分解为m个信道，每个信道传送一个数据流。分析：为了提高系统利用率，系统中采用统计复用方式。,爱尔兰等待制系统分析举例,当一个数据流没有数据包需要传输时候，其对应的传输信道可以用于传输其他数据流的数据包。系统的每个数据包的平均延迟可用M/M/S模型得到。平均延迟时间平均等待时间和平均服务时间的和。平均延迟时间T：,爱尔兰等待制系统分析举例,例3.8 分组交换系统的时间分析数据分组或包在进入交换系统后，依照路由表完成交换。由于出线冲突等原因，数据分组将会排队等待服务，出端排队是一种较常见的形式。分析中暂不考虑包的开销对时间的影响数据业务对语义透明性要求较高，在网络正常工作时，存储器溢出概率很小，因此可以近似认为存储器无限大。,爱尔兰等待制系统分析举例,图3.10 分组交换系统的时间分析,爱尔兰等待制系统分析举例,图3.10 分组交换系统的时间分析,爱尔兰等待制系统分析举例,图3.10 分组交换系统的时间分析,爱尔兰等待制系统分析举例,图3.10 分组交换系统的时间分析,爱尔兰等待制系统分析举例,图3.10 分组交换系统的时间分析,爱尔兰等待制系统分析举例,图3.10 分组交换系统的时间分析,线路速率,爱尔兰等待制系统分析举例,到达的数据分组流服从参数 的泊松过程 表示线路速率数据包长度为变长，平均包长为假设包长度服从负指数分布因此，服务时间也服从负指数分布,爱尔兰等待制系统分析举例,平均服务时间为：交换机的每个出线可以用一个M/M/1系统模拟M/M/1排队系统在稳态时，系统时间 服从参数为 的负指数分布,爱尔兰等待制系统分析举例,M/M/1的系统时间 可由下式计算得出。,上式中 将是数据包经历的主要时间。,介绍了等待制系统和爱尔兰等待制系统的假设，排队模型为M/M/S。,爱尔兰等待制系统课程回顾,课程回顾,A,基于状态转移图的稳态分析，得到爱尔兰C公式。,介绍了等待制系统和爱尔兰等待制系统的假设，排队模型为M/M/S。,爱尔兰等待制系统课程回顾,课程回顾,A,B,1、如果为了对数据包进行差错控制，要经历逐段反馈重发，包经历的延时时间的计算会比较复杂。,爱尔兰等待制系统课程拓展,1、如果为了对数据包进行差错控制，要经历逐段反馈重发，包经历的延时时间的计算会比较复杂。,爱尔兰等待制系统课程拓展,2、现代网络一般使用光纤为传输媒介，网络已将差错控制交给用户层完成，反馈重发一般为端对端的形式。,爱尔兰等待制系统课程拓展,3、网络层一般最多做一些差错监测，而不负责差错控制。因此计算时间的时候，可以不考虑差错控制的影响。,爱尔兰等待制系统课程拓展,3、网络层一般最多做一些差错监测，而不负责差错控制。因此计算时间的时候，可以不考虑差错控制的影响。,4、如果考虑包的开销和网络中的控制，网络模型会复杂一些。,一般混合制的M/M/s(n)系统,M/M/s(n)问题的一般性：M/M/1问题、非截至的M/M/m问题、延时拒绝的单窗口问题M/M/1(n)、即时拒绝的多窗口问题M/M/m(m)均为其特例。M/M/s(n)问题的稳态分析，得到：新到顾客的平均等待时间、平均等待的顾客数、平均队长、系统效率在上述稳态分析中，注意体现M/M/s(n)问题的一般性，对特例问题也做简单分析各种特性曲线及其分析,现在考虑一般的M/M/s(n)排队系统，这个系统有s个服务员但系统的容量为n。呼叫到达系统时，如果有任何一个空闲的中继线，可以立即得到服务，而系统如果已有n个呼叫，新到的呼叫就会被拒绝。如果到达的呼叫流为参数的泊松过程，服务时间服从参数为的负指数分布，则这个系统是一个生灭过程，各状态的参数如式（3.24）、（3.25）所示。状态转移图如图3.9所示。,M/M/s(n)的稳态分布,图3.9 M/M/s(n)状态转移图,M/M/s(n)的稳态分布,M/M/s(n)的稳态分布,从而根据（2.7），稳态分布根据概率归一性，求得p0：,M/M/s(n)的稳态分布,（3.25）和（3.26）给出了M/M/s(n)的稳态分布。特别的，呼叫需要等待的概率：,M/M/s(n)的稳态分布,当n时,时间阻塞率Pn为：当ns 时，M/M/s(n)排队系统是一个混合系统，既可以允许呼叫等待，系统又有一定的容量限制，随着系统中s 和n 取不同的值，会得到不同的排队系统。,M/M/s(n)的稳态分布,M/M/s(n)等待时间分布对于排队系统，除了队长分布，另外一个最重要的指标是呼叫的等待时间分布。对于任意t 0，考虑计算pw t，利用分布 k，有：其中p w t k 表示呼叫到达时系统中有k 个顾客的情况下，等待时间w t的概率。,M/M/s(n)的稳态分布,因为 k 和p k是一致的，则：下面考虑计算p k w t,s k n 1。,M/M/s(n)的稳态分布,因为系统在呼叫到来时有k 个呼叫，其中s 个正在被服务，ks 个在等待。在时间t 内离开的呼叫数小于等于ks 这个事件与事件w t等价；又系统在此期间的输出过程是参数为s 的Poisson 过程。由Poisson 过程（2.1）则：,M/M/s(n)的稳态分布,将（3.25）和（3.26）（3.29），则其中p0 由（3.26）给出。,M/M/s(n)的稳态分布,总结：对于一个排队系统，如果知道稳态分布p k和等待时间w 的分布，可以认为对这个排队系统的稳态特征有完整的了解。这样，对系统M/M/s(n)的稳态分析基本完成。,一般混合制的M/M/s(n)系统,习题,3-1 3-2 3-3 3-43-63-12,