排队模型下的任务损失优化与负载均衡

杨喜娟; 张亚清; 王博; 曹存宇; 李学军

doi:10.12404/j.issn.1671-1815.2506197

科学技术与工程 ›› 2026, Vol. 26 ›› Issue (25) :10967-10981 DOI: 10.12404/j.issn.1671-1815.2506197

自动化技术、计算机技术

排队模型下的任务损失优化与负载均衡

杨喜娟 ¹^,² ,
张亚清 ¹ ,
王博 ¹ ,
曹存宇 ¹ ,
李学军 ²

作者信息 +

Task Loss Optimization and Load Balancing under Queueing Model

YANG Xi-juan ¹^,² ,
ZHANG Ya-qing ¹ ,
WANG Bo ¹ ,
CAO Cun-yu ¹ ,
LI Xue-jun ²

Author information +

文章历史 +

摘要

针对云计算环境中任务调度效率低和负载失衡问题,提出了一种排队模型下的任务损失优化与负载均衡调度算法。将多服务器环境抽象为多个无限容量 GI/M/1/∞队列模型,其中任务到达服从一般分布,服务时间服从负指数分布。通过构造无限状态拟生灭过程(quasi-birth-and-death, QBD),并应用二维马尔可夫过程与矩阵几何解法,推导稳态概率并量化性能指标。其次,设计多策略融合的负载均衡算法:提出虚等待时间概念,基于其计算量化任务等待容忍阈值的损失率,以提升任务分配精度;结合空闲队列(join-idle-queue, JIQ)策略,将任务优先分配至空闲服务器,降低等待时间;通过心跳机制实时感知服务器状态,动态调整参数以提升资源利用率。最后,通过数值实验对比所提算法与传统方法在任务损失率、等待时间及系统稳定性方面的性能,结果表明该算法显著提升资源分配效率、降低任务损失率并增强系统稳定性,为高流量网络环境下的负载均衡调度提供理论与实践支持。

Abstract

A task loss optimization and load balancing scheduling algorithm under a queuing model was proposed to address the problems of inefficient task scheduling and load imbalance in cloud computing environments. A multi-server environment was abstracted into multiple infinite-capacity GI/M/1/∞ queue models, where task inter-arrival times follow a general distribution and service times adhere to an exponential distribution. By constructing an infinite-state Quasi-Birth-and-Death (QBD) process and applying a two-dimensional Markov process with a matrix geometric solution, steady-state probabilities were derived and performance metrics were quantified. Secondly, a multi-strategy integrated load balancing algorithm was designed: the concept of virtual waiting time was proposed, based on which the loss rate of the quantified task waiting tolerance threshold was calculated to improve the accuracy of task allocation. Combined with the idle queue (join-idle-queue, JIQ) strategy, tasks were prioritized to be assigned to idle servers to reduce waiting time. Through the heartbeat mechanism, the server status was sensed in real time, and parameters were dynamically adjusted to improve resource utilization. Finally, numerical experiments were conducted to compare the performance of the proposed algorithm with that of traditional methods in terms of task loss rate, waiting time, and system stability. The results show that the proposed algorithm significantly improves resource allocation efficiency, reduces the task loss rate, and enhances system stability, providing both theoretical and practical support for load balancing scheduling in high-traffic network environments.

Graphical abstract

关键词

网络任务 / 负载均衡 / 任务调度 / 排队论 / 性能指标

Key words

network tasks / load balancing / task scheduling / queuing theory / performance metrics

引用本文

引用格式 ▾

杨喜娟, 张亚清, 王博, 曹存宇, 李学军. 排队模型下的任务损失优化与负载均衡[J]. 科学技术与工程, 2026, 26(25): 10967-10981 DOI:10.12404/j.issn.1671-1815.2506197

YANG Xi-juan, ZHANG Ya-qing, WANG Bo, CAO Cun-yu, LI Xue-jun. Task Loss Optimization and Load Balancing under Queueing Model[J]. Science Technology and Engineering, 2026, 26(25): 10967-10981 DOI:10.12404/j.issn.1671-1815.2506197

登录浏览全文

4963

注册一个新账户忘记密码

中国网络经济发展迅速,打破了传统行业的边界。跨界融合催生出了许多新兴业态。电商、社交、大数据等业态的发展对计算和存储的需求急剧增长,迫切需要通过虚拟化、分布式存储和高速网络等技术对计算资源进行整合。

云计算作为一种提供计算资源的服务模式,其核心在于资源共享和动态分配。根据中国信息通信研究院《云计算蓝皮书》,预计到2030年中国云计算市场规模将突破3万亿元^[1];IDC报告显示,到2029年AI IaaS市场规模将接近1 500亿元^[2]。市场对云计算、算力产业的发展诉求与行业期待,已逐步传导至国家顶层政策设计层面,为产业规范化、高质量发展提供了重要政策支撑。工业和信息化部印发的《云计算综合标准化体系建设指南(2025版)》明确提出推进云计算领域标准化体系建设的核心任务,旨在以标准化为抓手,加速云计算技术、产业与实体经济的深度融合落地^[3]。同时,“十五五”规划进一步明确算力基础设施的战略定位^[4],持续强化算力基础设施统筹建设,将其作为培育新质生产力、赋能经济社会高质量发展的核心新动能,为传统产业转型升级、全域数字生态体系构建提供关键支撑。

过去一段时间,中国云计算作为数字经济的核心基础设施,在AI基础设施、算力调度平台和异构资源优化等领域均取得了进展^[4],但随着“东数西算”工程的深入实施以及边缘计算与云计算的融合发展,中国的云计算环境呈现出任务规模爆炸式增长、资源跨区域分布式部署以及业务场景高度多元化的鲜明特征,从而对传统负载均衡技术构成了严峻挑战。这些问题不仅导致资源利用率低下,还会引发任务丢失和服务质量下降。因此,研究高效的任务调度和负载均衡算法具有重要意义。

在分布式计算与云计算环境中,多服务器系统广泛用于高并发任务处理^[5],对于云计算提供商而言,确保最佳负载均衡的可靠性至关重要^[6]。随着任务规模增长,高效负载均衡成为关键研究方向^[7];因计算资源分布广且动态变化,需要合理的负载均衡机制来降低尾部延迟、提升系统性能^[8]。任务调度算法性能受排队策略影响^[9],如考虑机器启动时间的虚拟机扩展策略及 STARS 算法,可平衡任务时效性与节能^[10];在网络环境中无形排队易引发拥堵,当流量强度剧变时还涉及到达率可变排队系统的等待时间问题^[11-13]。针对边缘设备资源有限与负载失衡,已有研究通过多边缘设备协作的任务卸载与服务缓存在线优化,降低执行时延并平衡负载^[14]。

随着计算机技术发展,网络资源规划与数据中心任务分配已成为核心课题^[15]。云计算彻底改变了计算方式,并已成为IT行业不可或缺的一部分。排队论作为一种数学方法,已被用于模拟涉及等待队列的系统^[16]。传统排队系统研究中,M/M/1 因假设到达与服务过程均服从马尔可夫分布,成为经典分析模型^[17],但在任务到达具有一般独立分布(general independent,GI)、服务过程稳定可量化的场景中,GI/M/1模型展现出更强的适应性。Matsak等^[18]聚焦 M/G/1 和GI/M/1系统,分析了队列长度与等待时间极值的渐近行为,为这类非马尔可夫排队系统的性能边界提供了理论支撑。Mageed等^[19]则将非平稳 D/M/1 队列的 GI/M/1 点态平稳流体流近似模型,应用于自动驾驶超低延迟服务场景,揭示了稳定性与随机性的内在关联,进一步拓展了该模型在复杂动态场景中的应用价值。

网络无形排队中的负载失衡易导致网络节点负载过重^[20],引发过载节点拒流、级联拥塞及服务质量下降等问题^[21]。许晶等^[22]提出智算中心通过自适应负载均衡、主动拥塞控制等细粒度技术应对该问题。当前集中式负载均衡常用随机、轮转、门限、最小连接4种定位策略^[23],负载指标选取需匹配当前模型下的策略,且已有基于M/M/1/N模型的负载均衡算法^[24];针对集群系统,DRDSTI策略通过周期性信息收集减少负载信息传输量^[25];基于DPDK框架的NFV负载均衡机制,结合软件定义网络思想与多核多队列架构,可提升数据包转发性能^[26]。

经典调度算法虽易实现^[27],但粒子群算法^[28]、灰狼优化算法^[29]、人工蜂群算法^[30]等启发式算法效果更优。随着网络的不断发展,引入预测机制对网络动态变化进行预测,从而可以调整负载调度以提升效率。如基于特征选择与SHAP的云平台任务终止预测模型^[31],或基于时间卷积和长短期记忆网络的短期云资源组合预测模型等^[32]。且针对异构的高性能计算机,提出了一种新颖负载均衡策略,实现了一种用于格子玻尔兹曼方法的大规模异构并行算法^[33];吕光宏等^[34]提出的注意力机制动态流量预测方法,可提升SDN流量预测精度。然而,上述文献多仅用排队模型做最终分析,未深度结合负载均衡,且高负载下资源利用率不足。

高负载环境中,任务损失率(因系统满容或任务不耐等待被丢弃的比例)是关键性能指标。Hight 等^[35]首次在M/M/1系统中考虑止步/中途退出现象。Devi等^[36]对云计算环境中的任务调度和负载均衡算法做了综述,旨在分析用于云计算环境中的各种技术,包括优化和机器学习算法等,但未充分考虑动态网络变化下的任务损失优化。Chaudhar等^[37]提出了一种整合人工智能与模型阶次约简的队列理论模型架构,用于优化云环境中的队列和调度,但忽略了任务退出时的隐性损失影响。Niranjan等^[38]分析了结合负载均衡和休假情况下的批量队列模型,考察了基于队列长度的服务器过载和欠载问题,但未融入多策略来减少系统中任务丢弃率带来的影响。

综上所述,现有研究多关注标准队列模型和一般性能优化,忽略了任务隐性损失的精确捕捉。现针对任务隐性损失问题,以GI/M/1排队理论模型为核心,创新性地引入虚等待时间机制,融合JIQ策略与心跳动态调整,构建GI/M/1系统的无限状态拟生灭过程(quasi-birth-and-death, QBD),提供高流量网络下任务损失优化与负载均衡的全面解决方案。最后通过数值实验验证算法在损失率、系统稳定性等方面的优越性,评估任务丢失与服务器负载均衡策略对系统性能的差异化影响,为云计算实践提供理论支撑。

1 问题描述和假设

系统由一个任务负载调度器和多个服务器组成,因此整体来看集群系统是一个多服务台排队系统,即GI/M/c/∞排队模型。因为每个服务器子队列彼此独立,且任务请求都平等,因此每个节点都为一个GI/M/1/∞的单服务器单队列模型,所以整体可抽象为多个GI/M/1排队模型。模型中输入请求首先进入输入队列,形成排队等待处理的任务集合。在核心处理部分,采用GI/M/c模型对任务进行分流和服务,每个服务单元被建模为一个 GI/M/1排队系统,负责独立处理任务,以提高系统的吞吐能力。在各服务单元完成任务处理后,系统根据预定义的服务规则,即先来先服务规则(first-come, first-served, FCFS),对任务进行统一合并处理,最后将结果转移到输出队列,供后续阶段使用,因此模型适用于各种复杂到达过程及多任务并行处理等场景。队列分析模型如图1所示。

GI/M/1排队系统中服务器的任务到达间隔时间服从一般分布,服务时间服从负指数分布^[39]。任务的到达间隔时间序列$\{{\mathit{\tau }}_{\mathit{i}},\mathit{i}\ge 1\}$独立、具有相同的一般分布$\mathit{F}\left(\mathit{t}\right),\mathit{t}\ge 0$,其中τ_i为第i次到达与第i-1次到达之间的时间间隔。平均到达间隔时间为$0<\frac{1}{\mathit{\lambda }}={\int }_{0}^{\mathit{\infty }}\mathit{t}\mathrm{d}\mathit{F}\left(\mathit{t}\right),\mathit{\lambda }>0$为常数,任务所需的服务时间序列$\{{\mathit{\chi }}_{\mathit{i}},\mathit{i}\ge 1\}$独立、服从参数μ>0的负指数分布$\mathit{G}\left(\mathit{t}\right)=1-{\mathrm{e}}^{-\mathit{\mu }\mathit{t}},\mathit{t}\ge 0$;系统中的任务经过负载均衡调度器分配任务给各服务器,结合排队论中的不耐烦顾客模型,考虑到若有任务在等待期间退出队列的任务损失率,这期间任务并没有真正到达队头进行服务,所以这段时间也称为虚等待时间。

当队列中的全部任务服务完成或因某种原因被取消,导致队列进入空闲状态时,系统将采用JIQ策略,以充分利用空闲计算资源并减少任务调度开销。为进一步优化任务分配效率,集成心跳机制,使新到达的任务在检测到空闲服务器后,能够跳过传统的负载调度器,直接分配至空闲服务器,其反馈模型如图2所示。

简而言之,若当前有空闲队列,则首先执行JIQ策略,若当前队列全部无空闲时,通过动态参数调整策略用中央调度器实现负载均衡,负载均衡调度整体系统模型如图3所示。服务期间任务排成一个队列等待,并按到达的先后顺序逐个接受服务,任务在服务完毕后离开系统。建立GI/M/1排队系统,模型描述如下。

(1) 中央调度器。系统仅有一个调度器,调度器作为中央调度员统筹调度所有任务,任务量为N,服务器遵循先来先服务的服务策略,一个服务器每次执行一个任务。

(2) 到达过程。任务的到达过程服从参数为λ的泊松过程,即任务到达率为λ,任务调度时,调度器和服务器集成心跳机制输出心跳日志,当有空闲队列时,任务直接到达服务器中无需调配,任务将不再通过中央调度器调度。假设在时间T内有N个任务请求到达服务器,任务请求到达的时间间隔是一个随机变量,各个任务请求之间相互独立,则任务平均到达率为

(1)$\mathit{\lambda }=\frac{\mathit{N}}{\mathit{T}}$

(3) 服务过程。服从参数μ>0的负指数分$\mathit{G}\left(\mathit{t}\right)=1-{\mathrm{e}}^{-\mathit{\mu }\mathit{t}},\mathit{t}\ge 0$,即任务服务率为μ, 在每个任务进入队列时,设每个任务的到达时间为t_a、服务开始时间为t_s、服务结束时间为t_e。假设在时间T内服务器将a∼a+k个任务处理完毕,则该服务器的平均服务率为

(2)$\mathit{\mu }=\frac{\mathit{k}+1}{\stackrel{\mathit{a}+\mathit{k}}{\sum _{\mathit{i}=\mathit{a}}}({\mathit{t}}_{\mathrm{e}}-{\mathit{t}}_{\mathrm{s}})}$

(4) 任务取消过程。任务进入系统后,由于排队等待,根据队列长度的大小可能会出现忍耐度降低,在未接受服务的情况下中途退出。特别是在系统可能变得过载的情况下,这个参数反映了系统处理能力的限制以及任务等待时间的容忍度,对于理解资源规划和系统优化至关重要。过高的任务损失率通常也意味着需要增加服务资源或优化排队策略来提高系统效率,设定θ(t)表示任务退出率,即任务在排队期间退出的可能性,用来描述任务流的损失行为。退出率θ(t)满足指数分布,即任务的退出是记忆无关的随机过程,设定任务损失速率为α_c,即任务中途退出的速率,则

(3)$\mathit{\theta }\left(\mathit{t}\right)={\mathit{\alpha }}_{\mathit{c}}{\mathrm{e}}^{-{\mathit{\alpha }}_{\mathit{c}}\mathit{t}},{\mathit{\alpha }}_{\mathit{c}}>0$

(5) 原状态转移过程。当任务因为某种原因在排队过程中或服务过程中被取消时,此时服务器的资源占用率等都发生了改变。某一时刻某一服务器的队列中有n个任务,此时因故取消一个任务,则会返回该状态的上一个时刻状态,即队列中有n-1个任务未被取消的状态,设从已取消状态到前一个正常状态的原状态转移速率为η,即原状态转移速率,则其转移过程可表示为

(4)${\mathit{P}}_{\mathit{i}\to \mathit{i}-1}=\mathit{\eta }\mathrm{\Delta }\mathit{t}+\mathit{o}\left(\mathrm{\Delta }\mathit{t}\right)$

(6) 假设各随机变量独立,以某服务器节点GI/M/1排队模型为主,表1列出了研究中所用符号。

由于每个服务器都有各自的任务队列,因此单个服务器节点也是一个独立的排队系统,且其对待每一个任务请求都是平等的,从而每个服务器都可抽象为一个单服务器单队列排队模型,即GI/M/1排队模型。通过这种排队模型求出平均等待队长L_Wq、平均等待时间W_Qt和虚等待时间W_v 3个重要的系统评估指标。

2 模型建立

2.1 系统平稳方程

令L(t)为t时刻任务数,则0≤L(t)≤N。设W(t)表示t时刻任务是否取消,则

(5)$\mathit{W}\left(\mathit{t}\right)=\left\{\begin{array}{ll}0,& \mathrm{任}\mathrm{务}\mathrm{未}\mathrm{取}\mathrm{消}\\ 1,& \mathrm{任}\mathrm{务}\mathrm{被}\mathrm{取}\mathrm{消}\end{array}\right.$

则$\left\{\mathit{L}\right(\mathit{t}),\mathit{W}(\mathit{t}\left)\right\}$为二维Markov过程,其状态空间为

(6)$\mathit{\Omega }=\left\{\right(\mathit{i},\mathit{j}\left)\right|\mathit{i}\ge 0,\mathit{j}\in \left\{\mathrm{0,1}\right\}\}$

式(6)中:i为当前任务的数量,可以是任意非负整数;j为任务的状态,0表示队列中未有取消的任务,1表示队列中有任务被取消。每个任务到达的速率为λ,如果系统在状态(i,0),即当前有i个任务未取消且有i-1个任务正在排队,则到达新任务会使系统进入状态(i+1,0),每个任务完成服务的速率为μ。当i>0时,如果系统在状态(i,0),服务完一个任务会使队列进入状态(i-1,0);当i=0时,系统处于(0,0)状态,此时没有可完成的任务,因此不会有向左的状态转移。每个任务有一个被取消的速率α_c,如果系统在状态(i,0),此时队列中某个任务被取消将导致系统进入状态(i,1),状态变为“取消”状态。每个取消的任务有一个恢复的速率η,如果系统在状态(i,1),即队列中有任务处于“取消”状态,那么任务恢复会使系统进入状态(i-1,0),即重新进入正常排队状态。{(0,0)}表示队列中没有任务;{(1,0)}表示当前队列中有一个任务且该任务未被取消正在接受服务,这里默认遵循FCFS原则,即队头任务接受服务,从(0,0)到(1,0)表示一个任务到达系统;{(2,0)}表示队列中有2个任务,1个任务正在被服务1个任务正在排队,且都未取消;当这些任务正在排队时,其中一些可能被取消(j=1),另一些未被取消(j=0),则{(2,1)}表示队列中的任务有的因为一些原因被取消,此时队列状态从(2,0)到(2,1)。其中一个任务被取消,其取消速率为α_c,当任务取消完成时,队列状态变为之前未取消队列的状态。从(2,1)到(1,0),取消的任务恢复,恢复速率为η,此时队列中有一个任务,且该任务处于队头正在接受服务。所以状态空间的完整形式表示为

(7)$\mathit{\Omega }=\left\{\right(\mathit{i},0),(\mathit{i},1\left)\right|\mathit{i}\ge 0\}$

系统的状态转移图如图4所示。图4中系统在稳态下,给定状态的转移率出入平衡,可得系统的平稳方程为

(8)$\mathit{\mu }\mathit{P}\left(\mathrm{1,0}\right)=\mathit{\lambda }\mathit{P}\left(\mathrm{0,0}\right)$

(9)$\begin{array}{l}\mathit{\lambda }\mathit{P}\left(\mathrm{0,0}\right)+\mathit{\mu }\mathit{P}\left(\mathrm{2,0}\right)+\mathit{\eta }\mathit{P}\left(\mathrm{2,1}\right)=\\ \mathit{　}\mathit{　}(\mathit{\lambda }+\mathit{\mu })\mathit{P}\left(\mathrm{1,0}\right)\end{array}$

(10)$\begin{array}{l}\mathit{\lambda }\mathit{P}\left(\mathrm{1,0}\right)+\mathit{\mu }\mathit{P}\left(\mathrm{3,0}\right)+\mathit{\eta }\mathit{P}\left(\mathrm{3,1}\right)=\\ \mathit{　}\mathit{　}(\mathit{\lambda }+\mathit{\mu }+{\mathit{\alpha }}_{\mathit{c}})\mathit{P}\left(\mathrm{2,0}\right)\end{array}$

(11)${\mathit{\alpha }}_{\mathit{c}}\mathit{P}\left(\mathrm{2,0}\right)=\mathit{\eta }\mathit{P}\left(\mathrm{2,1}\right)$

(12)$\begin{array}{l}\mathit{\lambda }\mathit{P}\left(\mathrm{2,0}\right)+\mathit{\mu }\mathit{P}\left(\mathrm{4,0}\right)+\mathit{\eta }\mathit{P}\left(\mathrm{4,1}\right)=\\ \mathit{　}\mathit{　}(\mathit{\lambda }+\mathit{\mu }+{\mathit{\alpha }}_{\mathit{c}})\mathit{P}\left(\mathrm{3,0}\right)\end{array}$

(13)${\mathit{\alpha }}_{\mathit{c}}\mathit{P}\left(\mathrm{3,0}\right)=\mathit{\eta }\mathit{P}\left(\mathrm{3,1}\right)$

(14)$\begin{array}{l}\mathit{\lambda }\mathit{P}(\mathit{N}-\mathrm{1,0})+\mathit{\mu }\mathit{P}(\mathit{N}+\mathrm{1,0})+\mathit{\eta }\mathit{P}(\mathit{N}+\mathrm{1,1})=\\ \mathit{　}\mathit{　}(\mathit{\lambda }+\mathit{\mu }+{\mathit{\alpha }}_{\mathit{c}})\mathit{P}(\mathit{N},0)\end{array}$

(15)${\mathit{\alpha }}_{\mathit{c}}\mathit{P}(\mathit{N},0)=\mathit{\eta }\mathit{P}(\mathit{N},1)$

(16)$\begin{array}{l}\mathit{\lambda }\mathit{P}(\mathit{N},0)+\mathit{\mu }\mathit{P}(\mathit{N}+\mathrm{2,0})+\mathit{\eta }\mathit{P}(\mathit{N}+\mathrm{2,1})=\\ \mathit{　}\mathit{　}(\mathit{\lambda }+\mathit{\mu }+{\mathit{\alpha }}_{\mathit{c}})\mathit{P}(\mathit{N}+\mathrm{1,0})\end{array}$

(17)${\mathit{\alpha }}_{\mathit{c}}\mathit{P}(\mathit{N}+\mathrm{1,0})=\mathit{\eta }\mathit{P}(\mathit{N}+\mathrm{1,1})$

对上述状态归纳整理得$\mathit{i}(\mathit{i}\ge 2)$状态时的平稳方程为

(18)$\begin{array}{l}(\mathit{i},0):\\ \mathit{\lambda }\mathit{P}(\mathit{i}-\mathrm{1,0})+\mathit{\mu }\mathit{P}(\mathit{i}+\mathrm{1,0})+\mathit{\eta }\mathit{P}(\mathit{i}+\mathrm{1,1})=\\ \mathit{　}\mathit{　}(\mathit{\lambda }+\mathit{\mu }+{\mathit{\alpha }}_{\mathit{c}})\mathit{P}(\mathit{i},0)\end{array}$

(19)$\begin{array}{l}(\mathit{i},1):\\ {\mathit{\alpha }}_{\mathit{c}}\mathit{P}(\mathit{i},0)=\mathit{\eta }\mathit{P}(\mathit{i},1)\end{array}$

上述状态表示任务在进入队列时状态的变化。

2.2 稳态概率

对状态按字典序排列,可得到系统的无穷小生成元为

(20)$\mathrm{Q}=\left[\begin{array}{llllll}{\mathit{B}}_{00}& {\mathit{C}}_{00}& & & & \\ {\mathit{A}}_{00}& \mathrm{B}& \mathrm{C}& & & \\ & \mathrm{A}& \mathrm{B}& \mathrm{C}& & \\ & & \mathrm{A}& \mathrm{B}& \mathrm{C}& \\ & & & \ddots & \ddots & \ddots \end{array}\right]$

式(20)中:

${\mathit{A}}_{00}=\left[\begin{array}{ll}-\mathit{\lambda }& \mathit{\lambda }\\ \mathit{\mu }& -(\mathit{\lambda }+\mathit{\mu })\end{array}\right];{\mathit{B}}_{00}=\left[\begin{array}{ll}0& \mathit{\mu }\\ 0& \mathit{\eta }\end{array}\right]$;

${\mathit{C}}_{00}=\left[\begin{array}{ll}0& 0\\ \mathit{\lambda }& 0\end{array}\right];\mathit{A}=\left[\begin{array}{ll}-(\mathit{\lambda }+\mathit{\mu }+{\mathit{\alpha }}_{\mathit{c}})& {\mathit{\alpha }}_{\mathit{c}}\\ 0& -\mathit{\eta }\end{array}\right]$;

$\mathit{B}=\left[\begin{array}{ll}\mathit{\mu }& 0\\ \mathit{\eta }& 0\end{array}\right];\mathit{C}=\left[\begin{array}{ll}\mathit{\lambda }& 0\\ 0& 0\end{array}\right]$。

最小生成元Q的结构表明了$\left\{\mathit{L}\right(\mathit{t}),\mathit{W}(\mathit{t}\left)\right\}$是一个QBD,根据Neuts^[40]、Latouche等^[41]所提,要分析这个QBD过程,必须求解矩阵二次方程的最小非负解,即

(21)${\mathit{R}}^{2}\mathit{B}+\mathit{R}\mathit{A}+\mathit{C}=0$

式(21)中:R为速率矩阵。

定理1 如果$\mathit{\rho }=\frac{\mathit{\lambda }}{{\mathit{\alpha }}_{\mathit{c}}+\mathit{\mu }}<1$,式(21)有最小非负解R为

(22)$\mathit{R}=\left[\begin{array}{ll}\mathit{\rho }& \frac{\mathit{\rho }{\mathit{\alpha }}_{\mathit{c}}}{\mathit{\eta }}\\ 0& 0\end{array}\right]$

式(22)中:$\mathit{\rho }=\frac{\mathit{\lambda }}{{\mathit{\alpha }}_{\mathit{c}}+\mathit{\mu }}$。

证明因为式(20)的矩阵A、B、C都是二阶矩阵,所以假设R为二阶矩阵。

(23)$\mathit{R}=\left[\begin{array}{ll}{\mathit{r}}_{11}& {\mathit{r}}_{12}\\ {\mathit{r}}_{21}& {\mathit{r}}_{22}\end{array}\right]$

将R²和R代入式(21)可以得到方程组为

(24)$\left\{\begin{array}{l}\begin{array}{l}({\mathit{r}}_{11}^{2}+{\mathit{r}}_{12}{\mathit{r}}_{21})\mathit{\mu }+({\mathit{r}}_{11}{\mathit{r}}_{12}+{\mathit{r}}_{12}{\mathit{r}}_{22})\mathit{\eta }-\\ \mathit{　}\mathit{　}{\mathit{r}}_{11}(\mathit{\lambda }+\mathit{\mu }+{\mathit{\alpha }}_{\mathit{c}})+\mathit{\lambda }=0\end{array}\\ {\mathit{r}}_{11}{\mathit{\alpha }}_{\mathit{c}}-{\mathit{r}}_{12}\mathit{\eta }=0\\ \begin{array}{l}({\mathit{r}}_{21}{\mathit{r}}_{11}+{\mathit{r}}_{22}{\mathit{r}}_{21})\mathit{\mu }+({\mathit{r}}_{21}{\mathit{r}}_{12}+{\mathit{r}}_{22}^{2})\mathit{\eta }-\\ \mathit{　}\mathit{　}{\mathit{r}}_{21}(\mathit{\lambda }+\mathit{\mu }+{\mathit{\alpha }}_{\mathit{c}})=0\end{array}\\ {\mathit{r}}_{21}{\mathit{\alpha }}_{\mathit{c}}-{\mathit{r}}_{22}\mathit{\eta }=0\end{array}\right.$

为了得到式(21)的最小非负解R,将式(24)中的第4个方程化简得

(25)${\mathit{r}}_{22}=\frac{{\mathit{r}}_{21}{\mathit{\alpha }}_{\mathit{c}}}{\mathit{\eta }}$

由于方程的结构特性有r₂₁=0,代入式(25)得到r₂₂=0,此时验证这种解是否满足方程,将r₂₁和r₂₂代入式(24)中的第3个方程和第4个方程,这时第3个方程与第4个方程成立。

之后将式(24)中的第二个方程化简得

(26)${\mathit{r}}_{12}=\frac{{\mathit{r}}_{11}{\mathit{\alpha }}_{\mathit{c}}}{\mathit{\eta }}$

再将r₂₁、r₂₂、r₁₂代入式(24)中的第一个方程,得

(27)$(\mathit{\mu }+{\mathit{\alpha }}_{\mathit{c}}){\mathit{r}}_{11}^{2}-(\mathit{\lambda }+\mathit{\mu }+{\mathit{\alpha }}_{\mathit{c}}){\mathit{r}}_{11}+\mathit{\lambda }=0$

化简求得${\mathit{r}}_{11}=\frac{\mathit{\lambda }}{{\mathit{\alpha }}_{\mathit{c}}+\mathit{\mu }}=\mathit{\rho }$(另一个根为r₁₁=1),随后再将${\mathit{r}}_{11}=\frac{\mathit{\lambda }}{{\mathit{\alpha }}_{\mathit{c}}+\mathit{\mu }}=\mathit{\rho }$代入式(26)中,得到${\mathit{r}}_{12}=\frac{\mathit{\lambda }{\mathit{\alpha }}_{\mathit{c}}}{({\mathit{\alpha }}_{\mathit{c}}+\mathit{\mu })\mathit{\eta }}=\frac{\mathit{\rho }{\mathit{\alpha }}_{\mathit{c}}}{\mathit{\eta }}$(另一个根为${\mathit{r}}_{12}=\frac{{\mathit{\alpha }}_{\mathit{c}}}{\mathit{\eta }}$)。

根据上述求解,整理得: r₁₁=ρ、${\mathit{r}}_{12}=\frac{\mathit{\rho }{\mathit{\alpha }}_{\mathit{c}}}{\mathit{\eta }}$、r₂₁=0、r₂₂=0。

由此$\mathit{R}=\left[\begin{array}{ll}\mathit{\rho }& \frac{\mathit{\rho }{\mathit{\alpha }}_{\mathit{c}}}{\mathit{\eta }}\\ 0& 0\end{array}\right]$,其中$\mathit{\rho }=\frac{\mathit{\lambda }}{{\mathit{\alpha }}_{\mathit{c}}+\mathit{\mu }}$。

定理2 当且仅当ρ<1时,QBD过程$\left\{\mathit{L}\right(\mathit{t}),\mathit{W}(\mathit{t}\left)\right\}$是正循环过程。

证明在QBD过程中,π_ij(其中i,j∈{ 0,1 })表示系统为处于状态(i,j)的平稳概率。并且向量{π₀₀,π₀₁,π₁₀,π₁₁}是这些平稳概率的集合,形式为一个行向量。根据Neuts^[40]的定理,当且仅当速率矩阵R的谱半径SP(R)<1,且方程组(π₀₀,π₀₁,π₁₀,π₁₁)B[R]=0具有正解时,QBD 过程$\left\{\mathit{L}\right(\mathit{t}),\mathit{W}(\mathit{t}\left)\right\}$才是正循环过程。矩阵B[R]是通过速率矩阵R构造的转移概率矩阵,即

(28)$\mathit{B}\left[\mathit{R}\right]=\left[\begin{array}{llll}-\mathit{\lambda }& \mathit{\lambda }& 0& 0\\ \mathit{\mu }& -(\mathit{\lambda }+\mathit{\mu })& \mathit{\lambda }& 0\\ 0& \mathit{\mu }& -(\mathit{\mu }+{\mathit{\alpha }}_{\mathit{c}})& {\mathit{\alpha }}_{\mathit{c}}\\ 0& \mathit{\eta }& 0& -\mathit{\eta }\end{array}\right]$

B[R]是一个具有有限状态的不可约非周期的状态矩阵。因此(π₀₀,π₀₁,π₁₀,π₁₁)B[R]=0有正解(例如B[R]的平衡概率向量是正解),过程$\left\{\mathit{L}\right(\mathit{t}),\mathit{W}(\mathit{t}\left)\right\}$是正循环的。求得det(R-βI)=0时的特征值^[42]为

(29)$\mathit{R}-\mathit{\beta }\mathit{I}=\left(\begin{array}{ll}\mathit{\rho }-\mathit{\beta }& \frac{{\mathit{\alpha }}_{\mathit{c}}\mathit{\lambda }}{{\mathit{\alpha }}_{\mathit{c}}\mathit{\eta }+\mathit{\eta }\mathit{\mu }}\\ 0& -\mathit{\beta }\end{array}\right)$

式(29)中:I为与矩阵R同阶的单位矩阵,则

(30)$\begin{array}{l}\mathrm{d}\mathrm{e}\mathrm{t}(\mathit{R}-\mathit{\beta }\mathit{I})=(\mathit{\rho }-\mathit{\beta })(-\mathit{\beta })-\left(\frac{{\mathit{\alpha }}_{\mathit{c}}\mathit{\lambda }}{{\mathit{\alpha }}_{\mathit{c}}\mathit{\eta }+\mathit{\eta }\mathit{\mu }}0\right)\\ =0\end{array}$

此时β=0和β=ρ,当且仅当

(31)$\mathrm{S}\mathrm{P}\left(\mathit{R}\right)=\mathrm{m}\mathrm{a}\mathrm{x}(0,\left|\mathit{\rho }\right|)<1$

此时$\mathit{\rho }=\frac{\mathit{\lambda }}{{\mathit{\alpha }}_{\mathit{c}}+\mathit{\mu }}<1$,系统达到稳态条件,因此得证。

定理3 若集合$\{\mathit{n}:\mathit{n}\ge 1,{\mathit{p}}_{\mathit{i}\mathit{i}}^{\left(\mathit{n}\right)}>0\}$非空,则称该集合的最大公约数$\mathit{d}=\mathit{d}\left(\mathit{i}\right)=\{\mathit{n}:{\mathit{p}}_{\mathit{i}\mathit{i}}^{\left(\mathit{n}\right)}>0\}$为状态i的周期。若d>1就称i为周期的,若d=1就称i为非周期的。

证明 B[R]的状态转换图如图5所示。通过状态转换,可以看到每个状态到达任意其他状态的转换过程。

其中,状态1可以转换到状态2;状态2可以转换到状态1和状态3;状态3可以转换到状态2和状态4;状态 4 可以转换到状态2。从这些转换关系中,可以看出所有状态间存在路径连接,即从任意状态出发可以到达任何其他状态^[40]。

因此,矩阵B[R]是不可约的。

定理4 状态空间I的子集C称为 (随机) 闭集,若对任意 $\mathit{i}\in \mathit{C}$及$\mathit{k}\notin \mathit{C}$都有p_ik=0。闭集C称为不可约的,若C的状态互通。马氏链$\left\{{\mathit{X}}_{\mathit{n}}\right\}$称为不可约的,则其状态空间不可约。

证明从矩阵B[R]的结构和转换关系来看^[43],状态空间$\mathit{I}=\{\mathrm{1,2},\mathrm{3,4}\}$,由状态转移图可知p₁的步数可能为${\mathit{T}}_{1}=\{\mathrm{2,4},5,\dots \}$,依次推知每个状态的循环路径没有共同的周期长度,即从每个状态到自身的路径长度没有严格的周期。

因此,矩阵B[R]是非周期的。

通过求解速率矩阵R[式(23)],证明当系统利用率$\mathit{\rho }=\frac{\mathit{\lambda }}{{\mathit{\alpha }}_{\mathit{c}}+\mathit{\mu }}<1$时,QBD过程为正循环过程,从而系统达到稳态。该条件实际意义在于确保任务到达率不超过服务与损失速率的总和,避免系统不稳定。同时,证明了转移矩阵B[R]的非周期性和其不可约性,这些性质共同确保QBD过程的遍历性和达到稳态。只有在稳态状态下,后续性能指标如平均队列长度、等待时间和虚等待时间等才能被可靠推导和量化,为高负载环境下的任务损失优化与负载均衡调度提供坚实的理论基础。

2.3 系统性能指标

如果ρ<1,则QBD过程$\left\{\mathit{L}\right(\mathit{t}),\mathit{W}(\mathit{t}\left)\right\}$的稳态极限为(L,W),令π_k=(π_k0,π_k1)。

2.3.1 联合概率分布

当$\mathit{\rho }=\frac{\mathit{\lambda }}{{\mathit{\alpha }}_{\mathit{c}}+\mathit{\mu }}<1$时,(L,W)的联合概率分布为

(32)$\left\{\begin{array}{l}{\mathit{\pi }}_{\mathit{k}0}={\mathit{\pi }}_{00}\frac{\mathit{\lambda }{\mathit{\rho }}^{\mathit{k}-1}}{\mathit{\mu }}\\ {\mathit{\pi }}_{01}=\frac{\mathit{\lambda }}{\mathit{\mu }}{\mathit{\pi }}_{00}\\ {\mathit{\pi }}_{\mathit{k}1}={\mathit{\pi }}_{00}\frac{{\mathit{\lambda }}^{\mathit{k}}{\mathit{\alpha }}_{\mathit{c}}}{\mathit{\eta }\mathit{\mu }}\end{array}\right.$

式(32)中:${\mathit{\pi }}_{00}=\frac{\mathit{\mu }}{\mathit{\lambda }}\frac{\mathit{\eta }\mathit{\rho }(1-\mathit{\rho })}{\mathit{\eta }+{\mathit{\alpha }}_{\mathit{c}}\mathit{\rho }}$。

求解使用矩阵几何解法^[40-41],可得

(33)${\mathit{\pi }}_{\mathit{k}}=({\mathit{\pi }}_{\mathit{k}0},{\mathit{\pi }}_{\mathit{k}1})=({\mathit{\pi }}_{10},{\mathit{\pi }}_{11}){\mathit{R}}^{\mathrm{k}-1},\mathit{k}\ge 1$

且${\mathit{\pi }}_{0}\mathit{和}{\mathit{\pi }}_{1}\mathit{满}\mathit{足}({\mathit{\pi }}_{00},{\mathit{\pi }}_{01},{\mathit{\pi }}_{10},{\mathit{\pi }}_{11})\mathit{B}\left[\mathit{R}\right]=0$。

将式(28)代入(π₀₀,π₀₁,π₁₀,π₁₁)B[R]=0,可得

(34)$\left\{\begin{array}{l}-\mathit{\lambda }{\mathit{\pi }}_{00}+\mathit{\mu }{\mathit{\pi }}_{01}=0\\ \mathit{\lambda }{\mathit{\pi }}_{00}-(\mathit{\lambda }+\mathit{\mu }){\mathit{\pi }}_{01}+\mathit{\mu }{\mathit{\pi }}_{10}+\mathit{\eta }{\mathit{\pi }}_{11}=0\\ \mathit{\lambda }{\mathit{\pi }}_{01}-(\mathit{\mu }+{\mathit{\alpha }}_{\mathit{c}}){\mathit{\pi }}_{10}=0\\ {\mathit{\alpha }}_{\mathit{c}}{\mathit{\pi }}_{10}-\mathit{\eta }{\mathit{\pi }}_{11}=0\end{array}\right.$

将π₀₀视为已知常数,可得

$\begin{array}{l}{\mathit{\pi }}_{0}=({\mathit{\pi }}_{00},{\mathit{\pi }}_{01})={\mathit{\pi }}_{00}\left(1,\frac{\mathit{\lambda }}{\mathit{\mu }}\right);\\ {\mathit{\pi }}_{1}=({\mathit{\pi }}_{10},{\mathit{\pi }}_{11})={\mathit{\pi }}_{00}\left(\frac{\mathit{\lambda }\mathit{\rho }}{\mathit{\mu }},\frac{{\mathit{\alpha }}_{\mathit{c}}\mathit{\lambda }\mathit{\rho }}{\mathit{\eta }\mathit{\mu }}\right)\mathit{。}\end{array}$

有

(35)$\begin{array}{l}{\mathit{R}}^{\mathit{k}}=\left[\begin{array}{ll}{\mathit{\rho }}^{\mathit{k}}& \frac{{\mathit{\alpha }}_{\mathit{c}}\mathit{\lambda }}{{\mathit{\alpha }}_{\mathit{c}}\mathit{\eta }+\mathit{\eta }\mathit{\mu }}\stackrel{\mathit{k}-1}{\sum _{\mathit{j}=0}}{\mathit{\rho }}^{\mathit{k}-1-\mathit{j}}\\ 0& 0\end{array}\right]\\ =\left[\begin{array}{ll}{\mathit{\rho }}^{\mathit{k}}& \frac{{\mathit{\rho }}^{\mathit{k}}{\mathit{\alpha }}_{\mathit{c}}}{\mathit{\eta }}\\ 0& 0\end{array}\right],\mathit{k}\ge 1\end{array}$

将(π₁₀,π₁₁)和R^k-1代入式(33)得到式(32)。最后,π₀₀可以通过归一化条件从而确定为${\mathit{\pi }}_{00}=\frac{\mathit{\mu }}{\mathit{\lambda }}\frac{\mathit{\eta }\mathit{\rho }(1-\mathit{\rho })}{\mathit{\eta }+{\mathit{\alpha }}_{\mathit{c}}\mathit{\rho }}$。

此外依据式(32),可以得到服务器在不同状态下的概率为

(36)$\begin{array}{l}\mathit{P}\{\mathit{W}=0\}=\stackrel{\mathit{\infty }}{\sum _{\mathit{k}=0}}{\mathit{\pi }}_{\mathit{k}0}=\frac{\mathit{\lambda }}{\mathit{\mu }}{\mathit{\pi }}_{00}\stackrel{\mathit{\infty }}{\sum _{\mathit{k}=0}}{\mathit{\rho }}^{\mathit{k}-1}\\ =\frac{\mathit{\lambda }{\mathit{\pi }}_{00}}{\mathit{\mu }}\frac{1}{\mathit{\rho }(1-\mathit{\rho })}\end{array}$

(37)${\mathit{\pi }}_{01}=\frac{\mathit{\lambda }}{\mathit{\mu }}{\mathit{\pi }}_{00}=\frac{\mathit{\lambda }}{\mathit{\mu }}\frac{(1-\mathit{\rho })\mathit{\mu }\mathit{\eta }\mathit{\rho }}{\mathit{\lambda }(\mathit{\eta }+{\mathit{\alpha }}_{\mathit{c}}\mathit{\rho })}=\frac{\mathit{\eta }\mathit{\rho }(1-\mathit{\rho })}{\mathit{\eta }+{\mathit{\alpha }}_{\mathit{c}}\mathit{\rho }}$

(38)$\begin{array}{l}\mathit{P}\{\mathit{W}=1\}=\stackrel{\mathit{\infty }}{\sum _{\mathit{k}=0}}{\mathit{\pi }}_{\mathit{k}1}=\frac{\mathit{\lambda }}{\mathit{\mu }}{\mathit{\pi }}_{00}\frac{{\mathit{\alpha }}_{\mathit{c}}}{\mathit{\eta }}\stackrel{\mathit{\infty }}{\sum _{\mathit{k}=0}}{\mathit{\rho }}^{\mathit{k}}\\ =\frac{{\mathit{\alpha }}_{\mathit{c}}\mathit{\lambda }{\mathit{\pi }}_{00}}{\mathit{\mu }\mathit{\eta }}\frac{1}{1-\mathit{\rho }}\end{array}$

其中π₀₁代表系统在边界状态下的初始分布,独立于递归部分,其实际意义在于捕捉空闲或初始取消状态的稳态占比。由此,通过上述求解可得到稳态下系统中任务数量W的随机分解结构。

2.3.2 平均队长与平均等待队长

当$\mathit{\rho }=\frac{\mathit{\lambda }}{{\mathit{\alpha }}_{\mathit{c}}+\mathit{\mu }}<1$时,平均队长L_{Q_t}与平均等待队长L_Wq分别为

(39)${\mathit{L}}_{\mathit{Q}\mathrm{t}}=\frac{\mathit{\lambda }{\mathit{\pi }}_{00}}{\mathit{\mu }{(1-\mathit{\rho })}^{2}}\left(1+\frac{{\mathit{\alpha }}_{\mathit{c}}\mathit{\rho }}{\mathit{\eta }}\right)$

(40)${\mathit{L}}_{\mathit{W}\mathrm{q}}=\frac{\mathit{\lambda }{\mathit{\pi }}_{00}}{\mathit{\mu }{(1-\mathit{\rho })}^{2}}\left(1+\frac{{\mathit{\alpha }}_{\mathit{c}}\mathit{\rho }}{\mathit{\eta }}\right)-\mathit{\rho }$

求解由联合概率分布可知,系统稳态下队长的概率分布是${\mathit{\pi }}_{\mathit{k}}={\mathit{\pi }}_{00}\left[\frac{\mathit{\lambda }{\mathit{\rho }}^{\mathit{k}-1}}{\mathit{\mu }},\frac{\mathit{\lambda }{\mathit{\rho }}^{\mathit{k}}{\mathit{\alpha }}_{\mathit{c}}}{\mathit{\eta }\mathit{\mu }}\right]$,其中π_k=(π_k0,π_k1)为行向量,两个元素分别对应系统队长为k时,工作状态0与工作状态1的稳态概率。

队列的平均长度为

(41)$\begin{array}{l}{\mathit{L}}_{\mathit{Q}\mathrm{t}}=\stackrel{\mathit{\infty }}{\sum _{\mathit{k}=0}}\mathit{k}{\mathit{\pi }}_{\mathit{k}}\\ =\stackrel{\mathit{\infty }}{\sum _{\mathit{k}=0}}\mathit{k}\left({\mathit{\pi }}_{00}\frac{\mathit{\lambda }{\mathit{\rho }}^{\mathit{k}-1}}{\mathit{\mu }}\right)+\stackrel{\mathit{\infty }}{\sum _{\mathit{k}=0}}\mathit{k}\left({\mathit{\pi }}_{00}\frac{\mathit{\lambda }{\mathit{\rho }}^{\mathit{k}}{\mathit{\alpha }}_{\mathit{c}}}{\mathit{\eta }\mathit{\mu }}\right)\\ =\frac{\mathit{\lambda }{\mathit{\pi }}_{00}}{\mathit{\mu }{(1-\mathit{\rho })}^{2}}\left(1+\frac{{\mathit{\alpha }}_{\mathit{c}}\mathit{\rho }}{\mathit{\eta }}\right)\end{array}$

平均等待队长为

(42)${\mathit{L}}_{\mathit{W}\mathrm{q}}={\mathit{L}}_{{\mathit{Q}}_{\mathrm{t}}}-\mathit{\rho }=\frac{\mathit{\lambda }{\mathit{\pi }}_{00}}{\mathit{\mu }{(1-\mathit{\rho })}^{2}}\left(1+\frac{{\mathit{\alpha }}_{\mathit{c}}\mathit{\rho }}{\mathit{\eta }}\right)-\mathit{\rho }$

2.3.3 平均等待时间和平均逗留时间

对于 GI/M/c/∞ 排队系统,在统计平衡下,即$\mathit{\rho }=\frac{\mathit{\lambda }}{{\mathit{\alpha }}_{\mathit{c}}+\mathit{\mu }}<1$条件下,当c=1时,即GI/M/1/∞排队系统,Little公式成立;当c>1时,Little公式不成立^[44]。根据Little定理,平均等待时间W_Qt和平均逗留时间W分别为

(43)${\mathit{W}}_{\mathit{Q}\mathrm{t}}=\frac{{\mathit{\pi }}_{00}}{\mathit{\mu }{(1-\mathit{\rho })}^{2}}\left(1+\frac{{\mathit{\alpha }}_{\mathit{c}}\mathit{\rho }}{\mathit{\eta }}\right)$

(44)$\mathit{W}=\frac{1}{\mathit{\mu }}\left[\frac{{\mathit{\pi }}_{00}}{{(1-\mathit{\rho })}^{2}}\left(1+\frac{{\mathit{\alpha }}_{\mathit{c}}\mathit{\rho }}{\mathit{\eta }}\right)+1\right]$

求解根据Little定理,平均等待时间W_Qt和平均队长L_Qt的关系为

(45)${\mathit{W}}_{\mathit{Q}\mathrm{t}}=\frac{{\mathit{L}}_{\mathit{Q}\mathrm{t}}}{\mathit{\lambda }}$

其后可以将平均队长L_Qt的式(39)代入式(45)计算得${\mathit{W}}_{\mathit{Q}\mathrm{t}}=\frac{{\mathit{\pi }}_{00}}{\mathit{\mu }{(1-\mathit{\rho })}^{2}}\left(1+\frac{{\mathit{\alpha }}_{\mathit{c}}\mathit{\rho }}{\mathit{\eta }}\right)$。

平均逗留时间为

(46)$\mathit{W}={\mathit{W}}_{\mathit{Q}\mathrm{t}}+\frac{1}{\mathit{\mu }}=\frac{1}{\mathit{\mu }}\left[\frac{{\mathit{\pi }}_{00}}{{(1-\mathit{\rho })}^{2}}\left(1+\frac{{\mathit{\alpha }}_{\mathit{c}}\mathit{\rho }}{\mathit{\eta }}\right)+1\right]$

2.3.4 虚等待时间

虚等待时间W_v量化了任务在队列中等待但最终因不耐烦(如超时等因素)退出而未获得服务的“无效”时间总和。该机制不同于传统等待时间W_Qt(仅考虑成功服务的延迟),通过捕捉“隐形损失”,即任务占用队列位置但最终流失,导致资源浪费,揭示了传统模型忽略的动态流失问题。在复杂场景下,通过W_v评估服务器 “潜在过载风险”,优先调度任务可以优化队伍负载。该机制基于退出率θ(t)[式(3)]和等待时间分布W_q(t),实时动态调整,提升系统整体效率和资源利用率。

对于 GI/M/1 排队系统,在统计平衡和Little公式成立条件下,由于在时间t时任务可能会离开系统,考虑任务在等待期间未能获得服务而离开的时间总和,即虚等待时间W_v为

(47)${\mathit{W}}_{\mathrm{v}}=\frac{{\mathit{\alpha }}_{\mathit{c}}{\mathit{\pi }}_{00}}{({\mathit{\alpha }}_{\mathit{c}}{+\mathit{\mu })}^{2}}\stackrel{\mathit{\infty }}{\sum _{\mathit{k}=0}}\left(\frac{\mathit{\lambda }{\mathit{\rho }}^{\mathit{k}-1}}{\mathit{\mu }}+\frac{\mathit{\lambda }{\mathit{\rho }}^{\mathit{k}}{\mathit{\alpha }}_{\mathit{c}}}{\mathit{\eta }\mathit{\mu }}\right)$

求解在平稳条件$\mathit{\rho }=\frac{\mathit{\lambda }}{{\mathit{\alpha }}_{\mathit{c}}+\mathit{\mu }}<1$下,排队系统中的等待时间分布W_q(t)满足条件为

(48)$\begin{array}{l}{\mathit{W}}_{\mathrm{q}}\left(\mathit{t}\right)=1-\stackrel{\mathit{\infty }}{\sum _{\mathit{k}=0}}{\mathit{\pi }}_{\mathit{k}}{\mathrm{e}}^{-\mathit{\mu }\mathit{t}}{\mathit{W}}_{\mathrm{q}}\left(\mathit{t}\right)\\ =1-{\mathit{\pi }}_{00}\stackrel{\mathit{\infty }}{\sum _{\mathit{k}=0}}\left(\frac{\mathit{\lambda }{\mathit{\rho }}^{\mathit{k}-1}}{\mathit{\mu }}+\frac{\mathit{\lambda }{\mathit{\rho }}^{\mathit{k}}{\mathit{\alpha }}_{\mathit{c}}}{\mathit{\eta }\mathit{\mu }}\right){\mathrm{e}}^{-\mathit{\mu }\mathit{t}}\end{array}$

结合任务的退出率θ(t)和排队系统的等待时间分布,对于任务在t时离开的情形,虚等待时间分布的概率密度为

(49)${\mathit{f}}_{\mathrm{v}}\left(\mathit{t}\right)=\mathit{\theta }\left(\mathit{t}\right)[1-{\mathit{W}}_{\mathrm{q}}(\mathit{t}\left)\right]$

式(49)中:1-W_q(t)为任务在时间t时仍未完成任务的概率。

虚等待时间的累积分布函数为

(50)${\mathit{F}}_{\mathrm{v}}\left(\mathit{t}\right)={\int }_{0}^{\mathit{t}}{\mathit{f}}_{\mathrm{v}}\left(\mathit{s}\right)\mathrm{d}\mathit{s}={\int }_{0}^{\mathit{t}}{\mathit{\alpha }}_{\mathit{c}}{\mathit{e}}^{-{\mathit{\alpha }}_{\mathit{c}}\mathit{s}}[1-{\mathit{W}}_{\mathrm{q}}(\mathit{s}\left)\right]\mathrm{d}\mathit{s}$

虚等待时间期望为

(51)${\mathit{W}}_{\mathrm{v}}={\int }_{0}^{\mathit{\infty }}\mathit{t}{\mathit{f}}_{\mathrm{v}}\left(\mathit{t}\right)\mathrm{d}\mathit{t}={\int }_{0}^{\mathit{\infty }}\mathit{t}\mathit{\theta }\left(\mathit{t}\right)[1-{\mathit{W}}_{\mathrm{q}}(\mathit{t}\left)\right]\mathrm{d}\mathit{t}$

在稳态下,虚等待时间期望W_v反映了基本退出影响,精确量化了隐性损失,支持算法在高流量场景下减少任务丢弃率。

随后通过分解积分进行求解,根据积分公式${\int }_{0}^{\mathit{\infty }}\mathit{t}{\mathrm{e}}^{-\mathit{\lambda }\mathit{t}}\mathrm{d}\mathit{t}=\frac{1}{{\mathit{\lambda }}^{2}}$计算之后可得

(52)$\begin{array}{l}{\mathit{W}}_{\mathrm{v}}={\mathit{\alpha }}_{\mathit{c}}\stackrel{\mathit{\infty }}{\sum _{\mathit{k}=0}}{\mathit{\pi }}_{\mathit{k}}{\int }_{0}^{\mathit{\infty }}\mathit{t}{\mathrm{e}}^{-({\mathit{\alpha }}_{\mathit{c}}+\mathit{\mu })\mathit{t}}\mathrm{d}\mathit{t}\\ ={\mathit{\alpha }}_{\mathit{c}}\stackrel{\mathit{\infty }}{\sum _{\mathit{k}=0}}{\mathit{\pi }}_{\mathit{k}}\frac{1}{({\mathit{\alpha }}_{\mathit{c}}{+\mathit{\mu })}^{2}}\end{array}$

统计平衡下$\mathit{\rho }=\frac{\mathit{\lambda }}{{\mathit{\alpha }}_{\mathit{c}}+\mathit{\mu }}<1$,将联合概率分布π_k=(π_k0,π_k1),即式(32)代入式(52),最终计算得到${\mathit{W}}_{\mathrm{v}}=\frac{{\mathit{\alpha }}_{\mathit{c}}{\mathit{\pi }}_{00}}{({\mathit{\alpha }}_{\mathit{c}}{+\mathit{\mu })}^{2}}\stackrel{\mathit{\infty }}{\sum _{\mathit{k}=0}}\left(\frac{\mathit{\lambda }{\mathit{\rho }}^{\mathit{k}-1}}{\mathit{\mu }}+\frac{\mathit{\lambda }{\mathit{\rho }}^{\mathit{k}}{\mathit{\alpha }}_{\mathit{c}}}{\mathit{\eta }\mathit{\mu }}\right)$。

3 负载调度

3.1 系统模型

在服务器负载调度均衡的研究中,评估服务器状态与负载指标对实现高效资源分配至关重要。传统性能度量主要包括平均等待队列长度L_Wq与平均等待时间W_Qt。其中,L_Wq表示服务器的即时排队压力,数值越小意味着排队任务越少;W_Qt则用于衡量任务在实际获得服务前的时间成本,数值越小代表处理效率越高。然而,在任务动态性强、存在不耐烦或取消行为的复杂场景中,仅靠这两类指标难以全面准确评估服务器的实际负载与效率。

为弥补这一不足,引入虚等待时间W_v,表示在等待过程中因任务提前退出导致未实际获得服务的等待时长,以量化任务流失引起的资源浪费与性能损失,从而增强指标体系的精度与敏感性。进一步地,通过对任务平均等待队列长度、平均等待时间和虚等待时间进行加权平均,构建负载分配衡量指标K,据此为后续任务调度决策提供依据。数值较大的K表示服务器负载较重,反之则较轻。调度器根据K值优先向负载较低的服务器分配任务,实现服务器负载的有效均衡。基于上述3类指标,K被定义为上述3个指标的加权函数,用于指导任务的分配决策,表达式为

(53)$\left\{\begin{array}{l}\mathit{K}=\mathit{\alpha }{\mathit{L}}_{\mathit{W}\mathrm{q}}+\mathit{\sigma }{\mathit{W}}_{\mathit{Q}\mathrm{t}}+\mathit{r}{\mathit{W}}_{\mathrm{v}}\\ \mathit{\alpha }+\mathit{\sigma }+\mathit{r}=1\end{array}\right.$

该加权组合方式有助于在多维度性能衡量中实现权衡,L_Wq强调了系统缓冲区长度对当前负载的直接贡献,W_Qt刻画了任务获得服务前的实际延迟成本,而W_v则为识别潜在任务损失提供了有效的观测窗口。其中α、σ、r分别表示各指标的权重,可根据实际场景动态调整,以满足不同的调度需求。例如针对任务退出率较高的特殊情形,应重点关注虚等待时间W_v,通过增加的权重,减少任务因等待时间过长而流失的概率。

评估此分配策略的优越性可根据方差大小进行判断,对n个任务统计K,可得出任务分配指标的平均值$\stackrel{-}{\mathit{K}}$与方差F如下。

(54)$\stackrel{-}{\mathit{K}}=\frac{1}{\mathit{n}}\stackrel{\mathit{n}}{\sum _{\mathit{i}=1}}{\mathit{K}}_{\mathit{i}}$

(55)$\mathit{F}=\frac{1}{\mathit{n}}\stackrel{\mathit{n}}{\sum _{\mathit{i}=1}}({\mathit{K}}_{\mathit{i}}{-\stackrel{-}{\mathit{K}})}^{2}$

式中:$\stackrel{-}{\mathit{K}}$为整体负载状态的期望估计值,而方差则体现了负载分布的离散度及波动特征,方差越小表明任务分配均衡度越好,这一度量方案在服务器复杂场景下尤为重要。

3.2 系统的调度策略

在动态任务场景下,任务的复杂性与随机性对传统调度策略提出较大挑战。为高效分配资源、减少不必要的调度开销,基于上述建立的模型提出了基于损失的心跳调度算法,包含负载调度和任务分配决策两部分。算法引入基于“心跳机制”的空闲队列快速检测策略,系统周期性地检测服务器状态。当任务到达时,若检测到空闲服务器,任务将直接分配,无需中央调度;否则由中央调度器根据负载分配衡量指标K分配任务。

运行过程中,系统根据任务到达率与退出行为实时调整策略。当任务到达率低时,更多采用心跳机制快速分配,降低开销;当任务到达率高时,由中央调度器依据指标K动态优化任务分配至负载最轻的服务器,避免过载。JIQ策略能显著缩短等待时间,减少因等待过长而引发的任务流失。此时,任务直接加入空闲队列的概率为

(56)${\mathit{P}}_{\mathrm{J}}=\frac{\mathit{I}\left(\mathit{t}\right)}{\mathit{N}}$

式(56)中:I(t)为当前空闲服务器的数量;N为服务器总数。较高的P_J说明资源有较多空闲,利用率相对较低,较低的P_J则可能表明系统处于高负载或过载状态。

基于分布式系统和负载均衡领域的标准实践,心跳日志(Heartbeat Log)作为心跳机制的核心记录组件,在分布式系统中扮演着关键角色,用于实时状态监控、故障诊断和决策触发,确保高效解析和存储。心跳日志主要记录以下日志信息:

时间戳(Timestamp):记录心跳发送/接收的时间,用于追踪延迟或异常。

节点/服务器标识(Server ID):记录发送心跳的服务器唯一标识,便于定位问题。

状态信息(Status Info):包括当前负载(如CPU使用率、内存占用)、队列长度、退出率θ(t)以及健康状态。

心跳间隔(Heartbeat Interval):记录当前心跳频率或调整后的间隔,用于动态适应负载变化。

事件或指标(Events/Metrics):记录特定事件,如任务分配成功/失败、拥塞信号、错误码(Timeout, Failure等)、性能指标(平均等待队长L_Wq、平均等待时间W_Qt、虚等待时间W_v)。

通过以上记录的信息,确认触发条件并支持JIQ策略激活,心跳日志在代码实现中设计为事件驱动机制。随后通过日志聚合记录触发次数,以验证该功能的有效性和鲁棒性。将心跳机制作为日志驱动的方法不仅提升了系统的自适应能力,还为后续性能调优提供了量化依据。借助心跳机制与空闲队列策略,可显著提升调度灵活性、降低调度延迟,并有效减少因任务取消所引起的性能损失。

进一步地,可定义综合策略度量Z,通过度量Z体现负载与资源利用程度之间的平衡,表达式为

(57)$\mathit{Z}=\mathit{\Delta }\mathit{K}+\mathit{\zeta }{\mathit{P}}_{\mathrm{J}}$

Z可以结合P_J衡量资源使用效率,通过调整权重,在空闲资源与负载均衡之间寻找最优点,从而优化资源分配策略。此外,该方法也可用于评估系统对突发负载和动态场景的适应性,当任务到达率突然增加时,较低的ΔK和较高的$\mathit{\zeta }{\mathit{P}}_{\mathrm{J}}$表明系统能够快速适应变化。之后可以通过调节Δ、$\mathit{\zeta }$与指标K的权重α、σ、r使得策略框架得以在较低负载波动(即低方差)与合理利用空闲资源(即高P_J值)之间寻求理想的折中点。该策略适用于高动态性与复杂队列行为的多服务器系统,能在不确定环境下维持高弹性与响应速度,既能提升调度灵活性、降低延迟,又可有效削减任务取消导致的性能损失。

4 实验分析

通过上述分析,推导出带任务损失的服务器GI/M/1队列系统性能指标,结合公式计算静态指数并设计基于损失的心跳调度算法。针对系统性能指标动态变化、动态排队模型高仿真复杂度的特点,鉴于Python在并行计算和数据处理方面具备卓越性能,因此,采用Python构建数值算例验证方法的有效性。系统到达率、服务率及损失率基于随机初始队列数据计算以贴近实际场景,仿真参数为任务总数6 000、服务器数量1 000,初始队列任务量随仿真动态变化。为明晰算法负载均衡作用机制,首先分析心跳触发次数特征,心跳频率提升可反映系统负载增加时任务调度与资源分配频率的同步提高,其触发结果如图6所示。

从图6中可见,随着时间推移,任务量累积导致系统负载攀升,心跳频率随之显著提高;此时任务丢失率同步上升,调度系统需通过更频繁的资源分配调整以维持任务平稳执行,进而使心跳机制触发次数维持在较高水平。后期经负载调整,大量任务完成执行,系统逐步进入稳态,空闲队列数量增加,心跳频率亦趋于平稳增长。这表明所提算法可动态调控心跳机制,在高负载场景下通过高频心跳触发优化调度策略,实现高效资源管理与负载均衡,保障系统长期运行的稳定性与高效性。

为验证所提基于损失的心跳调度算法的优越性,选取服务器占用率为核心对比指标之一,将该算法与随机调度、轮询调度、最小连接调度及哈希调度4种典型算法进行性能对比实验,实验结果如表2与图7所示。

设置每5个时间步为一个进程时,表2展示了各算法在不同时间点的服务器占用率。由于实验环境的任务量与服务器数量较高,任务动态变化对调度算法提出较大挑战,因此对不同算法的资源占用情况进行了监测和分析。通过对比发现,基于损失的心跳调度算法在高负载阶段能保持较低的资源占用率,仅在后期任务大量完成后才显著降低,表现出较好的资源优化和负载均衡能力。

为更清晰地分析服务器占用率随负载变化的趋势,将表2的数据以墙体图形式可视化,动态展示了5种算法随时间的性能表现,通过多维可视化对比了不同算法在各时间段资源利用率的差异。经多次仿真与实验验证,各算法表现差异如图7所示。

从图7中可以看出基于损失的心跳调度算法在服务器占用率上具有独特优势。初期资源利用最优,对负载增加响应敏感,高负载时能避免过度分配,表现出较强的自适应性。该算法根据实际负载动态调整资源分配,提升了资源利用率和系统稳定性,在高负载环境中提高了系统整体效率,减少了浪费,这对于保证长时间的高效运行至关重要。

为进一步验证基于损失的心跳调度算法的优劣,将方差作为比较指标之一,方差能够反映调度策略对资源利用和任务分配的影响,依据式(55)计算并比较了5种调度算法在不同时间点的服务器负载方差,结果如表3所示。

方差反映负载稳定性,低方差表示分配更均衡。以每 5 个时间步作为一个进程,持续监测负载分布情况。表3数据显示,基于损失的心跳算法方差显著低于其他算法,证明其在高动态负载环境下的均衡性和稳定性,验证了其调度有效性。

为进一步评估算法在长时间、高动态负载场景下的性能差异,对五种算法的服务器负载方差进行了动态可视化对比,如图8所示。

从图8可见,不同调度算法的方差随时间表现出明显差异。哈希调度算法初期方差较低,但随时间推移迅速增加,长时间运行下系统稳定性明显下降。随机、最小连接及轮询调度算法方差增长缓慢,整体波动较小,但方差水平仍高于基于损失的心跳调度算法。基于损失的心跳调度算法始终维持较低且稳定的方差,表现出较强的动态负载自适应能力,尤其在高负载或长期运行中,能有效平衡负载、降低资源分配的不均匀性。这些仿真对比与数据分析结果揭示了不同算法在动态负载环境下的均衡性与适应性差异,并为进一步优化调度策略提供了参考依据。

为进一步验证不同算法的性能表现,从平均完成时间(即平均逗留时间)和平均等待时间角度展开分析。依据式(43)和式(44)求出了基于损失的心跳调度算法的平均等待时间和平均逗留时间,通过与其他算法进行对比,结果如图9和图10所示。

从图9可以看出,基于损失的心跳调度算法的平均任务完成时间始终较低且增长缓慢,长时间运行仍能保持合理水平,避免了任务堆积,后期呈下降趋势,说明大量任务已经完成,提高了完成效率。然而最小连接调度算法在较长时间运行后完成时间开始增加,说明在任务处理过程中可能出现资源过度集中竞争。其余算法则是随着时间增加呈显著上升趋势,表明效率较低造成任务堆积,致使负载增加。图10结果显示基于损失的心跳调度算法在整个时间序列中的等待时间均最低,增长趋势平缓,有效降低了资源竞争和任务延迟,避免了长时间等待造成的资源浪费。相反,最小连接调度算法在相同条件下,平均等待时长随时间推移缓慢增加,表明其在处理大量任务时容易出现队列积压而严重影响系统效率。

综上所述,从平均完成时间和平均等待时间两个维度来看,基于损失的心跳调度算法表现出较强的稳定性、适应性和资源利用率,能有效减少任务延迟和系统拥堵。因此,该算法适用于长期高负载运行的系统环境,在多任务调度中具有较高的效率。

此外,系统吞吐量和任务完成数量也是衡量算法好坏的重要关注点,二者直接反映了算法对系统资源的有效利用程度和任务处理效率。任务完成数量体现了算法实际处理能力,也体现了系统在实际运行中的生产力水平,而高的吞吐量意味着系统能在单位时间内处理更多的任务。这里通过实验分析和对比,如图11和图12所示。

从图11和图12的对比中可以看出,基于损失的心跳调度算法的任务完成数量和吞吐率均显著高于其他算法,长时间运行后的优势更加突出。基于损失的心跳调度算法相较于其他调度算法不仅在大量任务负载下能维持较高的任务处理速度,充分利用系统资源,减少任务积压。且能在相同时间内完成更多任务,表现出更高的吞吐量。相比之下,其他算法的任务完成数量及吞吐率增长缓慢,表明在处理大量任务时系统效率较低。因此,基于损失的心跳调度算法更适合于高吞吐量需求的系统,能更加适应动态负载变化。

综合以上各项性能指标的分析,基于损失的心跳调度算法在方差控制、任务平均完成时间和平均等待时间、任务完成数量以及系统吞吐量等各方面均展现出明显优势,在高负载、长期稳定运行的动态任务调度环境中体现出更强的适应性和资源调度效率。同时,通过动态调整心跳频率,有效实现了负载均衡与资源优化管理。

5 结论

针对 GI/M/1 排队系统的负载均衡问题,提出结合虚等待时间与空闲队列策略的基于损失的心跳调度算法。通过将虚等待时间作为补充指标,量化任务流失带来的资源浪费与性能损失,结合心跳机制增强连接稳定性、动态调整空闲队列调度,有效提升了高负载及任务流失场景下的系统吞吐量,减少了资源浪费与平均等待时间。

通过构建系统 Markov 链,将最小生成元分块矩阵化得到QBD,利用矩阵几何方法求解稳态概率方程获得性能指标,为任务分配与负载均衡提供了精准决策依据。实验验证了该算法在引入虚等待时间和心跳机制后的有效性,为复杂网络环境下排队系统优化提供了理论支撑。后续研究将进一步完善模型,拓展其应用领域。

参考文献

原文顺序 | 出版日期 | 本文引用

[1]	中国信息通信研究院. 云计算蓝皮书(2025年)[R/OL]. (2025-07-22) [2025-08-26]. 北京: 中国信息通信研究院, 2025. https://www.caict.ac.cn/kxyj/qwfb/bps/index_1.htm.

[2]	China Academy of Information and Communications Technology (CAICT). Cloud Computing Blue Book (2025)[R/OL]. (2025-07-22) [2025-08-26]. Beijing: China Academy of Information and Communications Technology. https://www.caict.ac.cn/kxyj/qwfb/bps/index_1.htm.

[3]	IDC 中国. 2025 上半年中国 AI IaaS 市场跟踪报告: prCHC53879525[R]. 北京: IDC 中国, 2025.

[4]	IDC China. 2025 first half China AI IaaS market tracking report: prCHC53879525[R]. Beijing: IDC China, 2025.

[5]	中华人民共和国工业和信息化部, 国家标准化管理委员会. 两部门关于印发《云计算综合标准化体系建设指南(2025版)》的通知: 工信部联科〔2025〕175号[Z/OL]. 北京: 工业和信息化部, 2025. (2025-10-09) [2025-12-12]. https://www.miit.gov.cn/zwgk/zcwj/wjfb/tz/art/2025/art_60eeb6e673e1423ea27ac6dd81830013.html.

[6]

Ministry of Industry and Information Technology of the People’s Republic of China, Standardization Administration of the People’s Republic of China (SAC). Notice of the two ministries and commissions on issuing the “Guidelines for the Construction of a Comprehensive Standardization System for Cloud Computing (2025 Edition)”: MIIT Joint Sci. 〔2025〕No. 175[Z/OL]. Beijing: Ministry of Industry and Information Technology, 2025. (2025-10-09) [2025-12-12]. https://www.miit.gov.cn/zwgk/zcwj/wjfb/tz/art/2025/art_60eeb6e673e1423ea27ac6dd81830013.html.

[7]	新华社. 中共中央关于制定国民经济和社会发展第十五个五年规划的建议[Z/OL]. 北京: 中共中央, 2025. (2025-10-28) [2025-12-12]. https://www.gov.cn/zhengce/202510/content_7046052.htm.

[8]

Central Committee of the Communist Party of China (CCCPC). Proposal of the Central Committee of the Communist Party of China on Formulating the 15th Five-Year Plan for National Economic and Social Development[Z/OL]. Beijing: Central Committee of the Communist Party of China, 2025. (2025-10-28) [2025-12-12]. https://www.gov.cn/zhengce/202510/content_7046052.htm.

[9]	Chippagiri S, Ravula P, Gangwani D. Optimizing load balancing and task scheduling in cloud computing based on nature-inspired optimization algorithms[J]. European Journal of Theoretical and Applied Sciences, 2024, 2 (6): 794-805.

[10]	Elsakaan N, Kamal A. A novel multi-level hybrid load balancing and tasks scheduling algorithm for cloud computing environment[J]. The Journal of Supercomputing, 2024, 80: 1-41.

[11]	李梦寒, 郑小盈, 李明齐, 等. 基于负载均衡的在线云存储流量调度研究[J]. 科学技术与工程, 2015, 15(26): 70-75.

[12]	Li Menghan, Zheng Xiaoying, Li Mingqi, et al. Research on online cloud storage traffic scheduling based on load balancing[J]. Science Technology and Engineering, 2015, 15(26): 70-75.

[13]	许小媛, 李海波, 黄黎. 云存储多异构文件联合延迟尾概率凸优化分析[J]. 计算机工程与应用, 2021, 57(5): 88-94.

[14]	Xu Xiaoyuan, Li Haibo, Huang Li. Convex optimization analysis of joint delay tail probability for multi-heterogeneous files in cloud storage[J]. Computer Engineering and Applications, 2021, 57(5): 88-94.

[15]	Patel M G, Bhoi U. A systematic review of different task scheduling algorithms in cloud computing[J]. International Journal of Modern Trends in Engineering and Research, 2015, 2(3): 382-388.

[16]	陈黄科, 祝江汉, 朱晓敏, 等. 云计算中资源延迟感知的实时任务调度方法[J]. 计算机研究与发展, 2017, 54(2): 446-456.

[17]	Chen Huangke, Zhu Jianghan, Zhu Xiaomin, et al. Resource delay-aware real-time task scheduling method in cloud computing[J]. Journal of Computer Research and Development, 2017, 54(2): 446-456.

[18]	闫寒, 李霞, 崔洪军, 等. 基于排队论的服务区加油区合理用地规模计算[J]. 科学技术与工程, 2017, 17(28): 150-153.

[19]	Yan Han, Li Xia, Cui Hongjun, et al. Calculation of reasonable land use scale for refueling area in service area based on queuing theory[J]. Science Technology and Engineering, 2017, 17(28): 150-153.

[20]	Doll A, Abbasi M, Zhao M, et al. Oversaturated intersections: a real-world assessment of polynomial fluid queue models[J]. Physica A: Statistical Mechanics and Its Applications, 2024, 651: 129864.

[21]	Bogachev M I, Pyko N S, Tymchenko N, et al. Approximate waiting times for queuing systems with variable cross-correlated arrival rates[J]. Physica A: Statistical Mechanics and its Applications, 2024, 654: 130152.

[22]	张秋平, 孙胜, 刘敏, 等. 面向多边缘设备协作的任务卸载和服务缓存在线联合优化机制[J]. 计算机研究与发展, 2021, 58(6): 1318-1339.

[23]	Zhang Qiuping, Sun Sheng, Liu Min, et al. Online joint optimization mechanism of task offloading and service caching for multi-edge device collaboration[J]. Journal of Computer Research and Development, 2021, 58(6): 1318-1339.

[24]	Lima D H S, Aquino A L L, Rosso O A, et al. Characterization of task allocation techniques in data centers based on information theory[J]. Physica A: Statistical Mechanics and Its Applications, 2024, 634: 129447.

[25]	Savita M, Tiwari R, Saini M L. Applications of queuing theory in cloud computing: a review[J]. SSRN Electronic Journal, 2024. DOI:10.2139/ssrn.4485292.

[26]	杨喜娟, 李忠学, 黎锁平, 等. 带启动时间和工作故障的 M/M/1/N 排队系统性能分析[J]. 控制理论与应用, 2019, 36 (4): 561-569.

[27]	Yang Xijuan, Li Zhongxue, Li Suoping, et al. Performance analysis of M/M/1/N queuing system with start-up time and working breakdown[J]. Control Theory & Applications, 2019, 36(4): 561-569.

[28]	Matsak I, Krasnitskiy S. Asymptotic behavior of the extreme values of queue length and waiting time in M/G/1 and GI/M/1 Systems[J]. Cybernetics and Systems Analysis, 2025, 61(1): 106-115.

[29]

Mageed I A, Becheroul A. The fine thread between stability and randomness of the non-stationary D/M/1 Queue’s GI/M/1 pointwise of stationary fluid flow approximation model with application ultra-low latency of autonomous driving service[EB/OL]. (2024-05) [2025-08-26]. https://doi.org/10.20944/preprints202405.0649.v2.

[30]	贺道德, 徐计, 黄正鹏. 基于簇首负载均衡的无线传感器网络分层路由协议[J]. 科学技术与工程, 2020, 20(22): 9122-9127.

[31]	He Daode, Xu Ji, Huang Zhengpeng. Hierarchical routing protocol for wireless sensor networks based on cluster head load balancing[J]. Science Technology and Engineering, 2020, 20 (22): 9122-9127.

[32]	Shen Y, Yang H, Xie Y, et al. Adaptive robustness optimization against network cascading congestion induced by fluctuant load via a bilateral-adaptive strategy[J]. Physica A: Statistical Mechanics and its Applications, 2023, 630: 129229.

[33]	许晶, 王展, 元国军, 等. 面向智算中心的细粒度流量控制技术综述[J]. 计算机研究与发展, 2025, 62(11): 2806-2825.

[34]	Xu Jing, Wang Zhan, Yuan Guojun, et al. Survey on fine-grained traffic control technology for intelligent computing centers[J]. Journal of Computer Research and Development, 2025, 62(11): 2806-2825.

[35]	Milani A S, Navimipour N J. Load balancing mechanisms and techniques in the cloud environments: systematic literature review and future trends[J]. Journal of Network and Computer Applications, 2016, 71: 86-98.

[36]	Singh P. Queuing theory in cloud computing: analyzing M/M/1 and M/M/c/N models with AWS[J]. International Journal of Science and Social Science Research, 2025, 2(4): 122-134.

[37]	陈超, 赵跃龙, 王文丰, 等. 基于反馈的改进动态负载均衡策略[J]. 计算机工程, 2010, 36(14): 34-36, 39.

[38]	Chen Chao, Zhao Yuelong, Wang Wenfeng, et al. Improved dynamic load balancing strategy based on feedback[J]. Computer Engineering, 2010, 36(14): 34-36, 39.

[39]	王煜炜, 刘敏, 马诚, 等. 面向网络功能虚拟化的高性能负载均衡机制[J]. 计算机研究与发展, 2018, 55(4): 689-703.

[40]	Wang Yuwei, Liu Min, Ma Cheng, et al. High-performance load balancing mechanism for network function virtualization[J]. Journal of Computer Research and Development, 2018, 55(4): 689-703.

[41]	刘敬玲, 黄家玮, 蒋万春, 等. 数据中心负载均衡方法研究综述[J]. 软件学报, 2021, 32(2): 300-326.

[42]	Liu Jingling, Huang Jiawei, Jiang Wanchun, et al. Survey on load balancing methods in data centers[J]. Journal of Software, 2021, 32(2): 300-326.

[43]	陈攀, 孙鉴, 吴隹伟, 等. 基于改进粒子群的云计算任务调度算法[J]. 科学技术与工程, 2025, 25(12): 5045-5057.

[44]	Chen Pan, Sun Jian, Wu Zhuiwei, et al. Cloud computing task scheduling algorithm based on improved particle swarm optimization[J]. Science Technology and Engineering, 2025, 25(12): 5045-5057.

[45]	程林钢, 王亚光. 基于分布特征学习灰狼优化算法的云计算资源调度方法[J]. 计算机应用与软件, 2025, 42(5): 306-316.

[46]	Cheng Lingang, Wang Yaguang. Cloud computing resource scheduling method based on gray wolf optimization algorithm with distribution feature learning[J]. Computer Applications and Software, 2025, 42(5): 306-316.

[47]	贾嘉, 慕德俊. 基于人工蜂群的云计算负载均衡算法[J]. 科学技术与工程, 2020, 20(16): 6532-6537.

[48]	Jia Jia, Mu Dejun. Cloud computing load balancing algorithm based on artificial bee colony[J]. Science Technology and Engineering, 2020, 20(16): 6532-6537.

[49]	刘春红, 李为丽, 焦洁, 等. 一种可解释的云平台任务终止状态预测方法[J]. 计算机研究与发展, 2024, 61(3): 716-727.

[50]	Liu Chunhong, Li Weili, Jiao Jie, et al. An interpretable task termination state prediction method for cloud platforms[J]. Journal of Computer Research and Development, 2024, 61(3): 716-727.

[51]	陈基漓, 李海军, 谢晓兰. 基于时间卷积和长短期记忆网络的短期云资源预测模型[J]. 科学技术与工程, 2025, 25(7): 2856-2864.

[52]	Chen Jili, Li Haijun, Xie Xiaolan. Short-term cloud resource prediction model based on temporal convolution and long short-term memory network[J]. Science Technology and Engineering, 2025, 25(7): 2856-2864.

[53]	Tao S, Li Q, Zhou Q, et al. Optimization research of heterogeneous 2D-parallel lattice boltzmann method based on deep computing unit[J]. Applied Sciences, 2024, 14(14): 6078.

[54]	吕光宏, 王坤. 时空图注意力机制下的 SDN 网络动态流量预测[J]. 计算机工程与应用, 2025, 61(8): 267-273.

[55]	Lü Guanghong, Wang Kun. Dynamic traffic prediction of SDN network under spatio-temporal graph attention mechanism[J]. Computer Engineering and Applications, 2025, 61(8): 267-273.

[56]	Haight F A. Queueing with reneging[J]. Metrika, 1957, 1: 186-197.

[57]	Devi N, Dalal S, Solanki K, et al. A systematic literature review for load balancing and task scheduling techniques in cloud computing[J]. Artificial Intelligence Review, 2024, 57(10): 276.

[58]	Chaudhary H, Sharma G, Nishad D, et al. Advanced queueing and scheduling techniques in cloud computing using AI-based model order reduction[J]. Discover Computing, 2025, 28(1): 9581.

[59]	Niranjan S P, Devi Latha S, Vlase S, et al. Analysis of bulk queueing model with load balancing and vacation[J]. Axioms, 2024, 14: 18.

[60]	Medhi J. Stochastic models in queueing theory[M]. Boston: Birkhäuser, 2003.

[61]	Neuts M F. Matrix-geometric solutions in stochastic models: an algorithmic approach[M]. Baltimore: Johns Hopkins University Press, 1981.

[62]	Latouche G, Ramaswami V. Introduction to matrix analytic methods in stochastic modeling[M]. Philadelphia: SIAM, 1999.

[63]	张文丽, 万晓娟, 杨静雅. 矩阵特征值和特征向量在微分方程求解中的应用[J]. 长治学院学报, 2024, 41(5): 7-15.

[64]	Zhang Wenli, Wan Xiaojuan, Yang Jingya. Application of matrix eigenvalues and eigenvectors in solving differential equations[J]. Journal of Changzhi University, 2024, 41(5): 7-15.