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

第七章马尔可夫排队网络三种队长分布的关系Burke定理开马尔可夫排队网络闭马尔可夫排队网络到达与离开时的队长分布的关系下面我们研究三种时刻队长分布的关系pn-=P(顾客到达时系统中已有n个顾客)Pn=P(N=n)=平稳分布队长为n的概率pn+=P(顾客离开系统时系统还有n个顾客的概率)到达与离开时的队长分布的关系G/G/1系统pn-=pn+N(t)tn+1n跟踪N(t)实际走过的一条路线到达与离开时的队长分布的关系假定从状态n上跳到状态n+1的次数为An(t)从状态n+1下跳到状态n的次数为Dn(t)由于到达与离去是一个一个发生的，并且n-n+1与n+1-n是交错发生的。所以到t时刻为止，An(t)与Dn(t)至多相差1设A(t)、D(t)为从任何状态开始上跳一步的总次数和下跳一步的总次数，在统计平衡条件下，有：()()()lim1()tAtDtDtAt到达与离开时的队长分布的关系()()()()()()lim()()()()()()lim()()()()()()()()limlim1()()()()0nnnnnntnnnntnnnttnnAtDtppAtDtDtAtDtAtDtAtAtAtDtDtDtAtDtAtAtAtDtDtAtDtppM/G系统到达时刻看到的的队长分布与队长分布的关系M/G系统有pn-(t)=pn(t)，即任意时刻，到达的顾客看到的队长分布等于系统队长的分布证明令A(t,t+∆t)表示在[t,t+∆t)]时间内到达了一个顾客，则因为输入流是泊松流，所以A(t,t+∆t)发生的概率是∆t+o(∆t)，与N(t)=n这个事件无关。所以00()[()|(,)][(),(,)]lim[(,)][()][(,)|()]lim[(,)]nttptPNtnAtttPNtnAtttPAtttPNtnPAtttNtnPAttt0[(,)|()][(,)()lim()()nnntPAtttNtnPAtttptptpt＝】结论G/G排队系统pn-=pn+即到达的顾客与离开的顾客所看到的队长分布是相等的M/G排队系统中pn-=pn+=pn即顾客为泊松流到达的排队系统中，到达的顾客与离开的顾客看到的队长分布与系统的队长分布都相等马尔可夫排队网络我们前面学习的情况，都是顾客只请求一种服务，服务完离去，这种系统叫做单节点系统或叫单节点网络。如果一个排队系统只是一个节点，那么多个节点就可以组成一个排队网络。每个节点都含有一个服务机构和排队机构，是一个简单的排队系统，当顾客离开某个排队系统节点就进入下一个节点。例如数据包在通信网中传输123到达到达到达离开离开离开排队网络(注意不要与状态流图混淆)马尔可夫排队网络定义：马尔可夫排队网络指的是各节点外部到达顾客流是泊松流，各节点的服务时间是负指数分布的网络系统。关注的问题：网络结构－描述了节点之间的允许的转移使用随机过程对顾客流的描述－例如离开节点i的顾客都立即进入节点i＋1，则前者的顾客离去间隔时间就是后者的顾客到达间隔时间马尔可夫排队网络一个二节点的级联网络举例，假定1号节点是一个M/M/1排队系统2号节点的顾客输入流就是1号节点的顾客输出流考虑1号节点顾客离开的间隔时间，假定其服从分布d(t)，d(t)的拉普拉斯变换为D*(x)。1号节点的服务时间分布的拉普拉斯变换为B*(x)，顾客到达间隔时间分布的的拉普拉斯变换为A*(x)。有：λ12？*()*()AxBxxx马尔可夫排队网络一个二节点的级联网络情况一：前面顾客离开后，后面接着有顾客来接受服务两顾客离开的间隔时间就是后面顾客的服务时间情况二：前面顾客离开后，系统顾客为0两顾客离开的间隔时间是后面顾客到达的间隔时间＋后面顾客服务的时间1*()*()DxBx2*()*()*()DxAxBx后一个顾客前一个顾客前一个顾客后一个顾客马尔可夫排队网络一个二节点的级联网络情况一出现的概率＝顾客离开时发现系统中有顾客的概率＝顾客到达时发现系统中有顾客的概率＝统计平衡时系统队长不为0的概率＝同理，情况二出现的概率＝1-所以可见，M/M/1排队系统的顾客输出流是泊松流，并且强度与其输入流强度相同12*()*()(1)*()()(1)()()()tDxDxDxxxxxdte马尔可夫排队网络－Burke定理Burke定理在平稳状态下，M/M/n排队系统的顾客离开的过程为泊松过程，离开率等于到达率。并且M/M/n是唯一具有此种性质的FCFS排队系统。马尔可夫排队网络一个二节点的级联网络因此，此时再看2号节点2号节点的输入流是强度为的泊松流，所以2号节点也是一个普通的M/M/1排队系统，并且可以与1号节点独立分开讨论。Burke定理：多个M/M/n排队系统连接在一起所形成的网络，每个节点能够依旧保持原本M/M/n的特性。λ12泊松流λ开马尔可夫排队网络（Jackson定理）假定排队网络由N个节点组成，且满足如下条件每个节点都是一个./M/n排队系统，节点i有ni个服务窗，每个服务窗独立工作，平均服务时间为1/i。顾客从网络外部到达第i个节点的流是参数为i的泊松流在节点i服务完的顾客以概率pij到达节点j或者以的概率离开网络系统设节点i的总平均到达率为i（包括网络外部的到达率i和其他节点到达节点i的全部到达率之和），则i满足方程组设在节点i处有ki个顾客，则系统的状态记做（k1,k2,…,kN）设在统计平衡条件下的概率为P(k1,k2,…,kN),如果iniui则pi(ki)是节点i在统计平衡条件下有ki个顾客的概率。11Nijjp121122(,,...)()()()NNNPkkkpkpkpk11,2,3.....NiijijjpjN开马尔可夫排队网络Jackson定理的直观理解N个节点的马尔可夫网络，如果把到达节点i的合流理解成是强度为i的泊松流，则节点i就是一个独立的排队系统，从而整个网络的状态概率是各个节点相应状态概率的乘积。求解开马尔可夫排队网络模型的步骤：求解各个节点的顾客平均到达率分别求解各个节点的目标参量开马尔可夫排队网络例题多重程序二阶段循环模型。在多重程序的计算机系统中，一些程序同时存在主存储器中，每一程序有中央处理机指令和输入输出指令组成。当输入输出器处理某一程序的输入输出时，直到它完成这种输入或输出此程序才执行中央处理机处理的其他程序指令。这种程序就是这样在中央处理机与输入输出器之间循环，直到全部完成为止。每一程序在存储器中处于四种状态之一：等待中央处理机处理，在中央处理机中执行，等待输入输出器处理，在输入输出器中执行。表示如图输入输出器中央处理机12p1－p开马尔可夫排队网络例题程序到达是参数为λ的泊松流，又中央处理机、输入输出器的工作时间都是负指数分布，参数为1、2，中央处理机和输入输出器前均设有排队等待位置。当一程序在中央处理机上处理完成时，或以概率p离开系统，或以概率q＝1－p在输入输出器前排队等待。当在输入输出器处完成服务后，该程序再反馈到中央处理机前排队等待。这样循环反复，直到全部操作完为止。此处假定有无限个等待位置，试求相应的目标参量输入输出器中央处理机12p1－p闭马尔可夫排队网络什么是闭马尔可夫排队网络如果一个马尔可夫排队网络没有从网络外部的到达流，也不向网络外部输出。整个网络内共有K个顾客保持不变，顾客只是在网络内部节点之间移动。闭马尔可夫排队网络设网络有N个节点组成，满足下面的条件：每个节点都是一个./M/n排队系统，节点i有ni个服务窗，每个服务窗独立工作，平均服务时间为1/i。顾客只能在网络内部节点之间转移，不能走出网络，网络外部也无顾客到达，系统中由K个顾客。顾客在节点i服务完后转移到节点j的概率是pij设节点i的总平均到达率为i，则i满足方程组设11,2,3.....NijijjpjN1iiiiiiNjjiiijixxxxp闭马尔可夫排队网络1211211(,,...,)()()...!()!()()iiiikNiNiiiNiiiiikniiikNiKAiiixPkkkGKkkkkKkknknnknxGKk其中证明过程略，最终结果为随堂测验4一个三节点的马尔可夫排队网络，如图，1＝2＝15（分组/秒）,3＝20（分组/秒）。分组在各节点间的转发情况可表示为：，每一节点服务速率U＝50（分组/秒），求：网络中平均分组数每一分组在网络中的总平均停留时间平均吞吐量123λ1λ2λ301/31/31/601/31/41/80ijr