基于拥塞博弈的微服务运行时资源管理方法

doi:10.3969/j.issn.0372-2112.2019.07.013

电子学报 ›› 2019, Vol. 47 ›› Issue (7): 1497-1505.DOI: 10.3969/j.issn.0372-2112.2019.07.013

基于拥塞博弈的微服务运行时资源管理方法

罗睿辞¹, 叶蔚², 刘学洋², 孙基男², 张世琨²

1. 北京大学信息科学技术学院, 北京 100871;
2. 北京大学软件工程国家工程研究中心, 北京 100871

收稿日期:2018-05-11 修回日期:2018-11-28 出版日期:2019-07-25
- 作者简介:
- 罗睿辞 男,1988年生于湖南株洲.北京大学信息科学技术学院博士研究生,主要研究领域为基于Web的软件工程和软件体系结构;叶蔚男,1985年生于江西全南.北京大学软件工程国家工程中心副教授.主要研究领域为基于Web的软件工程、软件体系结构、应用集成等.E-mail:wye@pku.edu.cn;刘学洋 男,1978年生于湖北钟祥.北京大学软件工程国家工程研究中心副教授,主要研究领域为软件工程、信息安全等.E-mail:liuxueyang@pku.edu.cn

A Runtime Resource Management Approach of Microservices Based on Congestion Game

LUO Rui-ci¹, YE Wei², LIU Xue-yang², SUN Ji-nan², ZHANG Shi-kun²

1. School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China;
2. National Engineering Research Center for Software Engineering, Peking University, Beijing 100871, China

Received:2018-05-11 Revised:2018-11-28 Online:2019-07-25 Published:2019-07-25

摘要/Abstract

摘要： 随着云计算技术的不断发展，微服务体系结构逐渐成为一种广泛应用的软件设计风格.在基于微服务的应用系统中，微服务数量众多、相互依赖关系复杂、持续在线演化等特征使得微服务运行时资源的有效管理面临新的挑战.本文充分考虑微服务之间的关系特征，提出了一种基于拥塞博弈理论的运行时资源管理方法.首先，对微服务之间的复杂依赖关系进行建模，给出了带权有向无环图描述的微服务调用关系模型；然后，基于微服务关系调用模型对各个微服务的请求到达频率进行计算，并用排队论中的M/G/1队列刻画微服务处理请求的过程，进而设计了一种以服务等级协议（Service Level Agreement）满足程度为衡量标准的服务收益函数；最后利用拥塞博弈模型刻画对计算资源的竞争关系，给出了求解博弈的纳什均衡状态的多项式算法.实验表明，该方法在计算资源有限的场景下可以有效地提高微服务应用的整体性能.

关键词: 微服务体系结构, 资源管理, 博弈论

Abstract: With the continuous development of cloud computing technology, the microservice architecture has gradually become a widely used software design style. In microservice-based applications, different microservices collaborate with one another via interface calls, but they may also compete for limited resources during online evolvement. This poses new challenges for allocating resources efficiently during runtime. To tackle the problem, we propose a novel approach based on congestion game. Firstly, we use a weighted directed acyclic graph to model the inter-relationship of the microservices that compose an application. Then we use M/G/1 queue in queue theory to describe the arrival process of access requests, and combine it with the above graph to calculate the arrival rate of access requests to each microservice, which in turn is used to estimate response time in a newly-designed microservice revenue function. Finally, we define resources competing problem as a congestion game where each microservice is a player aiming to maximize its revenue, and propose an algorithm to find Nash equilibrium in polynomial time. Experiment results show that our approach can effectively improve the overall performance of the system with limited resources.

Key words: microservice architecture, resource management, game theory

中图分类号:

TP311

罗睿辞, 叶蔚, 刘学洋, 等. 基于拥塞博弈的微服务运行时资源管理方法[J]. 电子学报, 2019, 47(7): 1497-1505.

LUO Rui-ci, YE Wei, LIU Xue-yang, et al. A Runtime Resource Management Approach of Microservices Based on Congestion Game[J]. Acta Electronica Sinica, 2019, 47(7): 1497-1505.

参考文献

[1] 王怀民,史佩昌,丁博,尹刚,史殿习.软件服务的在线演化[J].计算机学报,2011,34(02):318-328.
[2] 梅宏,黄罡,张路,张伟.ABC:一种全生命周期软件体系结构建模方法[J].中国科学:信息科学,2014,44(05):564-587.
[3] Dragoni N,Lanese I,Larsen S T,et al.Microservices:How to make your application scale[A].International Andrei Ershov Memorial Conference on Perspectives of System Informatics[C].Springer,Cham,2017.95-104.
[4] Altman E,Boulogne T,El-Azouzi R,et al.A survey on networking games in telecommunications[J].Computers & Operations Research,2006,33(2):286-311.
[5] Stolyar A L,Zhong Y.An infinite server system with general packing constraints:Asymptotic optimality of a greedy randomized algorithm[A].The 51st Annual Allerton Conference on Communication,Control,and Computing (Allerton)[C].US:IEEE,2013.575-582.
[6] Li Y,Tang X,Cai W.Dynamic bin packing for on-demand cloud resource allocation[J].IEEE Transactions on Parallel and Distributed Systems,2016,27(1):157-170.
[7] Chaisiri S,Lee B S,Niyato D.Optimal virtual machine placement across multiple cloud providers[A].2009 IEEE Asia-Pacific Services Computing Conference (APSCC)[C].US:IEEE,2009.103-110.
[8] Kansal S,Kumar H,Kaushal S,et al.Genetic algorithm-based cost minimization pricing model for on-demand IaaS cloud service[J].The Journal of Supercomputing,2018:1-26.
[9] Gupta A,Garg R.Load balancing based task scheduling with ACO in cloud computing[A].2017 International Conference on Computer and Applications (ICCA)[C].US:IEEE,2017.174-179.
[10] Sheikholeslami F,Navimipour N J.Service allocation in the cloud environments using multi-objective particle swarm optimization algorithm based on crowding distance[J].Swarm and Evolutionary Computation,2017,35:53-64.
[11] Hoenisch P,Schulte S,Dustdar S,et al.Self-adaptive resource allocation for elastic process execution[A].2013 IEEE Sixth International Conference on Cloud Computing[C].US:IEEE,2013.220-227.
[12] Baresi L,Guinea S,Leva A,et al.A discrete-time feedback controller for containerized cloud applications[A].Proceedings of the 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering[C].US:ACM,2016.217-228.
[13] 俞岭,谢奕,陈碧欢,等.基于前馈和反馈控制运行时虚拟资源动态分配[J].计算机研究与发展,2015,52(4):889-897.
[14] Ardagna D,Ciavotta M,Passacantando M.GeneralizedNash equilibria for the service provisioning problem in multi-cloud systems[J].IEEE Transactions on Services Computing,2017,10(3):381-395.
[15] Wei G,Vasilakos A V,Zheng Y,et al.A game-theoretic method of fair resource allocation for cloud computing services[J].The Journal of Supercomputing,2010,54(2):252-269.
[16] Milchtaich I.Congestion games with player-specific payoff functions[J].Games and Economic Behavior,1996,13(1):111-124.
[17] Carnell J.Spring Microservices in Action[M].Manning Publications Co,2017.
[18] Bolch G,Greiner S,De Meer H,et al.Queueing Networks and Markov Chains:Modeling and Performance Evaluation with Computer Science Applications[M].John Wiley & Sons,2006.
[19] Remi Cadene,David Panou.LI328-Simpler Twitter with JavaEE,JQuery,MySQL,MongoDB[OL].https://github.com/Cadene/Pwitter,2018.

基于拥塞博弈的微服务运行时资源管理方法

A Runtime Resource Management Approach of Microservices Based on Congestion Game

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张清华, 黄志康, 高满, 艾志华. 基于不确定性与错误分类率博弈的序贯三支决策模型[J]. 电子学报, 2022, 50(5): 1033-1041.
[2]	郑涛, 蒙祖尧, 张宏科. 基于多信道绑定的应急终端协同方法[J]. 电子学报, 2022, 50(11): 2645-2652.
[3]	陈亮, 李峰, 任保全, 杨建喜. 软件定义物联网研究综述[J]. 电子学报, 2021, 49(5): 1019-1032.
[4]	刘雷, 陈晨, 冯杰, 肖婷婷, 裴庆祺. 车载边缘计算卸载技术研究综述[J]. 电子学报, 2021, 49(5): 861-871.
[5]	张恒巍, 黄世锐. Markov微分博弈模型及其在网络安全中的应用[J]. 电子学报, 2019, 47(3): 606-612.
[6]	李秋贤, 田有亮, 王缵. 基于全同态加密的理性委托计算协议[J]. 电子学报, 2019, 47(2): 470-474.
[7]	黄健明, 张恒巍. 基于随机演化博弈模型的网络防御策略选取方法[J]. 电子学报, 2018, 46(9): 2222-2228.
[8]	张恒巍, 李涛, 黄世锐. 基于攻防微分博弈的网络安全防御决策方法[J]. 电子学报, 2018, 46(6): 1428-1435.
[9]	张恒巍, 黄健明. 基于Markov演化博弈的网络防御策略选取方法[J]. 电子学报, 2018, 46(6): 1503-1509.
[10]	汪志勇, 张沪寅, 徐宁, 郝圣. 认知无线电网络中基于随机学习博弈的信道分配与功率控制[J]. 电子学报, 2018, 46(12): 2870-2877.
[11]	陈白, 辛敏洁, 刘伟静, 姚宁, 郝晓辰, 汝小月. 一种基于链路质量的自维护拓扑控制博弈算法[J]. 电子学报, 2016, 44(9): 2227-2234.
[12]	卜湛, 伍之昂, 曹杰, 朱桂祥. 在线评论情感计算与博弈预测[J]. 电子学报, 2015, 43(12): 2530-2535.
[13]	贾亚男, 岳殿武. 博弈论框架下认知小蜂窝网络的动态资源分配算法[J]. 电子学报, 2015, 43(10): 1911-1917.
[14]	匡桂娟, 曾国荪, 曹洁, 熊焕亮. 基于图匹配理论的云任务与云资源满意“婚配”方法[J]. 电子学报, 2014, 42(8): 1582-1586.
[15]	刘静, 汤光明. 大容量自适应隐写对抗的博弈研究[J]. 电子学报, 2014, 42(10): 1963-1969.