基于Kubernetes的多云网络成本优化模型

高明，刘铭，陈泱婷，王伟明

基于Kubernetes的多云网络成本优化模型

高明，刘铭，陈泱婷，王伟明

（浙江工商大学信息与电子工程学院，浙江 杭州 310018）

以Kubernetes为代表的云原生编排系统在多云环境中被云租户广泛使用，随之而来的网络观测性问题愈发突出，跨云跨地区的网络流量成本尤为突出。在Kubernetes中引入扩展的伯克利数据包过滤器（extended Berkeley packet filter，eBPF）技术采集操作系统内核态的网络数据特征解决网络观测问题，随后将网络数据特征建模为二次分配问题（quadratic assignment problem，QAP），使用启发式搜索与随机搜索组合的方法在实时计算的场景下求得最佳近优解。此模型在网络资源成本优化中优于Kubernetes原生调度器中仅基于计算资源的调度策略，在可控范围内增加了调度链路的复杂度，有效降低了多云多地区部署环境中的网络资源成本。

Kubernetes；
eBPF；
多云网络；
二次分配问题

云原生模式是面向云进行软件工程设计的一种思想理念，是一种充分发挥云效能的最佳实践，用于帮助企业构建弹性可靠、松耦合、易管理的软件系统，从而提升软件的交付效率，降低软件的运维复杂度[1]。Gartner行业数据显示：到2025年，将有超过95%的新数字项目以云原生平台为基础设施，远高于2021年40%的比例[2]。

以Kubernetes为代表的云原生编排系统已被广泛应用在云中，各大云厂商均推出了云原生编排系统产品，如Google的GKE（Google Kubernetes引擎）、Microsoft的AKS（Azure Kubernetes服务）、Amazon的EKS（Elastic Kubernetes服务）、阿里云的ACK（阿里云容器服务Kubernetes版）以及华为云的CEE（云容器引擎）。随之而来的网络观测性问题愈发突出，云租户难以感知云原生网络的实际带宽及流量画像。扩展的伯克利数据包过滤器（extended Berkeley packet filter，eBPF）技术的面世推动了云原生可观测性的发展，使得网络观测性问题的解决成为可能。2014年eBPF代码合入Linux3.18内核的主分支，新的Linux内核加进去的内核观测功能，从系统内核层读取网络数据包，从而观测到云原生编排系统集群内部服务之间的相互调用关系与调用频率，有效解决了云原生网络的观测问题[3]。

此外，没有任何一家云厂商在云的可靠性方面可保证100%的服务等级协定（service level agreement，SLA），但通过云厂商历年的公开事故报告统计可发现，几乎不存在所有云在同一时刻均不可用的情况。所以，云租户为确保服务的实时可用，已逐渐采用多云部署的方案。

云原生编排系统通常基于计算资源进行服务调度，而非基于网络资源进行服务调度，因此在多云部署的具体实践中，跨云跨地区的网络流量成本居高不下，网络资源成本优化问题亟待解决[4]。针对上述问题，本文提出了一种基于Kubernetes的多云网络成本优化模型，目标是为云租户降低使用多云、多地区、多数据中心之间云网络资源的经济成本，该模型的工作步骤如下。

步骤1 基于Kubernetes进行多云多地区服务部署，在操作系统内核态通过eBPF指标采集器实时采集不同服务之间的网络数据包，并解析数据包头部的元数据，生成含网络通信数据包数量的权重网络拓扑。

步骤2 将权重网络拓扑的数据特征数学建模为二次分配问题（quadratic assignment problem，QAP）。

步骤3 使用蚁群优化（ant colony optimization，ACO）算法、模拟退火（simulated annealing，SA）算法、遗传算法（genetic algorithm，GA）、免疫算法（immune algorithm，IA）4种启发式搜索算法与随机优化（stochastic optimization，SO）并行的方式计算每一个时刻的数据特征，计算持续的时间为一个单位时刻，最终采用最佳算法的近优解，并生成使全局网络资源经济成本最小的计算资源调度方案。

步骤4 计算资源调度方案进入Kubernetes调度器队列，在下一时刻结束时对此调度方案进行评估，阶段性反馈成本优化率用于优化模型。

实验数据表明，此模型在网络资源成本优化中优于基于计算资源的调度方法，有效降低了多云多地区部署环境中的网络资源成本，虽然增加了调度链路的复杂性，但在当前样本数据规模下，其调度链路复杂度带来的计算资源用量水位的上升是固定可调控的。

目前有大量文献对网络资源成本优化问题做出了深入的研究。文献[5]通过将深度强化学习原理引入软件定义网络的路由过程优化网络资源成本。文献[6-8]通过蚁群算法、遗传算法、粒子群算法等启发式算法进行路由优化降低网络资源成本。文献[9]提出了混合虚拟网络环境的概念，使用遗传算法部署虚拟网络功能（virtual network function，VNF），并设计了4种遗传算法用于最小化带宽开销和最大化链路利用率优化降低网络资源成本。文献[10]利用复制的方式部署VNF保证网络的负载均衡，并为大型网络设计了遗传算法优化降低网络资源成本。文献[11]通过遗传算法在云数据中心动态部署VNF，最大限度地利用网络资源优化降低网络资源成本。

上述文献主要通过优化路由算法的方式降低网络资源的传输成本，但在多云网络环境的应用中存在阻碍，首先云租户通常无法更改云厂商设定的网络路由策略等基础设施，其次云厂商网络通常基于覆盖网络（Overlay）实现弹性网络，即在现有物理网络的技术上创建的虚拟或逻辑网络，从而导致云租户无法感知物理网络的真实带宽水位。文献[12]提出了一种通过编排VNF资源并将其合理部署在物理网络中的方式，通过调整计算资源的位置达到了优化网络资源成本的效果，此类研究具备多云环境的应用条件。

本文基于多云环境研究，在网络成本的优化方案中通过不改变网络资源拓扑仅改变计算资源位置的方法，进一步实现计算资源的位置随时间及流量的变化进行动态调整，从而降低网络资源的经济成本。该方案在物理机器和虚拟机部署阶段实现的时间成本较高，而基于云原生技术部署服务可实现毫秒级跨云跨地区调度服务，使此方案的实现成为可能。

模型采用Kubernetes云原生编排系统作为基础设施，以Kubernetes中最小可调度的计算单元（Pod）之间的流量特征为研究对象，实现云原生网络资源成本优化工作的实时计算，并根据最佳近优解分时刻调度计算资源。模型的系统架构如图1所示，自下而上由数据生产、数据采集、数据存储、数据处理、基础支撑、功能服务与数据接口组成。

图1 系统架构

网络资源成本优化的基础是网络资源的数据信息，首要任务就是采集网络资源的数据并进行结构化用于数据分析。采集云原生网络数据包的核心技术是eBPF，在经典的网络数据包采集工具链中，通常在用户态采集网络数据包，而通过eBPF在更靠近硬件网卡的内核态位置采集网络数据比用户态采集数据具有更高的性能优势[13-14]。

图1中的数据生产和数据采集模块属于云原生网络特征观测子系统，是模型的数据来源。云原生网络特征观测子系统在多云多地区的计算资源池内通过eBPF指标采集器从内核态采集业务服务与网络功能服务之间的网络数据包，并将其输出到Cilium网络功能服务中，由Fluent Bit数据转发器将Cilium内的网络数据包数据写入Kafka内存型消息队列，并使用Logstash实时数据传输管道工具消费消息队列内的数据，将元数据的关键字段清洗后转储到分布式时间序列检索引擎（Elastic search engine，ES）集群中，Kibana数据检索工具可以对ES集群中的全量数据进行查询。在数据处理的过程中读取ES集群中的数据，处理完将数据落库到PostgreSQL结构化数据库中。

最终处理完成的网络数据核心指标包含每个服务被哪些服务连接、连接了哪些服务以及服务之间的连接频率。根据这些指标可以通过调整服务运行的时间和空间优化计算资源成本和网络资源成本。调整服务运行的时间，例如，时效性要求较低且数据量较少的服务可定时运行服务，处理完数据后销毁服务，从而有效节省弹性计算资源成本。调整服务运行的空间，例如，通信频率较高的两个服务的物理间隔位置较远，可增加服务之间的亲和性使其运行在同一台宿主机，降低网络资源成本。

模型数据流图如图2所示，在多家云厂商（Cloud）的多个地区（Region）的多个数据中心（Zone）的多个Kubernetes工作平面节点（Node）中的操作系统内核态采集到网络数据包后，将数据特征清洗并适配蚁群优化算法、模拟退火算法、遗传算法和免疫算法4种启发式搜索算子以及随机搜索算子进行计算，并行在一单位时刻时间内迭代多次取得近优解，获取最佳最优解后生成计算资源新的放置位置，每个时刻循环往复。根据业务需求一单位时刻定义为5 min，时间太短将导致调度频繁，时间太长将导致模型无法及时对流量的变化产生反馈。最佳算子的产出结果是下一个时刻的目标计算资源的位置状态，调度器以受控速率改变计算资源的实际位置状态，使其达到期望位置状态，本文的调度器复用Kubernetes原生计算资源调度器。

图2 模型数据流图

在云原生环境中的成本主要分为计算资源成本和网络资源成本两个部分，本文重点在固定计算资源成本的前提下分时刻优化网络资源成本。在优化网络资源成本时将Pod所在的计算资源池的子集（计算资源插槽，Slot）之间的网络流量价格作为Pod之间的流量成本权重，每个Slot最大仅可容纳1个Pod，且Slot具备流量成本权重表中的位置属性，流量成本权重见表1。

表1 流量成本权重

本文通过计算Pod之间的通信成本和流量的方式调整Pod位置，以此优化网络资源成本，因此该方法可建模为组合优化中的QAP。组合优化是计算资源调度策略实施过程中重要的步骤，其过程是结合不同的调度目标及成本约束给出最优的组合权重[15]。由于QAP已被证明为NP难问题，无法在多项式时间内计算得到准确结果[16]，而网络流量的数据特征具备时效性，计算资源的调度方案要求实时性，所以最终方案的实施需要兼顾时间成本和优化效率。

模型的核心是在限定时间内求解不定规模的QAP，在无法得知最优解的情况下获取最佳近优解。

云上跨Cloud、Region、Node、Zone、Pod之间的流量均属于东西向流量，模型的本质是降低云原生网络东西向流量的成本。模型需要在每个时刻决策把每一个Pod分配到指定的Slot，每个Slot具备不同的Node、Zone、Region和Cloud位置，并且每个位置属性均有固定配额，存在资源门限，一旦达到限制，则无法调度。因此，合理分配所有时刻的所有Pod并调度到指定Slot，降低总网络资源成本是模型的主要工作。

网络资源成本最低的极限方案是把所有计算资源都放在同一个位置，然而单位置有计算资源上限瓶颈，无法满足大规模计算场景，而且单地区或者单云的方案存在限额和灾备问题，模型需要满足以上约束条件。

表2 示例Pod位置属性

综合对比上述5种搜索算子和仅基于计算资源的算子，即原生（Native）算子，启发式搜索和随机搜索的结果均存在随机性，仅基于计算资源的算子存在大量网络资源成本浪费情况。示例样本网络成本优化算子对比如图3所示，由于示例数据采用了较小规模的样本，5种搜索算子相对于Native算子均取得了较好的优化效果，其中GA算子和SA算子优化效果最佳，都将此样本初始的网络资源成本3 120元优化到了794元，优化率约为74.55%。

图4 示例样本计算资源调度方案对比

模型验证模拟实验环境使用4台树莓派模拟3云29地区数据中心共计174个Slot，使用1台二层交换机模拟多云多地区之间的专线网络，实验环境硬件设备信息见表3。

表3 实验环境硬件设备信息

本实验中树莓派主板操作系统的版本采用了2022年3月发布的openEuler 22.03 LTS，此版本中Linux内核采用了5.10版本，Linux内核自4.16版本起支持eBPF功能。基于openEuler Linux操作系统部署了Kubernetes云原生编排系统，并在编排系统内部署实验环境软件，实验环境软件版本信息见表4。

表4 实验环境软件版本信息

模拟实验首先从优化算子、迭代时间、迭代次数3个维度组合的方式对样本进行求解，形成多样化的对比实验任务。采样时刻0、5、10、60、150和280的样本数据，分别使用5种搜索算子对样本迭代300次，对比实验结果，实验任务见表5。

表5 实验任务

表5实验任务中的样本时刻算子成本优化效果如图6所示，在Pod规模为174的场景中，对其中6份样本数据迭代运算300次，并进行效果对比。图6中，GA算子第88次计算结果和IA算子在第219次计算结果的算子排名与第300次计算结果的算子排名无较大差异，因此，同时取300次迭代数据进行算子评估。其中，ACO算子在试验结果中有5/6的样本取得了最佳近优解，GA算子在1/6的样本中取得了最佳近优解，IA算子、SA算子和SO算子在小迭代次数时存在最佳近优解的情况，特别是50次以下的迭代，适用于求解时间要求较高的场景。当Pod资源规模较大，无法在限定时间内取得优化效果时，需要对样本数据进行拆分处理，取多个样本数据子集的局部最优解作为全局最优解。

图6 样本时刻算子成本优化效果

使用ACO算子和GA算子对全量样本数据进行计算，并保存每次的迭代的结果，参照原生调度方案对比每个时刻搜索算子的优化效果，每个时刻算子优化对比如图7所示，两种算子最优解均优于原生调度方案，因此，混合算子最优解更优于原生调度方案。

图7 每个时刻算子优化对比

综合全部样本数据，可得24 h成本优化情况，全量样本成本优化对比如图8所示，ACO算子、GA算子以及ACO算子和GA算子混合的算子优化率分别是89.18%、86.85%和89.23%，采用ACO算子和GA算子混合为最佳组合算子。

图8 全量样本成本优化对比

由于本文定义一个时刻单位为5 min，在限定单位时间内，取ACO算子和GA算子比例为5:1的数量进行模型部署，可取得最佳结果。使用Kubernetes编排系统内计算资源的空余水位部署算子，算子的副本数量按照比例根据计算资源空余动态生成。

本文通过对云原生网络特征的采集与分析，基于Kubernetes和eBPF设计与研发了一套具备根据网络资源的状态调度计算资源、多云多地区负载高可用部署的模型，满足云原生网络成本优化的需求，使得模型初步具备了对以云原生网络为例的云原生应用系统的统一云化承载与运维的系统原型能力。此模型的原型实现证明了该结构的可实施性，云原生技术既能对网络服务灵活管理，也可降低网络资源成本，对多云租户具有较好的经济价值。

[1] 中国信息通信研究院. 云原生发展白皮书（2020年）[R]. 2020.

China Academy for Information and Communications Technology. Cloud native development white paper (2020) [R]. 2020.

[2] RIOS J, JHA S, SHWARTZ L. Localizing and explaining faults in micro services using distributed tracing[C]//Proceedings of 2022 IEEE 15th International Conference on Cloud Computing (CLOUD). Piscataway: IEEE Press, 2022: 489-499.

[3] eBFP: extended berkeley packet filter[EB]. 2022.

[4] BE A, MG B, ZZ A. Evaluating and reducing cloud waste and cost—a data-driven case study from Azure workloads[J]. Sustainable Computing: Informatics and Systems, 2022, 35: 100708.

[5] LI W, LI G J, YU X F. A fast traffic classification method based on SDN network[M]. Electronics, Communications and Networks IV.U.S.A: CRC Press, 2015: 223-229.

[6] WANG F, LIU B, ZHANG L J, et al. Dynamic routing and spectrum assignment based on multilayer virtual topology and ant colony optimization in elastic software-defined optical networks[J]. Optical Engineering, 2017, 56(7): 076111.

[7] PARSAEI M R, MOHAMMADI R, JAVIDAN R. A new adaptive traffic engineering method for telesurgery using ACO algorithm over Software Defined Networks[J]. LaRechercheEur opéenneEn Télémédecine, 2017, 6(3/4): 173-180.

[8] WANG J C, DE LAAT C, ZHAO Z M. QoS-aware virtual SDN network planning[C]//Proceedings of 2017 IFIP/IEEE Symposium on Integrated Network and Service Management (IM). Piscataway: IEEE Press, 2017: 644-647.

[9] CAO J Y, ZHANG Y, AN W, et al. VNF placement in hybrid NFV environment: modeling and genetic algorithms[C]//Proceedings of 2016 IEEE 22nd International Conference on Parallel and Distributed Systems (ICPADS). Piscataway: IEEE Press, 2017: 769-777.

[10] CARPIO F, DHAHRI S, JUKAN A. VNF placement with replication for Loac balancing in NFV networks[C]//Proceedings of 2017 IEEE International Conference on Communications (ICC). Piscataway: IEEE Press, 2017: 1-6.

[11] RANKOTHGE W, MA J F, LE F, et al. Towards making network function virtualization a cloud computing service[C]//Proceedings of 2015 IFIP/IEEE International Symposium on Integrated Network Management (IM). Piscataway: IEEE Press, 2015: 89-97.

[12] YI B, WANG X, LI K, et al. A comprehensive survey of network function virtualization[J]. Computer Networks, 2018(133): 212-262.

[13] MIANO S, RISSO F, BERNAL M V, et al. A framework for eBPF-based network functions in an era of micro services[J]. IEEE Transactions on Network and Service Management, 2021, 18(1): 133-151.

[14] MAYER A, LORETI P, BRACCIALE L, et al. Performance Monitoring with Hˆ2: hybrid Kernel/eBPF data plane for SRv6 based Hybrid SDN[J]. Computer Networks, 2021(185): 107705.

[15] DRORI I, KHARKAR A, SICKINGER W R, et al. Learning to solve combinatorial optimization problems on real-world graphs in linear time[C]//Proceedings of 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA). Piscataway: IEEE Press, 2021: 19-24.

[16] VESSELINOVA N, STEINERT R, PEREZ-RAMIREZ D F, et al. Learning combinatorial optimization on graphs: a survey with applications to networking[J]. IEEE Access, 2020(8): 120388-120416.

Cost optimization model for multi-cloud network based on Kubernetes

GAO Ming, LIU Ming, CHEN Yangting, WANG Weiming

School of Information and Electronic Engineering, Zhejiang Gongshang University, Hangzhou 310018, China

The cloud-native scheduling system, represented by Kubernetes, is widely used by cloud tenants in a multi-cloud environment. The problem of network observation becomes more and more serious, especially the cost of network traffic across cloud and region. In Kubernetes, the eBPF technology was introduced to collect the network data features of kernel state of operating system to solve the network observation problem, and then the network data features were modeled as QAP, a combination of heuristic and stochastic optimization was used to obtain the best near optimal solution in a real-time computing scenario. This model is superior to the Kubernetes native scheduler in the cost optimization of network resources, which is based on the scheduling strategy of computing resources only, and increases the complexity of scheduling links in a controllable range, effectively reduces the cost of network resources in a multi-cloud area deployment environment.

Kubernetes, eBPF, multi-cloud network, quadratic assignment problem

TP393

A

10.11959/j.issn.1000–0801.2023028

高明（1979-），男，博士，浙江工商大学信息与电子工程学院副教授、网络系主任，主要研究方向为新型网络体系架构和工业互联网。

刘铭（1997-），男，浙江工商大学信息与电子工程学院硕士生，主要研究方向为新型网络体系架构和云原生网络。

陈泱婷（1998-），女，浙江工商大学信息与电子工程学院硕士生，主要研究方向为软件定义网络。

王伟明（1964-），男，博士，浙江工商大学信息与电子工程学院教授，主要研究方向为新一代网络体系结构和开放可编程网络。

The National Natural Science Foundation of China (No.61871468), The Basic Public Welfare Research Program of Zhejiang Province (No.LGG20F010015), The Key Laboratory of Network Standards and Applied Technology Foundation of Zhejiang Province (No.2013E10012)

2022-11-02；

2023-02-09

国家自然科学基金资助项目（No.61871468）；
浙江省基础公益研究计划项目（No.LGG20F010015）；
浙江省新型网络标准与应用技术重点实验室基金资助项目（No.2013E10012）

猜你喜欢多云计算资源网络资源基于模糊规划理论的云计算资源调度研究科学技术创新(2021年18期)2021-06-23向日葵·成长·礼物作文周刊·小学一年级版(2020年20期)2020-09-02改进快速稀疏算法的云计算资源负载均衡微型电脑应用(2019年10期)2019-10-23基于Wi-Fi与Web的云计算资源调度算法研究计算机测量与控制(2017年12期)2018-01-05耦合分布式系统多任务动态调度算法计算机技术与发展(2017年12期)2017-12-20何氏“十全大补粥”小学生作文·小学低年级适用(2016年4期)2017-01-16网络资源在高中班级管理中的运用中国教育技术装备(2016年15期)2016-03-01谈网络资源在大学计算机教学中的应用新教育时代电子杂志(学生版)(2015年31期)2015-12-20网络资源在语文综合性学习中的运用语文教学与研究(2014年7期)2014-02-28对等网络资源搜索模型研究电子设计工程(2014年18期)2014-02-27