在网计算中资源受限的流汇聚算法

doi:10.7523/j.ucas.2023.044

摘要/Abstract

摘要： 考虑在总资源量和节点容量的限制下，如何为任务找到一棵最小代价汇聚树。该问题是一个NP难问题，分别提出问题的线性整数规划模型和启发式算法GCAT。仿真结果显示，相比于其他的启发式算法，GCAT算法生成的汇聚树代价更小，同时有更高的资源利用率，小规模网络下性能接近于最优解。

关键词: 在网计算, 汇聚树, 资源分配, 线性整数规划, GCAT

Abstract: In-network computation can greatly reduce the traffic generated during many-to-one transmission by establishing aggregation trees to merge data streams at the aggregation nodes. In this paper, we consider finding the minimum-cost aggregation tree under the constraints of a given amount of resources and the capacity of switch nodes. Since this problem is an NP-hard problem, a linear integer programming model and a heuristic algorithm called greedy cost aggregation tree (GCAT) are given to solve it. Simulation results show that the GCAT algorithm can generate a tree with less cost and utilize the resource more efficiently than other heuristics, and the performance is close to the optimal solution for small-scale networks.

Key words: in-network computation, aggregation tree, resource allocation, linear integer programming (ILP), greedy cost aggregation tree (GCAT)

中图分类号:

TN929.5

盛家华, 洪佩琳, 王航. 在网计算中资源受限的流汇聚算法[J]. 中国科学院大学学报, 2025, 42(2): 248-259.

SHENG Jiahua, HONG Peilin, WANG Hang. Flow aggregation with constrained resource for in-network computation[J]. Journal of University of Chinese Academy of Sciences, 2025, 42(2): 248-259.

参考文献

[1] Li M, Andersen D G, Smola A, et al. Communication efficient distributed machine learning with the parameter server[C]//Proceedings of the 27th International Conference on Neural Information Processing Systems-Volume 1. December 8-13, 2014, Montreal, Canada. New York: ACM, 2014: 19-27. DOI:10.5555/2968826.2968829.
[2] Dean J, Ghemawat S. MapReduce: simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113. DOI: 10.1145/1327452.1327492.
[3] Liu K X, Tian C, Wang Q Y, et al. Floodgate: taming incast in datacenter networks[C]//Proceedings of the 17th International Conference on emerging Networking EXperiments and Technologies. December 7 - 10, 2021, Virtual Event, Germany. New York: ACM, 2021: 30-44. DOI: 10.1145/3485983.3494854.
[4] Li Y L, Miao R, Liu H H, et al. HPCC: high precision congestion control[C]//Proceedings of the ACM Special Interest Group on Data Communication. August 19-23, 2019, Beijing, China. New York: ACM, 2019: 44-58. DOI: 10.1145/3341302.3342085.
[5] Viswanathan R, Balasubramanian A, Akella A. Network-accelerated distributed machine learning for multi-tenant settings[C]//Proceedings of the 11th ACM Symposium on Cloud Computing. October 19-21, 2020, Virtual Event, USA. New York: ACM, 2020: 447-461. DOI: 10.1145/3419111.3421296.
[6] McCauley J, Panda A, Krishnamurthy A, et al. Thoughts on load distribution and the role of programmable switches[J]. ACM SIGCOMM Computer Communication Review, 2019, 49(1): 18-23. DOI: 10.1145/3314212.3314216.
[7] Ports D R K, Nelson J. When should the network be the computer?[C]//Proceedings of the Workshop on Hot Topics in Operating Systems. May 13-15, 2019, Bertinoro, Italy. New York: ACM, 2019: 209-215. DOI: 10.1145/3317550.3321439.
[8] Sapio A, Abdelaziz I, Aldilaijan A, et al. In-network computation is a dumb idea whose time has come[C]//Proceedings of the 16th ACM Workshop on Hot Topics in Networks. 30 November, 2017, Palo Alto, CA, USA. New York: ACM, 2017: 150-156. DOI: 10.1145/3152434.3152461.
[9] Al-Fares M, Loukissas A, Vahdat A. A scalable, commodity data center network architecture[C]//Proceedings of the ACM SIGCOMM 2008 conference on Data communication. August 17-22, 2008, Seattle, WA, USA. New York: ACM, 2008: 63-74. DOI: 10.1145/1402958.1402967.
[10] Maculan N. The steiner problem in graphs^*[J]. North-Holland Mathematics Studies, 1987, 132: 185-211. DOI: 10.1016/S0304-0208(08)73236-5.
[11] Intanagonwiwat C, Govindan R, Estrin D. Directed diffusion: a scalable and robust communication paradigm for sensor networks[C]//Proceedings of the 6th annual international conference on Mobile computing and networking. August 6-11, 2000, Boston, Massachusetts, USA. New York: ACM, 2000: 56-67. DOI: 10.1145/345910.345920.
[12] Villas L A, Boukerche A, Ramos H S, et al. DRINA: a lightweight and reliable routing approach for in-network aggregation in wireless sensor networks[J]. IEEE Transactions on Computers, 2013, 62(4): 676-689. DOI: 10.1109/TC.2012.31.
[13] Sahasrabuddhe L H, Mukherjee B. Multicast routing algorithms and protocols: a tutorial[J]. IEEE Network, 2000, 14(1): 90-102. DOI: 10.1109/65.819175.
[14] Ramanathan S. Multicast tree generation in networks with asymmetric links[J]. IEEE/ACM Transactions on Networking, 1996, 4(4): 558-568. DOI: 10.1109/90.532865.
[15] Yang F, Wang Z, Ma X X, et al. Understanding the performance of In-network computing: a case study[C]//2019 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom). December 16-18, 2019, Xiamen, China. IEEE, 2020: 26-35. DOI: 10.1109/ISPA-BDCloud-SustainCom-SocialCom 48970.2019.00016.
[17] Segal R, Avin C, Scalosub G. SOAR: minimizing network utilization with bounded in-network computing[C]//Proceedings of the 17th International Conference on emerging Networking EXperiments and Technologies. December 7-10, 2021, Virtual Event, Germany. New York: ACM, 2021: 16-29. DOI:10.1145/3485983.3494853.
[18] Takashami H, Matsuyama A. An approximate solution for the Steiner problem in graphs[J]. Math Japonica, 1980, 24(6): 573-577.
[19] Iyer A, Kumar P, Mann V. Avalanche: data center Multicast using software defined networking[C]//2014 Sixth International Conference on Communication Systems and Networks (COMSNETS). January 6-10, 2014. Bangalore, India. IEEE, 2014: 1-8. DOI: 10.1109/COMSNETS.2014.6734903.
[20] Costa P, Donnelly A, Rowstron A, et al. Camdoop: exploiting in-network aggregation for big data applications[C]//9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12). April 25-27, 2012, San Jose, CA. USENIX Association, 2012: 29-42. DOI: 10.5555/2228298.2228302.
[21] Guo D K, Xie J J, Zhou X L, et al. Exploiting efficient and scalable shuffle transfers in future data center networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(4): 997-1009. DOI: 10.1109/TPDS.2014.2316829.
[22] Abu-Libdeh H, Costa P, Rowstron A, et al. Symbiotic routing in future data centers[C]//Proceedings of the ACM SIGCOMM 2010 conference. 30 August, 2010, New Delhi, India. New York: ACM, 2010: 51-62. DOI: 10.1145/1851182.1851191.
[23] Guo C X, Lu G H, Li D, et al. BCube: a high performance, server-centric network architecture for modular data centers[C]//Proceedings of the ACM SIGCOMM 2009 conference on Data communication. August 16-21, 2009, Barcelona, Spain. New York: ACM, 2009: 63-74. DOI:10.1145/1592568.1592577.
[24] Graham R L, Bureddy D, Lui P, et al. Scalable hierarchical aggregation protocol (SHArP): a hardware architecture for efficient data reduction[C]//2016 First International Workshop on Communication Optimizations in HPC (COMHPC). November 18-18, 2016, Salt Lake City, UT, USA. IEEE, 2017: 1-10. DOI: 10.1109/COMHPC.2016.006.
[25] Edmonds J. Optimum branchings[J]. Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1967, 71B(4): 233-240. DOI: 10.6028/jres.071b.032.
[26] Ganesh A, Massoulie L, Towsley D. The effect of network topology on the spread of epidemics[C]//Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies. March 13-17, 2005. Miami, FL, USA. IEEE, 2005: 1455-1466. DOI:10.1109/INFCOM.2005.1498374.