Semi-Distributed Coflow Scheduling in Datacenters
Authors: 
Rachid El-Azouzi, Francesco De Pellegrini, Afaf Arfaoui, Cedric Richier, Jeremie Leguay, Quang-Trung Luu, Youcef Magnouche, Sebastien MartinAuthors Info & Claims
Pages 4268 - 4281
Abstract
With the advent of big data applications, coflow scheduling has become a cornerstone for the engineering of traffic in datacenters. Minimizing the average weighted Coflow Completion Times (CCT) is a crucial step to minimize the execution time of jobs running in distributed computing frameworks. In this paper, we present a new <inline-formula> <tex-math notation="LaTeX">$\sigma $ </tex-math></inline-formula>-order coflow scheduling solution, ONE-PARIS, an online semi-clairvoyant and semi-distributed implementation suitable to minimize the weighted CCT in production environments. We achieves this through ONE-PARIS scheduler for ordering coflows and a decentralized resource allocation mechanism, called Sync-Rate, enabling to respect the order of priority of coflows provided by ONE-PARIS and ensuring efficient synchronization between flows of the same coflow in order to free up bandwidth for low-priority flows. Extensive simulations on both synthetic and real traffics show that our proposed coflow scheduler outperforms other state-of-art schemes.
References
[1]
J. Dean and S. Ghemawat, “MapReduce: Simplified data processing on large clusters,” Commun. ACM, vol. 51, no. 1, pp. 107–113, Jan. 2008. [Online]. Available: https://doi.org/10.1145/1327452.1327492
[2]
M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica, “Spark: Cluster Comput. with working sets,” in Proc. 2nd USENIX Conf. Hot Topics Cloud Comput., 2010, p. 10.
[3]
M. Chowdhury and I. Stoica, “Coflow: A networking abstraction for cluster applications,” in Proc. 11th ACM Workshop Hot Topics Netw., 2012, pp. 31–36.
[4]
N. M. K. Chowdhury, “Coflow: A networking abstraction for distributed data-parallel applications,” Ph.D. dissertation, Dept. Comput. Sci., Univ. California, Berkeley, CA, USA, 2015.
[5]
Y. Liu, J. Muppala, M. Veeraraghavan, D. Lin and M. Hamdi, A Survey of Data Center Network Architectures. New York, NY, USA: Springer, 2013.
[6]
M. Al-Fares, S. Radhakrishnan, B. Raghavan, N. Huang, and A. Vahdat, “Hedera: Dynamic flow scheduling for data center networks,” in Proc. 7th USENIX Conf. Netw. Syst. Design Implement., 2010, p. 19.
[7]
M. Chowdhury, Y. Zhong, and I. Stoica, “Efficient coflow scheduling with Varys,” in Proc. ACM Conf. SIGCOMM, 2014, pp. 443–454.
[8]
W. Li et al., “Survey on traffic management in data Center network: From link layer to application layer,” IEEE Access, vol. 9, pp. 38427–38456, 2021.
[9]
M. Chowdhury, M. Zaharia, J. Ma, M. I. Jordan, and I. Stoica, “Managing data transfers in computer clusters with orchestra,” ACM SIGCOMM Comput. Commun. Rev., vol. 41, no. 4, pp. 98–109, 2011.
[10]
O. Brun, R. El-Azouzi, Q.-T. Luu, F. De Pellergrini, B. J. Prabhu, and C. Richier, “Weighted scheduling of time-sensitive coflows,” 2023, arXiv:2303.17175.
[11]
M. Noormohammadpour and C. S. Raghavendra, “Datacenter traffic control: Understanding techniques and tradeoffs,” IEEE Commun. Surveys Tuts., vol. 20, no. 2, pp. 1492–1525, 2nd Quart., 2018.
[12]
S. Agarwal, S. Rajakrishnan, A. Narayan, R. Agarwal, D. Shmoys, and A. Vahdat, “Sincronia: Near-optimal network design for coflows,” in Proc. ACM SIGCOMM, 2018, pp. 16–29.
[13]
S. Ahmadi, S. Khuller, M. Purohit, and S. Tanj, “On scheduling coflows,” Algorithmica, vol. 82, no. 12, pp. 3604–3629, 2020.
[14]
L. Cheng, Y. Wang, Y. Pei, and D. Epema, “A coflow-based co-optimization framework for high-performance data analytics,” in Proc. 46th Int. Conf. Parallel Process. (ICPP), 2017, pp. 392–401.
[15]
F. De Pellegrini, V. K. Gupta, R. El Azouzi, S. Gueye, C. Richier, and J. Leguay, “Fair coflow scheduling via controlled slowdown,” 2022, arXiv:2208.06513.
[16]
Q.-T. Luu, O. Brun, R. El-Azouzi, F. De Pellegrini, B. J. Prabhu, and C. Richier, “DCoflow: Deadline-aware scheduling algorithm for coflows in datacenter networks,” in Proc. IFIP Netw. Conf., 2022, pp. 1–9.
[17]
Z. Wang et al., “Efficient scheduling of weighted coflows in data centers,” IEEE Trans. Parallel Distrib. Syst., vol. 30, no. 9, pp. 2003–2017, Sep. 2019.
[18]
S. Khuller and M. Purohit, “Brief announcement: Improved approximation algorithms for scheduling co-flows,” in Proc. 28th ACM Symp. Parall. Algorithms Archit., 2016, pp. 239–240. [Online]. Available: https://doi.org/10.1145/2935764.2935809
[19]
Z. Qiu, C. Stein, and Y. Zhong, “Minimizing the total weighted completion time of coflows in datacenter networks,” in Proc. 27th ACM Symp. Parall. Algorithms Archit., 2015, pp. 294–303. [Online]. Available: https://doi.org/10.1145/2755573.2755592
[20]
M. Shafiee and J. Ghaderi, “An improved bound for minimizing the total weighted completion time of coflows in datacenters,” IEEE/ACM Trans. Netw., vol. 26, no. 4, pp. 1674–1687, Aug. 2018.
[21]
M. Mastrolilli, M. Queyranne, A. S. Schulz, O. Svensson, and N. A. Uhan, “Minimizing the sum of weighted completion times in a concurrent open shop,” Oper. Res. Lett., vol. 38, no. 5, pp. 390–395, 2010.
[22]
M. Chowdhury, S. Khuller, M. Purohit, S. Yang, and J. You, “Near optimal coflow scheduling in networks,”`in Proc. 31st ACM Symp. Parall. Algorithms Archit., 2019, pp. 123–134.
[23]
R. Mao, V. Aggarwal, and M. Chiang, “Stochastic non-preemptive co-flow scheduling with time-indexed relaxation,” in Proc. IEEE Conf. Comput. Commun. Workshops, 2018, pp. 385–390.
[24]
T. Zhang, F. Ren, R. Shu, and B. Wang, “Scheduling coflows with incomplete information,” in Proc. IEEE/ACM 26th Int. Symp. Qual. Service (IWQoS), 2018, pp. 1–10.
[25]
Y. Gao, H. Yu, S. Luo, and S. Yu, “Information-agnostic coflow scheduling with optimal demotion thresholds,” in Proc. IEEE Int. Conf. Commun. (ICC), 2016, pp. 1–6.
[26]
H. Zhang, L. Chen, B. Yi, K. Chen, M. Chowdhury, and Y. Geng, “CODA: Toward automatically identifying and scheduling coflows in the dark,” in Proc. ACM Conf. SIGCOMM, 2016, pp. 160–173.
[27]
F. R. Dogar, T. Karagiannis, H. Ballani, and A. Rowstron, “Decentralized task-aware scheduling for data center networks,” in Proc. ACM Conf. SIGCOMM, 2014, pp. 431–442.
[28]
Z. Li, J. Bi, Y. Zhang, and C. Wang, “EAalo: Enhanced coflow scheduling without prior knowledge in a datacenter network,” in Proc. IEEE Symp. Comput. Commun. (ISCC), 2017, pp. 1136–1141.
[29]
L. Shi, Y. Liu, J. Zhang, and T. Robertazzi, “Coflow scheduling in data centers: Routing and bandwidth allocation,” IEEE Trans. Parallel Distrib. Syst., vol. 32, no. 11, pp. 2661–2675, Nov. 2021.
[30]
F. P. Kelly, A. K. Maulloo, and D. K. H. Tan, “Rate control for communication networks: Shadow prices, proportional fairness and stability,” J. Oper. Res. Soc., vol. 49, no. 3, pp. 237–252, 1998.
[31]
K. J. Babiarz and F. B. Chan, “BConfiguration guidelines for DiffServ service classes,” in Internet Eng. Task Force, RFC 4594, 2006.
[32]
T. Zhang, R. Shu, Z. Shan, and F. Ren, “Distributed bottleneck-aware coflow scheduling in data centers,” IEEE Trans. Parallel Distrib. Syst., vol. 30, no. 7, pp. 1565–1579, Jul. 2019.
[33]
M. Chowdhury and I. Stoica, “Efficient coflow scheduling without prior knowledge,” in Proc. ACM Conf. Special Interest Group Data Commun., 2015, pp. 393–406.
[34]
L. Wang, W. Wang, and B. Li, “Utopia: Near-optimal coflow scheduling with isolation guarantee,” in Proc. IEEE Conf. Comput. Commun., 2018, pp. 891–899.
[35]
M. Chowdhury, Z. Liu, A. Ghodsi, and I. Stoica, “HUG: Multi-resource fairness for correlated and elastic demands,” in Proc. 13th USENIX Symp. Netw. Syst. Design Implement., 2016, pp. 407–424.
[36]
Y. Li et al., “Efficient online coflow routing and scheduling,” in Proc. 17th ACM Int. Symp. Mobile Ad Hoc Netw. Comput., 2016, pp. 161–170.
[37]
L. Chen, W. Cui, B. Li, and B. Li, “Optimizing coflow completion times with utility max-min fairness,” in Proc. 35th Annu. IEEE Int. Conf. Comput. Commun., 2016, pp. 1–9.
[38]
S. Luo, H. Yu, Y. Zhao, S. Wang, S. Yu, and L. Li, “Towards practical and near-optimal coflow scheduling for data center networks,” IEEE Trans. Parallel Distrib. Syst., vol. 27, no. 11, pp. 3366–3380, Nov. 2016.
[39]
S. Tseng and A. Tang, “Coflow deadline scheduling via network-aware optimization,” in Proc. Annu. Allert. Conf. Commun. Control Comput., 2018, pp. 829–833.
[40]
A. Arfaoui, R. Elazouzi, F. De Pellegrini, C. Richier, and J. Leguay, “ELITE: Near-optimal heuristics for coflow scheduling,” in Proc. 22nd IEEE Int. Symp. Cluster, Cloud Internet Comput. (CCGrid), 2022, pp. 665–674.
[41]
L. Liu et al., “Bottleneck-aware non-clairvoyant coflow scheduling with Fai,” IEEE Trans. Cloud Comput., vol. 11, no. 1, pp. 1011–1025, Jan.–Mar. 2023.
[42]
J. Du and K. C.-J. Lin, “Distributed in-network coflow scheduling,” in Proc. IEEE 30th Int. Conf. Netw. Protocols (ICNP), 2022, pp. 1–11.
[43]
H. Yaiche, R. Mazumdar, and C. Rosenberg, “A game theoretic framework for bandwidth allocation and pricing in broadband networks,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 667–678, Oct. 2000.
Index Terms
- Semi-Distributed Coflow Scheduling in Datacenters
Index terms have been assigned to the content through auto-classification.
Recommendations
Multi-Attributes-Based Coflow Scheduling Without Prior Knowledge
In data centers, the coflow abstraction is proposed to better express the requirements and communication semantics of a group of parallel flows generated by the jobs of cluster computing frameworks. Knowing the coflow-level information, such as coflow ...
Efficient coflow scheduling with Varys
SIGCOMM '14: Proceedings of the 2014 ACM conference on SIGCOMMCommunication in data-parallel applications often involves a collection of parallel flows. Traditional techniques to optimize flow-level metrics do not perform well in optimizing such collections, because the network is largely agnostic to application-...
Efficient online coflow routing and scheduling
MobiHoc '16: Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and ComputingA coflow is a collection of related parallel flows that occur typically between two stages of a multi-stage compute task in a network, such as shuffle flows in MapReduce. The coflow abstraction allows applications to convey their semantics to the network ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
1932-4537 © 2024 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
Publisher
IEEE Press
Publication History
Published: 01 August 2024
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025