《系统模拟-第12讲》由会员分享，可在线阅读，更多相关《系统模拟-第12讲（65页珍藏版）》请在金锄头文库上搜索。
1、系统模拟,第12讲授课教师: 左德承,排队网络模型,全局平衡 考虑一个马尔可夫链 在平衡状态下，其稳定分布具有如下特征对于系统的一个稳定状态，该状态“进入速率” 的等于该状态的“离开速率”,排队网络模型,局部平衡特性 对于排队网络的一个节点 排队网络由于一个顾客离开该节点而引起的一个状态的“离开速率” 等于由于一个顾客进入该系统而引起的该状态的“进入速率” 将状态的改变速率与节点顾客到达和离开速率联系到了一起,排队网络模型,局部平衡,“The departure rate from a state of the queueing networks due to the departure of
2、 a job from node i equals the arrival rate to this state due to an arrival of a job to this node-i”,排队网络模型,局部平衡 局部平衡所满足的条件,排队网络模型,局部平衡 系统局部平衡是系统全局平衡的充分条件 局部平衡的解是全局平衡的唯一解 如果系统每一个节点具有局部平衡的特性 整个系统具有局部平衡的特性 系统存在乘积形式的稳定分布解,排队网络模型,具有局部平衡特性的排队网络类型 M/M/N-FCFS，I/O系统或DISK M/G/1-PS，计算机系统的CPU可以用利用该模型 M/G/，计算机系统
3、的终端可以利用该模型分析 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，根据局部平衡特性,排队网络模型,通过前面的计算，可得,排队网络模型,根
4、据归一化条件,排队网络模型,局部平衡 系统局部平衡是系统全局平衡的充分条件 局部平衡的解是全局平衡的唯一解 如果系统每一个节点具有局部平衡的特性 整个系统具有局部平衡的特性 系统存在乘积形式的稳定分布解,排队网络模型,乘积形式解 Jackson(1963)开环排队网络 GordonNewell(1967)闭环排队网络 其结论为开环、闭环网络指数时间到达间隔、服务时间 其稳定分布的解可以表示成每个节点状态的乘积形式 该结果被推广到开环、闭环、混合型网络，多类顾客的情形,排队网络模型,乘积形式(Product-Form)的解 MM特性(马尔可夫蕴含马尔可夫过程) 一个泊松流经过一个节点后 仍然是一
5、个泊松流 泊松到达 服务时间指数分布,排队网络模型,几种特性的关系,Local Balance-LB,Product Form-PF,MM,排队网络模型,Jackson网络(Jackson 1963) 网络系统中只有一种类型的顾客 服务时间寻道概率都相同 系统是开环的 顾客数是无限多的 每个节点的系统外部到达为泊松到达 所有节点的服务时间分布是指数分布 节点的服务规则为FCFS,排队网络模型,Jackson定理 如果符合前面的条件的开环网络系统是遍历的 系统稳定分布的解为：稳定分布的解可以分解为M个独立的M/M/N排队系统稳定分布的乘积形式,排队网络模型,Jackson网络 考察每一个节点，其
6、输入根据前面的分析 有反馈的存在，不是相互独立的泊松过程的迭加 但整个网络的行为表现行为就像每一个节点的输入都为泊松过程 整个系统由M个相互独立的M/M/N排队系统所组成,排队网络模型,每一个节点的特性 输入速率为i的泊松流节点的处理速度为队列长度相关的(QLD),排队网络模型,网络节点的局部特性稳定分布的解,排队网络模型,Jackson定理的证明 必须要满足如下的全局平衡特性对于系统的一个稳定状态，该状态“进入速率” 的等于该状态的“离开速率”,排队网络模型,对于Jackson网络来说，平衡条件为,排队网络模型,根据前面的Jackson定理中的公式 根据M/M/N排队模型稳定分布的解,排队网
7、络模型,同理，可得,排队网络模型,将全局平衡等式两边同时除以可得如下等式,排队网络模型,根据全局平衡的特性 在平衡条件下，外部对整个系统的输入等于系统对外的输出现在考察如下公式,排队网络模型,根据排队网络的通信量方程可以得出,排队网络模型,根据前面的结果,排队网络模型,所以，下面的等式成立,排队网络模型,说明 前面的推导过程每一步可逆 从而下面的乘积形式解是Jackson网络稳定状态的一个解 根据马尔可夫稳定分布解的唯一性 上面的解是Jackson网络稳定状态的唯一解,排队网络模型,根据Jackson定理 每个节点相互独立 那么，系统的平均队长、平均等待队长为,排队网络模型,Jackson网络
8、求解的过程 STEP1：对每一个节点根据通信量方程计算i STEP2：对于每一个节点，根据M/M/N排队模型计算稳定分布的解和节点的各性能指标 STEP3：利用Jackson定理求出系统稳定分布的解 整个系统的行为就好像M个相互独立的M/M/N排队系统,排队网络模型,举例 具有4个节点的计算机系统模型,排队网络模型,系统的特性 节点的服务时间服从指数分布任务到达系统的时间间隔也服从指数分布,排队网络模型,任务在系统中的寻道概率为求系统在稳定状态下，状态(3,2,4,1)的概率,排队网络模型,根据Jackson网络系统的求解步骤 STEP1：根据通信量方程，求i解得,排队网络模型,Step2：
9、计算每个节点的稳定分布和重要的性能参数,排队网络模型,每个节点的平均队长整个系统的平均队长,排队网络模型,根据Little公式 整个系统的平均 响应时间为系统的平均等待队长为根据Little公式，平均等待时间为,排队网络模型,所需的边缘分布STEP3：根据Jackson定理,排队网络模型,Gordon/Newell网络 具有M个节点的闭环网络 节点i的服务时间是指数分布 一个顾客在一个节点完成它的服务后 按概率选择下一个节点，与过去的历史无关 与Jackson网络的区别是该网络是闭环的,排队网络模型,Gordon/Newell网络 可以用开环网络的求解方法求解 通过对系统稳定分布归一化 删除不
10、存在的状态 仍然可以得到正确的解 Gordon&Newell(1967)将Jackson定理推广到指数服务时间的闭环网络 Gordon-Newell定理,排队网络模型,对于M个节点闭环网络 系统中的顾客数为常数系统总的状态数为,排队网络模型,Gordon-Newell定理 系统具有如下的乘积形式稳定分布解G(N)为归一化常数,排队网络模型,Gordon-Newell定理 对于第i个节点对于i (ni),排队网络模型,说明 对于M/M/N节点注意，Fi(ni)只是将上面的边缘分布律的实际输入变成了相对访问速率,排队网络模型,对于更一般的节点服务速率 Gordon-Newell定理可以用下面更一般
11、的方式表示节点的队列长度相关的服务速率函数为,排队网络模型,Gordon-Newell定理的证明 与Jackson定理相同，证明其符合全局平衡 闭环网络全局平衡的公式可以用如下形式表示,排队网络模型,为了证明定理 定义下面的变换,排队网络模型,根据前面的结果，可得,排队网络模型,全局平衡的等式可以变换为,排队网络模型,根据Gordon-Newell定理形式 变换函数Q为xi为前面讲过的相对利用率xi =vi/i c是一个常数,排队网络模型,根据结果，可得所以,排队网络模型,根据结果，可知根据xi =vi/i，所以,排队网络模型,Gordon-Newell定理 上述过程每一步均可逆 说明Gord
12、on-Newell定理乘积形式的解是闭环网络系统稳定分布的一个解 根据解的唯一性 Gordon-Newell定理乘积形式的解是系统唯一的解,排队网络模型,根据Gordon-Newell定理求解闭环网络的过程 Step1：对每一个节点求出相对访问率 Step2：对每个节点计算函数Fi(ni) Step3：计算归一化常数G(N) Step4：根据Gordon-Newell定理计算系统稳定分布的解,排队网络模型,举例 下面的闭环网络系统,排队网络模型,顾客的寻道概率为节点的服务速率为,排队网络模型,顾客数为3个 系统的状态数为系统的状态为,排队网络模型,根据闭环网络求解步骤 Step1：计算相对访问率,排队网络模型,Step2:计算每个Fi(ni) for i=1,2,3,排队网络模型,Step3：计算归一化常数Step4：根据Gordon-Newell定理，计算系统稳定分布的解 根据前面的公式，计算边缘分布 由边缘分布，可以计算节点各性能指标参数,
