協同流的抽象概念，捕捉多個流的集體行為，被提出且證明了在數據中心引用此抽象概念可以優化數據的傳輸速度。這一抽象概念對於優化平行計算中的通信階段至關重要。在多個網路核心中調度協同流問題是NP-hard的。本文的三個啟發式演算法，都是以縮小協同流完成時間。我們改進了Chen以及Chen的FLPT算法[9]，進一步利用已知的協同流信息。在每個選擇的回合，會觀察當前流量和後續流量在每個網路核心中的鏈路狀態。最初，我們為每個鏈路分配優先值。因此，任兩個流量的關係是依據各自流量所需鏈路的優先級定義的。為了解決不同種類的關係，此研究提出了選擇網路核心的方法。實驗評估模擬了各種協同流組合來評估性能。在實驗結果中，演算法在協同流數量增加時達到了更優的性能，並優Weaver[18]和FLPT[9]算法。

Coflow abstraction, capturing the collective behavior of multiple flows, is proven that can improve data transfer efficiency in data centers. This concept is crucial for optimizing communication stages in parallel computing. The coflow scheduling problem in multi-core is NP-hard. This paper proposes three heuristic algorithms to minimize coflow completion time in identical parallel networks. Our research improve the FLPT algorithm by Chen and Chen by [9] further utilizing information about known coflows: when selecting which core to assign in each iteration, the link state of both the current flow and the subsequent flow are considered for each core. Initially, each link is assigned a priority value. Therefore, the relationship between any two flows is determined based on the priorities of the links. Specifically, the priority values assigned to these links establish the different relationship between the flows. To address various situations, three methods are proposed for assigning flows to the appropriate core. Experimental evaluations simulate various coflow compositions to assess performance. Results show that our heuristic algorithms achieve superior performance, especially with increasing the number of coflows, outperforming both Weaver [18] and the FLPT [9]algorithm.

[1] Saksham Agarwal, Shijin Rajakrishnan, Akshay Narayan, Rachit Agarwal, David Shmoys, and Amin Vahdat. Sincronia: near-optimal network design for coflows. In Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication, SIGCOMM ’18, page 16–29, New York, NY, USA, 2018. Association for Computing Machinery.
[2] SabaAhmadi,SamirKhuller, ManishPurohit, andShengYang. Onschedulingcoflows. Algorithmica, 82(12):3604–3629, 2020.
[3] Afaf Arfaoui, Rachid Elazouzi, Francesco De Pellegrini, Cedric Richier, and Jeremie Leguay. Elite: Near-optimal heuristics for coflow scheduling. In 2022 22nd IEE International Symposium on Cluster, Cloud and Internet Computing (CCGrid), pages 665–674, 2022.
[4] Dhruba Borthakur. The hadoop distributed file system: Architecture and design. Hadoop Project Website, 11(2007):21, 2007.
[5] Chi-Yeh Chen. Improved approximation algorithms for minimizing the total weighted completion time of coflows. arXiv preprint arXiv:2311.11296, 2023.
[6] Chi-Yeh Chen. Improved approximation coflows scheduling algorithms for minimizing the total weighted completion time and makespan in heterogeneous parallel networks. arXiv preprint arXiv:2312.16413, 2023.
[7] Chi-Yeh Chen. Scheduling coflows for minimizing the total weighted completion time in heterogeneous parallel networks. Journal of Parallel and Distributed Computing, 182:104752, 2023.
[8] Chi-Yeh Chen. Efficient approximation algorithms for scheduling coflows with total weighted completion time in identical parallel networks. IEEE Transactions on Cloud Computing, 12(1):116–129, 2024.
[9] Chi-Yeh Chen and Jun Chen. Scheduling coflows for minimizing the makespan in identical parallel networks. arXiv preprint arXiv:2302.06846, 2023. 40
[10] Mosharaf Chowdhury. Coflow-benchmark. https://github.com/coflow/coflow-benchmark.
[11] Mosharaf Chowdhury and Ion Stoica. Coflow: A networking abstraction for cluster applications. In Proceedings of the 11th ACM Workshop on Hot Topics in Networks, pages 31–36, 2012.
[12] Mosharaf Chowdhury and Ion Stoica. Efficient coflow scheduling without prior knowledge. SIGCOMM Comput. Commun. Rev., 45(4):393–406, aug 2015.
[13] Mosharaf Chowdhury, Yuan Zhong, and Ion Stoica. Efficient coflow scheduling with varys. In Proceedings of the 2014 ACM conference on SIGCOMM, pages 443–454, 2014.
[14] Jeffrey Dean and Sanjay Ghemawat. Mapreduce: simplified data processing on large clusters. Communications of the ACM, 51(1):107–113, 2008.
[15] Fahad R. Dogar, Thomas Karagiannis, Hitesh Ballani, and Antony Rowstron. Decentralized task-aware scheduling for data center networks. In Proceedings of the 2014 ACMConferenceonSIGCOMM,SIGCOMM’14,page431–442,NewYork,NY,USA,2014. Association for Computing Machinery.
[16] Rachid El-Azouzi, Francesco De Pellegrini, Afaf Arfaoui, Cedric Richier, Jeremie Leguay, Quang-Trung Luu, Youcef Magnouche, and Sebastien Martin. Semidistributed coflow scheduling in datacenters. IEEE Transactions on Network and Ser vice Management, pages 1–1, 2024.
[17] Yuanxiang Gao, Hongfang Yu, Shouxi Luo, and Shui Yu. Information-agnostic coflow scheduling with optimal demotion thresholds. In 2016 IEEE International Conference on Communications (ICC), pages 1–6, 2016.
[18] Xin Sunny Huang, Yiting Xia, and TS Eugene Ng. Weaver: Efficient coflow scheduling in heterogeneous parallel networks. In 2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 1071–1081. IEEE, 2020.
[19] Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. Dryad: distributed data-parallel programs from sequential building blocks. In Proceedings 41 of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, pages 59–72, 2007.
[20] Samir Khuller and Manish Purohit. Brief announcement: Improved approximation algorithms for scheduling co-flows. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’16, page 239–240, New York, NY, USA, 2016. Association for Computing Machinery.
[21] Zhaogeng Li, Jun Bi, Yiran Zhang, and Chuang Wang. Eaalo: Enhanced coflow scheduling without prior knowledge in a datacenter network. In 2017 IEEE Symposium on Computers and Communications (ISCC), pages 1136–1141, 2017.
[22] Francesco De Pellegrini, Vaibhav Kumar Gupta, Rachid El Azouzi, Serigne Gueye, Cedric Richier, and Jeremie Leguay. Fair coflow scheduling via controlled slowdown, 2022.
[23] Zhen Qiu, Cliff Stein, and Yuan Zhong. Minimizing the total weighted completion time of coflows in datacenter networks. In Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures, pages 294–303, 2015.
[24] Sushant Sachdeva and Rishi Saket. Optimal inapproximability for scheduling problems via structural hardness for hypergraph vertex cover. In 2013 IEEE Conference on Computational Complexity, pages 219–229. IEEE, 2013.
[25] Mehrnoosh Shafiee and Javad Ghaderi. An improved bound for minimizing the total weighted completion time of coflows in datacenters. IEEE/ACM Transactions on Networking, 26(4):1674–1687, 2018.
[26] Zhiliang Wang, Han Zhang, Xingang Shi, Xia Yin, Yahui Li, Haijun Geng, Qianhong Wu, and Jianwei Liu. Efficient scheduling of weighted coflows in data centers. IEEE Transactions on Parallel and Distributed Systems, 30(9):2003–2017, 2019.
[27] Hong Zhang, Li Chen, Bairen Yi, Kai Chen, Mosharaf Chowdhury, and Yanhui Geng. Coda: Toward automatically identifying and scheduling coflows in the dark. In Proceedings of the 2016 ACM SIGCOMM Conference, SIGCOMM ’16, page 160–173, New York, NY, USA, 2016. Association for Computing Machinery.