基于瓶颈感知的多级反馈队列Coflow调度机制

doi:10.19678/j.issn.1000-3428.0062472

计算机工程 ›› 2022, Vol. 48 ›› Issue (10): 193-201,211. doi: 10.19678/j.issn.1000-3428.0062472

基于瓶颈感知的多级反馈队列Coflow调度机制

都繁杰¹, 李静¹, 郭志勇², 任颖文², 尹晓宇³, 董小菱³

1. 南京航空航天大学计算机科学与技术学院, 南京 211106;
2. 国家电网有限公司信息通信分公司, 北京 100761;
3. 国网安徽省电力有限公司信息通信分公司, 合肥 231299

收稿日期:2021-08-25 修回日期:2021-10-18 发布日期:2021-11-03
作者简介:都繁杰(1997—),男,硕士研究生,主研方向为云计算、流量调度;李静(通信作者),副教授、博士;郭志勇,工程师;任颖文、尹晓宇、董小菱,助理工程师。
基金资助:
国家电网有限公司科技项目“业务应用改造上云与全链路运行分析技术研究”（SGAHXTOOXYQT2100008）。

Coflow Scheduling Mechanism for Multi-Level Feedback Queue Based on Bottleneck Perception

DU Fanjie¹, LI Jing¹, GUO Zhiyong², REN Yingwen², YIN Xiaoyu³, DONG Xiaoling³

1. College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China;
2. Information and Communication Branch of State Grid Corporation, Beijing 100761, China;
3. Information and Communication Branch of State Grid Anhui Electric Power Co., Ltd., Hefei 231299, China

Received:2021-08-25 Revised:2021-10-18 Published:2021-11-03

摘要/Abstract

摘要： Coflow作为并行计算框架的典型流量模型，降低Coflow的完成时间（CCT）成为云计算领域的研究热点。现有Coflow调度机制未考虑云数据中心内网络瓶颈问题，容易造成网络拥塞，导致CCT增加。针对该问题，构建基于瓶颈感知的Coflow调度机制Bamq。利用Lagrange对偶优化Coflow调度模型，以加快Coflow流速并增大吞吐量，从而降低CCT。通过设计多级反馈队列机制，降低吞吐量对网络拥塞产生的影响，根据已发流的大小、宽度和流速信息，构建瓶颈因子以动态调整多级队列的优先级，实现拥塞感知，提高Coflow调度性能。在Facebook真实数据集上进行实验，结果表明，相比Baraat、Varys、Aalo机制，该机制的CCT平均缩短21.3%，吞吐量平均提高17.9%，能够有效提高链路的利用率。

关键词: Coflow调度, 多级反馈队列, 队列稳定性, 流量调度, 云数据中心

Abstract: Coflow is a typical traffic model based on a parallel computing framework.Reducing the Coflow Completion Time (CCT) has become a popular research topic in cloud computing.The existing Coflow scheduling mechanism does not consider the network bottleneck in the cloud data center, which easily causes network congestion and increases the CCT.Hence, Coflow scheduling mechanism, Bamq, based on bottleneck perception is constructed.The Lagrange duality is used to optimize the Coflow scheduling model such that the Coflow flow rate and throughput are increased, whereas the CCT is reduced.The multi-level feedback queue mechanism reduces the effect of throughput on network congestion.Based on the size, width, and flow rate of the sent flow, the bottleneck factor is constructed to dynamically adjust the priority of multi-level queue, realize congestion perception, and enhance the performance of Coflow scheduling.Experiments on the Facebook dataset show that compared with the Baraat, Varys and Aalo mechanisms, the CCT of this mechanism is reduced by 21.3%, whereas the throughput is increased by 17.9% on average.The proposed mechanism can significantly reduce the CCT and effectively improve link utilization.

Key words: Coflow scheduling, multi-level feedback queue, queue stability, flow scheduling, cloud data center

中图分类号:

TP393

都繁杰, 李静, 郭志勇, 任颖文, 尹晓宇, 董小菱. 基于瓶颈感知的多级反馈队列Coflow调度机制[J]. 计算机工程, 2022, 48(10): 193-201,211.

DU Fanjie, LI Jing, GUO Zhiyong, REN Yingwen, YIN Xiaoyu, DONG Xiaoling. Coflow Scheduling Mechanism for Multi-Level Feedback Queue Based on Bottleneck Perception[J]. Computer Engineering, 2022, 48(10): 193-201,211.

https://www.ecice06.com/CN/Y2022/V48/I10/193

图/表 10

参考文献

[1] 李文信, 齐恒, 徐仁海, 等.数据中心网络流量调度的研究进展与趋势[J].计算机学报, 2020, 43(4):600-617. LI W X, QI H, XU R H, et al.Data center network flow scheduling progress and trend[J].Chinese Journal of Computers, 2020, 43(4):600-617.(in Chinese)
[2] ZAHARIA M, CHOWDHURY M, FRANKLIN M J, et al.Spark:cluster computing with working sets[EB/OL].[2021-07-22].http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.374.2156&rep=rep1&type=pdf.
[3] ISARD M, BUDIU M, YUAN Y, et al.Dryad:distributed data-parallel programs from sequential building blocks[EB/OL].[2021-07-22].http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=060CD3BCF423260745F996B762464E19?doi=10.1.1.538.4272&rep=rep1&type=pdf.
[4] DEAN J, GHEMAWAT S.MapReduce:simplified data processing on large clusters[J].Communications of the ACM, 2008, 51(1):107-113.
[5] MURRAY D G, SCHWARZKOPF M, SMOWTON C, et al.CIEL:a universal execution engine for distributed data-flow computing[C]//Proceedings of the 8th Symposium on Networked Systems Design and Implementation.New York, USA:ACM Press, 2011:113-126.
[6] CHOWDHURY M, STOICA I.Coflow:a networking abstraction for cluster applications[C]//Proceedings of the 11th ACM Workshop on Hot Topics in Networks.New York, USA:ACM Press, 2012:31-36.
[7] CHOWDHURY M, ZHONG Y, STOICA I.Efficient Coflow scheduling with Varys[C]//Proceedings of ACM Conference on SIGCOMM.New York, USA:ACM Press, 2014:443-454.
[8] CHOWDHURY M, STOICA I.Efficient Coflow scheduling without prior knowledge[J].ACM SIGCOMM Computer Communication Review, 2015, 45(5):393-406.
[9] DOGAR F R, KARAGIANNIS T, BALLANI H, et al.Decentralized task-aware scheduling for data center networks[J].ACM SIGCOMM Computer Communication Review, 2014, 44(4):431-442.
[10] GAO P X, NARAYAN A, KUMAR G, et al.pHost:distributed near-optimal datacenter transport over commodity network fabric[C]//Proceedings of the 11th ACM Conference on Emerging Networking Experiments and Technologies.New York, USA:ACM Press, 2015:1-12.
[11] ZENG Y, YE B, TANG B, et al.Scheduling Coflows of multi-stage jobs under network resource constraints[J].Computer Networks, 2021, 184:1-10.
[12] HONG Z, LI C, YI B, et al.CODA:toward automatically identifying and scheduling Coflows in the dark[C]//Proceedings of ACM SIGCOMM Conference.New York, USA:ACM Press, 2016:160-173.
[13] ZHANG S, ZHANG S, QIAN Z, et al.Efficient scheduling for multi-stage coflows[J].CCF Transactions on Networking, 2019, 2(2):83-97.
[14] ZHANG J, GUO D, LI K, et al.Coflow scheduling in the multi-resource environment[J].IEEE Transactions on Network and Service Management, 2019, 16(2):783-796.
[15] WANG Z, ZHANG H, SHI X, et al.Efficient scheduling of weighted Coflows in data centers[J].IEEE Transactions on Parallel and Distributed Systems, 2019, 30(9):2003-2017.
[16] WANG S, ZHANG J, HUANG T, et al.Multi-attributes-based Coflow scheduling without prior knowledge[J].IEEE-ACM Transactions on Networking, 2018, 26(4):1962-1975.
[17] WANG L, WANG W.Fair Coflow scheduling without prior knowledge[C]//Proceedings of the 38th International Conference on Distributed Computing Systems.Washington D.C., USA:IEEE Press, 2018:22-32.
[18] SHI L, LIU Y, ZHANG J, et al.Coflow scheduling in data centers:routing and bandwidth allocation[J].IEEE Transactions on Parallel & Distributed Systems, 2021, 32(11):2661-2675.
[19] CHEN Y, WU J.Joint Coflow routing and scheduling in leaf-spine data centers[J].Journal of Parallel and Distributed Computing, 2021, 148:83-95.
[20] LI Y, JIANG H C, TAN H, et al.Efficient online coflow routing and scheduling[C]//Proceedings of the 17th ACM International Symposium.New York, USA:ACM Press, 2016, 161-170.
[21] LIU L, XU H, GAO C, et al.Bottleneck-aware Coflow scheduling without prior knowledge[C]//Proceedings of IEEE Conference on Computer Communications Workshops.Washington D.C., USA:IEEE Press, 2020:50-55.
[22] ZHANG T, SHU R, SHAN Z, et al.Distributed bottleneck-aware coflow scheduling in data centers[J].IEEE Transactions on Parallel and Distributed Systems, 2019, 30(7):1565-1579.
[23] PALOMAR D P, MUNG C.A tutorial on decomposition methods for network utility maximization[J].IEEE Journal on Selected Areas in Communications, 2006, 24(8):1439-1451.
[24] PENG M, YU Y, XIANG H, et al.Energy-efficient resource allocation optimization for multimedia heterogeneous cloud radio access networks[J].IEEE Transactions on Multimedia, 2016, 18(5):879-892.

选择文件类型/文献管理软件名称

选择包含的内容

基于瓶颈感知的多级反馈队列Coflow调度机制

Coflow Scheduling Mechanism for Multi-Level Feedback Queue Based on Bottleneck Perception

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献

相关文章 9

编辑推荐

Metrics

本文评价

[1]	徐啸, 顾玲丽, 陈建平, 傅启明, 陆悠. 一种智能多路径路由及子流分配协同算法[J]. 计算机工程, 2021, 47(9): 136-144,152.
[2]	曹志鹏, 刘勤让, 刘冬培, 张霞. 面向时间敏感网络的流量调度方法[J]. 计算机工程, 2021, 47(7): 168-175,182.
[3]	刘开南. 云数据中心基于任务映射的虚拟机选择策略[J]. 计算机工程, 2019, 45(10): 33-39.
[4]	李文信, 周晓波, 徐仁海, 齐恒, 李克秋. 一种近似最小有效瓶颈优先的Coflow调度机制[J]. 计算机工程, 2019, 45(10): 19-25,32.
[5]	胡志刚, 欧阳晟, 阎朝坤. 云环境下面向能耗降低的资源负载均衡方法[J]. 计算机工程, 2012, 38(5): 53-55.
[6]	梁本来, 杨忠明, 邓家斌, 蔡昭权, 金志平, 梁志标. 基于流量调度的多链路负载均衡算法[J]. 计算机工程, 2011, 37(9): 118-120.
[7]	梁可结;魏文红;王高才. 一种有效的网络多出口流量调度方案[J]. 计算机工程, 2010, 36(5): 116-118,.
[8]	郭小雪, 秦勇, 袁奕. 支持IPv6的大规模链路接入系统应用研究[J]. 计算机工程, 2010, 36(11): 101-104.
[9]	郭小雪;梁根;秦勇;魏文红. 多逻辑链路最大可用带宽比流量调度算法[J]. 计算机工程, 2009, 35(20): 103-105.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于瓶颈感知的多级反馈队列Coflow调度机制

Coflow Scheduling Mechanism for Multi-Level Feedback Queue Based on Bottleneck Perception

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献

相关文章 9

编辑推荐

Metrics

本文评价