-
摘要: 分布异构计算资源通过网络连接形成算力网络 (Computing power network, CPN), 其以“连”和“算”为核心. 针对广分布异构性导致可行解空间巨大、强不确定性导致可行解空间易变、高约束复杂性导致可行解孤岛繁多、多目标性导致冲突目标权衡优化难等挑战, 提出一个多层次算力网络体系框架, 包括参数化结构化业务管理、三阶段(计划、调度、执行)闭环调度模式、多模态资源管理三个功能. 提出支持快速、高效、鲁棒的“算法+知识+数据+算力”的算力网络智慧调度框架, 形式化分析可行解空间, 解析调度策略关键参数, 定性分析调度算法性能与效率的内在关系, 详细综述调度算法类型, 综述算力网络调度研究进展与发展方向. 对比已有相关综述研究, 展望算力网络调度未来理论和技术的难点与趋势.Abstract: Distributed heterogeneous computing resources are connected through the network to form a computing power network (CPN), in which “connection” and “computing” are the cores. There are several great challenges including the huge feasible solution space resulted from widely distributed heterogeneity, the variable feasible solution space caused by strong uncertainty, a large number of feasible solution islands resulted from highly constrained complexity, and the difficulty in optimizing multiple conflicting objectives. For these challenges, a multi-level computing power network framework is proposed in this paper, which contains three functions: Parameterized structural process management, three-phase (planning, scheduling, execution) closed-loop scheduling model, and multi-modal resource management. A computing power network intelligent scheduling framework with “algorithm +knowledge + data + computing power” is proposed to wisely schedule complex tasks to CPN resources effectively, efficiently and robustly. The feasible solution space is formally analyzed. The key parameters of scheduling strategy are introduced. The intrinsic relationship between effectiveness and efficiency of scheduling algorithms are qualitatively analyzed. Different types of scheduling algorithms are surveyed thoroughly. The state-of-the-art and future work are illustrated. The surveys on CPN scheduling algorithms are compared, followed by the theoretical and technical problems and tendency in CPN scheduling algorithms.
-
Key words:
- Computing power network (CPN) /
- cloud computing /
- edge computing /
- resource scheduling /
- knowledge
-
算力网络是支撑国家网络强国、数字中国、智慧社会战略的新型基础设施, 是对接国家规划、落实“东数西算”工程部署的重要支撑. 2022年2月, 在京津冀、长三角、粤港澳大湾区、成渝、内蒙古、贵州、甘肃、宁夏等8地启动建设国家算力枢纽节点, 并规划了10个国家数据中心集群, 完成全国一体化大数据中心体系的总体布局. 算力网络也越来越受到学术界和产业界的广泛关注.
面向“东数西算”大数据的算力网络包括算什么(计算需求)、由谁算(算力资源)、如何算(调度算法)等核心步骤. 看起来“东数西算”是将“数”或者“算”进行搬迁, 但并不意味着所有的数据都需要从东传到西, 也并非东部不作任何计算而由西部完成所有计算业务, “东数”是否需要“西算”的决策依赖于相应大数据的计算开销与通信开销总和. 如何将分布异构计算资源通过网络连接形成算力网络是必然趋势, 主要体现为[1]: 1)算力需求量激增: “东数西算”工程、虚拟现实[2]、数字孪生[3]、元宇宙[4]等对算力需求越来越大. 例如, 据罗兰·贝格公司预测, 从2018年到2030年, 无人驾驶算力需求增加390倍, 数字货币算力需求增加约2000倍, 游戏算力需求增加约300倍、端到端时延需小于20 ms. 2)算力供需地域不平衡[1, 5]: 东部算力需求大、算力不足, 西部算力需求相对小、算力充足, 将东部算力需求有序引导到西部, 优化数据中心建设布局, 促进东西部协同联动, 让西部算力资源更充分地支撑东部数据运算, 更好地为数字化发展赋能. 3)算力供应融合共生度不高[6]: 我国云边端(Cloud-edge-terminal) 三级算力整体上呈现内核多样化、分布泛在化趋势, 已有海量终端接入网络, 边端算力逐渐丰富, 但缺乏网络连接的泛在算力, 亟需突破单点算力性能极限以发挥算力集群优势, 算力融合度和共生度需完善[7].
面向多元化、多粒度复杂计算需求, 充分利用通过网络连接形计算资源是算力网络的核心科学问题. 尽管目前计算需求量激增, 但互联网数据中心统计的结果表明: 由于算力供需地域不平衡等原因, 数据中心、物理服务器、个人计算机以及消费终端等各类平台计算资源的利用率都低于15%. 需求激增与算力资源大量闲置的矛盾日益突出, 亟需构建合理的算力网络体系架构, 突破以需求−资源快优稳智慧调度为核心的关键技术[8].
本文提出一个多层次算力网格体系框架, 其创新性和优势体现为: 1)参数化结构化业务管理模型: 面向算力业务需求量激增难以有效管理等挑战, 提出参数化结构化业务管理模型, 无论用户业务需求属于何种类型, 都可刻画为最小粒度任务集合及这些任务间线性、非线性关系; 参数化任务到达、任务执行、截止时间、预算等参数. 2)算力网络调度优化模型: 针对算力供需地域不平衡等挑战, 面向计划、调度、执行等不同阶段优化问题, 提出以快优稳为终极目标的“算法+知识+数据+算力”的算力网络调度优化模型, 支持快速、高效、鲁棒地解决这类复杂优化问题. 3)以智慧调度为核心的算力网络体系架构: 针对算力供应融合共生度不高等挑战, 提出以算力网络管理层为操作系统功能的算力网络体系架构, 包含用户层、算力网络管理层、资源层. 其中算力网络管理层包含业务管理层、业务调度层、资源管理层, 分别对应中国移动《算力网络白皮书》[8]的算网运营层、算网大脑层、算网底座层, 并且更关注算力的智慧调度.
1. 算力网络概念及挑战
算力网络尚没有统一定义, 较为典型的定义由中国移动[8]给出:
定义 1. 算力网络是以算为中心, 网为根基, 网、云、数、智、安、边、端、链(ABCD-NETS)等深度融合, 提供一体化服务的新型信息基础设施.
为达成“网络无所不达、算力无所不在、智能无所不及”的愿景, 算力网络需实现“算力泛在、算网共生、智能编排、一体服务”, 以“连”和“算”为核心, 通信开销和计算开销的共生融合是关键.
算力网络正在成为研究热点, 但英文名称不统一, 较为常见的有computing power network, compute first networking, computing force network, computing first networking, computing first network, 从Scopus上搜索到95篇相关研究论文, 不同算力网络概念分布情况如图1所示.
算力网络是通过网络连接用户、数据和算力的多层立体泛在算力架构, 通过深度融合算力, 实现算网的统一编排、调度、管理、运维, 打造算力网络资源一体设计、全局编排、灵活调度、高效优化的能力. 算力网络提供算、网、数、智等多要素融合的一体化服务, 具有如下典型特征:
1) 一体化: 分布异构计算资源、通信资源通过网络连接, 提供算、网、数、智、安、边、端、链等多要素融合的多层次叠加一体化服务供给;
2) 高效化: 社会算力融合的可信算网服务统一交易和运营平台, 统一纳管社会闲散算力和泛终端设备, 实现算力的跨层高效调度;
3) 便捷化: 基于“任务式”量纲的数智服务融合供给新服务模式, 实现对算力和网络等服务的随需使用和一键式获取.
算力网络的核心科学问题是需求−资源调度, 需求层和服务层关注的优化目标不同, 前者关注用户满意度最大化, 后者以提高资源利用率为目标. 相关调度问题十分复杂, 主要挑战包括[1−2, 8−9]:
1) 广分布异构性导致可行解空间巨大(大, 难快). 算力网络包括计算资源和通信资源两大类, 计算资源主要有物理服务器、PC机、虚拟机、容器、无服务器函数、智能终端(智能手机、平板)等; 通信资源主要有路由器、交换机、基站、带宽等. 两大类资源地理上分布、结构上异构严重阻碍算网服务统一交易和运营的实现, 即实现算力网络的便捷化和高效化极具挑战.
2) 强不确定性导致可行解空间易变(变, 难稳). 主要体现在需求和资源层面, 需求层包括任务到达、计算时间、传输路径改变等; 资源层面包括计算资源进入/退出、计算资源故障、传输链路故障等. 不确定性主要分为随机(概率度量)、模糊(隶属度度量)、不完整等三类, 不确定性使得实现算力网络一体化和高效化非常困难, 特别是任务−资源匹配(任务调度或资源调度)问题的建模、优化、求解极其困难.
3) 高约束复杂性导致可行解孤岛繁多(散, 难解). 算力网络中存在许多约束, 分别可能属于任务、任务−任务、任务−资源或资源. 任务约束包括隐私、截止时间、学习/退化效应、处理时间、到达模式、准备时间和安全性等; 任务−任务约束主要包括偏序关系、亲和性、衔接时间等; 任务−资源约束主要包括运输成本、传输时间、优先级、隐私性、特殊性等; 资源约束主要有容量、可用性、位置、安全性等. 复杂约束是实现算力网络高效化的瓶颈.
4) 多目标性导致冲突目标权衡优化难(异, 难优)[10−12]. 尽管大多数调度问题仅考虑一个目标(单目标), 但算力网络中通常需同时优化两个或三个目标(多目标), 甚至四个或更多目标(超多目标). 常见目标包括完成时间(如最大完成时间、总完成时间或总流转时间、总加权完成时间、平均加权完成时间)、延误时间、延迟(如最大延迟、总延迟、加权总延迟)、响应时间(如最大响应时间、总响应时间、加权总响应时间)、等待时间(如最大等待时间、总等待时间、加权总等待时间)和延迟任务数(如延迟任务总数、加权延迟任务总数)、服务成本(服务付款)、租赁成本、通信成本、存储成本、资源闲置率、吞吐量、能耗、用户满意度等, 多目标或超多目标是这些目标的组合, 不同目标可能不一致甚至矛盾, 多目标性给算力网络高效化的实现带来巨大挑战.
新一代算力网络和传统云边端计算都是提供分布式计算资源, 二者紧密联系和区别, 并且有各自的优缺点和适用性. 传统云边端计算将数据处理任务从云中心迁移到网络边缘, 减少数据传输延迟, 提高系统效率和响应速度(如图2所示). 新一代算力网络包含算网运营、算网大脑、算网底座等层次, 其中算网底座以传统云边端为主要计算资源. 二者都涉及到计算资源的管理与利用, 新一代算力网络的计算资源进入与退出相对柔性, 即计算资源更具动态性、分散性、易用性; 云边端的计算资源进出相对固定, 即计算资源更具静态性、聚集性、专业性. 新一代算力网络关注“算”“网”融合, 而云边端计算更关注“算”. 二者的优缺点对比如表1所示.
表 1 算力网络与云边端计算比较Table 1 Comparison between computing power network and cloud-edge-terminal computing云边端计算 算力网络 优点 大规模计算资源, 大规模存储设施, 计算能力强, 可扩展
计算资源静态、聚集、专业, 技术相对成熟网、云、数、智、安、边、端、链深度融合, 计算性能好, 可扩展计算资源动态、分散、易用, 去中心化, 延迟低, 适合实时任务, 安全性和隐私性强 缺点 延迟较高, 不适合实时性高的任务, 安全性与隐私性差 技术不成熟 适用性 计算密集型、存储密集型任务 分布式一体化算网服务 2. 算力网络体系架构
以算为中心、网为根基的算力网络是算力需方(分布式用户)和算力供方(分布式计算和通信资源)的接口, 是提供计算服务的服务管理系统: 1)方便用户, 为用户提供智能、极简、无感的“一点接入、即取即用”算网便捷式服务; 2)通过多云管理器对云、边等分布式算力进行统一纳管、跨层调度, 实现算力网络资源的最优化高效利用. 整个算力网络体系架构分为3层: 用户层、算力网络管理层、资源层, 如图3所示.
图 3 智慧调度为核心的算力网络体系架构Fig. 3 Computing power network system architecture centered on intelligent scheduling2.1 用户层
分析不同用户请求特性是有效管理计算服务的前提, 用户请求主要包括如下类型[13−15]:
● 随机请求[14, 16−25]: 用户提交的实时性请求, 通常请求任务计算量比较小、实时性要求较高, 尽可能在本地执行; 也可能是较大的任务, 甚至是相对独立的工作流任务.
● 批计算请求[26−30]: 用户提交一批具有相似业务流程的计算请求, 请求任务间通常没有约束关系, 成批请求任务通常具有相同的截止期约束.
● 流计算请求[31−33]: 对具有时效性的数据计算, 依赖上游数据传输的正确性和实时性、下游存储系统的高吞吐能力, 多媒体、视频、音频、游戏等是典型的流计算任务.
● 工作流计算请求[34−40]: 业务过程的所有任务按照一定的触发顺序和触发条件组织起来, 任务间具有偏序约束关系, 每个任务可由一个或多个计算资源完成.
2.2 算力网络管理层
算力网络管理层包括面向用户层请求的业务管理层、以需求−资源匹配为核心的业务调度层和面向资源的资源管理层, 其核心分别为做什么(What to do)、如何做(How to do)和谁来做(Who to do). 算力服务为每个用户请求提供具有不同成本的算力资源, 如何用最少的资源获得最大的用户满意度是核心问题. 假设需求任务集为$ D = \{d_1,\;d_2,\;\cdots , d_n\} $, 服务资源集为$ R = \{r_1,\;r_2,\;\cdots ,\;r_m\} $, 需求−资源匹配就是要寻求最佳的二元组集合$ \{(d_{i},\; r_{j})|\forall i = 1,\;\cdots ,\;n;\; j = 1,\;\cdots ,\;m\} $, 即, 为每个任务分派合适资源, 使得用户满意度最大化[41−43]、服务资源利用率最大化[44−46].
2.2.1 业务管理层
为得到最佳供需匹配集合$ \{(d_{i},\; r_{j})|\forall i = 1,\;\cdots , n;\; j = 1,\;\cdots ,\;m\} $, 首先需要对用户需求建模. 业务管理层主要确定任务信息与任务间的关系, 即需求模型的结构化描述和需求信息参数确定. 随机、批计算、流计算、工作流等不同类型需求结构不同; 需求信息参数包括任务功能、处理时间、资源类型、资源需要量等.
1) 结构化需求模型: 无论用户需求属于何种类型, 都可以刻画为最小粒度任务集合以及这些任务间的关系组成. 任务间主要有如图4(a) ~ 4(c)所示的三种基本关系:
● 独立任务: 任务与任务之间没有任何约束关系, 如不同用户所提交的随机请求通常没有任何约束关系, 这些任务形成独立任务集合.
● 线性约束: 除首尾任务外, 每个任务有且仅有一个直接前驱和一个直接后继. 机器调度领域中的流水作业调度(Flow shop)、车间作业调度(Job shop)、开放作业调度(Open shop)等度问题是典型的线性约束关系.
● 非线性约束: 所有任务的直接前驱和直接后继数不一定唯一, 可能有0个(起点任务没有直接前驱、终点任务没有直接后继)、1个或者多个, 该类应用通常用有向无环图(Directed acyclic graph, DAG)描述, 工作流模型、项目调度模型等都是典型的非线性约束.
随机、批计算、流计算、工作流等不同类型需求通常非常复杂, 可以建模为上述基本结构的组合, 如图4(d) 所示.
2) 需求信息参数: 任务属性是需求−资源匹配的前提, 主要参数包括:
● 任务到达: 到达方式(随机、固定周期)、到达分布(泊松、随机、均匀、正态)等;
● 任务执行参数: 由什么类型资源执行、需多长时间、需多少资源、执行成本(如租赁成本)是多少等;
● 约束条件: 截止时间、预算等.
上述参数部分可由用户完全确定, 如截止时间、预算、执行资源类型、需要资源等, 其他参数不能完全由用户给定, 如到达方式、达到分布等参数有时可由用户给定, 有时只能通过人工智能等技术(如深度学习)挖掘历史大数据的统计规律和知识, 预测相应任务属性参数. 需求信息参数的确定对应图5所示调度周期中的计划阶段.
2.2.2 业务调度层
业务调度是算力网络系统的核心, 图5给出了包括计划、调度、执行的三阶段闭环调度模式.
1) 调度阶段: 理论上算力网络拥有无限的算力资源, 但某时刻实际可用资源量是有限的, 调度器需要确定可以接收多少任务、接收哪些任务、拒绝哪些任务, 所接受的任务按照什么顺序分配资源、什么时候分配哪些资源等, 即包括选择/卸载、任务排序和任务调度等基本功能.
● 选择/卸载: 根据任务的偏序关系和紧急程度确定任务的优先处理顺序, 从到达系统的所有任务中筛选可执行任务, 包括选择多少任务、选择哪些任务; 或者将部分任务卸载到其他资源. 算力网络中任务卸载需考虑传输代价. 选择/卸载问题是一个典型的优化问题, 通常可通过设置决策变量, 建立相应的优化模型; 这也可以等价地转化为根据可用资源量, 通过马尔科夫决策过程分析任务的拒绝率.
● 任务排序: 为所选任务分配资源时需考虑先后顺序, 即哪些任务先分配、哪些任务后分配资源. 独立任务可以基于所定义的优先级计算模型对任务排序; 线性约束任务按照约束关系和可用资源状况确定任务顺序; 非线性约束任务通常采用拓扑排序策略生成任务顺序, 同一个非线性任务图所包含的拓扑顺序通常很多, 难以确定哪个顺序能得到最优目标函数值.
● 任务调度: 给排好序的候选任务指定服务资源、资源量、开完工时间等. 由于最小化问题和最大化问题可以等价转化, 其通用模型可描述如下
$$ \begin{split} &{\mathrm{min}} F(\bar{x}) = (f_{1}(\bar{x}),\;\cdots ,\;f_{p}(\bar{x}))^{{\rm{T}}}\; \\ & \text{s.t. }\\ & g_{i}(\bar{x}) < 0\; (i = 1,\;\cdots ,\;k)\\ & h_{i}(\bar{x}) = 0\; (i = k+1,\;\cdots ,\;m) \end{split} $$ (1) 其中, $ F(\bar{x}) $为目标函数向量, 即需要优化的$ p $个目标, $ p = 1 $时为单目标优化问题, 优化目标通常包括任务最大完工时间最短、用户租赁成本最小、云服务商利润最大、资源利用率最大、服务能耗最小、用户满意度最高等; $ g_{i}(\bar{x})< 0\; (i = 1,\;\cdots ,\;k) $和$ h_{i}(\bar{x}) = 0\; (i = k+1,\;\cdots ,\;m) $是约束条件, 通常约束条件来源于需求方和资源方, 如需求截止期、任务间偏序约束关系、响应时间、需求预算等为需求约束, 资源租赁方式(预留、按需、竞价)、公有云/私有云/混合云等为资源约束; $ \bar{x}\in {\bf{R}}^{n} $为决策变量.
2) 执行阶段: 任务调度执行过程由于大量强不确定因素使得相应的调度结果需频繁调整, 主要原因包括随机因素(如数据准备不充分、用户需求变更、执行资源变更、突发资源故障等)、模糊因素(如任务执行时间、计算资源启动时间等预估不准)、信息不完整因素(如需求信息不完整、业务流程不完整或信息缺失等). 上述因素将导致原调度结果需要调整开完工时间和所分配的资源. 其核心问题包括调节时机、调节范围等, 目前主要有两种调度调节方式: 预判式(Proactive) 和反应式(Reactive), 前者是规定多长时间主动调整一次, 可在一定程度上预防调度大范围失效; 后者是一旦出现变化就应急式调整, 其结果是大量不确定因素可能导致调节过于频繁.
目标函数和约束是算力网络业务调度的关键. 不同约束限定问题的边界, 划定可行解范围. 调度优化中的约束包括任务内、任务间(任务−任务)、任务与资源间(任务−资源)或资源内.
● 任务约束: 由用户需求给出的限制, 如数据隐私性、截止日期、学习/恶化影响、处理时间、到达模式、设置时间和安全性等. 例如, 尽管大多数调度问题都假定每个任务的处理时间是事先已知的, 但实际调度由于受信息的模糊性、随机性或不完全性等因素的影响, 调度时间难以事前确定, 特别是算力网络场景下的用户需求.
● 任务−任务约束: 任务间有许多约束, 偏序关系是调度最常见的任务−任务约束, 除非其直接前驱已完成, 否则直接后继任务不能开始; 亲和约束(Affinity)表示某些任务比其他任务具有更密切的关系, 尽量将亲和任务分配给相同或最近的资源.
● 任务−资源约束: 任务映射到资源的调度过程中, 通常能完成各任务的资源为一个候选集, 但并不是所有的候选对象都符合任务要求, 任务与资源间存在许多约束, 例如任务需由特定的资源处理, 这些资源为任务选择资源时定义了优先级偏好.
● 资源约束: 资源约束指资源受到容量、可用性、位置甚至安全性的限制, 例如资源的周期性维护.
优化目标是用户和服务供应商都关注的核心. 通常大多数调度问题只考虑一个目标(或单目标), 有时同时考虑两个或三个目标(称为多目标), 实际应用中可能考虑四个或者更多目标(超多目标). 需要指出, 多个目标在优化过程中通常不一致(即一个目标最优但其他目标不是最优).
● 单目标: 优化目标包括用户或服务供应商所关注的目标, 通常包括时间类、价值类、资源类(能量、利用率等)和其他服务质量(Quality of service, QoS)类. 每类都可包含更多指标, 例如, 时间指标包括完成时间(Makespan或最大完成时间、总完成时间或总流动时间、总加权完成时间和贴现总加权完成时间等)、延迟(最大延迟、总延迟和总加权延迟等)、提前(最大提前、总提前和总加权提前等)、响应时间(最大响应时间、总响应时间和总加权响应时间等)、等待时间(最大等待时间、总等待时间和总加权等待时间等)和拖期数(拖期任务总数、加权拖期任务总数等).
● 多目标: 不同用户角色关注不同目标, 这些目标可能一致也可能不一致. 如降低数据中心的温度和减少碳排放是两个一致的目标, 即一个目标最佳意味着另一个目标也最佳, 多个一致性目标可作为单目标而不需要作为多目标进行优化; 时间和成本通常是不一致的目标, 减小一个目标总是导致另一个目标增大. 多目标优化问题考虑不一致目标(不是简单的反比关系). 如何在多目标间取得平衡或权衡是最大化不同角色满意度的核心. 多目标优化通常采用两种方法: 加权目标的和(将问题转移到单目标优化), 提供一组Pareto (帕累托)最优解集.
● 超多目标: 超多目标优化是具有四个或更多目标优化的问题, 随着非支配解和计算多样性测度的增加、重组效率的降低, 超多目标优化问题比多目标优化问题更加困难. 现有研究大多集中在超多目标连续优化问题, 算力网络调度是典型的离散优化问题, 相关超多目标调度值得深入研究.
2.2.3 资源管理层
算力网络的多模态资源包括容器、虚拟机、路由器、交换机等物理计算资源, 也包括单个无服务器函数时效的软件服务或者多个软件服务的组合、服务聚合等软件资源. 资源管理包括算力资源的风险分析, 如根据历史数据建立容器资源发生故障的风险模型、计算资源和通信资源的故障预测模型、故障发生频率、维修时长等; 发生故障后的故障特征、故障诊断等. 故障通常有两种处理方式: 故障恢复和任务迁移.
2.3 资源层
用户请求都要由资源实现, 即资源提供最终服务. 算力网络资源层是对云网融合的深化和新升级, 包含边端等更丰富形态、更立体泛在; 不仅体现为编排管理融合, 更强调算力和网络的形态与协议一体化融合; 网络运营管理从一站式向一体化、智慧化演进; 以算力为载体, 提供多要素融合的新型一体化服务.
算力网络以传和算为纽带, 计算资源和通信资源为核心, 计算资源的主要功能是存储和计算.
● 存储资源: 计算类资源通常指物理机的集合, 每个物理机由一个或多个处理器、内存、网络接口和本地I/O组成, 分析、传输和存储从自动化系统收集的数据. 需存储的数据通常被调度到存储资源, 如根据不同级别的数据一致性和可靠性将不同类型数据进行不同存储服务(虚拟磁盘、数据库服务、对象存储)调度, Robinson等[47]对此进行了综述.
● 计算资源: 从服务器或主机到云计算虚拟机、再到容器是计算资源发展的方向, 基于三层云计算资源IaaS、PaaS和SaaS[48−50]的虚拟机资源调度是近年的热点之一[51], 其中SaaS资源调度通常基于多租户体系结构[52]; 容器为执行微服务任务提供轻量级环境, 由于容器是独立、自包含单元, 用户能够以Docker[49, 53−56]或Kubernetes[57]映像(而不是虚拟机实例)的形式处理定制执行环境. Pahl等[58]对云计算中容器及其编排等现有研究进行区别、分类和系统比较. 为克服集中式云环境的缺陷, 可用边缘计算平台将进程推送到边缘设备[59]. 最近, 无服务器函数[56, 60−61]是研究热点, 为任务提供的服务其执行过程可由一个底层函数执行, 服务供应商按照用户实际的使用时间决定费用收取, 保证资源高效利用.
● 通信资源: 包括路由器、交换机等, 通信资源连接数据中心内不同物理机, 网络拓扑结构对网络性能和容错能力有很大影响, 经典的拓扑结构有胖树、超立方体或随机小世界拓扑等.
3. 智慧调度
算力网络中计算任务主要包括在线任务、批处理任务、流计算任务、工作流任务等, 具有规模大、约束繁杂、不确定性强、优化目标多等特征; 计算任务调度通常十分复杂, 可能会涉及跨地域的多阶段分布协同调度, 其各阶段的优化目标、约束条件可能不同但可能相关. 直观上, 解决复杂调度问题的手段主要有三种: 设计新算法, 简化复杂问题, 增加计算能力. 但对于上述复杂分布式调度, 仅靠其中任何一个都很难有效解决. 结合三种手段, 采用“算法+知识+数据+算力”的智慧调度框架(如图6所示)是快速、高效、鲁棒解决这类复杂调度问题的有效途径, 其核心元素包括:
1) 算法: 现有调度算法鲜有能直接适用于算力网络的复杂调度, 可采用复杂问题简单化的策略将原问题近似分解为多个相对简单的问题, 如果仍没有求解策略, 可递归继续分解直到所有子问题都有求解策略. 新问题的求解可秉承“持经达变”的思想, 从相似问题的调度算法中挖掘规则或知识, 应用于新调度问题. 通过分解法简化原问题, 运用调度知识简化求解过程, 以实现快速、高效、鲁棒的智能调度.
2) 数据: 构建数据库存放算力网络应用系统涉及的大量需求数据、服务资源数据, 系统运行过程中所产生的数据存储于相应数据库, 数据的不完整、不完备性通过数据清洗、治理、补充等手段消除.
3) 知识: 复杂问题简单化的核心策略是分解, 依据被服务单元(通常为任务)、资源服务单元(如虚拟机、容器、路由、无服务器函数)、任务−资源匹配规则(算法知识)等获取固定搭配模式知识, 基于模式的分解是智能调度的前提; 如何发现需求模式(调度任务间的固定搭配关系, 即需求知识)和服务模式(资源或服务间的固定搭配关系, 即服务知识)是关键.
4) 算力: 通过分解或降维可降低问题规模, 但简化后问题通常仍然非常复杂, 算法计算时间仍可能很长, 如何借助于云计算、边缘计算、移动计算或雾计算来提高计算速度、减少计算时间至关重要; 算力网络中计算和通信开销的平衡优化是算力分配的主要优化目标, 特别是“东数西算”场景下是否传输数据需要谨慎决策.
基于智慧调度框架, 设计具体算力网络调度策略需明确问题的可行解空间、调度策略关键参数、调度算法性能和效率、调度算法类型等.
3.1 可行解空间
为简单起见, 先不考虑用户需求的结构关系, 即假设需求任务相互独立, 对于具有偏序关系约束的用户需求, 可采用拓扑排序将需求分解为可并行执行的任务集(此时这些任务是相互独立的); 同理, 假设服务资源也相互独立. 任务集$ D = \{d_1,\;d_2, \; \cdots , d_n\} $调度到服务资源集 $ R = \{r_1,\;r_2,\;\cdots ,\;r_m\} $的映射关系是笛卡尔积$ \Omega = D\times R = \{(d_i,\;r_j )|\forall d_i\in D, r_j\in R\} $. 实际需求任务可能受到相应数据的隐私性、安全性、任务截止期、任务处理时间等约束, 服务资源可能受到可用时间、可用量、启动时间、维护等约束, 可行解集$ \Omega' $是$ \Omega $的子集, 即$ \Omega'\subset \Omega $. 一个可行调度实际上就是所有任务$ \forall d_i \in D $及与之可匹配的所有服务资源所构成的二元组集合$ \Omega'' $, 显然$ \Omega'' $是$ \Omega' $的子集, 即$ \Omega''\subset \Omega' $. 由于恰好每个需求任务都有一个服务资源对应, 所以每个可行调度满足$ |\Omega''| = n $; 所有可行调度的集合$ \Phi\subset 2^{\Omega'} $且$ \Omega''\in \Phi $. 因此, 算力网络中$ k $-目标调度本质上就是寻找函数$ F:\Phi\rightarrow (O_1,\;\cdots ,\; O_k) $的最优值, 由于最小和最大化问题可以等价转化, 该优化问题可以表述为$ \max(O_1,\;\cdots , O_k) = F(\Omega'') $, $ \Omega''\in \Phi $ ($ O_i $为第$ i $个目标函数). 相应的逻辑关系如图7所示.
3.2 调度策略关键参数
上述算力网络调度优化模型表明其为离散空间寻优问题, 不能采用连续空间的求导求极值寻优策略; 解空间结构也难以确定, 不能采用演绎法进行递归求解; 解的分布未知, 不能通过统计方式预测最优解分布的概率. 实际上可行解空间$ \Omega' $可能由一些孤岛组成, 每个孤岛包含离散的可行解, 相应的调度优化就是从这些孤岛中寻找最优解. 由于最优解在何处难以预测, 离散空间寻优过程也没有规律可循, 非规律离散性解分布不宜采用演绎法, 只能采用归纳式搜索策略. 类似于智能优化策略, 寻优搜索过程需要确定如下关键参数:
1) 搜索方向: 如何更新搜索方向, 类似于随机游走过程中如何更新粒子运动方向;
2) 搜索步长: 确定每步搜索的步长, 类似于模拟退火算法中的降温策略或者粒子群算法中的粒子速度更新策略;
3) 搜索范围: 明确搜索范围大小, 类似于智能算法中的种群规模、邻域结构等;
4) 搜索形状: 划定搜索区域, 类似于智能算法中邻域结构的插入、对换等算子;
5) 停止准则: 搜索多少次或多长时间算法停止, 类似于智能算法中迭代次数等结束条件.
3.3 调度算法性能和效率
依据算力网络智能调度框架, 考虑问题的可行解空间和搜索策略的关键参数, 算力网络调度算法设计需考虑两个基本指标: 计算时间$ t $ (效率)和求解质量$ Q $ (性能). 由于算力网络调度算法$ A $的核心是搜索, $ t $与$ Q $之间有一定关联关系: 算法本质上是解决问题的操作步骤或序列, 可将$ A $看作一个函数或者黑盒, 将一个实例$ I $作为输入, $ A $在给定的时间$ t $内求得相应的结果(算力调度算法产生的是调度时间表), 该输出结果需进一步评价获得相应的质量$ Q $ (该关系如图8所示), 即
$$ \begin{equation} Q\propto A(I,\;t) \end{equation} $$ (2) 
图 8 调度算法时间与质量关系Fig. 8 The relationship between time and quality of scheduling algorithm由式 (2)可以看出:
1) 相同实例$ I $和计算时间$ t $: 调度算法求解质量$ Q $依赖于所设计的算法$ A $, 即, 对于同样的调度问题实例和停止准则, 不同算法的搜索方向、搜索步长、搜索范围、搜索形状等不同, 所得到的求解质量不同.
2) 相同算法$ A $和实例$ I $: 调度算法求解质量$ Q $依赖于计算时间$ t $, $ t $越长, 搜索的范围越大, 获取更优解的可能性越大, 求解质量$ Q $通常也越高(如元启发式算法GA[62]、PSO[63]等); 反之, $ t $越短, 搜索的范围越小, 获取更优解的可能性越小, 求解质量Q通常也越低(如规则或启发式算法); 不同应用需要的响应时间不同(要求$ t $不同), 实时应用要求响应时间快, 而非实时任务(如科学计算)则不然.
3) 相同算法$ A $和计算时间$ t $: 调度算法求解质量$ Q $依赖于实例$ I $的特征, 不同特征实例的有效算法也不同, 正所谓“千人千面”, 需“对症下药”, 即某个调度算法通常只针对某个调度类有效; 不同调度实例的调度结果质量通常也会有差异. 因此, $ Q $通常指统计意义上的质量评价, 即常采用方差分析等方法评价解的质量.
调度算法$ A $作为黑盒函数, 其结构可简单可复杂, 可单次搜索也可多次搜索. 单次搜索侧重于问题本身的静态属性或者隐含关系, 通常指根据知识一次性求解实例$ I $的规则, 即给定输入能快速得到输出, 包括经验规则和学习规则; 多次搜索侧重于动态的寻优操作, 即朝着优化的方向不断改善调度时间表(求变), 基于操作算子组合(算法每个步骤如何操作、所有步骤按照什么顺序操作)进行多次迭代优化, 可分为启发式算法[64−68]和元启发式算法[69]. 特别说明: 算法复杂性取决于算法步骤, 不同调度算法的顺序、分支、循环等结构差异很大, 特别是迭代搜索的循环停止准则直接影响算法复杂度, 不同场景的停止准则设置通常差别很大, 导致相应的复杂度难以确定, 即通常难以给出整个调度算法复杂度, 但算法局部复杂度可分析得出.
3.4 调度算法类型
尽管人工智能技术在很多领域展开了广泛应用, 但任务−资源匹配的NP (Non-deterministic polynomial) 完全问题属性使得深度学习等技术难以应用于调度优化中. 与经典调度算法类似, 算力网络调度算法可分为基于经验的调度规则、基于学习知识的调度规则和启发调度算法.
3.4.1 经验调度规则
通常经验调度规则基于优先级, 其关键在于如何定义优先级函数. 调度规则的优点是求解速度快、效率高, 但性能不一定好. 调度优先级指任务被调度的先后顺序, 直接取决于任务、资源、约束条件等属性(目标函数是求解的最终目标, 通常不能用于定义优先级函数). 根据优先级函数依赖的属性在调度过程中是否变化, 优先级可分为静态优先级和动态优先级.
● 基于任务属性的优先级函数: 常见的任务属性包括任务的到达时间(如先来先服务FIFS规则[70])、处理时间(如短作业优先SPT[71−73])、用户优先权(如重要用户优先[74−76])等. 处理时间和用户优先权可能随着时间的推移而变化, 即基于二者优先级既可能是静态的也可能是动态的.
● 基于资源属性的优先级函数: 常见资源包括人、财、物、信息等类型, 资源属性包括单位运行成本(如关键设备优先[77])、租赁成本(如按需租赁[78−80]、预留租赁[81]、竞标租赁[82])、可满足性(如专业人员的技能水平[83])、学习效应[84]、退化效应[85]、时间槽(轮转法[86])、亲和性[87]、数据隐私性[88−90]、数据安全性[91−95]等.
● 基于约束条件的优先级函数: 调度中的约束有很多类型, 常见的有截止期(如最早截止期优先EDF[82])、任务间偏序关系(通常采用拓扑排序[64, 96−97]).
3.4.2 学习调度规则
学习调度规则是基于黑盒函数的规则, 黑盒函数是给定结构的学习函数(如神经网络), 但函数变量(神经网络中的节点和边)的权重未知, 需通过样本(训练集和测试集)学习获得. 通过已知输入输出的训练集反复调节函数中变量的权值, 建立隐含样本实例的特征关系, 即确定输入(样本实例)与输出(标签)间的函数关系. 该函数关系通过输入输出已知的测试集进行验证, 如果超出误差范围, 则需返回训练过程重新确定权值, 直到训练集和测试集的所有样本的实际输出与标签的差值都在预先给定的阈值范围内为止.
基于神经网络的深度学习难以应用于调度问题, 更不用说算力网络智慧调度这样复杂的问题, 原因如下:
1) 算力网络智慧调度的NP完全属性表明训练集和测试集样本标签只能是近似最优解, 如果能在多项式复杂度内给出随机样本的最优解作为标签, 则该调度问题为P (Polynomial)问题, 与其NP完全性质矛盾;
2) 训练集和测试集的典型性难以保证, 即训练样本和测试样本是否与总体服从同样分布难以准确度量, 依据二者学习出来的权值通用性难以保证;
3) 问题的复杂性表明相应的深度学习模型结构复杂, 学习所用的训练集需要具有所求解调度问题的典型特征, 学习时间长, 不适用于实时性要求较高的应用场景[98].
尽管如此, 统计学习或基于神经网络的机器学习(如深度学习)可用于获取调度问题的某些属性, 例如需求任务的结构(线性或者非线性)特征[99]. 强化学习可应用于与环境交互的实时任务动态调度[44, 100−102]. 总体来看, 学习调度规则尚处于初级阶段.
3.4.3 启发式/元启发式调度算法
启发式算法heuristic (来源于希腊语, 原意为“to find”)通过某种局部寻优策略(通常与优化目标直接相关)生成解, 按照生成解的不同策略主要分为构造型启发式算法(Constructive heuristic)和复合型启发式算法(Composite heuristic)两类. 构造型启发式算法类似于搭积木, 逐个增加解的组成元素直到形成完整解; 复合型启发式算法基于迭代优化的思想, 即, 将一个构造的初始解作为起点, 通过一定的邻域结构生成新邻域解集, 从中选择一个解作为下次迭代的起点, 重复该过程直到满足停止准则.
元启发式算法Meta-heuristic (Meta意为beyond, 即超越、更高之意)是更高抽象层次、独立于问题的通用算法框架(即将一组相似启发式算法所具有的相同结构抽象为一个元启发式算法框架)[103−105]. 从面向对象的角度可将元启发式算法框架看作类, 而求解某个具体问题时, 确定算子和参数的具体元启发式算法可看作该类的一个对象. 元启发式算法有很多种分类方法, 例如轨迹型(Trajectory-based)和种群式(Population-based). 应用于调度优化问题的启发式、元启发式调度算法分类如表2所示.
表 2 启发式和元启发式调度算法类型Table 2 Types of heuristic scheduling algorithm and meta-heuristic scheduling algorithm启发式调度算法构造或复合生成时间表.
● 构造型启发式调度算法: 先按照某种策略选择一个调度任务, 产生只有一个任务的调度时间表(部分解); 然后按照所给定策略增加一个任务, 与已有调度时间表(部分解)结合, 将新增任务放在当前最合适的位置(但这种局部最优并不能保证全局最优); 再按照同样方法依次增加剩余任务, 最后形成包含所有任务的调度时间表. 如求解flowshop调度makespan最小化的NEH算法[107, 114]就是典型的构造型启发式调度算法.
● 复合型启发式调度算法: 采用局部迭代搜索的思想, 从一个初始解(调度时间表, 可以采用随机调度规则或者构造型启发式调度等算法生成)出发, 通过一定的邻域结构生成新邻域解集; 重复该过程直到满足停止准则(如达到给定计算时间$ t $). 如求解flowshop调度makespan最小化算法就是典型的复合型启发式调度算法.
定义 2. 邻域结构: 函数$ {\cal{N}}:\Phi\rightarrow 2^{\Phi} $, 给任意$ s\in \Phi $指定一个邻域集$ {\cal{N}}(s)\subseteq \Phi $生成解$ s $的邻域解集$ {\cal{N}}(s) $, 选择其中一个解作为邻域结构作用的新起点.
元启发式调度算法有多种分类方式, 典型分为轨迹式和种群式两大类.
● 轨迹式元启发算法: 每次搜索产生一个解, 解空间中多个单点(解)按次序连接起来的轨迹形成一条解路径, 所求得的近似最优解是该路径中的某点. 搜索过程的动力学特征由问题实例、问题表达和算法决定. 问题表达与邻域结构定义搜索范围(每次搜索范围多大), 算法描述用于探索该搜索范围的策略(如何搜), 问题实例定义实际搜索空间特性(整个搜索空间如何构成). 根据轨迹形成策略可分成简单轨迹式元启发法和复杂轨迹式元启发法. 简单轨迹式元启发法通过迭代提高, 可以看出, 简单轨迹式元启发法可看作复合型启发式算法框架(算法类). 简单轨迹式元启发法的三个核心步骤由多个算法的复合替代形成复杂轨迹式元启发法, 由式 (2)可知需更长的搜索时间; 典型的复杂轨迹式元启发法有模拟退火算法[110, 115-116]、禁忌搜索算法[117]、自适应搜索算法[118]、GLS算法[119]、VNS算法[120]、ILS算法[111]等.
● 种群式元启发算法: 与轨迹式元启发算法每代只处理一个解不同, 种群式元启发算法每代处理一个解集(种群), 更符合搜索空间的内在并行探索特性. 每代搜索过程中平衡种群的多样性(Diversification)与聚集性(Intensification)是关键. 多样性保证种群的差异化, 有利于获得全局最优解, 但如果多样性过强, 则退化为随机搜索; 聚集性保证搜索的范围尽可能集中, 有利于获取局部最优解, 但如果聚集性太强, 则算法可能早熟. 因此, 如何保证每代中多样性与聚集性的动态平衡是种群式元启发算法尚需突破的核心问题(包括如何度量多样性和聚集性、如何度量平衡). 目前解决复杂服务调度的种群式元启发算法主要有进化算法[121]、ACO算法[122]、PSO算法[113]、禁忌搜索算法[123]、EDA算法[124]等.
3.5 算力网络调度研究进展
算力网络尚处于初级阶段, 相关调度算法研究还不多, 目前相关论文的发表时间和类型如表3所示, 主要集中在资源负载均衡、资源动态分配、数据传播路由选择、调度任务分类、安全可靠通信等方面. 为应对算力网络中系统动态变化和连续变化带来的强不确定性, Xie等[125]提出基于双延迟深层确定性策略梯度的DRL算法, 基于算力网络集成框架, 充分利用边缘层计算资源, 保证系统负载平衡的同时降低任务总处理延迟. Lei等[126]提出基于IP扩展的计算网络互联体系结构, 通过网络编排为用户启动的应用程序动态分配计算资源和对应的网络连接方式. 基于算力节点的潮汐特性, 将节点分为潮汐算力节点和非潮汐算力节点. He等[127]考虑通信场景的计算资源调度问题, 将其建模为一个混合整形问题并分解为数个子问题, 证明应用数字二维通信能够进一步提高蜂窝网络计算的潜力. Pang等[128]提出具有加权唤醒路由惩罚的选播路由算法, 利用路由降低算力网络的能耗. 基于算力网络的可编程服务系统, Zhang等[129]提出基于“段标识符即服务”的可编程服务系统, 通过网络控制层网络节点和链路的权重计算路由, 以指导数据包的转发, 提升了可编程网络的灵活性. Yao等[130]提出一个计算感知路由协议, 将计算信息作为代价引入网络, 提供沿着网络路径向最优服务端点联合调度服务请求的能力, 解决计算与网络间的相互感知、协调和调度问题. 针对算力网络下的数据下载问题, Liu等[131]提出边缘数据中心放置−内容放置算法, 采取边缘数据中心与内容联和放置的策略, 结合网络资源和计算资源, 分别基于Kuhn-Munkres算法和K-Means算法指定边缘数据中心放置算法和内容放置算法. Wang等[5]提出面向人工智能的算力网络框架, 针对人工智能算法的计算需求, 其调度优化层将根据任务计算需求、网络需求进行分类, 通过强化学习、凸优化等设计任务调度算法. 针对时延密集型任务的需求, Liu等[132]提出基于交叉熵的任务调度模型, 将更多的边缘设备参与到算力网络中以降低传输时延, 基于多层算力网络提出一种分布式调度算法, 实现边端系统的最优性能. Zhang等[133]考虑三层分布式多访问边缘计算网络中具有多数据中心多接入的变换计算场景, 数据中心归属不同运营商且存在竞争, 提出一种基于强化学习的分布式任务调度方法. 为控制平面感知数据平面的服务和计算资源, Zou等[134]提出基于信息中心网络的算力网络架构, 采用数据平面中的转发节点命名用户发送的任务, 通过强化学习算法将其调度到适当的计算节点执行计算服务. Zhao等[135]构造的算力网络联邦学习平台, 考虑信息安全的相关内容在调度时需通过受信任的连接进行通信, 以确保通信各方不被伪造、交互数据也受到保护, 讨论基础设施的加密方式, 保证联邦通信方之间的连接可信.
表 3 算力网络调度算法发表情况分析Table 3 Analysis of the publication situation of computing power network scheduling algorithms2018 年 2019 年 2020 年 2021 年 2022 年 期刊论文数量 0 1 1 2 0 会议论文数量 1 0 0 2 5 3.6 算力网络调度算法的发展方向
算力网络的出现、演进和推进分为三个阶段: 泛在协同, 融合统一, 一体内生. 在资源、编排、运营、服务四个维度都有相应的特点, 如表4所示. 算力网络三个发展阶段的调度算法研究核心也呈现出“协同→智能→智慧”的发展趋势.
表 4 算力网络三个演化阶段的四个维度特点Table 4 Four-dimensional characteristics of three evolutionary stages of computing power network资源 编排 运营 服务 泛在协同 网随算动 协同编排 协同运营 一站服务 融合统一 算网融合 智能编排 统一运营 融合服务 一体内生 算网一体 智慧内生 模式创新 一体服务 1)泛在协同阶段: 算力多样泛在, 算力呈现出内核多样化、分布泛在化的趋势, 算力逐渐向边缘侧和端侧延伸, 边缘算力逐渐丰富, 算力整体呈现云边端三级架构, 具备云算力超集中、边端算力超分布的特征. 云计算、边缘计算、智能终端等多级超集中、超分布算力的协同调度, 综合了现有云计算调度、边缘计算调度的特征, 大大增加了相应调度问题的复杂性. 基于算力网络所吸纳的全社会云边端多级算力资源泛在调度, 综合考虑网络的实时状态、用户的移动位置、数据流动要素, 需研究算力网络统一管理、跨层调配和应用的敏捷部署、动态调整; 同时网络基础设施的灵活调度将聚焦业务全颗粒、低时延、高效率调度. 协同调度是该阶段分布多级资源分配的核心.
2)融合统一阶段: 泛在算力通过网络连接并协同扩展, 通过物理空间融通、逻辑空间融通、异构空间融通实现算力与网络的深度融合, 突破单点算力性能极限, 充分发挥集群优势并提升规模算力效能, 让数据更易流动, 用户更便捷使用. 基于对网络、计算、存储等多维资源服务的状态感知, 引入云原生、无服务器函数、异构计算、算力卸载等技术, 算力路由通告所感知的算力, 通过“算力+网络”的多因子智能计算, 动态生成按需业务的调度策略, 将应用请求沿最优路径调度至算力节点, 最大化算力和网络资源利用率、业务对算力需求的满意程度, 智能调度是该阶段算网资源全局智能融合调度的核心.
3)一体内生阶段: 改变算网服务“云+网”服务的简单组合, 通过算、网、数、智等多原子的灵活组合, 实现算网多要素深度融合、灵活组合的跨层次、多形态极简一体化服务, 服务模式也逐渐从“资源式”向“任务式”转变, 旨在为用户提供智能、极简、无感服务. 一体内生服务包含多层次叠加的多要素融合供给、基于区块链的可信社会算力融合供给、无感知算力和网络的“任务式”数字服务融合供给. 考虑智能分析、灵活编排形成的主动免疫、协同弹性内生安全约束, 研究满足网络行为可预期、端到端极度差异化的调度算法, 智慧调度是该阶段算网资源自免疫、高安全、对抗调度的核心.
4. 总结与展望
4.1 总结
以“连”和“算”为核心的算力网络是网、云、数、智、安、边、端、链等深度融合, 广泛分布的异构计算资源和通信资源使得算力网络调度可行解空间巨大, 需求和资源层面强不确定性导致可行解空间不定, 大量复杂约束性导致可行解孤岛繁多, 通常需同时考虑两个或三个目标(多目标), 甚至四个或更多(超多目标)的多目标性导致多个不一致目标的权衡难消解, 这些特征给相应的调度算法带来难快、难稳、难解、难优等挑战. 本文分析不同算力网络的国内外研究现状, 比较算力网络与传统云边端计算的联系和区别. 提出包含用户层、算力网络管理层、资源层的多层次算力网络体系框架; 面向算力业务需求量激增难以有效管理等挑战, 提出参数化、结构化业务管理模型. 将用户需求刻画为最小粒度任务集合以及这些任务间线性、非线性关系; 并参数化任务到达、任务执行、截止时间、预算等参数; 业务调度考虑算力供需地域不平衡, 面向计划、调度、执行等不同阶段优化问题, 采用以快优稳为终极目标的“算法+知识+数据+算力”的算力网络调度优化模型, 支持快速、高效、鲁棒调度; 资源管理针对算力供应融合共生度不高等问题, 建立算力网络管理机制. 从理论上分析可行的算力网络调度解空间和算法性能与计算时间的定性关系, 详细分析并综述了算力网络调度算法的进展与发展方向.
本文从算力网络的发展趋势分析出相应调度研究呈现的“协同→智能→智慧”发展趋势. 指出算力网络统一管理、跨层调配和应用的敏捷部署、动态调整等计算资源和网络基础设施的灵活调度将聚焦业务全颗粒、低时延、高效率通信资源的协同调度是泛在协同阶段的核心. 通过引入云原生、无服务器计算、异构计算、算力卸载和“算力+网络”的多因子智能计算, 提出动态生成按需业务调度策略, 实现应用请求沿最优路径调度至算力节点, 以最大化算力和网络资源利用率、业务对算力需求的满足程度, 智能调度是融合统一阶段的核心. 基于多层次叠加的多要素融合供给、基于区块链的可信社会算力融合供给及无感知算力和网络的“任务式”数字服务融合供给, 考虑智能分析、灵活编排形成的主动免疫、协同弹性内生安全约束, 提出满足网络行为可预期、端到端极度差异化的算网资源自免疫、高安全、对抗调度, 智慧调度是一体内生阶段的核心.
已有两篇关于算力网络的综述论文, 本文与已有研究的区别如表5所示.
表 5 算力网络综述对比Table 5 Comparison of computing power network surveies文献[136] 文献[137] 本文 角度 5G通信 5G通信; 移动互联网 算力调度 关注重点 边缘节点计算资源限制; 业务需求与网络解耦; 静态服务器与移动客户端限制 泛在计算资源协同; 用户网络服务体验 广分布异构性导致可行解空间巨大; 强不确定性导致可行解空间易变; 高约束复杂性导致可行解孤岛繁多; 多目标性导致冲突目标权衡优化难 主要内容 提出基于分布式系统的计算网络融合架构; 协同共享多个边缘节点计算资源; 实现大量请求的处理和负载均衡; 考虑网络条件和可用计算资源的边缘节点交互; 提供基于网络的负载均衡服务分配方法 提出基于IETF的算力网络基本架构; 阐述算力网络的工作机制; 介绍计算任务调度等关键技术 提出多层次的算力网络体系架构; 提出算力网络管理机制; 提出算力网络智慧调度框架; 分析算力网络智慧调度问题性质 创新点 提出基于分布式系统的计算网络融合架构 介绍算力网络的基本架构与工作流程 提出参数化结构化业务管理模型; 提出算力网络调度优化模型; 提出算力网络智慧调度体系架构 4.2 展望
算力网络三阶段四个维度发展途径(如表4所示)要求其具有坚实的技术创新, 算力网络提供了广阔的发展机遇和巨大的应用需求空间, 同时也带来重大挑战. 基于现有技术需求, 亟需解决的关键问题包括:
1) 业务管理器(算网运营层): 满足客户灵活、动态、多样业务需求, 突破用户需求意图感知、算力交易、多量纲、算力并网、算力封装等产业生态培育、算网服务创新、社会算力整合关键问题.
2) 业务调度器(算网大脑层): 深度AI、大数据, 研究各种资源融合一体化编排、算力结构和泛在调度, 探索算网自制、数字孪生意图网络等新方向. 以绿色低碳为总体目标, 重点研究处理器动态功耗调节、服务器液冷、数据中心节能等关键问题.
3) 资源管理器(算网底座层): 为持续增强算力能力并释放算力价值, 发展边缘计算、超边缘计算和端计算, 形成更加泛在的多维立体算力, 需探索算力原生、存算一体、云原生、无服务器计算、异构计算、算力卸载、网络结构优化、网络带宽扩展、数据绕转时延减少、安全可信计算、隐私计算、内生安全等关键问题.
4.2.1 理论层面
算力网络调度有大量的理论问题亟待突破, 主要包括:
1) 多元需求模式知识智能感知: 感知用户需求意图, 建立用户需求模型; 诊断用户需求模型完整性; 基于人在回路等技术, 建立基于最大似然函数的工作流缺失任务填充模型和方法; 分析用户需求批量到达特性, 建立分布式多元用户需求管理模型; 研究用户需求特征度量, 运用聚类算法归类用户需求; 基于深度学习、图神经网络等技术挖掘需求模型共性结构, 构建需求模式; 基于需求模式知识, 提出复杂用户需求的结构化分解方法.
2) 多约束算力网络智慧调度: 考虑跨域分布、结构复杂、嵌套耦合、弹性易变需求业务流程受多重不稳定不确定因素影响而频繁重构调整, 导致调度结果的执行极端不稳定, 研究合适的重构时机和范围; 研究基于频繁子图的超多目标业务调度模型和算法; 研究基于分层切片的业务活动内聚耦合度度量方法; 研究全流程业务的模块化弹性建模方法. 构建基于“算法+知识+数据+算力”智慧框架的多场景全业务流程多目标调度方法.
3) 多模态资源的一体化管控: 建立横向约束、纵向嵌套的多维资源知识图谱, 构建合理的资源分类体系、开放式资源模型; 研究服务持续配置及演化方法、高效服务监测机制及异常状态检测方法, 建立规模可伸缩、服务可扩展、运行可监测的云服务管理框架; 研究服务的自动注册与发现机制; 研究基于软件定义的服务协作模型、多平台异构服务通信机制; 研究跨界服务协同优化方法和多租户服务的智能管控.
4.2.2 方法技术层面
针对上述理论性难题, 需突破知识驱动的调度算法设计、需求−资源特征选择、分布式资源动态部署等技术.
1) 知识驱动的调度算法设计: 获取需求和资源模块化模式知识; 研究认知型服务的跨界智能汇聚; 研究基于双边需求资源整合的调度模式; 研究基于多维链路矩阵分解的多约束需求与资源匹配方法; 面向频繁服务和个性化服务分别建立静态关联和动态链接集成模型; 面向需求多元化、服务碎片化、资源多态化、系统管理分散化等问题, 设计知识驱动的快优稳智慧调度算法, 最大化用户满意度并最大化资源利用率.
2) 需求−资源特征选择: 分析算力网络用户需求的到达速率、资源处理速率, 基于截止期、成本等约束条件, 研究算力网络资源分配模式; 构建分布式算力网络排队模型. 结合粒计算和模糊粗糙集等理论, 探索模糊粗糙需求和资源特征选择的稳健粒计算模型与方法, 研究不确定性变量的统计特性和熵变规律, 揭示属性值含噪场景下的复杂特征关联变化规律及协同机理, 建立对抗噪声环境的稳健模糊粗糙特征选择方法.
3) 分布式资源动态部署: 面向分布异构算力网络计算和通信资源, 建立可兼容资源管理机制; 基于需求−资源映射历史大数据, 构建需求−资源映射时空模型、空闲资源时空分布规律; 依据用户需求规律, 预测空闲资源服务段需求量; 研究知识驱动的多层次资源优化配置与聚类; 构建资源动态部署模型和方法, 提升算力网络服务的智能化水平, 充分利用所获取的知识, 提高智慧调度效率.
5. 结束语
我国数字经济数智化转型的关键取决于用户、数据、算力的有效连接. “东数西算”等工程的正式启动及新技术、新业态、新场景和新模式的不断涌现, 迫切需求构建数据中心、云计算、大数据一体化的算力网络服务体系, 实现跨运营主体的算力资源统一编排调用: 供给侧通过整合内外部资源、盘活社会闲置算力, 优化全产业的算计全系统算力供给能力; 消费侧面向国家治理、社会民生、传统产业等多领域的升级改造, 推动算力网络服务, 拓展国内外更多应用领域, 实现算力网络的多元供给、多元服务和多元业态.
算力网络还处于起步阶段, 还有很多理论和方法技术层面的值得深入研究的挑战性问题, 但同时也带来很多机遇, 特别是大模型和相关人工智能技术的兴起, 对算力的需求急剧增加, 也给算力网络带来意想不到的挑战. 就算力网络智慧调度而言, 如何挖掘调度知识、如何灵活应用调度知识将是算力网络调度智慧化程度的关键. 可以预见, 在未来相当长一段时间, 算力网络智慧调度将持续成为研究热点.
-
图 3 智慧调度为核心的算力网络体系架构
Fig. 3 Computing power network system architecture centered on intelligent scheduling
图 8 调度算法时间与质量关系
Fig. 8 The relationship between time and quality of scheduling algorithm
表 1 算力网络与云边端计算比较
Table 1 Comparison between computing power network and cloud-edge-terminal computing
云边端计算 算力网络 优点 大规模计算资源, 大规模存储设施, 计算能力强, 可扩展
计算资源静态、聚集、专业, 技术相对成熟网、云、数、智、安、边、端、链深度融合, 计算性能好, 可扩展计算资源动态、分散、易用, 去中心化, 延迟低, 适合实时任务, 安全性和隐私性强 缺点 延迟较高, 不适合实时性高的任务, 安全性与隐私性差 技术不成熟 适用性 计算密集型、存储密集型任务 分布式一体化算网服务 
下载: 导出CSV
表 2 启发式和元启发式调度算法类型
Table 2 Types of heuristic scheduling algorithm and meta-heuristic scheduling algorithm
下载: 导出CSV
表 3 算力网络调度算法发表情况分析
Table 3 Analysis of the publication situation of computing power network scheduling algorithms
2018 年 2019 年 2020 年 2021 年 2022 年 期刊论文数量 0 1 1 2 0 会议论文数量 1 0 0 2 5
下载: 导出CSV
表 4 算力网络三个演化阶段的四个维度特点
Table 4 Four-dimensional characteristics of three evolutionary stages of computing power network
资源 编排 运营 服务 泛在协同 网随算动 协同编排 协同运营 一站服务 融合统一 算网融合 智能编排 统一运营 融合服务 一体内生 算网一体 智慧内生 模式创新 一体服务
下载: 导出CSV
表 5 算力网络综述对比
Table 5 Comparison of computing power network surveies
文献[136] 文献[137] 本文 角度 5G通信 5G通信; 移动互联网 算力调度 关注重点 边缘节点计算资源限制; 业务需求与网络解耦; 静态服务器与移动客户端限制 泛在计算资源协同; 用户网络服务体验 广分布异构性导致可行解空间巨大; 强不确定性导致可行解空间易变; 高约束复杂性导致可行解孤岛繁多; 多目标性导致冲突目标权衡优化难 主要内容 提出基于分布式系统的计算网络融合架构; 协同共享多个边缘节点计算资源; 实现大量请求的处理和负载均衡; 考虑网络条件和可用计算资源的边缘节点交互; 提供基于网络的负载均衡服务分配方法 提出基于IETF的算力网络基本架构; 阐述算力网络的工作机制; 介绍计算任务调度等关键技术 提出多层次的算力网络体系架构; 提出算力网络管理机制; 提出算力网络智慧调度框架; 分析算力网络智慧调度问题性质 创新点 提出基于分布式系统的计算网络融合架构 介绍算力网络的基本架构与工作流程 提出参数化结构化业务管理模型; 提出算力网络调度优化模型; 提出算力网络智慧调度体系架构
下载: 导出CSV
-
[1] Tang X Y, Cao C, Wang Y X, Zhang S, Liu Y, Li M X, et al. Computing power network: The architecture of convergence of computing and networking towards 6G requirement. China Communications, 2021, 18(2): 175−185 doi: 10.23919/JCC.2021.02.011 [2] He X, Tu Z Y, Wagner M, Xu X F, Wang Z J. Online deployment algorithms for microservice systems with complex dependencies. IEEE Transactions on Cloud Computing, 2023, 11(2): 1746−1763 doi: 10.1109/TCC.2022.3161684 [3] Qi Q L, Tao F, Hu T L, Anwer N, Liu A, Wei Y L, et al. Enabling technologies and tools for digital twin. Journal of Manufacturing Systems, 2021, 58: 3−21 doi: 10.1016/j.jmsy.2019.10.001 [4] Zhang D Y, Luo Y Z, Wang Y B, Kui X Y, Ren J. BatOpt: Optimizing GPU-based deep learning inference using dynamic batch processing. IEEE Transactions on Cloud Computing, 2024, 12(1): 174−185 doi: 10.1109/TCC.2024.3350561 [5] Wang X F, Ren X X, Qiu C, Cao Y F, Taleb T, Leung V C M. Net-in-AI: A computing-power networking framework with adaptability, flexibility, and profitability for ubiquitous AI. IEEE Network, 2021, 35(1): 280−288 doi: 10.1109/MNET.011.2000319 [6] Bao Q Z, Ren X X, Liu C F, Wang X, Wang X F, Qiu C. Resource trading with hierarchical game for computing-power network market. In: Proceedings of the 5th International Joint Conference. Guangzhou, China: Springer, 2021. 94−109 [7] Lei B, Zhou G F. Exploration and practice of computing power network (CPN) to realize convergence of computing and network. In: Proceedings of the Optical Fiber Communications Conference and Exhibition (OFC). San Diego, USA: IEEE, 2022. 1−3 [8] 中国移动. 算力网络白皮书, 中国移动全球合作伙伴大会, 中国, 2021.China Mobile. The White Paper of Computing Force Network, China Mobile Global Partners Conference, China, 2021. [9] Zhang Y M, Feng B H, Tian A L T, Yu S, Zhang H K. Task offloading control and customized workload scheduling in multi-layer cloud networks. IEEE Transactions on Network and Service Management, 2024, 21(1): 714−728 doi: 10.1109/TNSM.2023.3317810 [10] Wang S G, Zhao Y L, Xu J L, Yuan J, Hsu C H. Edge server placement in mobile edge computing. Journal of Parallel and Distributed Computing, 2019, 127: 160−168 doi: 10.1016/j.jpdc.2018.06.008 [11] Xu X L, Zhang X, Liu X H, Jiang J L, Qi L Y, Bhuiyan Z A. Adaptive computation offloading with edge for 5G-envisioned internet of connected vehicles. IEEE Transactions on Intelligent Transportation Systems, 2021, 22(8): 5213−5222 doi: 10.1109/TITS.2020.2982186 [12] Jiang K H, Ni H, Han R, Wang X. An improved multi-objective grey wolf optimizer for dependent task scheduling in edge computing. International Journal of Innovative Computing, Information and Control, 2019, 15(6): 2289−2304 [13] Li Y, Ma Y Y, Zeng Z Y. A novel approach to location-aware scheduling of workflows over edge computing resources. International Journal of Web Services Research (IJWSR), 2020, 17(3): 56−68 doi: 10.4018/IJWSR.2020070104 [14] Ali Z, Khaf S, Haq Abbas Z, Abbas G, Jiao L, Irshad A, et al. A comprehensive utility function for resource allocation in mobile edge computing. Computers, Materials & Continua, 2021, 66(2): 1461−1477 [15] Khazaei H, Misic J, Misic V B. Performance of cloud centers with high degree of virtualization under batch task arrivals. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(12): 2429−2438 doi: 10.1109/TPDS.2012.318 [16] Chen X, Li M, Zhong H, Chen X N, Ma Y, Hsu C H. FUNOff: Offloading applications at function granularity for mobile edge computing. IEEE Transactions on Mobile Computing, 2024, 23(2): 1717−1734 [17] Lee W, Kang M, Kim S. Highly VM-scalable SSD in cloud storage systems. IEEE Transactions on Computer-aided Desi gn of Integrated Circuits and Systems, 2024, 43(1): 113−126 doi: 10.1109/TCAD.2023.3305573 [18] Baghban H, Rezapour A, Hsu C H, Nuannimnoi S, Huang C Y. Edge-AI: IoT request service provisioning in federated edge computing using actor-critic reinforcement learning. IEEE Transactions on Engineering Management, DOI: 10.1109/TEM.2022.3166769 [19] Guo H Z, Zhang J, Liu J J, Zhang H B, Sun W. Energy-efficient task offloading and transmit power allocation for ultra-dense edge computing. In: Proceedings of the IEEE Global Communications Conference (GLOBECOM). Abu Dhabi, United Arab Emirates: IEEE, 2018. 1−6 [20] Zhao J H, Sun X K, Li Q P, Ma X T. Edge caching and computation management for real-time internet of vehicles: An online and distributed approach. IEEE Transactions on Intelligent Transportation Systems, 2021, 22(4): 2183−2197 doi: 10.1109/TITS.2020.3012966 [21] Wang Z W, Fan J X. Flexible threshold ring signature in chronological order for privacy protection in edge computing. IEEE Transactions on Cloud Computing, 2022, 10(2): 1253−1261 doi: 10.1109/TCC.2020.2974954 [22] Ali I, Chen Y, Li J Q, Wakeel A, Pan C W, Ullah N. Efficient offline/online heterogeneous-aggregated signcryption protocol for edge computing-based internet of vehicles. IEEE Transactions on Intelligent Transportation Systems, 2023, 24(12): 14506−14519 doi: 10.1109/TITS.2023.3296974 [23] Tchaye-Kondi J, Zhai Y L, Shen J, Zhu L H. Privacy-preserving offloading in edge intelligence systems with inductive learning and local differential privacy. IEEE Transactions on Network and Service Management, 2023, 20(4): 5026−5037 doi: 10.1109/TNSM.2023.3266257 [24] Ren D W, Gui X L, Zhang K Y. Adaptive request scheduling and service caching for MEC-assisted IoT networks: An online learning approach. IEEE Internet of Things Journal, 2022, 9(18): 17372−17386 doi: 10.1109/JIOT.2022.3157677 [25] Ma C M, Zhu J Q, Liu M, Zhao H, Liu N B, Zou X Y. Parking edge computing: Parked-vehicle-assisted task offloading for urban VANETs. IEEE Internet of Things Journal, 2021, 8(11): 9344−9358 doi: 10.1109/JIOT.2021.3056396 [26] Wu Z R, Deng Y H, Zhou Y, Li J, Pang S J, Qin X. FaaSBatch: Boosting serverless efficiency with in-container parallelism and resource multiplexing. IEEE Transactions on Computers, 2024, 73(4): 1071−1085 doi: 10.1109/TC.2024.3352834 [27] Li T G, Ying S, Zhao Y S, Shang J A. Batch jobs load balancing scheduling in cloud computing using distributional reinforcement learning. IEEE Transactions on Parallel and Distributed Systems, 2024, 35(1): 169−185 doi: 10.1109/TPDS.2023.3334519 [28] Zhang Q Y, Zhang Z M, Cui J, Zhong H, Li Y, Gu C J, et al. Efficient blockchain-based data integrity auditing for multi-copy in decentralized storage. IEEE Transactions on Parallel and Distributed Systems, 2023, 34(12): 3162−3173 doi: 10.1109/TPDS.2023.3323155 [29] Li J L, Xiao D Y, Yao J Q, Long Y J, Wu W G. Learning scheduling policies for co-located workloads in cloud datacenters. IEEE Transactions on Cloud Computing, 2023, 11(4): 3725−3736 doi: 10.1109/TCC.2023.3319383 [30] Tong W, Chen W J, Jiang B B, Xu F Y, Li Q, Zhong S. Privacy-preserving data integrity verification for secure mobile edge storage. IEEE Transactions on Mobile Computing, 2023, 22(9): 5463−5478 [31] Zhao X, Zhang S, Dou W C. Multi-request scheduling and collaborative service processing for DASH-video optimization in cloud-edge network. In: Proceedings of the IEEE 13th International Conference on Cloud Computing (CLOUD). Beijing, China: IEEE, 2020. 582−589 [32] Zhou J, Chen Z, Feng G. Game theoretical bandwidth request allocation strategy in P2P streaming systems. In: Proceedings of the IEEE Global Communications Conference (GLOBECOM). Atlanta, USA: IEEE, 2013. 1657−1662 [33] Altin H, Topcuoglu H R, Gürgen F S. Network congestion aware multiobjective task scheduling in heterogeneous fog environments. IEEE Transactions on Industrial Informatics, 2024, 20(2): 3015−3024 doi: 10.1109/TII.2023.3299624 [34] Niu M, Cheng B, Chen J L. GMAS: A geo-aware mas-based workflow allocation approach on hybrid-edge-cloud environment. In: Proceedings of the IEEE 13th International Conference on Cloud Computing (CLOUD). Beijing, China: IEEE, 2020. 574−581 [35] Tang T, Ma Y Y, Feng W J. Probabilistic-QoS-aware multi-workflow scheduling upon the edge computing resources. International Journal of Web Services Research (IJWSR), 2021, 18(2): 25−39 doi: 10.4018/IJWSR.2021040102 [36] Yang Y H, Shen H, Tian H. Scheduling workflow tasks with unknown task execution time by combining machine-learning and greedy-optimization. IEEE Transactions on Services Computing, DOI: 10.1109/TSC.2024.3351622 [37] Lin B, Zhu F N, Zhang J S, Chen J Q, Chen X, Xiong N N, et al. A time-driven data placement strategy for a scientific workflow combining edge computing and cloud computing. IEEE Transactions on Industrial Informatics, 2019, 15(7): 4254−4265 doi: 10.1109/TII.2019.2905659 [38] Feng B B, Ding Z J, Zhou X B, Jiang C J. Heterogeneity-aware proactive elastic resource allocation for serverless applications. IEEE Transactions on Services Computing, DOI: 10.1109/TSC.2024.3350711 [39] Bacanin N, Zivkovic M, Bezdan T, Venkatachalam K, Abouhawwash M. Modified firefly algorithm for workflow scheduling in cloud-edge environment. Neural Computing and Applications, 2022, 34(11): 9043−9068 doi: 10.1007/s00521-022-06925-y [40] Tuli S, Casale G, Jennings N R. MCDS: AI augmented workflow scheduling in mobile edge cloud computing systems. IEEE Transactions on Parallel and Distributed Systems, 2022, 33(11): 2794−2807 [41] Kim J, Mohan K, Ramesh B. Functional and nonfunctional quality in cloud-based collaborative writing: An empirical investigation. IEEE Transactions on Professional Communication, 2014, 57(3): 182−203 doi: 10.1109/TPC.2014.2344331 [42] Sithipolvanichgul J, Chen C, Land J, Ractham P. Enhancing user experiences with cloud computing via improving utilitarian and hedonic factors. Energies, 2021, 14(7): Article No. 1822 doi: 10.3390/en14071822 [43] Sun Z M, Sun G, Liu Y H, Wang J, Cao D P. BARGAIN-MATCH: A game theoretical approach for resource allocation and task offloading in vehicular edge computing networks. IEEE Transactions on Mobile Computing, 2024, 23(2): 1655−1673 [44] Su Q, Zhang Q H, Li W D, Zhang X J. Primal-dual-based computation offloading method for energy-aware cloud-edge collaboration. IEEE Transactions on Mobile Computing, 2024, 23(2): 1534−1549 [45] Lin Z, Lu L M, Shuai J P, Zhao H, Shahidinejad A. An efficient and autonomous planning scheme for deploying IoT services in fog computing: A metaheuristic-based approach. IEEE Transactions on Computational Social Systems, 2024, 11(1): 1415−1429 doi: 10.1109/TCSS.2023.3254922 [46] Zafari F, Basu P, Leung K K, Li J, Towsley D, Swami A. Resource sharing in the edge: A distributed bargaining-theoretic approach. IEEE Transactions on Network and Service Management, 2023, 20(4): 4369−4382 doi: 10.1109/TNSM.2023.3265813 [47] Robinson I, Webber J, Eifrem E. Graph Databases: New Opportunities for Connected Data. Sebastopol: O'Reilly Media, Inc., 2015. [48] Son J, Buyya R. SDCon: Integrated control platform for software-defined clouds. IEEE Transactions on Parallel and Distributed Systems, 2019, 30(1): 230−244 doi: 10.1109/TPDS.2018.2855119 [49] Ruan M K, Titcheu T, Zhai E N, Li Z H, Liu Y, E J L, et al. On the synchronization bottleneck of OpenStack Swift-like cloud storage systems. IEEE Transactions on Parallel and Distributed Systems, 2018, 29(9): 2059−2074 doi: 10.1109/TPDS.2018.2810179 [50] Khan F, Jan M A, Alturki R, Alshehri M D, Shah S T, Rehman A U. A secure ensemble learning-based fog-cloud approach for cyberattack detection in IoMT. IEEE Transactions on Industrial Informatics, 2023, 19(10): 10125−10132 doi: 10.1109/TII.2022.3231424 [51] Byun E K, Kee Y S, Kim J S, Maeng S. Cost optimized provisioning of elastic resources for application workflows. Future Generation Computer Systems, 2011, 27(8): 1011−1026 doi: 10.1016/j.future.2011.05.001 [52] Aleem S, Ahmed F, Batool R, Khattak A. Empirical investigation of key factors for SaaS architecture. IEEE Transactions on Cloud Computing, 2021, 9(3): 1037−1049 doi: 10.1109/TCC.2019.2906299 [53] Pérez A, Moltó G, Caballer M, Calatrava A. Serverless computing for container-based architectures. Future Generation Computer Systems, 2018, 83: 50−59 doi: 10.1016/j.future.2018.01.022 [54] Li Z Z, Chard R, Babuji Y, Galewsky B, Skluzacek T J, Nagaitsev K, et al. funcX: Federated function as a service for science. IEEE Transactions on Parallel and Distributed Systems, 2022, 33(12): 4948−4963 doi: 10.1109/TPDS.2022.3208767 [55] Jiménez L L, Schelén O. HYDRA: Decentralized location-aware orchestration of containerized applications. IEEE Transactions on Cloud Computing, 2022, 10(4): 2664−2678 doi: 10.1109/TCC.2020.3041465 [56] Xu Z C, Zhou L Z, Liang W F, Xia Q F, Xu W Z, Ren W H, et al. Stateful serverless application placement in MEC with function and state dependencies. IEEE Transactions on Computers, 2023, 72(9): 2701−2716 doi: 10.1109/TC.2023.3262947 [57] Medel V, Tolosana-Calasanz R, Bañares J Á, Arronategui U, Rana O F. Characterising resource management performance in kubernetes. Computers & Electrical Engineering, 2018, 68: 286−297 [58] Pahl C, Brogi A, Soldani J, Jamshidi P. Cloud container technologies: A state-of-the-art review. IEEE Transactions on Cloud Computing, 2019, 7(3): 677−692 doi: 10.1109/TCC.2017.2702586 [59] Li X M, Wan J F, Dai H N, Imran M, Xia M, Celesti A. A hybrid computing solution and resource scheduling strategy for edge computing in smart manufacturing. IEEE Transactions on Industrial Informatics, 2019, 15(7): 4225−4234 doi: 10.1109/TII.2019.2899679 [60] Varghese B, Buyya R. Next generation cloud computing: New trends and research directions. Future Generation Computer Systems, 2018, 79: 849−861 doi: 10.1016/j.future.2017.09.020 [61] Xiao K, Yang S, Li F, Zhu L H, Chen X, Fu X M. Making serverless not so cold in edge clouds: A cost-effective online approach. IEEE Transactions on Mobile Computing, DOI: 10.1109/TMC.2024.3355118 [62] Zhao B W, Chen W N, Wei F F, Liu X M, Pei Q Q, Zhang J. PEGA: A privacy-preserving genetic algorithm for combinatorial optimization. IEEE Transactions on Cybernetics, DOI: 10.1109/TCYB.2023.3346863 [63] Beheshti Z, Hj. Shamsuddin S M. CAPSO: Centripetal accelerated particle swarm optimization. Information Sciences, 2014, 258: 54−79 doi: 10.1016/j.ins.2013.08.015 [64] Chen X, Hu S X, Yu C J, Chen Z Y, Min G Y. Real-time offloading for dependent and parallel tasks in cloud-edge environments using deep reinforcement learning. IEEE Transactions on Parallel and Distributed Systems, 2024, 35(3): 391−404 doi: 10.1109/TPDS.2023.3349177 [65] Zhang R R, Xie Z Z, Yu D X, Liang W F, Cheng X Z. Digital twin-assisted federated learning service provisioning over mobile edge networks. IEEE Transactions on Computers, 2024, 73(2): 586−598 doi: 10.1109/TC.2023.3337317 [66] Ramesh D, Rizvi N, Rao P C S, Sundararajan E A, Mondal K, Srivastava G, et al. Improved chemical reaction optimization with fitness-based quasi-reflection method for scheduling in hybrid cloud-fog environment. IEEE Transactions on Network and Service Management, 2024, 21(1): 653−669 doi: 10.1109/TNSM.2023.3299358 [67] Zhang L M, Xiao K, Jin L B, Dong P P, Tong Z. Mobility-aware and double auction-based joint task offloading and resource allocation algorithm in MEC. IEEE Transactions on Network and Service Management, 2024, 21(1): 821−837 doi: 10.1109/TNSM.2023.3295406 [68] Ding W C, Luo F, Gu C H, Dai Z M, Lu H F. A multiagent meta-based task offloading strategy for mobile-edge computing. IEEE Transactions on Cognitive and Developmental Systems, 2024, 16(1): 100−114 doi: 10.1109/TCDS.2023.3246107 [69] Lian Z C, Shu J G, Zhang Y, Sun J. Convergent grey wolf optimizer metaheuristics for scheduling crowdsourcing applications in mobile edge computing. IEEE Internet of Things Journal, 2024, 11(2): 1866−1879 doi: 10.1109/JIOT.2023.3304909 [70] Bittencourt L F, Diaz-Montes J, Buyya R, Rana O F, Parashar M. Mobility-aware application scheduling in fog computing. IEEE Cloud Computing, 2017, 4(2): 26−35 doi: 10.1109/MCC.2017.27 [71] Guo M, Guan Q S, Chen W Q, Ji F, Peng Z P. Delay-optimal scheduling of VMs in a queueing cloud computing system with heterogeneous workloads. IEEE Transactions on Services Computing, 2022, 15(1): 110−123 doi: 10.1109/TSC.2019.2920954 [72] Kaur A, Kumar R, Saxena S. OCTRA-5G: Osmotic computing based task scheduling and resource allocation framework for 5G. Concurrency and Computation: Practice and Experience, 2022, 34(28): Article No. e7369 doi: 10.1002/cpe.7369 [73] Khan A, Abbas A, Khattak H A, Rehman F, Din I U, Ali S. Effective task scheduling in critical fog applications. Scientific Programming, DOI: 10.1155/2022/9208066 [74] Bosilca G, Bouteiller A, Danalis A, Herault T, Lemarinier P, Dongarra J. DAGuE: A generic distributed DAG engine for high performance computing. Parallel Computing, 2012, 38(1−2): 37−51 doi: 10.1016/j.parco.2011.10.003 [75] Zhang G W, Shen F, Liu Z N, Yang Y, Wang K L, Zhou M T. FEMTO: Fair and energy-minimized task offloading for fog-enabled IoT networks. IEEE Internet of Things Journal, 2019, 6(3): 4388−4400 doi: 10.1109/JIOT.2018.2887229 [76] Lu X F, Liu C, Zhu S H, Mao Y L, Lio P, Hui P. RLPTO: A reinforcement learning-based performance-time optimized task and resource scheduling mechanism for distributed machine learning. IEEE Transactions on Parallel and Distributed Systems, 2023, 34(12): 3266−3279 doi: 10.1109/TPDS.2023.3317388 [77] Wu Z Y, Yan D F. Deep reinforcement learning-based computation offloading for 5G vehicle-aware multi-access edge computing network. China Communications, 2021, 18(11): 26−41 doi: 10.23919/JCC.2021.11.003 [78] Peng Q L, Xia Y N, Wang Y, Wu C R, Zheng W B, Luo X, et al. A decentralized collaborative approach to online edge user allocation in edge computing environments. In: Proceedings of the IEEE International Conference on Web Services (ICWS). Beijing, China: IEEE, 2020. 294−301 [79] Mondal S, Ruffin M. A min-max fair resource allocation framework for optical x-haul and DU/CU in multi-tenant O-RANs. In: Proceedings of the IEEE International Conference on Communications. Seoul, South Korea: IEEE, 2022. 3016−3021 [80] Zhang J Q, Li X P, Chen L, Ruiz R. Scheduling workflows with limited budget to cloud server and serverless resources. IEEE Transactions on Services Computing, DOI: 10.1109/TSC.2023.3332697 [81] Peng K, Nie J T, Kumar N, Cai C, Kang J W, Xiong Z H, et al. Joint optimization of service chain caching and task offloading in mobile edge computing. Applied Soft Computing, 2021, 103: Article No. 107142 doi: 10.1016/j.asoc.2021.107142 [82] Zhang Y, Wu J T, Lin W X, Hou M Y. Competitive analysis for two-option online leasing problem under sharing economy. Journal of Combinatorial Optimization, 2022, 44(1): 670−689 doi: 10.1007/s10878-022-00855-0 [83] Zheng X L, Huang J, Xia X H, Hwang G J, Tu Y F, Huang Y P, et al. Effects of online whiteboard-based collaborative argumentation scaffolds on group-level cognitive regulations, written argument skills and regulation patterns. Computers & Education, 2023, 207: Article No. 104920 [84] Qu G J, Wu H M, Li R D, Jiao P F. DMRO: A deep meta reinforcement learning-based task offloading framework for edge-cloud computing. IEEE Transactions on Network and Service Management, 2021, 18(3): 3448−3459 doi: 10.1109/TNSM.2021.3087258 [85] Bhargava A, Verma S. DEIT: Dempster shafer theory-based edge-centric internet of things-specific trust model. Transactions on Emerging Telecommunications Technologies, 2021, 32(6): Article No. e4248 doi: 10.1002/ett.4248 [86] Jayasena K P N, Thisarasinghe B S. Optimized task scheduling on fog computing environment using meta heuristic algorithms. In: Proceedings of the IEEE International Conference on Smart Cloud (SmartCloud). Tokyo, Japan: IEEE, 2019. 53−58 [87] Wang J. Edge artificial intelligence-based affinity task offloading under resource adjustment in a 5G network. Applied Intelligence, 2022, 52(7): 8167−8188 doi: 10.1007/s10489-021-02786-5 [88] Sikarwar H, Das D. SecEdge: Secure edge-computing-based hybrid approach for data collection and searching in IoV. IEEE Transactions on Network and Service Management, 2024, 21(1): 1213−1225 doi: 10.1109/TNSM.2023.3299264 [89] Wang N, Zhou W, Wang J J, Guo Y F, Fu J S, Liu J W. Secure and efficient similarity retrieval in cloud computing based on homomorphic encryption. IEEE Transactions on Information Forensics and Security, 2024, 19: 2454−2469 doi: 10.1109/TIFS.2024.3350909 [90] Zhang C, Ming Y L, Wang M Y, Guo Y, Jia X H. Encrypted and compressed key-value store with pattern-analysis security in cloud systems. IEEE Transactions on Information Forensics and Security, 2024, 19: 221−234 doi: 10.1109/TIFS.2023.3320612 [91] Deng X H, Chen B, Chen X C, Pei X J, Wan S H, Goudos S K. A trusted edge computing system based on intelligent risk detection for smart IoT. IEEE Transactions on Industrial Informatics, 2024, 20(2): 1445−1454 doi: 10.1109/TII.2023.3245681 [92] Datta S, Namasudra S. Blockchain-based smart contract model for securing healthcare transactions by using consumer electronics and mobile-edge computing. IEEE Transactions on Consumer Electronics, 2024, 70(1): 4026−4036 doi: 10.1109/TCE.2024.3357115 [93] Saatloo A M, Mehrabi A, Marzband M, Mirzaei M A, Aslam N. Local energy market design for power-and hydrogen-based microgrids considering a hybrid uncertainty controlling approach. IEEE Transactions on Sustainable Energy, 2024, 15(1): 398−413 doi: 10.1109/TSTE.2023.3288745 [94] Mahmood K, Shamshad S, Ayub M F, Ghaffar Z, Khan M K, Das A K. Design of provably secure authentication protocol for edge-centric maritime transportation system. IEEE Transactions on Intelligent Transportation Systems, 2023, 24(12): 14536−14545 doi: 10.1109/TITS.2023.3295818 [95] Rizvi S, Williams I. Analyzing transparency and malicious insiders prevention for cloud computing environment. Computers & Security, 2024, 137: Article No. 103622 [96] Liu Z, Liwang M H, Hosseinalipour S, Dai H Y, Gao Z B, Huang L F. RFID: Towards low latency and reliable DAG task scheduling over dynamic vehicular clouds. IEEE Transactions on Vehicular Technology, 2023, 72(9): 12139−12153 doi: 10.1109/TVT.2023.3266582 [97] Li X X, Xie Y, Wang H, Su X, Li H F. dAPRE: Efficient and reliable attribute-based proxy re-encryption using DAG for data sharing in IoT. IEEE Transactions on Consumer Electronics, 2024, 70(1): 584−596 doi: 10.1109/TCE.2023.3346028 [98] Wang D G L, Wang M M Y, Zhang S Q. Determining the edge metric dimension of the generalized petersen graph P(n, 3). Journal of Combinatorial Optimization, 2022, 43(2): 460−496 doi: 10.1007/s10878-021-00780-8 [99] Zhu S, Ota K, Dong M X. Green AI for IIoT: Energy efficient intelligent edge computing for industrial internet of things. IEEE Transactions on Green Communications and Networking, 2022, 6(1): 79−88 doi: 10.1109/TGCN.2021.3100622 [100] Meng S M, Li Q M, Wu T R, Huang W J, Zhang J, Li W M. A fault-tolerant dynamic scheduling method on hierarchical mobile edge cloud computing. Computational Intelligence, 2019, 35(3): 577−598 doi: 10.1111/coin.12219 [101] Bai Z Y, Lin Y F, Cao Y, Wang W. Delay-aware cooperative task offloading for multi-UAV enabled edge-cloud computing. IEEE Transactions on Mobile Computing, 2024, 23(2): 1034−1049 [102] Shahid A R, Imteaj A. Securing user privacy in cloud-based whiteboard services against health attribute inference attacks. IEEE Transactions on Artificial Intelligence, DOI: 10.1109/TAI.2024.3352529 [103] Pham Q V, Mirjalili S, Kumar N, Alazab M, Hwang W J. Whale optimization algorithm with applications to resource allocation in wireless networks. IEEE Transactions on Vehicular Technology, 2020, 69(4): 4285−4297 doi: 10.1109/TVT.2020.2973294 [104] Huynh L N T, Pham Q V, Pham X Q, Nguyen T D T, Hossain M D, Huh E N. Efficient computation offloading in multi-tier multi-access edge computing systems: A particle swarm optimization approach. Applied Sciences, 2020, 10(1): Article No. 203 [105] Shao Y L, Li C L, Fu Z, Jia L Y, Luo Y L. Cost-effective replication management and scheduling in edge computing. Journal of Network and Computer Applications, 2019, 129: 46−61 doi: 10.1016/j.jnca.2019.01.001 [106] Metlicka M, Davendra D, Hermann F, Meier M, Amann M. GPU accelerated NEH algorithm. In: Proceedings of the IEEE Symposium on Computational Intelligence in Production and Logistics Systems (CIPLS). Orlando, USA: IEEE, 2014. 114−119 [107] Zheng J X, Zhang P, Li F, Du G L. The high performing backtracking algorithm and heuristic for the sequence-dependent setup times flowshop problem with total weighted tardiness. Engineering Optimization, 2016, 48(9): 1571−1592 doi: 10.1080/0305215X.2015.1124870 [108] Wang S, Li X P, Ruiz R. Performance analysis for heterogeneous cloud servers using queueing theory. IEEE Transactions on Computers, 2020, 69(4): 563−576 doi: 10.1109/TC.2019.2956505 [109] Wang S, Li X P, Sheng Q Z, Ruiz R, Zhang J Q, Beheshti A. Multi-queue request scheduling for profit maximization in IaaS clouds. IEEE Transactions on Parallel and Distributed Systems, 2021, 32(11): 2838−2851 doi: 10.1109/TPDS.2021.3075254 [110] Wu J H, Sheng X F, Li G S, Yu K, Liu J K. An efficient and secure aggregation encryption scheme in edge computing. China Communications, 2022, 19(3): 245−257 doi: 10.23919/JCC.2022.03.018 [111] El-Bouri A. An investigation of initial solutions on the performance of an iterated local search algorithm for the permutation flowshop. In: Proceedings of the IEEE Congress on Evolutionary Computation. Brisbane, Australia: IEEE, 2012. 1−5 [112] Wang Z L, Li P F, Shen S, Yang K. Task offloading scheduling in mobile edge computing networks. Procedia Computer Science, 2021, 184: 322−329 doi: 10.1016/j.procs.2021.03.041 [113] Xie R C, Gu D E, Tang Q Q, Huang T, Yu F R. Workflow scheduling using hybrid PSO-GA algorithm in serverless edge computing for the internet of things. In: Proceedings of the IEEE 95th Vehicular Technology Conference (VTC2022-Spring). Helsinki, Finland: IEEE, 2022. 1−7 [114] Seifhosseini S, Shirvani M H, Ramzanpoor Y. Multi-objective cost-aware bag-of-tasks scheduling optimization model for IoT applications running on heterogeneous fog environment. Computer Networks, 2024, 240: Article No. 110161 doi: 10.1016/j.comnet.2023.110161 [115] Liu L Q, Yuan X M, Chen D C, Zhang N, Sun H F, Taherkordi A. Multi-user dynamic computation offloading and resource allocation in 5G MEC heterogeneous networks with static and dynamic subchannels. IEEE Transactions on Vehicular Technology, 2023, 72(11): 14924−14938 [116] Liu L Q, Yuan X M, Zhang N, Chen D C, Yu K P, Taherkordi A. Joint computation offloading and data caching in multi-access edge computing enabled internet of vehicles. IEEE Transactions on Vehicular Technology, 2023, 72(11): 14939−14954 [117] Li C L, Tang J H, Tang H L, Luo Y L. Collaborative cache allocation and task scheduling for data-intensive applications in edge computing environment. Future Generation Computer Systems, 2019, 95: 249−264 doi: 10.1016/j.future.2019.01.007 [118] Zhou H, Wu T, Chen X, He S B, Guo D K, Wu J. Reverse auction-based computation offloading and resource allocation in mobile cloud-edge computing. IEEE Transactions on Mobile Computing, 2023, 22(10): 6144−6159 doi: 10.1109/TMC.2022.3189050 [119] Cheng Z P, Min M H, Liwang M H, Gao Z B, Huang L F. Joint client selection and task assignment for multi-task federated learning in MEC networks. In: Proceedings of the IEEE Global Communications Conference (GLOBECOM). Madrid, Spain: IEEE, 2021. 1−6 [120] Yi B, Wang X W, Huang M. Content delivery enhancement in Vehicular Social Network with better routing and caching mechanism. Journal of Network and Computer Applications, 2021, 177: Article No. 102952 doi: 10.1016/j.jnca.2020.102952 [121] Qin S, Pi D C, Shao Z S, Xu Y. A discrete interval-based multi-objective memetic algorithm for scheduling workflow with uncertainty in cloud environment. IEEE Transactions on Network and Service Management, 2023, 20(3): 3020−3037 doi: 10.1109/TNSM.2022.3224158 [122] Sun Y L, Wu Z Y, Meng K, Zheng Y H. Vehicular task offloading and job scheduling method based on cloud-edge computing. IEEE Transactions on Intelligent Transportation Systems, 2023, 24(12): 14651−14662 doi: 10.1109/TITS.2023.3300437 [123] Mehrdoost Z, Bahrainian S S. A multilevel tabu search algorithm for balanced partitioning of unstructured grids. International Journal for Numerical Methods in Engineering, 2016, 105(9): 678−692 doi: 10.1002/nme.5003 [124] Li F, Li S J, Mei Z Z. A new evolutionary algorithm combining Alopex with estimation of distribution algorithm and its application to parameter estimation. Journal of Central South University, 2011, 42 (7): 1973−1980 [125] Xie R C, Zhu H, Tang Q Q, Chen Q X, Qiao S, Huang T. Joint task scheduling and load balancing in computing power network-enabled edge computing systems. In: Proceedings of the IEEE 8th International Conference on Computer and Communications (ICCC). Chengdu, China: IEEE, 2022. 563−568 [126] Lei B, Zhao Q Y, Mei J. Computing power network: An interworking architecture of computing and network based on IP extension. In: Proceedings of the IEEE 22nd International Conference on High Performance Switching and Routing (HPSR). Paris, France: IEEE, 2021. 1−6 [127] He Y H, Ren J K, Yu G D, Cai Y L. D2D communications meet mobile edge computing for enhanced computation capacity in cellular networks. IEEE Transactions on Wireless Communications, 2019, 18(3): 1750−1763 doi: 10.1109/TWC.2019.2896999 [128] Pang R, Li H, Ji Y F, Wang G Q, Cao C. Energy-saving mechanism based on tidal characteristic in computing power network. In: Proceedings of the International Conference on Networking and Network Applications (NaNA). Lijiang, China: IEEE, 2021. 150−154 [129] Zhang Y, Cao C, Tang X Y, Pang R, Wang S J, Wen X J. Programmable service system based on SIDaaS in computing power network. In: Proceedings of the 5th International Conference on Hot Information-Centric Networking (HotICN). Guangzhou, China: IEEE, 2022. 67−71 [130] Yao H J, Duan X D, Fu Y X. A computing-aware routing protocol for computing force network. In: Proceedings of the International Conference on Service Science (ICSS). Zhuhai, China: IEEE, 2022. 137−141 [131] Liu Z, Zhang J W, Gu Z Q. Network and computing-aware edge datacenter placement and content placement in edge compute first networking. In: Proceedings of the Asia Communications and Photonics Conference (ACP). Shenzhen, China: IEEE, 2022. 1233−1237 [132] Liu Z N, Yang Y, Zhou M T, Li Z Q. A unified cross-entropy based task scheduling algorithm for heterogeneous fog networks. In: Proceedings of the 1st ACM International Workshop on Smart Cities and Fog Computing. Shenzhen, China: ACM, 2018. 1−6 [133] Zhang Y T, Di B Y, Zheng Z J, Lin J L, Song L Y. Distributed multi-cloud multi-access edge computing by multi-agent reinforcement learning. IEEE Transactions on Wireless Communications, 2021, 20(4): 2565−2578 doi: 10.1109/TWC.2020.3043038 [134] Zou Z, Xie R C, Ren Y Z, Yu F R, Huang T. Task scheduling for ICN-based computing first network: A deep reinforcement learning approach. In: Proceedings of the IEEE 8th International Conference on Computer and Communications (ICCC). Chengdu, China: IEEE, 2022. 1615−1620 [135] Zhao L J, Tang X Y, You Z P, Pang Y, Xue H, Zhu L. Operation and security considerations of federated learning platform based on compute first network. In: Proceedings of the IEEE/CIC International Conference on Communications in China (ICCC Workshops). Chongqing, China: IEEE, 2020. 117−121 [136] Tian L, Yang M Z, Wang S G. An overview of compute first networking. International Journal of Web and Grid Services, 2021, 17(2): 81−97 doi: 10.1504/IJWGS.2021.114566 [137] 贾庆民, 丁瑞, 刘辉, 张晨, 谢人超. 算力网络研究进展综述. 网络与信息安全学报, 2021, 7(5): 1−12 doi: 10.11959/j.issn.2096-109x.2021034Jia Qing-Min, Ding Rui, Liu Hui, Zhang Chen, Xie Ren-Chao. Survey on research progress for compute first networking. Chinese Journal of Network and Information Security, 2021, 7(5): 1−12 doi: 10.11959/j.issn.2096-109x.2021034 期刊类型引用(1)
1. 赵宝康，时维嘉，周寰，孙薛雨. 算力网络研究进展：架构、关键技术与未来挑战. 上海理工大学学报. 2024(06): 600-609 . 
百度学术其他类型引用(1)
-
下载:
计量
- 文章访问数: 1339
- HTML全文浏览量: 546
- PDF下载量: 426
- 被引次数: 2
