《排队论基础》PPT课件.ppt

《《排队论基础》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《排队论基础》PPT课件.ppt（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Network Laboratory第二章第二章网内业务分析网内业务分析Network Laboratory1排队论基础排队论基础常见现象：常见现象：顾客顾客+服务服务排队系统排队系统矛盾统一矛盾统一 Network Laboratory广义化：广义化：通信中：呼叫通信中：呼叫线路线路信息包信息包分组交换机分组交换机移动体移动体服务区服务区计算机：总线指令计算机：总线指令CPU处理处理数据流数据流存储器存储器其它：敌机其它：敌机防空设施防空设施客机客机跑道跑道Network Laboratory复复杂杂性性：在在于于随随机机性性到到达达与与离离去去（服服务务率）均不确定率）均不确定工作于随机状

2、态工作于随机状态资源少资源少顾客排队长顾客排队长服务质量下降服务质量下降资源多资源多服务闲置服务闲置资源浪费资源浪费Network Laboratory目标：为顾客提供满意服务同时提高资目标：为顾客提供满意服务同时提高资源利用率。（与统计参数和工作方源利用率。（与统计参数和工作方式有关）式有关）在在通通信信网网的的业业务务分分析析和和性性能能计计算算中中，排排队队论论是不可缺少的是不可缺少的Network Laboratory、基本概念、基本概念 m-窗口数，表示资源的量。可同时向顾客提供窗口数，表示资源的量。可同时向顾客提供服务的设施数。（单窗口排队系统服务的设施数。（单窗口排队系统m=1；

3、多窗；多窗口排队系统口排队系统m1）-顾客到达率（平均）顾客到达率（平均）-系统服务率（平均）系统服务率（平均）1.排队系统三要素排队系统三要素:m，Network Laboratory平均到达时间平均到达时间:平均到达率平均到达率单位时间到达顾客数单位时间到达顾客数 或或(n(T)(n(T)T T内到达数）内到达数）负荷轻负荷轻-顾客到达率（平均）顾客到达率（平均）Network Laboratory同理同理 平均服务时间平均服务时间：系统服务率（平均）：系统服务率（平均）Network Laboratory此此三三量量可可已已知知或或可可测测出出，但但描描述述排排队队系系统统，此三要素不充

4、分。此三要素不充分。主主要要取取决决于于ti和和i的的统统计计特特性性（分分布布）和和排排队规则。队规则。Network Laboratory2、统计特性（分布）和排队规则统计特性（分布）和排队规则。常见排队系统的假设常见排队系统的假设l平稳性：平稳性：a，a+t内到达内到达k个顾客（或离去）的概率与个顾客（或离去）的概率与a无关，只与无关，只与t有关。有关。l无后效性无后效性顾客到达时刻相互独立顾客到达时刻相互独立不相交区间内到达顾客数相互独立不相交区间内到达顾客数相互独立系统顾客数具有马氏性系统顾客数具有马氏性l稀疏性：稀疏性：t内到达内到达2个或个或2个以上顾客概率为个以上顾客概率为0有

5、限区间内的有限区间内的k为有限，或为有限，或Network Laboratory(1)T内有内有k个顾客到达的概率个顾客到达的概率在以上假设下：在以上假设下：T内到达顾客数为内到达顾客数为k内有内有1顾客到达概率顾客到达概率内无顾客到达概率内无顾客到达概率1-有有2 2个到达概率个到达概率 Network Laboratory据无后效性据无后效性,独立独立据二项分布据二项分布,N个贝努利分布个贝努利分布T T内有内有k k个到达的概率个到达的概率:Network Laboratory（2）到达间隔）到达间隔t的概率密度的概率密度a（t）到达间隔到达间隔t连续变量连续变量 把把t t分分N N份

6、，到达间隔为份，到达间隔为t t的概率：的概率：（N N个个内无到达，第内无到达，第N+1N+1个必到达）个必到达）若若t t的概率密度的概率密度a a（t t）存在，则有：）存在，则有：指数分布Network Laboratory（3）服）服务时间的概率密度的概率密度以上结果亦适用于服务过程，以上结果亦适用于服务过程，可得Network Laboratory综上所述，在以上三个假设下？：综上所述，在以上三个假设下？：l顾客到达和离去均为泊松流，均值顾客到达和离去均为泊松流，均值，二阶矩，二阶矩(+1)l相邻事件发生的间隔负指数分布，均值相邻事件发生的间隔负指数分布，均值1/，二阶矩二阶矩1/

7、2l具有马尔可夫性，称具有马尔可夫性，称M分布称最简单流分布称最简单流Network Laboratory（4）运行方式及规则规定：）运行方式及规则规定：排排队队系系统统的的运运行行性性能能不不仅仅与与上上述述的的统统计计分分布布有有关关，还还与与系系统统预预 先先 规规 定定 的的 工工 作作 方方 式式 有有 关关。包包 括括 服服 务务 规规 则则 和和 排排 队队 规规 则则：Network Laboratory按服务规则分：按服务规则分：1）先到先服务：常见情况）先到先服务：常见情况2）后到先服务：不常见情况）后到先服务：不常见情况3）优先制服务：顾客分优先级）优先制服务：顾客分优先

8、级Network Laboratory按排队规则分：按排队规则分：1）等等待待型型：不不拒拒绝绝系系统统。若若窗窗口口不不空空，就就依依次次排队等待，直到被服务完毕后离去。排队等待，直到被服务完毕后离去。2）截止型：分为损失制、拒绝系统）截止型：分为损失制、拒绝系统系系统统已已有有n个个顾顾客客等等待待，顾顾客客到到来来时时，就就被被拒拒绝绝。分为如下分为如下2种种即即时时拒拒绝绝：如如窗窗口口数数为为m,m=n,满满，则则顾顾客客到到达达后后立即被拒绝，被拒绝排队等待立即被拒绝，被拒绝排队等待（电话网）（电话网）延迟拒绝：延迟拒绝：mn,mn,允许等待一定数量，超允许等待一定数量，超n n，

9、再拒，再拒绝绝(带缓冲存储的数据通信）带缓冲存储的数据通信）Network Laboratory(1)(1)队长队长k k：某时刻观察系统内滞留的顾客数。：某时刻观察系统内滞留的顾客数。(2)(2)等待时间等待时间w:w:顾客从到达至开始被服务这段时顾客从到达至开始被服务这段时间。间。(3)(3)服务时间服务时间 ：一个顾客被服务的时间：一个顾客被服务的时间(4)(4)系统时间系统时间s s，或称系统停留时间，或称系统停留时间 ：顾客从到：顾客从到达至离开的这段时间。达至离开的这段时间。S=w+S=w+(5)(5)系统效率系统效率 ：平均窗口占用率：平均窗口占用率目标参量：目标参量：（分析排队

10、系统时的主要求解指标（分析排队系统时的主要求解指标)Network Laboratory(6)(6)稳定性指定性指标：对于不拒于不拒绝系系统，当到，当到达率达率与服与服务率率 之比（称之比（称为排排队系系统强度度 ）大于窗口数）大于窗口数m m时，平均，平均顾客到达数将大于平均客到达数将大于平均顾客离去数，客离去数，顾客客的的队将越来越将越来越长，平均等待，平均等待时间将将趋于于无限大，系无限大，系统不不稳定。小于窗口数定。小于窗口数m m时，系系统是是稳定的定的(m)。对于截止型系于截止型系统，因因为队长被限制，即使排被限制，即使排队强度大于度大于m m，系系统仍然可以仍然可以稳定工作。定工

11、作。=/=/Network Laboratory队长队长kl排队长度排队长度t瞬间系统内的顾客数（含在窗口的）瞬间系统内的顾客数（含在窗口的）lk离散随机变量离散随机变量l三种观察：三种观察：ldk顾客到达时观察队长为顾客到达时观察队长为k的概率（不包括刚的概率（不包括刚到达的顾客）到达的顾客）lrk顾客服务完毕离去时观察队长为顾客服务完毕离去时观察队长为k的概率的概率（不包括正在离去的顾客）。（不包括正在离去的顾客）。l（以上为有条件抽样）（以上为有条件抽样）lpk（服务员）随机观察队长为（服务员）随机观察队长为k的概率的概率l在最简系统中，在最简系统中，pk=rk=dkl 平均队长，又称系

12、统数平均队长，又称系统数Network Laboratory等待时间等待时间w从到达从到达开始服务的时间，是连续随机变量，开始服务的时间，是连续随机变量，其统计平均为：其统计平均为：平均等待时间（网络中等待时延的主要平均等待时间（网络中等待时延的主要部分）部分）其它时延，如传输时延和处理时延较小其它时延，如传输时延和处理时延较小 Network Laboratory服务时间服务时间 l开始接受服务开始接受服务服务完毕离去服务完毕离去l 平均服务时间平均服务时间Network Laboratory到达到达离去离去 s=w+s=w+对任何排队系统，有对任何排队系统，有 系统时间系统时间s s，或称

13、系统停留时间，或称系统停留时间Network Laboratory系统效率系统效率 平均窗口占用率平均窗口占用率 共共m m个窗口，某时刻如有个窗口，某时刻如有r r个被占用，则个被占用，则 Network Laboratory=/=/稳定性指标稳定性指标Network Laboratory不拒绝系统：不拒绝系统：Network Laboratory 仍然仍然稳定定截止型系统：截止型系统：Network Laboratory排队系统表示符号：排队系统表示符号：A/B/m(N,n)A/B/m(N,n)A A到达规律，到达规律，分布分布a(t)a(t)（到达时间间隔）（到达时间间隔）B B 服务规

14、律，服务规律，分布分布b(b()（服务时间间隔）（服务时间间隔）m m窗口数窗口数N N顾客源，潜在顾客数，省略为顾客源，潜在顾客数，省略为 n n截止队长，省略为截止队长，省略为，不拒绝，不拒绝Network Laboratory常见分布：常见分布：Network LaboratoryM M指数分布指数分布Network Laboratory将将讨论:l基本：基本：M/M/1 M/M/m(n)M/M/1 M/M/m(n)l中中级：M/G/1 G/M/1M/G/1 G/M/1l高高级：G/G/1G/G/1Network Laboratory解法：解法：确定状确定状态变量，如量，如k画状画状态转

15、移移图列状列状态转移方程移方程求解目求解目标参量参量Network Laboratory设平均到达率平均到达率为，平均服，平均服务率率为。取取队长为状状态变量建立系量建立系统的差微分的差微分方程。方程。1 1、状、状态图与状与状态方程方程t t时刻刻，系系统内内有有k k个个顾客客的的概概率率（k=0,1,2,k=0,1,2,）二、M/M/1问题t t时刻，时刻，k k状态状态 则：则：tttt内到达内到达1 1人概率人概率 tttt内离去内离去1 1人概率人概率 Network Laboratoryt+t时时刻刻处处于于k状状态态（概概率率），由由下下述述情情况形成：况形成：t为为k-1态，

16、态，t内到达内到达1人，无人离去，人，无人离去，概率概率:t为为k+1态，态，t内离去内离去1人，无到达：人，无到达：t为为k态，态，t内到达内到达1人，离去人，离去1人人:t为为k态，态，t内无到达，无离去内无到达，无离去:Network LaboratoryNetwork Laboratory即柯尔莫哥洛夫方程。即柯尔莫哥洛夫方程。Network Laboratoryk=0,需重写需重写:原原1人人,去去1人人 tp1(t)原原0人人,无人到无人到 (1-t)p0(t)p0(t+t)=t)=tptp1 1(t)+(t)+(1-t t)p p0 0(t)(t)得得:至此至此，得得M/M/1完

17、整状态方程完整状态方程:Network Laboratory上式，已由上式，已由，表示转移，得状态转移图：表示转移，得状态转移图：Network Laboratory2 2、稳态解解l物理意物理意义：到达与离去平衡，到达与离去平衡，p pk k(t)(t)与与t t无关无关 l数学描述：数学描述：Network LaboratoryNetwork Laboratory求求p0:用归一化条件用归一化条件 p0系统无人概率（空闲率）系统无人概率（空闲率）1-p0=系统有人概率（忙概率）系统有人概率（忙概率）忙忙 太大太大不稳不稳得通解：得通解：Network Laboratory平均平均队长Net

18、work Laboratoryk k的方差的方差Network LaboratoryNetwork LaboratoryNetwork Laboratory等待等待时间w w 若系若系统已有已有k k人人,即即处于于K K状状态,来一来一人的等待人的等待时间w w是是为前面前面k k个人的服个人的服务时间总和和 即即:因因为为 i i相相互互独独立立，则则wk是是k个个独独立立变变量量之之和和，所所以，以，w wk k的特征函数为的特征函数为k个个 i i的特征函数之积。的特征函数之积。i的特征函数的特征函数:(b()概率的付氏变换概率的付氏变换)k个个 i和的特征函数和的特征函数 Netwo

19、rk Laboratory因为因为k为离散变量为离散变量,故故w的特征函数的特征函数:Network Laboratoryw的密度的密度:平均等待时间平均等待时间:w的方差的方差:系统时间系统时间(平均停留平均停留)反验反验Little公式公式:Network Laboratory至此至此,得得M/M/1M/M/1结论如下如下:Network LaboratoryNetwork Laboratory所所 以以,M/M/1主主 要要 矛矛 盾盾 集集 中中 在在 的的 选选 取取 服务质量与系统效率之间的矛盾服务质量与系统效率之间的矛盾解决目标解决目标:保证稳定运行条件下提高效率保证稳定运行条件

20、下提高效率M/M/1M/M/1系系统统的的主主要要缺缺点点是是服服务务质质量量与与系系统统效率的的矛盾。解决的办法有两种效率的的矛盾。解决的办法有两种措施措施:（1）增加窗口数（增大效率，但投资加大）增加窗口数（增大效率，但投资加大）（2）截截止止排排队队长长度度，即即采采用用拒拒绝绝型型系系统统（降降低低系统质量（顾客被拒绝），换取效率和稳定性）系统质量（顾客被拒绝），换取效率和稳定性）将上述两个方法结合为将上述两个方法结合为截止多窗口排队系统截止多窗口排队系统 Network Laboratory三、三、M/M/m(n)M/M/m(n)问题l常常见多窗口排多窗口排队方式有两种：方式有两种：

21、混合排混合排队（M/M/m(n)M/M/m(n)分别排队(为M个独立的M/M/1)Network LaboratoryM/M/m(n)M/M/m(n)排排队模型模型窗窗口口数数为为m,截截止止队队长长为为n.每每个个窗窗口口的的服服务务率率均均为为，服务时间和到达间隔均为指数分布。即：服务时间和到达间隔均为指数分布。即：窗口服务时间窗口服务时间总到达率总到达率令令:令系统内顾客数k为状态变量，此时，只有n+1种状态。K=m时，有k个窗口在被占用，则服务率为k ,当当mkn时时,pk=0,永稳定永稳定以拒绝换稳定以拒绝换稳定Network LaboratoryM/M/m(n)的平均等待时间的平均

22、等待时间 只算只算 情况即可情况即可 k=m等等1人人k=m+1等等2 对对k等等k-m+1人人Network Laboratory所以所以:Network LaboratoryM/M/m(n)M/M/m(n)的几种特例的几种特例Network Laboratorya)a)当当n=m.n=m.为多窗口即多窗口即时拒拒绝系系统Network Laboratoryb)b)当当n n,为多窗口非拒多窗口非拒绝系系统,数学的数学的M/M/mM/M/m问题拒拒绝概率概率p pc c=0=0平均等待的平均等待的顾客数客数:Network Laboratoryc)c)当当m=1,m=1,为单窗口。窗口。M/

23、M/1(n)M/M/1(n)Network Laboratoryd)d)当当m=1,nm=1,n为M/M/1M/M/1Network LaboratoryM/M/m(n)M/M/m(n)系系统效率效率:效率即指平均窗口占用率效率即指平均窗口占用率(统计平均统计平均)窗口不满窗口不满占用率占用率k/m窗口满窗口满(k=m)占用率占用率=1Network Laboratory 当当n,不拒绝多窗口不拒绝多窗口 单窗口单窗口 当当n=m,即时拒绝即时拒绝 当当m=1,M/M/1(n)不拒绝系统只能取不拒绝系统只能取,当当 时时 系统不稳定系统不稳定,Network Laboratory 拒绝型系统可以取拒绝型系统可以取 仍能稳定工作仍能稳定工作,以拒绝概率以拒绝概率(呼损呼损)为代价为代价 一一定定,增增加加截截止止队队长长(n)可可提提高高效效率率,但但等等待待时时间间亦长亦长延迟换效率延迟换效率 所以，若延迟指标允许，用非即时拒绝型是所以，若延迟指标允许，用非即时拒绝型是合理的合理的