爱尔兰拒绝和等待系统

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,104,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,通信网基础,第三章,爱尔兰拒绝与等待系统,无线通信与网络研究室,拒绝系统、等待系统,通信网络中,信息流有不确定性,没有有规律；,大量终端的信息流有统计规律性。,实际系统中，呼叫遇到无可用资源时：,立即拒绝该呼叫,如电话交换系统；,让该呼叫等待，有可用资源再处理，,如数据交换系统。,通信网与排队论中术语对应关系,电话网中基本指标,中继线，,s,条,电话呼叫流的到达率,一个呼叫，在中继线有空闲时，占用中继线，完成接续；,系统中,s,条中继线全部忙时，呼叫被拒绝。,电话交换系统,业务量、呼叫量（话务量）,业务量：在一定时间内，线路（,s,条）被占用的总时间。,第,r,条信道被占用,Q,r,秒，则,s,条信道上的业务量为：,t,0,为观察起点，,T,为观察时长，,R,（,t,）为时刻,t,被占用的信道数，则,业务量、呼叫量（话务量）,呼叫量用来近似表达电话呼叫流的大小。,单位为,erl,，无量纲,在电话交换系统中，一段时间,T,内通过的话务量就是该时段内被占用的平均中继数。,实际网络中，,R,（,t,）是非平稳的。通常称一天中最忙的一小时内的呼叫量为日呼叫量；在一年内取,30,天，这些天日呼叫量的平均值为年呼叫量。,爱尔兰系统、恩格谢特系统,对于从外界到达交换系统的呼叫流，一种为无限话源，这种系统被称为爱尔兰（,Erlang,）系统；,另一种为有限话源，这种系统被称为恩格谢特（,Engset,）系统。,电话和分组交换系统的基本模型,对应两种目前主要应用的交换方式,电话交换系统,时间阻塞率、呼叫阻塞率（呼损）,系统处于阻塞状态的时间和观察时间的比例称为时间阻塞率,拒绝呼叫的次数占总呼叫次数的比例定义为呼叫阻塞率，在实际应用中，呼叫阻塞率也被称为呼损,时延、时延的分析,对数据交换系统，数据包在穿越交换机时将经历一段延迟，其中包含交换时延，排队时延和服务时延。,交换时延一般固定且较小，,排队时延可变，排队时延和服务时延是时延中最重要的部分，它们和称为系统时间。,对于数据网络，首先需要分析数据包穿越一个交换机的系统时间。,全网平均呼损、全网平均延迟,电话网络和面向连接的数据网络分别用平均呼损和平均时延作为性能评估的重要指标。,假设网络用图,G,= (,V,E,),表示，端点和边集合的大小分别为：,|,V,|=,n,|,E,|=,m,。,全网平均呼损,如果任意两点之间的呼叫量为,a,i j, 1,i,j,n,它们之间的呼损为：,p,i j, 1,i,j,n,全网平均呼损、全网平均延迟,如果任意两点之间信息包的到达率为：,ij,，,1,i,j,n,它们之间的时延为：,T,i 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,公式,当,k,s,时，,p,s,表达了中继线全忙的概率，即为系统时间阻塞率。,为了强调,a,，,s,，,p,s,也用,B,（,s,，,a,）表达,即著名的,Erlang,公式，,A.K.Erlang,1917,年得到。公式中,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/,系统的平均队长,上式中的,p,k,服从参数为,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,=,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.9,erl,的呼叫量；而,10,条中继线可以承载,5.08,erl,的呼叫量。,这种集中也有负面影响，因为呼叫量可能会波动，在同样的波动水平下，大容量的中继线群上的呼损将上升较多。,例,3,：大群化效应,这两种情况下，效率是不一样的，效率高的中继线群对呼叫量的波动更加敏感。,同样的呼损下，小中继线群效率较低。,补充：综合效应,一般指不同性质的业务综合起来在一条线路上传输。例如：把数字和模拟、宽带和窄带、实时与非实时、高速和低速的业务等综合处理，以实现大容量信道的大群化效应。,信道综合可以提高信道利用率，降低呼损。,信源处也可以综合。例如在话音间隙或者图像扫描的逆程中插入数据，这属于在实时业务的间隙时间传输非实时业务。,例,4,：中继线顺序限制,在中继线群中，如果将中继线依次编号为,1,，,2,，,，,s,，并且严格按顺序使用。请计算每条中继线的通过呼叫量。,解：,对任意,k,，,1,k, 0,，考虑计算,p,w,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,个正在被服务，,k,s,个在等待。在时间,t,内离开的呼叫数小于等于,k,s,这个事件与事件,w,t,等价；又系统在此期间的输出过程是参数为,s,的,Poisson,过程。由,Poisson,过程（,2.1,）则：,M/M/s(n),的稳态分布,将（,3.25,）和（,3.26,）（,3.29,），则,其中,p,0,由（,3.26,）给出。,M/M/s(n),的稳态分布,总结：,对于一个排队系统，如果知道稳态分布,p,k,和等待时间,w,的分布，可以认为对这个排队系统的稳态特征有完整的了解。这样，对系统,M,/,M,/,s,(,n,),的稳态分析基本完成。,一般混合制的,M/M/s(n),系统,习题,3-1,3-2,3-3,3-4,3-6,3-12,