The research of flow aggregation with constrained resource for in-network computation

doi:10.7523/j.ucas.2023.044

Abstract

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 given amount of resource and the capacity of switch nodes. Since this problem is a NP-hard problem, a linear integer linear programming model and a heuristic algorithm called 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 compared with other heuristics, and the performance is close to the optimal solution for small-scale networks.

Key words: In-network computation, aggregation tree, resource allocation

CLC Number:

TN929.5

SHENG Jiahua, HONG Peilin, WANG Hang. The research of flow aggregation with constrained resource for in-network computation[J]. Journal of University of Chinese Academy of Sciences, DOI: 10.7523/j.ucas.2023.044.

References

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