针对大规模云边协同的容器集群，为了解决云边资源协同优化与服务质量保障的相关挑战，PPIO边缘云首席科学家王晓飞（天津大学教授，国家级青年人才）和PPIO边缘云联合创始人王闻宇（原PPTV联合创始人）陆续合作提出了两套云边资源优化框架，“KaiS”和“EdgeMatrix”，解决了资源调度、服务编排与请求指派的联合优化问题，并在真实数据集和场景展开了测试，成果收录至IEEE INFOCOM2021与2022（CCF-A网络领域顶会，录取率19%）
为了实现敏捷服务响应、缓解骨干网络压力，边缘计算正在与云计算逐渐融合，从而在尽可能接近请求生成的地方托管服务，图1展示了面向 Kubernetes的边缘云系统中的调度问题，产业界和学术界对此高度关注，其中学术领域的现有研究工作大多依赖于对资源、需求等条件进行准确建模或预测，产业界也有许多基于Kubernetes（K8s）的边云协同解决方案，例如KubeEdge（华为）、OpenYurt（阿里巴巴）、Baetyl（百度）等。
尽管上述解决方案可以融合边、云的异构资源，但是却还未面向边、云协同特性去设计协调请求指派与服务编排的「高效且友好」调度策略：如何将服务请求指派到合适设备进行处理？如何编排服务使之在合适设备上进行部署？如何高效保证服务等级协议（Service Level Agreement, SLA）？
图 1 面向Kubernetes边缘云系统的调度示意图
针对上述问题，天津大学教授PPIO边缘云首席科学家王晓飞和PPIO边缘云联合创始人王闻宇（原PPTV联合创始人）共同设计了“两步走”策略：第一步，研究边云混合集群系统内的高效调度问题，提出了调度框架KaiS；第二步，在调度优化的基础上加入服务等级协议保证策略，提出了调度框架EdgeMatrix。并且这两项工作均已在CCF-A类计算机领域顶级会议IEEE International Conference on Computer Communications (INFOCOM)中得到认可。
基于学习的Kubernetes边云系统定制化调度
摘要——当前传统网络已经难以应对日益增长的流量规模及不断兴起的网络服务，为了提供敏捷服务响应并缓解骨干网络压力，边缘计算和云计算正在逐渐融合。然而目前边云协同系统仍然缺乏请求指派与服务编排的高效调度策略。如图2所示，本文为边云集群系统设计了一种基于学习的调度框架KaiS，以提高请求处理的长期吞吐率。首先，我们利用多智能体演员-评论家算法设计了分布式请求指派算法，该算法可以处理动态动作空间以应对时变的系统资源。其次，针对不同的系统规模和结构，我们提出一种基于图神经网络（Graph Neural Network, GNN）的服务编排算法，该算法使用GNN高效编码系统信息，并使用策略网络通过逐步调度来降低编排维度。最后，我们采用了一种双时间尺度调度机制来协调请求指派和服务编排，并给出了部署上述算法与原生K8s组件兼容的设计实现。
图 2 KaiS架构图
主要研究贡献——本文提出了基于学习的Kubernetes边云系统定制化调度框架KaiS，可以通过系统的运行经验自主学习复杂的调度策略，而无需依赖于有关系统执行参数和运行状态的假设。为了指导KaiS学习高效的调度策略，我们设计了多智能体协同算法（cMMAC）以及基于图神经网络的策略梯度算法（GPG）分别用于解决请求指派和服务编排问题。此外，我们面向基于K8s的边云集群系统实现了两级调度框架，并在多种情况下利用实际工作负载对框架进行了评估。
图 3 协同的多智能体演员-批评家算法用于处理分布式请求指派
图4 基于GNN进行逐层状态编码
图 5 采用周期性逐步调度方式来降低高维动作空间造成的影响
综上所述，Kais首先基于图神经网络进行集中式服务编排，从而将不同类型的服务部署到各个计算节点，然后基于多智能体算法进行分布式请求指派，从而将不同类型的请求卸载到各个计算节点，实现了高效的系统调度，如算法1
算法 1 KaiS调度算法
实验结果评估——我们依据阿里巴巴的追踪数据集构造出四类请求模式，并在不同请求模式和场景下进行实验。图6给出了在不同请求模式下训练时KaiS的性能演变，所有情况下的吞吐率都随着时间的推移而提升，这表明KaiS可以逐渐学习适应不同的请求模式，且分布式调度可以带来更高的吞吐率。
图6 KaiS在不同请求模式（左）和集中/分布式调度模式下的调度性能
本文结合4种请求模式来构建一个长序列，并对比KaiS、GreedyGPG、cMMAC-Native和Greedy-Native调度框架在该序列下的编排性能。实验表明(i)KaiS的平均吞吐率比最相近的策略高3.6％，特别是每当请求到达模式发生变化时，KaiS仍然可以快速学习适应新模式的编排策略；(ii)采用基于GNN的状态编码方式，从而在复杂环境下仍然能快速获取请求特征，如图7所示。
图7 KaiS在波动的请求模式（左）和不同系统规模（右）下的编排能力
这篇文章以提高请求处理的长期吞吐率作为优化目标，为边云集群系统设计了一种基于学习的调度框架KaiS。但是，如果需进一步关注于满足多样化服务需求的话，则需要将SLA保证进一步融入调度优化的考虑范畴。为此，我们开展了下一步工作，并拓展了之前的研究成果，相关工作也发表在了CCF-A类计算机领域顶级会议INFOCOM2022之上。下面对该工作进行详细介绍。
EdgeMatrix：面向优先服务的资源重定义边云集群系统
摘要——边云集群系统有望对海量异构的网络设备进行有效管控，真正实现无处不在的计算。然而，对于服务提供商而言，复杂的网络环境为保证SLA带来了诸多挑战：多资源异构、资源竞争和网络系统动态。在本文中，我们为边云集群系统设计了一个框架EdgeMatrix，如图8，以保证多种SLA的同时最大化系统吞吐量。首先，EdgeMatrix引入了网络化多智能体演员-评判家算法，将物理资源重新定义为逻辑隔离的资源组合，我们称每一个资源组合为一个资源单元。然后，我们使用聚类算法将具有相似特征的资源单元分成不同的集合，每一个具有相似特征的资源单元集合称之为一个资源通道，其中不同的资源通道可以提供不同的SLA保证。此外，我们设计了一种多任务机制来解决边缘云集群之间的联合服务编排和请求指派问题，与传统方法相比，显著减少了运行时间。最后，为了保证系统稳定性，EdgeMatrix采用了双时间尺度框架，即在大时间尺度上协调资源和服务，在小时间尺度上调度请求。
图8 EdgeMatrix架构
动机与挑战——在云计算中，服务提供商可以基于SLA向用户提供可靠的服务。在本文中，我们基于云计算中的SLA思想，提出EdgeMatrix，它可以使边云集群系统在复杂网络环境下为用户服务提供强有力的SLA保证。尽管在边云集群系统中基于SLA为用户提供可靠的服务可以显著提高系统效率，但在具体实施过程中仍面对三个固有的挑战：(i)多资源异构：地理分布的边缘节点具有不同的计算能力、通信能力和系统架构；(ii)资源竞争：不同类型的服务有不同的资源需求，造成不同服务之间的资源竞争，从而影响请求的服务效率；(iii)网络系统动态：由于用户需求和网络设备的随机波动，网络系统的请求负载和可用资源处于不断的动态变化中。因此，目前边云集群系统迫切需要资源重新定义的架构来满足用户的SLA。
主要研究贡献——在本文中，为了更好地应对边云集群系统的三个固有挑战，我们的工作重点是资源定制、服务编排和请求指派，如图9。我们引入了网络化多智能体演员-评判家算法（Networked Multi-agent Actor-Critic, NMAC）进行资源定制，以及基于次模函数优化的启发式算法JSORD用于解决请求指派和服务编排问题。
图9 三大挑战及其应对方案
资源定制的工作流程如图11所示，首先，我们在每个边缘节点上都部署了一个深度强化学习智能体，每个智能体能够根据实时的系统状态计算出当前所需资源单元的大小；其次，智能体会从所在节点及其相邻节点中寻找满足条件的资源组合，进而将物理资源映射到虚拟的资源单元；再次，我们使用聚类算法，对所有的资源单元进行分类，同一类别的资源单元组成一个资源通道。
图10 网络化多智能体强化学习算法
图11 资源定制器的工作流程
问题1 服务编排和请求指派联合优化问题建模
算法 2 基于次模优化求解服务编排子问题
b）请求指派：网络系统的动态性对调度算法的适应性提出了重大挑战。请求指派是确定请求是否可以被成功服务的最后一个环节。面对系统的网络动态性，请求指派算法的设计对系统的鲁棒性起着至关重要的作用。由上文可知，服务编排子问题借助次模函数优化可以取得近似最优解，这大大简化了请求指派子问题的求解难度。因为在服务编排已知的前提下，请求指派子问题化为一个只与请求指派变量（连续型变量）相关的线性规划问题，如问题2，可直接借助线性规划求解器在线性时间内求解。
问题 2 请求指派子问题建模
实验结果评估——本文评估了EdgeMatrix在边缘云系统中面对三个固有挑战时的仿真性能，如图12所示。图12 (a)显示了EdgeMatrix在边缘节点资源异构下的性能表现。我们发现当计算资源和内存资源的异构级别相同时，EdgeMatrix表现最好。尽管EdgeMatrix的性能会随着一种资源的异构性加剧而下降，但在最坏情况下EdgeMatrix的性能仅下降了3.9%。从图12 (b)可以看出，EdgeMatrix能够自适应不同的资源竞争程度，灵敏感知环境中各种资源的负载变化并调整策略，从而保持高效的资源定制能力。带宽资源会严重影响网络系统的稳定性，图12 (c)显示无论边缘节点的平均带宽大小波动还是带宽异构性变化，EdgeMatrix中的系统吞吐率都保持在46%以上，这说明资源定制可以很好地应对系统的网络动态性。
图12 EdgeMatrix应对三大挑战的实验效果图
此外，EdgeMatrix的另一个重要贡献是显著减少了服务编排和请求指派的运行时间。如图13所示，我们比较了EdgeMatrix和pure-JSORD（在不进行资源定制下执行算法JSORD）的决策时间成本。结果显示EdgeMatrix所需时间成本的数量级远低于pure-JSORD。原因是pure-JSORD考虑了全局的所有服务类型，而EdgeMatrix（i）只在每个资源通道内编排具有相应SLA优先级的服务；(ii)请求指派只面向具有同一个SLA优先级的请求。EdgeMatrix的这些特性使不同通道间的服务编排和请求指派并行执行，显著降低了算法中参数的大小。
图13 运行时间对比
为方便读者阅读，编者已将两篇论文的重点内容翻译为中文供感兴趣的读者阅读，另外，完整英文版也可点击如下链接获取原文：
1.https://ieeexplore.ieee.org/abstract/document/9488701
2.https://arxiv.org/abs/2203.10470
(注：论文版权归属IEEEINFOCOM大会及IEEE版权方，论文的分享只体现学术贡献与分享目的，未经许可禁止用于商业用途。)
参考文献：
Han Y, Shen S,WangX, et al.Tailored learning-based scheduling forkubernetes-oriented edge-cloud system[C]//IEEEConference on Computer Communications (INFOCOM),2021.
Y. Ren, S. Shen,Y. Ju,X. Wang,W. Wang, and Victor C.M. Leung.EdgeMatrix:A Resources Redefined Edge-Cloud System for Prioritized Services[C]//IEEEConference on Computer Communications (INFOCOM),2022.
以上工作由天津大学教授PPIO边缘云首席科学家王晓飞和PPIO边缘云联合创始人王闻宇（原PPTV联合创始人）一同提出。
（注：论文版权归属IEEE INFOCOM大会及IEEE版权方，本论文于arxiv的分享只体现学术贡献与分享目的，未经许可禁止用于商业用途。）
CCF是中国计算机学会（China Computer Federation ，简称CCF）,成立于1962年，是国内首个中国计算机领域的全国一级学会。IEEE INFOCOM是CCF在计算机网络领域的A级学术大会，INFOCOM对其论文的质量要求严格：新颖、有价值、观点清晰、证据合理，因此正式论文的录取率近几年一直控制在20%以下，其中2022年全球范围内仅录取了227篇。
天津大学智能与计算学部边缘计算课题组多年耕耘于边云协同领域，主要研究边缘智能理论、边缘计算系统架构、云边协同算法等，发表高水平科研论文140余篇（含SCI论文80篇），引用5600次，发明专利30余项，负责省部级纵向和企业横向课题二十余项。该课题组主要负责人王晓飞，天津大学智能与计算学部长聘教授，博导，国家海外高层次人才引进计划（青年），曾获中国计算机学会分布式专委会青年创新奖，天津市科技进步奖一等奖，天津大学北洋青年学者。
PPIO边缘云于2018年5月创立，是一家专注于边缘计算领域的全球化云服务企业，秉承“汇聚全球计算资源，并为全人类提供服务”的使命，目前，PPIO边缘云在全国1000多个城市及地区设有微型数据中心和分布式算力资源，结合大数据、云原生、分布式计算技术，为用户提供垂直于下一代边缘计算场景，与中心云兼容协同，并符合低时延、高带宽、重计算需求的边缘云服务和解决方案，并已成为国内外多家一线互联网巨头、云计算公司、创业公司独角兽在分布式云服务领域的主要提供商。
