系统模拟-第12讲.ppt

系统模拟第12讲授课教师:左德承排队网络模型全局平衡考虑一个马尔可夫链在平衡状态下，其稳定分布具有如下特征对于系统的一个稳定状态，该状态“进入速率”的等于该状态的“离开速率”排队网络模型局部平衡特性对于排队网络的一个节点排队网络由于一个顾客离开该节点而引起的一个状态的“离开速率”等于由于一个顾客进入该系统而引起的该状态的“进入速率”将状态的改变速率与节点顾客到达和离开速率联系到了一起排队网络模型局部平衡排队网络模型局部平衡局部平衡所满足的条件排队网络模型局部平衡系统局部平衡是系统全局平衡的充分条件局部平衡的解是全局平衡的唯一解如果系统每一个节点具有局部平衡的特性整个系统具有局部平衡的特性系统存在乘积形式的稳定分布解排队网络模型具有局部平衡特性的排队网络类型M/M/N-FCFS，I/O系统或DISKM/G/1-PS，计算机系统的CPU可以用利用该模型M/G/∞，计算机系统的终端可以利用该模型分析M/G/1-LCFS，计算机系统中没有实际应用排队网络模型举例如下的闭环网络系统顾客数为2人服务平均速率μ1=4，μ2=1，μ3=2排队网络模型系统的特性节点1到节点2和节点3的寻道概率q12=0.4，q13=0.6；q21=q31=1系统的状态空间为排队网络模型系统的状态转移图为排队网络模型根据局部平衡特性考察节点2，状态(1,1,0)在状态(1,1,0)下顾客离开节点2的速率等于其它状态下顾客进入节点2使系统状态为(1,1,0)的速率同理排队网络模型对于节点3，根据局部平衡特性排队网络模型通过前面的计算，可得排队网络模型根据归一化条件排队网络模型局部平衡系统局部平衡是系统全局平衡的充分条件局部平衡的解是全局平衡的唯一解如果系统每一个节点具有局部平衡的特性整个系统具有局部平衡的特性系统存在乘积形式的稳定分布解排队网络模型乘积形式解Jackson(1963)开环排队网络Gordon＆Newell(1967)闭环排队网络其结论为开环、闭环网络指数时间到达间隔、服务时间其稳定分布的解可以表示成每个节点状态的乘积形式该结果被推广到开环、闭环、混合型网络，多类顾客的情形排队网络模型乘积形式(Product-Form)的解M→M特性(马尔可夫蕴含马尔可夫过程)一个泊松流经过一个节点后仍然是一个泊松流泊松到达服务时间指数分布排队网络模型几种特性的关系排队网络模型Jackson网络(Jackson1963)网络系统中只有一种类型的顾客服务时间寻道概率都相同系统是开环的顾客数是无限多的每个节点的系统外部到达为泊松到达所有节点的服务时间分布是指数分布节点的服务规则为FCFS排队网络模型Jackson定理如果符合前面的条件的开环网络系统是遍历的系统稳定分布的解为：稳定分布的解可以分解为M个独立的M/M/N排队系统稳定分布的乘积形式排队网络模型Jackson网络考察每一个节点，其输入根据前面的分析有反馈的存在，不是相互独立的泊松过程的迭加但整个网络的行为表现行为就像每一个节点的输入都为泊松过程整个系统由M个相互独立的M/M/N排队系统所组成排队网络模型每一个节点的特性输入速率为λi的泊松流节点的处理速度为队列长度相关的(QLD)排队网络模型网络节点的局部特性－稳定分布的解排队网络模型Jackson定理的证明必须要满足如下的全局平衡特性对于系统的一个稳定状态，该状态“进入速率”的等于该状态的“离开速率”排队网络模型对于Jackson网络来说，平衡条件为排队网络模型根据前面的Jackson定理中的公式根据M/M/N排队模型稳定分布的解排队网络模型同理，可得排队网络模型将全局平衡等式两边同时除以可得如下等式排队网络模型根据全局平衡的特性在平衡条件下，外部对整个系统的输入等于系统对外的输出现在考察如下公式排队网络模型根据排队网络的通信量方程可以得出排队网络模型根据前面的结果排队网络模型所以，下面的等式成立排队网络模型说明前面的推导过程每一步可逆从而下面的乘积形式解是Jackson网络稳定状态的一个解根据马尔可夫稳定分布解的唯一性上面的解是Jackson网络稳定状态的唯一解排队网络模型根据Jackson定理每个节点相互独立那么，系统的平均队长、平均等待队长为排队网络模型Jackson网络求解的过程STEP1：对每一个节点根据通信量方程计算λiSTEP2：对于每一个节点，根据M/M/N排队模型计算稳定分布的解和节点的各性