基于Kubernetes的多云網絡成本優(yōu)化模型

高明，劉銘，陳泱婷，王偉明

基于Kubernetes的多云網絡成本優(yōu)化模型

高明，劉銘，陳泱婷，王偉明

（浙江工商大學信息與電子工程學院，浙江 杭州 310018）

以Kubernetes為代表的云原生編排系統(tǒng)在多云環(huán)境中被云租戶廣泛使用，隨之而來的網絡觀測性問題愈發(fā)突出，跨云跨地區(qū)的網絡流量成本尤為突出。在Kubernetes中引入擴展的伯克利數(shù)據包過濾器（extended Berkeley packet filter，eBPF）技術采集操作系統(tǒng)內核態(tài)的網絡數(shù)據特征解決網絡觀測問題，隨后將網絡數(shù)據特征建模為二次分配問題（quadratic assignment problem，QAP），使用啟發(fā)式搜索與隨機搜索組合的方法在實時計算的場景下求得最佳近優(yōu)解。此模型在網絡資源成本優(yōu)化中優(yōu)于Kubernetes原生調度器中僅基于計算資源的調度策略，在可控范圍內增加了調度鏈路的復雜度，有效降低了多云多地區(qū)部署環(huán)境中的網絡資源成本。

Kubernetes；eBPF；多云網絡；二次分配問題

0 引言

云原生模式是面向云進行軟件工程設計的一種思想理念，是一種充分發(fā)揮云效能的最佳實踐，用于幫助企業(yè)構建彈性可靠、松耦合、易管理的軟件系統(tǒng)，從而提升軟件的交付效率，降低軟件的運維復雜度[1]。Gartner行業(yè)數(shù)據顯示：到2025年，將有超過95%的新數(shù)字項目以云原生平臺為基礎設施，遠高于2021年40%的比例[2]。

以Kubernetes為代表的云原生編排系統(tǒng)已被廣泛應用在云中，各大云廠商均推出了云原生編排系統(tǒng)產品，如Google的GKE（Google Kubernetes引擎）、Microsoft的AKS（Azure Kubernetes服務）、Amazon的EKS（Elastic Kubernetes服務）、阿里云的ACK（阿里云容器服務Kubernetes版）以及華為云的CEE（云容器引擎）。隨之而來的網絡觀測性問題愈發(fā)突出，云租戶難以感知云原生網絡的實際帶寬及流量畫像。擴展的伯克利數(shù)據包過濾器（extended Berkeley packet filter，eBPF）技術的面世推動了云原生可觀測性的發(fā)展，使得網絡觀測性問題的解決成為可能。2014年eBPF代碼合入Linux3.18內核的主分支，新的Linux內核加進去的內核觀測功能，從系統(tǒng)內核層讀取網絡數(shù)據包，從而觀測到云原生編排系統(tǒng)集群內部服務之間的相互調用關系與調用頻率，有效解決了云原生網絡的觀測問題[3]。

此外，沒有任何一家云廠商在云的可靠性方面可保證100%的服務等級協(xié)定（service level agreement，SLA），但通過云廠商歷年的公開事故報告統(tǒng)計可發(fā)現(xiàn)，幾乎不存在所有云在同一時刻均不可用的情況。所以，云租戶為確保服務的實時可用，已逐漸采用多云部署的方案。

云原生編排系統(tǒng)通?；谟嬎阗Y源進行服務調度，而非基于網絡資源進行服務調度，因此在多云部署的具體實踐中，跨云跨地區(qū)的網絡流量成本居高不下，網絡資源成本優(yōu)化問題亟待解決[4]。針對上述問題，本文提出了一種基于Kubernetes的多云網絡成本優(yōu)化模型，目標是為云租戶降低使用多云、多地區(qū)、多數(shù)據中心之間云網絡資源的經濟成本，該模型的工作步驟如下。

步驟1 基于Kubernetes進行多云多地區(qū)服務部署，在操作系統(tǒng)內核態(tài)通過eBPF指標采集器實時采集不同服務之間的網絡數(shù)據包，并解析數(shù)據包頭部的元數(shù)據，生成含網絡通信數(shù)據包數(shù)量的權重網絡拓撲。

步驟2 將權重網絡拓撲的數(shù)據特征數(shù)學建模為二次分配問題（quadratic assignment problem，QAP）。

步驟3 使用蟻群優(yōu)化（ant colony optimization，ACO）算法、模擬退火（simulated annealing，SA）算法、遺傳算法（genetic algorithm，GA）、免疫算法（immune algorithm，IA）4種啟發(fā)式搜索算法與隨機優(yōu)化（stochastic optimization，SO）并行的方式計算每一個時刻的數(shù)據特征，計算持續(xù)的時間為一個單位時刻，最終采用最佳算法的近優(yōu)解，并生成使全局網絡資源經濟成本最小的計算資源調度方案。

步驟4 計算資源調度方案進入Kubernetes調度器隊列，在下一時刻結束時對此調度方案進行評估，階段性反饋成本優(yōu)化率用于優(yōu)化模型。

實驗數(shù)據表明，此模型在網絡資源成本優(yōu)化中優(yōu)于基于計算資源的調度方法，有效降低了多云多地區(qū)部署環(huán)境中的網絡資源成本，雖然增加了調度鏈路的復雜性，但在當前樣本數(shù)據規(guī)模下，其調度鏈路復雜度帶來的計算資源用量水位的上升是固定可調控的。

1 相關工作

目前有大量文獻對網絡資源成本優(yōu)化問題做出了深入的研究。文獻[5]通過將深度強化學習原理引入軟件定義網絡的路由過程優(yōu)化網絡資源成本。文獻[6-8]通過蟻群算法、遺傳算法、粒子群算法等啟發(fā)式算法進行路由優(yōu)化降低網絡資源成本。文獻[9]提出了混合虛擬網絡環(huán)境的概念，使用遺傳算法部署虛擬網絡功能（virtual network function，VNF），并設計了4種遺傳算法用于最小化帶寬開銷和最大化鏈路利用率優(yōu)化降低網絡資源成本。文獻[10]利用復制的方式部署VNF保證網絡的負載均衡，并為大型網絡設計了遺傳算法優(yōu)化降低網絡資源成本。文獻[11]通過遺傳算法在云數(shù)據中心動態(tài)部署VNF，最大限度地利用網絡資源優(yōu)化降低網絡資源成本。

上述文獻主要通過優(yōu)化路由算法的方式降低網絡資源的傳輸成本，但在多云網絡環(huán)境的應用中存在阻礙，首先云租戶通常無法更改云廠商設定的網絡路由策略等基礎設施，其次云廠商網絡通?；诟采w網絡（Overlay）實現(xiàn)彈性網絡，即在現(xiàn)有物理網絡的技術上創(chuàng)建的虛擬或邏輯網絡，從而導致云租戶無法感知物理網絡的真實帶寬水位。文獻[12]提出了一種通過編排VNF資源并將其合理部署在物理網絡中的方式，通過調整計算資源的位置達到了優(yōu)化網絡資源成本的效果，此類研究具備多云環(huán)境的應用條件。

本文基于多云環(huán)境研究，在網絡成本的優(yōu)化方案中通過不改變網絡資源拓撲僅改變計算資源位置的方法，進一步實現(xiàn)計算資源的位置隨時間及流量的變化進行動態(tài)調整，從而降低網絡資源的經濟成本。該方案在物理機器和虛擬機部署階段實現(xiàn)的時間成本較高，而基于云原生技術部署服務可實現(xiàn)毫秒級跨云跨地區(qū)調度服務，使此方案的實現(xiàn)成為可能。

2 系統(tǒng)架構

模型采用Kubernetes云原生編排系統(tǒng)作為基礎設施，以Kubernetes中最小可調度的計算單元（Pod）之間的流量特征為研究對象，實現(xiàn)云原生網絡資源成本優(yōu)化工作的實時計算，并根據最佳近優(yōu)解分時刻調度計算資源。模型的系統(tǒng)架構如圖1所示，自下而上由數(shù)據生產、數(shù)據采集、數(shù)據存儲、數(shù)據處理、基礎支撐、功能服務與數(shù)據接口組成。

圖1 系統(tǒng)架構

網絡資源成本優(yōu)化的基礎是網絡資源的數(shù)據信息，首要任務就是采集網絡資源的數(shù)據并進行結構化用于數(shù)據分析。采集云原生網絡數(shù)據包的核心技術是eBPF，在經典的網絡數(shù)據包采集工具鏈中，通常在用戶態(tài)采集網絡數(shù)據包，而通過eBPF在更靠近硬件網卡的內核態(tài)位置采集網絡數(shù)據比用戶態(tài)采集數(shù)據具有更高的性能優(yōu)勢[13-14]。

圖1中的數(shù)據生產和數(shù)據采集模塊屬于云原生網絡特征觀測子系統(tǒng)，是模型的數(shù)據來源。云原生網絡特征觀測子系統(tǒng)在多云多地區(qū)的計算資源池內通過eBPF指標采集器從內核態(tài)采集業(yè)務服務與網絡功能服務之間的網絡數(shù)據包，并將其輸出到Cilium網絡功能服務中，由Fluent Bit數(shù)據轉發(fā)器將Cilium內的網絡數(shù)據包數(shù)據寫入Kafka內存型消息隊列，并使用Logstash實時數(shù)據傳輸管道工具消費消息隊列內的數(shù)據，將元數(shù)據的關鍵字段清洗后轉儲到分布式時間序列檢索引擎（Elastic search engine，ES）集群中，Kibana數(shù)據檢索工具可以對ES集群中的全量數(shù)據進行查詢。在數(shù)據處理的過程中讀取ES集群中的數(shù)據，處理完將數(shù)據落庫到PostgreSQL結構化數(shù)據庫中。

最終處理完成的網絡數(shù)據核心指標包含每個服務被哪些服務連接、連接了哪些服務以及服務之間的連接頻率。根據這些指標可以通過調整服務運行的時間和空間優(yōu)化計算資源成本和網絡資源成本。調整服務運行的時間，例如，時效性要求較低且數(shù)據量較少的服務可定時運行服務，處理完數(shù)據后銷毀服務，從而有效節(jié)省彈性計算資源成本。調整服務運行的空間，例如，通信頻率較高的兩個服務的物理間隔位置較遠，可增加服務之間的親和性使其運行在同一臺宿主機，降低網絡資源成本。

模型數(shù)據流圖如圖2所示，在多家云廠商（Cloud）的多個地區(qū)（Region）的多個數(shù)據中心（Zone）的多個Kubernetes工作平面節(jié)點（Node）中的操作系統(tǒng)內核態(tài)采集到網絡數(shù)據包后，將數(shù)據特征清洗并適配蟻群優(yōu)化算法、模擬退火算法、遺傳算法和免疫算法4種啟發(fā)式搜索算子以及隨機搜索算子進行計算，并行在一單位時刻時間內迭代多次取得近優(yōu)解，獲取最佳最優(yōu)解后生成計算資源新的放置位置，每個時刻循環(huán)往復。根據業(yè)務需求一單位時刻定義為5 min，時間太短將導致調度頻繁，時間太長將導致模型無法及時對流量的變化產生反饋。最佳算子的產出結果是下一個時刻的目標計算資源的位置狀態(tài)，調度器以受控速率改變計算資源的實際位置狀態(tài)，使其達到期望位置狀態(tài)，本文的調度器復用Kubernetes原生計算資源調度器。

圖2 模型數(shù)據流圖

3 數(shù)學建模

在云原生環(huán)境中的成本主要分為計算資源成本和網絡資源成本兩個部分，本文重點在固定計算資源成本的前提下分時刻優(yōu)化網絡資源成本。在優(yōu)化網絡資源成本時將Pod所在的計算資源池的子集（計算資源插槽，Slot）之間的網絡流量價格作為Pod之間的流量成本權重，每個Slot最大僅可容納1個Pod，且Slot具備流量成本權重表中的位置屬性，流量成本權重見表1。

表1 流量成本權重

本文通過計算Pod之間的通信成本和流量的方式調整Pod位置，以此優(yōu)化網絡資源成本，因此該方法可建模為組合優(yōu)化中的QAP。組合優(yōu)化是計算資源調度策略實施過程中重要的步驟，其過程是結合不同的調度目標及成本約束給出最優(yōu)的組合權重[15]。由于QAP已被證明為NP難問題，無法在多項式時間內計算得到準確結果[16]，而網絡流量的數(shù)據特征具備時效性，計算資源的調度方案要求實時性，所以最終方案的實施需要兼顧時間成本和優(yōu)化效率。

4 模型建立

模型的核心是在限定時間內求解不定規(guī)模的QAP，在無法得知最優(yōu)解的情況下獲取最佳近優(yōu)解。

云上跨Cloud、Region、Node、Zone、Pod之間的流量均屬于東西向流量，模型的本質是降低云原生網絡東西向流量的成本。模型需要在每個時刻決策把每一個Pod分配到指定的Slot，每個Slot具備不同的Node、Zone、Region和Cloud位置，并且每個位置屬性均有固定配額，存在資源門限，一旦達到限制，則無法調度。因此，合理分配所有時刻的所有Pod并調度到指定Slot，降低總網絡資源成本是模型的主要工作。

網絡資源成本最低的極限方案是把所有計算資源都放在同一個位置，然而單位置有計算資源上限瓶頸，無法滿足大規(guī)模計算場景，而且單地區(qū)或者單云的方案存在限額和災備問題，模型需要滿足以上約束條件。

表2 示例Pod位置屬性

綜合對比上述5種搜索算子和僅基于計算資源的算子，即原生（Native）算子，啟發(fā)式搜索和隨機搜索的結果均存在隨機性，僅基于計算資源的算子存在大量網絡資源成本浪費情況。示例樣本網絡成本優(yōu)化算子對比如圖3所示，由于示例數(shù)據采用了較小規(guī)模的樣本，5種搜索算子相對于Native算子均取得了較好的優(yōu)化效果，其中GA算子和SA算子優(yōu)化效果最佳，都將此樣本初始的網絡資源成本3 120元優(yōu)化到了794元，優(yōu)化率約為74.55%。

圖4 示例樣本計算資源調度方案對比

5 模型驗證

模型驗證模擬實驗環(huán)境使用4臺樹莓派模擬3云29地區(qū)數(shù)據中心共計174個Slot，使用1臺二層交換機模擬多云多地區(qū)之間的專線網絡，實驗環(huán)境硬件設備信息見表3。

表3 實驗環(huán)境硬件設備信息

本實驗中樹莓派主板操作系統(tǒng)的版本采用了2022年3月發(fā)布的openEuler 22.03 LTS，此版本中Linux內核采用了5.10版本，Linux內核自4.16版本起支持eBPF功能?；趏penEuler Linux操作系統(tǒng)部署了Kubernetes云原生編排系統(tǒng)，并在編排系統(tǒng)內部署實驗環(huán)境軟件，實驗環(huán)境軟件版本信息見表4。

表4 實驗環(huán)境軟件版本信息

模擬實驗首先從優(yōu)化算子、迭代時間、迭代次數(shù)3個維度組合的方式對樣本進行求解，形成多樣化的對比實驗任務。采樣時刻0、5、10、60、150和280的樣本數(shù)據，分別使用5種搜索算子對樣本迭代300次，對比實驗結果，實驗任務見表5。

表5 實驗任務

表5實驗任務中的樣本時刻算子成本優(yōu)化效果如圖6所示，在Pod規(guī)模為174的場景中，對其中6份樣本數(shù)據迭代運算300次，并進行效果對比。圖6中，GA算子第88次計算結果和IA算子在第219次計算結果的算子排名與第300次計算結果的算子排名無較大差異，因此，同時取300次迭代數(shù)據進行算子評估。其中，ACO算子在試驗結果中有5/6的樣本取得了最佳近優(yōu)解，GA算子在1/6的樣本中取得了最佳近優(yōu)解，IA算子、SA算子和SO算子在小迭代次數(shù)時存在最佳近優(yōu)解的情況，特別是50次以下的迭代，適用于求解時間要求較高的場景。當Pod資源規(guī)模較大，無法在限定時間內取得優(yōu)化效果時，需要對樣本數(shù)據進行拆分處理，取多個樣本數(shù)據子集的局部最優(yōu)解作為全局最優(yōu)解。

圖6 樣本時刻算子成本優(yōu)化效果

使用ACO算子和GA算子對全量樣本數(shù)據進行計算，并保存每次的迭代的結果，參照原生調度方案對比每個時刻搜索算子的優(yōu)化效果，每個時刻算子優(yōu)化對比如圖7所示，兩種算子最優(yōu)解均優(yōu)于原生調度方案，因此，混合算子最優(yōu)解更優(yōu)于原生調度方案。

圖7 每個時刻算子優(yōu)化對比

綜合全部樣本數(shù)據，可得24 h成本優(yōu)化情況，全量樣本成本優(yōu)化對比如圖8所示，ACO算子、GA算子以及ACO算子和GA算子混合的算子優(yōu)化率分別是89.18%、86.85%和89.23%，采用ACO算子和GA算子混合為最佳組合算子。

圖8 全量樣本成本優(yōu)化對比

由于本文定義一個時刻單位為5 min，在限定單位時間內，取ACO算子和GA算子比例為5:1的數(shù)量進行模型部署，可取得最佳結果。使用Kubernetes編排系統(tǒng)內計算資源的空余水位部署算子，算子的副本數(shù)量按照比例根據計算資源空余動態(tài)生成。

6 結束語

本文通過對云原生網絡特征的采集與分析，基于Kubernetes和eBPF設計與研發(fā)了一套具備根據網絡資源的狀態(tài)調度計算資源、多云多地區(qū)負載高可用部署的模型，滿足云原生網絡成本優(yōu)化的需求，使得模型初步具備了對以云原生網絡為例的云原生應用系統(tǒng)的統(tǒng)一云化承載與運維的系統(tǒng)原型能力。此模型的原型實現(xiàn)證明了該結構的可實施性，云原生技術既能對網絡服務靈活管理，也可降低網絡資源成本，對多云租戶具有較好的經濟價值。

[1] 中國信息通信研究院. 云原生發(fā)展白皮書（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-），男，博士，浙江工商大學信息與電子工程學院副教授、網絡系主任，主要研究方向為新型網絡體系架構和工業(yè)互聯(lián)網。

劉銘（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）