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