爱尔兰拒绝和等待系统

通信网基础第三章爱尔兰拒绝与等待系统无线通信与网络研究室李屹博士 拒绝系统、等待系统通信网络中信息流有不确定性没有有规律；大量终端的信息流有统计规律性。实际系统中，呼叫遇到无可用资源时：立即拒绝该呼叫如电话交换系统；让该呼叫等待，有可用资源再处理，如数据交换系统。 通信网与排队论中术语对应关系电话网中基本指标中继线，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。全网平均呼损如果任意两点之间的呼叫量为aij,1≤i,j≤n它们之间的呼损为：pij,1≤i,j≤n 全网平均呼损、全网平均延迟如果任意两点之间信息包的到达率为：λij，1≤i,j≤n它们之间的时延为：Tij,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公式当k＝s时，ps表达了中继线全忙的概率，即为系统时间阻塞率。为了强调a，s，ps也用B（s，a）表达即著名的Erlang公式，A.K.Erlang1917年得到。公式中a=λ∕μ的意义是到达交换机的总呼叫量 全利用度系统、部分利用度系统虽然这个公式的推导需要假设呼叫持续时间服从负指数分布，但证明公式对服务时间的分布没有要求。在Erlang公式的推导中，假设每个呼叫可以到达任意一个空闲的中继线，这种系统被称为全利用度系统。而Erlang公式仅能应用于全利用度系统。如果呼叫不能到达任意一个空闲的中继线，而只能到达部分中继线，这个系统称为部分利用度系统。其时间阻塞率或呼损的计算比较复杂，由于部分利用度系统利用率低，部分利用度系统的呼损会大于相应全利用度系统的呼损。Erlang公式计算出交换系统的时间阻塞率，考虑到a为客观值，Erlang公式表达了B(s,a)和s的关系，为电话网络的规划和中继线容量配置奠定了基础。 例1：M/M/∞系统的平均队长M/M/∞系统有∞个中继线，到达的呼叫流是参数λ的Poisson过程，呼叫持续时间服从参数为μ负指数分布。系统一定有稳态分布，取系统中的呼叫数为状态变量，这个排队系统是一个生灭过程。状态转移图为： 例1：M/M/∞系统的平均队长各状态的到达率和离去率λk=λ，k≥0μk=kμ，k≥1由生灭过程，设a=λ∕μ，则根据概率归一性，稳态分布为 例1：M/M/∞系统的平均队长上式中的{pk}服从参数为a的Poisson分布，如果N为系统中的呼叫数，则其平均队长E[N]和方差Var[N]同为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′=aB(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，1≤k0，考虑计算p{w>t}，利用分布{πk}，有：其中p{wt}k>表示呼叫到达时系统中有k个顾客的情况下，等待时间w>t的概率。M/M/s(n)的稳态分布 因为{πk}和{pk}是一致的，则：下面考虑计算pk{w>t},s≤k≤n−1。M/M/s(n)的稳态分布 因为系统在呼叫到来时有k个呼叫，其中s个正在被服务，k－s个在等待。在时间t内离开的呼叫数小于等于k－s这个事件与事件{w>t}等价；又系统在此期间的输出过程是参数为sμ的Poisson过程。由Poisson过程（2.1）则：M/M/s(n)的稳态分布 将（3.25）和（3.26）（3.29），则其中p0由（3.26）给出。M/M/s(n)的稳态分布 总结：对于一个排队系统，如果知道稳态分布{pk}和等待时间w的分布，可以认为对这个排队系统的稳态特征有完整的了解。这样，对系统M/M/s(n)的稳态分析基本完成。一般混合制的M/M/s(n)系统 习题3-13-23-33-43-63-12