通信网理论分析课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,通信网基础,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,通信网基础,*,第八章 通信网理论分析,参考教材第十一章,2024/9/17,通信网基础,2,提纲,排队论基础,电路交换网分析,分组交换网分析,2024/9/17,通信网基础,3,排队论基础,排队模型,泊松过程,M/M/1,排队,M/M/m,排队,2024/9/17,通信网基础,4,基本排队模型,输入过程,队 列,服务机构,排队系统,顾客,服务完离开,排队系统的三个基本组成部分,.,输入过程,(,顾客按照怎样的规律到达,);,排队规则,(,顾客按照一定规则排队等待服务,);,服务机构,(,服务机构的设置,服务员的数量,服务的方式,服务时间分布等,),2024/9/17,通信网基础,5,基本排队模型 输入过程,主要考察的是顾客到达服务系统的规律。,可以用一定时间内顾客数或相继到达的间隔时间描述，一般分为确定型和随机型。,随机型的输入是指在时间,t,内顾客到达数,n(t),服从某一概率分布，如泊松分布。,一般用,表示单位时间顾客平均到达率，,1/,为平均间隔时间。,2024/9/17,通信网基础,6,基本排队模型排队规则,不拒绝方式（等待制系统）,先到先服务（,FIFO,）,后到先服务（,LIFO,）,优先制服务,即时拒绝方式（损失制系统）,延时拒绝方式（混合制系统）,2024/9/17,通信网基础,7,基本排队模型服务机构,服务机构,服务设施， 服务渠道与服务员,服务员数量,服务时间分布,确定型,随机型（如：负指数分布）,2024/9/17,通信网基础,8,常见排队模型,M/M/1,排队,表示泊松到达、服务时间服从负指数分布、单服务员的排队系统。,M/M/m,排队,表示泊松到达、服务时间服从负指数服务分布、,m,个服务员的排队系统。,M/G/1,排队,表示泊松到达、服务时间服从一般分布的单服务员排队系统。,M/D/1,排队,表示泊松到达、服务时间为常数的单服务员排队系统。,2024/9/17,通信网基础,9,排队论基础,排队模型,泊松过程,定义,性质,M/M/1,排队,M/M/m,排队,2024/9/17,通信网基础,10,泊松过程定义,用下面三个条件来对泊松过程进行定义。,平稳性,:,在区间,a,，,a+t,内有,k,个顾客到来的概率与起点,a,无关，只与时间区间的长度有关,。,无后效性,：两顾客到达时刻相互独立。,稀疏性,：在足够小的时间间隔,t,内，到达两个或两个以上的顾客的概率为,0,。,t,t,a,a+t,2024/9/17,通信网基础,11,利用上述三点，我们可以求得在,T,间隔内有,k,个顾客到达的概率,p(k),：,其平均值,E(k),和方差：,2024/9/17,通信网基础,12,泊松过程和负指数分布的关系,如果到达是个泊松过程，则到达的时间间隔服从负指数分布，反之亦然,。,证明：设 是一个随即变量，代表任一时间起点与第一次到达之间的时间，取任一值,t,，则,时间起点,第一次到达,t,这正是随机变量 的概率分布函数：,2024/9/17,通信网基础,13,例题,1,某电话局忙时平均呼叫率为,1000,次，则平均来话时间间隔为多少？平均来话间隔小于等于,10,秒的概率是多少？,2024/9/17,通信网基础,14,泊松过程的附加特性,假定有,m,个独立的泊松流，它们的到达率分别为,1,2,n,，则复合流本身也是泊松流，其速率参数,（,证明略,）,2024/9/17,通信网基础,15,排队论基础,排队模型,泊松过程,M/M/1,排队,M/M/m,排队,2024/9/17,通信网基础,16,M/M/1,排队,利用此模型来分析该系统的相关统计特性：系统中的平均顾客数,E(n),、平均排队长度,E(q),、顾客在系统中的平均逗留时间,E(T),和平均等待时间,E(w),等。,泊松到达,负指数服务,无限大缓存器,系统服务强度,/,2024/9/17,通信网基础,17,假设，当系统中有,n,个顾客时，称此系统处于状态,n,，与此对应出现该状态的概率为,P,n,。由此，我们可以用下图表示系统的状态转移关系。,2024/9/17,通信网基础,18,在系统状态图中，有顾客到达时，状态以,速率向右转移一步；有顾客完成服务时状态以速率,向左移动一步。在系统处于统计平衡状态下，可列出系统统计平衡方程：,P,0,=P,1,(+)P,1,=P,0,+P,2,(+)P,n,=P,n-1,+P,n+1,2024/9/17,通信网基础,19,在系统稳态平衡条件下，脱离,n,状态与进入,n,状态保持平衡，所有等式两边相等。根据此平衡方程，我们可以得到：,依此类推，,2024/9/17,通信网基础,20,在,M/M/1,排队系统的存储容量为无穷大时，可以利用概率归一性条件,:,求得：,于是，可以得到无限存储容量,M,M,1,排队的平衡状态概率：,2024/9/17,通信网基础,21,根据所得到的状态概率,P,n,，可以求得不同的排队统计特性。根据随机变量平均值的定义，排队系统中的平均顾客数,(,包括正在被服务的一个,),可以表示为：,2024/9/17,通信网基础,22,M/M/1,排队的平均队长,2024/9/17,通信网基础,23,Little,公式,Little,公式是排队论中的一个重要公式，它说明了平均到达率,、平均时延,E(T),和平均队长,E(n),三者之间的关系，这一关系式对所有排队系统，包括具有优先级排队规则的系统都是适用的。,2024/9/17,通信网基础,24,应用,Little,公式，,M,M,1,排队的平均时延,E(T),可以表示为：,2024/9/17,通信网基础,25,平均等待时间,E(w),和平均等待顾客数量,E(q),这四个统计量可以归纳为与,、,的关系：,(,系统中平均顾客数,),(,顾客平均逗留时间,),(,平均等待顾客数,),(,平均等待时间,),2024/9/17,通信网基础,26,M/M/1/N,(,推广到存储容量为,N,的有限队列排队系统,),N,对应的状态概率的归一性条件为：,我们可以求得：,所以有限队列,M,M,1,排队的状态概率为：,排队系统全满的概率，即系统阻塞概率为：,2024/9/17,通信网基础,27,例题,2,有一个集中器被模型化为一个,M/M/1,排队，输出线的容量为,1200bps,，平均报文长度为,100bit,。它有,N,个输入端。每个平均输入率为,0.1,个报文,/,秒。计算：,如果要求报文在集中器中平均延时小于,1,秒，最多可容纳多少个输入端？,假设有,60,个输入端，系统的业务强度是多少？缓冲器中存储的报文数有多少？,2024/9/17,通信网基础,28,排队论基础,排队模型,泊松过程,M/M/1,排队,M/M/m,排队,2024/9/17,通信网基础,29,M/M/m,排队,M/M/m,排队系统是一个多服务员指数排队系统，属于到达率和离开率依赖于系统状态的排队系统。例如没有“顾客等候室”的电路交换系统属于这一种。,2024/9/17,通信网基础,30,模型及状态转移图,1,m,2024/9/17,通信网基础,31,系统平衡方程,2024/9/17,通信网基础,32,解平衡方程，可以求得系统的平衡概率：,式中，,P,0,为概率常数，可以利用概率归一性条件来求解。,2024/9/17,通信网基础,33,利用上述条件可以得到平衡概率：,2024/9/17,通信网基础,34,M/M/m,特例,1,比较,M/M/1,和,M/M/2,系统性能，说明“使传输能力加倍”与“增加第二条与原来能力相同的中继线”，谁更有效？,2024/9/17,通信网基础,35,M/M/m,特例,2,M/M/,相当于在分组交换或电路交换两种情况下，传输线或中继线的数量总是满足需要传输的分组或呼叫数，因而永远不会有阻塞的可能性。,证明：,2024/9/17,通信网基础,36,M/M/m,特例,3,有限服务机但无存储器的情况,M/M/m(m),在这个系统中，,概率归一化条件为，,于是,当,n=m,时出现阻塞，因此阻塞概率,P,B,和系统效率（每线利用率）分别为：,2024/9/17,通信网基础,37,B,2024/9/17,通信网基础,38,由上表（,M/M/m(m),）可知，若要求,P,B, 0.1,，则,:,当,a=1,爱尔兰时， 须,m,3,=0.31,当,a=10,爱尔兰时， 须,m,13,=0.705,当,a=100,爱尔兰时，须,m,96,=0.94,业务量,线路,m,效率,2024/9/17,通信网基础,39,大群化效应,以,P,B, 0.1,为例，传,10,爱尔兰业务量，要由,10,个,m=3,系统分散处理，共需,30,条线，系统效率,=0.31,：,2024/9/17,通信网基础,40,也可用一个,M/M/13,即拒系统传，同样传,10,爱尔兰，保证,P,B,0.1,，比方案一省,17,条线，,提高一倍多（,0.310.705,）,。,可见集中器，复用器的必要性！,2024/9/17,通信网基础,41,M/M/m(m),模型在实际系统的意义,顾客以泊松过程到达，并总能找到一条中继线，直到全部中继线占完。这时，顾客就不允许再进入了。这一模型常用于电路交换网的分析，由于系统不允许排队（无存储），所以被称为呼损系统，其主要的性能参数是呼损概率。,2024/9/17,通信网基础,42,总结,网络的性能分析在网络管理中具有重要作用。,排队论是通信网性能分析中的常用工具。,在通信网络中，最常用的排队模型是,M/M/m,，其中呼叫（分组）到达和离去过程都服从泊松分布。,电路交换系统的基本设计模型是,M/M/m(m),。,2024/9/17,通信网基础,43,提纲,排队论基础,电路交换网分析,呼损系统,溢呼系统,分组交换网分析,2024/9/17,通信网基础,44,呼损系统,传统的电话交换网是电路交换网。一个由若干个交换节点和交换节点间的中继链路组成的电话交换网,如果在交换节点的全部出线都被占用的情况下仍有新的呼叫发生，交换节点向用户送忙音，表示将这个呼叫从交换系统中清除，这种现象称为呼损。,2024/9/17,通信网基础,45,呼损清除,对于交换节点来讲，如果呼叫到达是泊松过程，中继线群是全利用度线群。当系统发生呼叫阻塞时，该呼叫会被立即清除。则该系统达到统计平衡状态时，呼叫损失概率可以按爱尔兰,B,公式进行计算：,2024/9/17,通信网基础,46,式中，,B(N,A),表示流入话务量为,A,，中继线数为,N,时的呼损概率，式中用,A,/,，表示系统的业务强度，对于电话网就是系统承受的电话负荷（话务量）,例如，电话网的平均来话率,300,次,/,时，每次通话平均时间,2,分钟（即,1/,2,分钟），则此电话网的流入话务量,A,10 Erl,。,话务量单位用,Erl(,爱尔兰，,Erlang),是为了纪念丹麦话务理论家,A.K.Erlang,而命名的。话务量单位也可以用每小时百秒呼（,ccs,）来表示。,Erl,与,ccs,的关系是：,Erl=36ccs,。,2024/9/17,通信网基础,47,利用爱尔兰,B,公式计算系统的呼损概率,例：假定某电话局在上午,9,时到,10,时,1,刻有,500,次呼叫发生，每次呼叫平均占用时间为,200,秒，中继输出线有,29,条，求呼损概率。,解：,平均来话率为：,500/,（,7560,）,0.1111,次,/,秒,平均占用时间为：,1/,200,秒,流入话务量为：,A,/,22.2 Erl,呼损概率为：,B,（,29,，,22.2,）,0.0312,2024/9/17,通信网基础,48,由以上分析可知，在流入话务量之中，除大部分完成通话外，还有一部分被阻塞。完成通话部分话务量可以表示为：,在上例中，容易算出完成话务量为：,对于此交换系统，我们可以进一步求出出线的利用率：,= A(1-B)/N = 21.5/29 = 74%,2024/9/17,通信网基础,49,呼损清除系统的阻塞概率,2024/9/17,通信网基础,50,溢呼系统,在电话网的交换节点之间既设置直达路由，又设置迂回路由，当流入话务量在高效直达路由上被阻塞以后即溢出到迂回路由上，这种系统称为溢呼系统。,2024/9/17,通信网基础,51,具有迂回路由选择的网,1,4,5,3,2,在节点,1,和,2,之间，除了直达路由以外，还有三条迂回路由，即：,(1,，,3)(3,，,2),，,(1,，,4)(4,，,5)(5,，,2),，,(1,，,3)(3,，,4)(4,，,5)(5,，,2),。节点,1,和,2,可以通过这几条路由中的任意一条来完成接续。,2024/9/17,通信网基础,52,在网中设置迂回路由的原因，,提高网络的可靠性，这是不言而喻的；,提高经济性。假设我们希望将从节点,1,到节点,2,的线群,(1,，,2),的呼损限制为,0.02,，如不设迂回路由，必须在这个线群中设置足够的电路以使呼损不超过,0.02,。对比之下，如果设迂回路由，则可在线群,(1,，,2),中配备较少的电路，使有较高的呼损，譬如说,0.1,。如果从节点,1,到节点,2,的呼叫遭到呼损，则可经一条呼损为,0.2,的迂回路由完成接续。由于最终的呼损为,0.10.2,0.02,，所以用户觉察到的总呼损和原设计的,0.02,是一样的。于是，线群,(1,，,2),得到了节省。因此，由直达路由承担两节点之间的主要话务量，而迂回路由承担部分话务量，可取得更好的经济效果。,2024/9/17,通信网基础,53,溢呼话务量的峰值特性,在溢呼系统中，有两类话务量，,一类是到达高效直达路由的话务量，它是服从泊松分布的随机话务量,一类是从高效直达路由溢出到迂回路由的溢出话务量，它是不具有随机特征的溢出话务量。高效路由溢呼话务量的特性如下页图所示。,为了对话务量的特性进行区分，我们引入峰值比概念。峰值比定义为话务量的方差与均值之比。,2024/9/17,通信网基础,54,高效路由溢呼话务量特性,2024/9/17,通信网基础,55,随机话务量,随机话务量是服从泊松分布的话务量。它的平均值,M,和方差,V,可以由下式给出，它的峰值比即为,1,。,当,A Erl,的话务量送入,N,条电路时，其溢呼话务量的均值,M,可以表示为：,M=AB(N,A),2024/9/17,通信网基础,56,溢呼话务量,溢呼话务量的均值,M,可以表示为：,M=AB(N,A),溢呼话务量的方差可按下式计算：,例：,设有随机话务量,A=5.53Erl,送入,N=10,的线群，查呼损表可得：,B (10,，,5.53),0.03,，于是,M=5.53,0.03,0.166Er1,。根据上式算出溢呼话务量的方差为：,2024/9/17,通信网基础,57,等效随机话务量,对于随机话务量，可以利用爱尔兰呼损公式来求呼损概率；而对于溢呼话务量，爱尔兰呼损公式就不再适用。为了解决这个问题，威尔金森,(Wilkinson),提出了一种用“等效随机话务量”来确定迂回路由的呼损概率和迂回路由所需电路数的方法。,2024/9/17,通信网基础,58,图示为一溢呼系统，一般有数条高效直达路由的话务量溢出至同一条迂回路由上，因此迂回路由,iT,上的溢出话务量的均值和方差为,:,j,i,T,2024/9/17,通信网基础,59,迂回路由,iT,上总的话务量为：,根据威尔金森等效随机话务理论，等效话务量,A,*,和等效中继线数量,N,*,可以表示为：,2024/9/17,通信网基础,60,等效关系,所谓等效，是指在以下两种情况下迂回路由 上溢出的话务量相等。,第一种情况是指流入话务量是迂回路由本身的话务量加高效路由的溢出话务量,(,均值为,M,iT,+M,0,),，而中继线群是迂回路由的中继电路数,N,m,。,第二种情况是指流入话务量是等效随机话务量,A,*,，而中继线群是等效中继线群加上迂回路由中继线群,(,数值为,N,*,+N,m,),2024/9/17,通信网基础,61,后一种情况可以利用爱尔兰呼损公式，因此迂回路由的中继线数可以利用下列公式求得：,式中，,B,i,是给定的迂回路由的呼损概率，,M,i,为迂回路由的溢出话务量的均值。,2024/9/17,通信网基础,62,例：参见教材,网的结构如教材图,10.28,，,AB,间的直达话务量为,20Erl,，迂回路由,AT,中的基础话务量为,10 Erl,，,AB,高效直达路由的电路数为,16,，迂回路由,AT,的呼损,0.01,，求迂回路由,AT,所需的电路数。,2024/9/17,通信网基础,63,具有迂回路由的网中阻塞概率,网络由,3,个节点组成，每对节点之间的中继线数目和呼叫量均已确定，如图所示：,路由表为：,第一路由 第一路由,a12 (1,2) (1,3),(3,2),a13 (1,3) (1,2),(2,3),a23 (2,3) (2,1),(1,3),假设,Aij,是链路（,i,j,）承载的业务量之和，则链路（,i,j,）的阻塞率为：,2024/9/17,通信网基础,64,假设：,p,i,j,表示边,(i,j),阻塞率，,P,i,j,表示端对端呼损，,a,i,j,表示端对端话务量，,A,i,j,表示边,(i,j),承载的话务量，,C,i,j,表示边,(i,j),的容量。下面来计算网络的平均呼损：,2024/9/17,通信网基础,65,已知,a,i,j,和,C,i,j,，求解边,(i,j),阻塞率,p,i,j,。,可以迭代求方程组中的边阻塞率,p,ij,，然后根据下面的公式计算,端对端呼损,P,ij,2024/9/17,通信网基础,66,具体过程不再演算，经过迭代，最后得到：,而如果没有迂回路由的话,:,2024/9/17,通信网基础,67,最后可以计算网络的平均呼损,应该能够看出，不同的路由规划会有不同的网络平均呼损。,2024/9/17,通信网基础,68,提纲,排队论基础,电路交换网分析,分组交换网分析,2024/9/17,通信网基础,69,分组交换网分析,分组交换采用存贮转发方式，它有两种服务方式，虚电路与数据报。,所谓虚电路方式是指用户在数据传送之前先要建立端到端的虚连接。它与电路交换建立的实的物理连接不同之处在于，虚连接只在有信息要传送（即信息“突发”）时此连接才被“占用”。但又和数据报服务方式不同，同一呼叫的各个“突发”分组信息的传送路径是相同的。由于虚电路并不独占线路，在一个物理线路上可以同时接纳多个虚电路，因此这种虚电路方式不仅在呼叫开始建立时会有呼损，而且在通信过程中每个“突发”分组到达时还会有阻塞问题,(,传送阻塞,),。不象电路交换，一旦连接建立后，在传送期间是无阻塞的。虚电路服务方式属于面向连接方式。,2024/9/17,通信网基础,70,本节主要分析分组长度不固定的交换网的性能,具体指标：,节点延时,端到端平均延时,网络平均延时,吞吐量,2024/9/17,通信网基础,71,节点延时,在分组交换网中，分组信息在每一个节点被存储、转发而产生时延。交换节点的存储、转发功能可以用一个带有有限容量缓冲器的,M/M/1,排队模型来表示。,缓冲器,=,2024/9/17,通信网基础,72,假定分组信息到达时，在缓冲器内已有,n,个分组在等待发送。因此，要发送的分组信息通过节点的时延由两部分组成，等待时间和服务时间：,T,等待时间服务时间,等待时间是分组信息在节点上等待链路空闲所消耗的时间，服务时间是分组在链路传输时间的总和。在分组网中，每个分组信息在链路上的服务时间即传输时间为：,式中,1/,，,是分组信息的平均长度,(bit/,分组,),，,C,是链路,i,的容量或速率（,bit/s,）。,2024/9/17,通信网基础,73,为了计算在节点的的等待时间，我们仍保持单服务员排队系统的假设条件，于是可求得平均等待时间为：,式中 是链路,i,的分组到达率，单位为（分组,/s,）。则分组通过节点和链路,i,的平均时延为：,2024/9/17,通信网基础,74,端端平均时延,分析端端的平均时延，需要考虑从源点到目的地所经过的路由上每段链路造成的时延影响。同时，由于路由中途经的节点处可能会有新的分组发生，因此，我们在计算从源点发生的分组在经过路由中各节点对时延的影响时，要同时考虑这些节点处发生的新分组。,1,2,3,5,4,2024/9/17,通信网基础,75,假设分组长度为负指数分布。在实际过程中，分组一旦从用户终端发出，在整个传输过程中长度始终不变。这里引入一个独立假设，即分组网中的节点每次收到分组以后加以存储，然后转发到下一个节点，在每一个节点给分组随机的选择一个新的长度。根据独立假设和每一链路模型为,M/M/1,排队，可以得到分组经过链路,i,的平均时延：,2024/9/17,通信网基础,76,例：参见教材,网络结构如图 示。图中节点边上的数字,n,（,x,）表示每秒有,n,个分组进入该节点，该分组的目的地是,x,。各节点发生的所选的路由如图中所示。链路速率为,4800bit/s,，分组平均长度,200bit,求分组从节点,AD,的平均时延。,5(B),2(D),6(A),6(D),4(C),C,A,B,D,E,G,路由：,GB,ABC,ABCD,BCD,CD,EA,3(D,),2024/9/17,通信网基础,77,分组交换吞吐量,吞吐量是进入节点的分组数与完成传送的输出分组数之比。当输入节点的分组数在其传输容量范围以内时，它将全部输出送往目的地，输入与输出数量成比例，输入分组数接近输出容量时吞吐量趋于饱和。,然而实际情况是，当输入量增加太快时，交换节点或路由器不再能够应付，输出分组数反而下降，导致情况恶化。在通信量非常高的情况下，网络完全阻塞，几乎没有分组能够发送。输入负荷与吞吐量的关系示意如图所示。,2024/9/17,通信网基础,78,输入负荷,吞吐量,输入负荷,2024/9/17,通信网基础,79,习题八,Page 352 6,、,7,、,11,、,13,