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

doi:10.19678/j.issn.1000-3428.0062472

Computer Engineering ›› 2022, Vol. 48 ›› Issue (10): 193-201,211. doi: 10.19678/j.issn.1000-3428.0062472

• Mobile Internet and Communication Technology • Previous Articles Next Articles

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

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

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

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

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

Abstract

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

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

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

CLC Number:

TP393

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.

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

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0062472

http://www.ecice06.com/EN/Y2022/V48/I10/193

Figures/Tables 10

References

[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.

Please choose a citation manager

Content to export