排队论大学课件11-马尔科夫排队网络.ppt

1、l三种队长分布的关系三种队长分布的关系lBurke定理定理l开马尔可夫排队网络开马尔可夫排队网络l闭马尔可夫排队网络闭马尔可夫排队网络l下面我们研究三种时刻队长分布的关系下面我们研究三种时刻队长分布的关系lpn-=P(顾客到达时系统中已有顾客到达时系统中已有n个顾客个顾客)lPn=P(N=n)=平稳分布队长为平稳分布队长为n的概率的概率lpn+=P(顾客离开系统时系统还有顾客离开系统时系统还有n个顾客的个顾客的概率概率)lG/G/1系统系统pn-=pn+N(t)tn+1n跟踪跟踪N(t)实际走过的一条路线实际走过的一条路线l假定从状态假定从状态n上跳到状态上跳到状态n+1的次数为的次数为An(

2、t)从状态从状态n+1下跳到状态下跳到状态n的次数为的次数为Dn(t)l由于到达与离去是一个一个发生的，并且由于到达与离去是一个一个发生的，并且n-n+1与与n+1-n是交错发生的。所以到是交错发生的。所以到t时刻为止，时刻为止，An(t)与与Dn(t)至多相至多相差差1l设设A(t)、D(t)为从任何状态开始上跳一步的总次数和下跳为从任何状态开始上跳一步的总次数和下跳一步的总次数，在统计平衡条件下，有：一步的总次数，在统计平衡条件下，有：()()()lim1()tA tD tD tA t()()()()()()lim()()()()()()lim()()()()()()()()limlim1

3、()()()()0nnnnnntnnnntnnnttnnA tD tppA tD tD tA tD tA tD tA tA tA tD tD tD tA tD tA tA tA tD tD tA tD tpplM/G系统有系统有pn-(t)=pn(t)，即任意时刻，到达的顾客看到的队长分布等，即任意时刻，到达的顾客看到的队长分布等于系统队长的分布于系统队长的分布l证明证明令令A(t,t+t)表示在表示在t,t+t)时间内到达了一个顾客，则时间内到达了一个顾客，则 因为输入流是泊松流，所以因为输入流是泊松流，所以A(t,t+t)发生的概率是发生的概率是 t+o(t)，与，与N(t)=n这个事件无

4、关。所以这个事件无关。所以00()()|(,)(),(,)lim(,)()(,)|()lim(,)nttp tP N tn A t ttP N tn A t ttP A t ttP N tnP A t ttN tnP A t tt 0(,)|()(,)()lim()()nnntP A t ttN tnP A t ttptp tp t 】lG/G排队系统排队系统pn-=pn+即到达的顾客与离开的顾客所看到的队长即到达的顾客与离开的顾客所看到的队长分布是相等的分布是相等的lM/G排队系统中排队系统中pn-=pn+=pn即顾客为泊松流到达的排队系统中，到达即顾客为泊松流到达的排队系统中，到达的顾客与

5、离开的顾客看到的队长分布与系的顾客与离开的顾客看到的队长分布与系统的队长分布都相等统的队长分布都相等 l我们前面学习的情况，都是顾客只请求一种服务，服务完我们前面学习的情况，都是顾客只请求一种服务，服务完离去，这种系统叫做单节点系统或叫单节点网络。离去，这种系统叫做单节点系统或叫单节点网络。l如果一个排队系统只是一个节点，那么多个节点就可以组如果一个排队系统只是一个节点，那么多个节点就可以组成一个排队网络。每个节点都含有一个服务机构和排队机成一个排队网络。每个节点都含有一个服务机构和排队机构，是一个简单的排队系统，当顾客离开某个排队系统节构，是一个简单的排队系统，当顾客离开某个排队系统节点就进

6、入下一个节点。例如数据包在通信网中传输点就进入下一个节点。例如数据包在通信网中传输123到达到达到达到达到达到达离开离开离开离开离开离开排队网络排队网络(注意不要与状态流图混淆注意不要与状态流图混淆)l定义：定义：马尔可夫排队网络指的是各节点外部到达顾客流马尔可夫排队网络指的是各节点外部到达顾客流是泊松流，各节点的服务时间是负指数分布的网是泊松流，各节点的服务时间是负指数分布的网络系统。络系统。l关注的问题：关注的问题：网络结构描述了节点之间的允许的转移网络结构描述了节点之间的允许的转移使用随机过程对顾客流的描述例如离开节点使用随机过程对顾客流的描述例如离开节点i的顾客都立即进入节点的顾客都立

7、即进入节点i1，则前者的顾客离去，则前者的顾客离去间隔时间就是后者的顾客到达间隔时间间隔时间就是后者的顾客到达间隔时间l举例，假定举例，假定1号节点是一个号节点是一个M/M/1排队系统排队系统2号节点的顾客输入流就是号节点的顾客输入流就是1号节点的顾客输出流号节点的顾客输出流考虑考虑1号节点顾客离开的间隔时间，假定其服从分布号节点顾客离开的间隔时间，假定其服从分布d(t)，d(t)的拉普拉斯变换为的拉普拉斯变换为D*(x)。1号节点的服务时间分布的号节点的服务时间分布的拉普拉斯变换为拉普拉斯变换为B*(x)，顾客到达间隔时间分布的的拉普，顾客到达间隔时间分布的的拉普拉斯变换为拉斯变换为A*(x

8、)。有：。有：12？*()*()AxBxxxl情况一：前面顾客离开后，后面接着有顾客来接受服务情况一：前面顾客离开后，后面接着有顾客来接受服务两顾客离开的间隔时间就是后面顾客的服务时间两顾客离开的间隔时间就是后面顾客的服务时间l情况二：前面顾客离开后，系统顾客为情况二：前面顾客离开后，系统顾客为0两顾客离开的间隔时间是后面顾客到达的间隔时间后面顾客两顾客离开的间隔时间是后面顾客到达的间隔时间后面顾客服务的时间服务的时间1*()*()DxBx2*()*()*()DxAxBx后一个顾客前一个顾客前一个顾客后一个顾客l情况一出现的概率顾客离开时发现系统中有顾客的概率情况一出现的概率顾客离开时发现系统

9、中有顾客的概率顾客到达时发现系统中有顾客的概率统计平衡时系统顾客到达时发现系统中有顾客的概率统计平衡时系统队长不为队长不为0的概率的概率 l同理，情况二出现的概率同理，情况二出现的概率1-l所以所以l可见，可见，M/M/1排队系统的顾客输出流是泊松流，并且强度排队系统的顾客输出流是泊松流，并且强度与其输入流强度相同与其输入流强度相同12*()*()(1)*()()(1)()()()tDxDxDxxxxxd telBurke定理定理在平稳状态下，在平稳状态下，M/M/n排队系统的顾客离开的过排队系统的顾客离开的过程为泊松过程，离开率等于到达率。并且程为泊松过程，离开率等于到达率。并且M/M/n是

10、唯一具有此种性质的是唯一具有此种性质的FCFS排队系统。排队系统。l因此，此时再看因此，此时再看2号节点号节点2号节点的输入流是强度为号节点的输入流是强度为 的泊松流，所以的泊松流，所以2号节点也是号节点也是一个普通的一个普通的M/M/1排队系统，并且可以与排队系统，并且可以与1号节点独立分号节点独立分开讨论开讨论。lBurke定理：定理：多个多个M/M/n排队系统连接在一起所形成的网络，排队系统连接在一起所形成的网络，每个节点能够依旧保持原本每个节点能够依旧保持原本M/M/n的特性。的特性。12泊松流泊松流l（Jackson定理）假定排队网络由定理）假定排队网络由N个节点组成，且满足如个节点

11、组成，且满足如下条件下条件每个节点都是一个每个节点都是一个./M/n排队系统，节点排队系统，节点i有有ni个服务窗，每个服个服务窗，每个服务窗独立工作，平均服务时间为务窗独立工作，平均服务时间为1/i。顾客从网络外部到达第顾客从网络外部到达第i个节点的流是参数为个节点的流是参数为 i的泊松流的泊松流在节点在节点i服务完的顾客以概率服务完的顾客以概率pij到达节点到达节点j或者以或者以 的概率的概率离开网络系统离开网络系统设节点设节点i的总平均到达率为的总平均到达率为 i（包括网络外部的到达率（包括网络外部的到达率 i和其他节和其他节点到达节点点到达节点i的全部到达率之和），则的全部到达率之和）

12、，则 i满足方程组满足方程组设在节点设在节点i处有处有ki个顾客，则系统的状态记做（个顾客，则系统的状态记做（k1,k2,kN）设在）设在统计平衡条件下的概率为统计平衡条件下的概率为P(k1,k2,kN),如果如果 iniui l则则pi(ki)是节点是节点i在统计平衡条件下有在统计平衡条件下有ki个顾客的概率。个顾客的概率。11Nijjp121122(,.)()()()NNNP k kkp k p kpk11,2,3.NiijijjpjN lJackson定理的直观理解定理的直观理解N个节点的马尔可夫网络，如果把到达节点个节点的马尔可夫网络，如果把到达节点i的合的合流理解成是强度为流理解成是

13、强度为 i的泊松流，则节点的泊松流，则节点i就是一个就是一个独立的排队系统，从而整个网络的状态概率是各独立的排队系统，从而整个网络的状态概率是各个节点相应状态概率的乘积。个节点相应状态概率的乘积。求解开马尔可夫排队网络模型的步骤：求解开马尔可夫排队网络模型的步骤：l求解各个节点的顾客平均到达率求解各个节点的顾客平均到达率l分别求解各个节点的目标参量分别求解各个节点的目标参量l多重程序二阶段循环模型。在多重程序的计算机系统中，多重程序二阶段循环模型。在多重程序的计算机系统中，一些程序同时存在主存储器中，每一程序有中央处理机指一些程序同时存在主存储器中，每一程序有中央处理机指令和输入输出指令组成。

14、当输入输出器处理某一程序的输令和输入输出指令组成。当输入输出器处理某一程序的输入输出时，直到它完成这种输入或输出此程序才执行中央入输出时，直到它完成这种输入或输出此程序才执行中央处理机处理的其他程序指令。这种程序就是这样在中央处处理机处理的其他程序指令。这种程序就是这样在中央处理机与输入输出器之间循环，直到全部完成为止。每一程理机与输入输出器之间循环，直到全部完成为止。每一程序在存储器中处于四种状态之一：等待中央处理机处理，序在存储器中处于四种状态之一：等待中央处理机处理，在中央处理机中执行，等待输入输出器处理，在输入输出在中央处理机中执行，等待输入输出器处理，在输入输出器中执行。表示如图器中

15、执行。表示如图输入输出器中央处理机 1 2p1pl程序到达是参数为程序到达是参数为的泊松流，又中央处理机、输入输出的泊松流，又中央处理机、输入输出器的工作时间都是负指数分布，参数为器的工作时间都是负指数分布，参数为 1、2，中央处理，中央处理机和输入输出器前均设有排队等待位置。当一程序在中央机和输入输出器前均设有排队等待位置。当一程序在中央处理机上处理完成时，或以概率处理机上处理完成时，或以概率p离开系统，或以概率离开系统，或以概率q1p在输入输出器前排队等待。当在输入输出器处完成在输入输出器前排队等待。当在输入输出器处完成服务后，该程序再反馈到中央处理机前排队等待。这样循服务后，该程序再反馈

16、到中央处理机前排队等待。这样循环反复，直到全部操作完为止。此处假定有无限个等待位环反复，直到全部操作完为止。此处假定有无限个等待位置，试求相应的目标参量置，试求相应的目标参量输入输出器中央处理机 1 2p1pl什么是闭马尔可夫排队网络什么是闭马尔可夫排队网络如果一个马尔可夫排队网络没有从网络外部的到如果一个马尔可夫排队网络没有从网络外部的到达流，也不向网络外部输出。整个网络内共有达流，也不向网络外部输出。整个网络内共有K个顾客保持不变，顾客只是在网络内部节点之间个顾客保持不变，顾客只是在网络内部节点之间移动。移动。l设网络有设网络有N个节点组成，满足下面的条件：个节点组成，满足下面的条件：每个

17、节点都是一个每个节点都是一个./M/n排队系统，节点排队系统，节点i有有ni个服务个服务窗，每个服务窗独立工作，平均服务时间为窗，每个服务窗独立工作，平均服务时间为1/i。顾客只能在网络内部节点之间转移，不能走出网络，顾客只能在网络内部节点之间转移，不能走出网络，网络外部也无顾客到达，系统中由网络外部也无顾客到达，系统中由K个顾客。个顾客。顾客在节点顾客在节点i服务完后转移到节点服务完后转移到节点j的概率是的概率是pij设节点设节点i的总平均到达率为的总平均到达率为 i，则，则 i满足方程组满足方程组设设11,2,3.NijijjpjN 1iiiiiiNjjiiijixxxx p1211211

18、(,.,)()().!()!()()iiiikNiNiiiNiiiiikniiikNiK A iiixP k kkG KkkkkKkknknnknxG Kk其中证明过程略，最终结果为证明过程略，最终结果为l一个三节点的马尔可夫排队网络，如图，一个三节点的马尔可夫排队网络，如图，1 215（分（分组组/秒）秒）,320（分组（分组/秒）。分组在各节点间的转发情况秒）。分组在各节点间的转发情况可表示为：，可表示为：，l每一节点服务速率每一节点服务速率U50（分组（分组/秒），求：秒），求：网络中平均分组数网络中平均分组数每一分组在网络中的总平均停留时间每一分组在网络中的总平均停留时间平均吞吐量平均吞吐量123123 01/31/31/601/31/41/80ijr