Dynamic Flow Scheduling Technique for Load Balancing in Fat-Tree Data Center Networks

doi:10.23940/ijpe.21.06.p1.491503

Int J Performability Eng ›› 2021, Vol. 17 ›› Issue (6): 491-503.doi: 10.23940/ijpe.21.06.p1.491503

Dynamic Flow Scheduling Technique for Load Balancing in Fat-Tree Data Center Networks

Wen-Hsuan Liang^a, Dun-Wei Cheng^a, Chih-Wei Hsu^a, Chia-Wei Lee^b, Chih-Heng Keand^c, Albert Y. Zomaya^d, and Sun-Yuan Hsieh^a,*

^aNational Cheng Kung University, Tainan, 70101, Taiwan;
^bNational Taitung University, Taitung, 95092, Taiwan;
^cNational Quemoy University, Jinning, 89441, Taiwan;
^dSchool of Information Technologies, University of Sydney, Sydney, NSW2006, Australia

Contact: * E-mail address: hsiehsy@mail.ncku.edu.tw
About author:Wen-Syuan Liang received his MS degree from the Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan, Taiwan, in 2016. He is currently an employee at a business computer company. His current research interests include operating systems (e.g., Android) and data center networking. Dun-Wei Cheng is currently pursuing the Ph.D. degree in the Department of Computer Science and Information Engineering at National Cheng Kung University in Tainan City, Taiwan. He received the M.S. degree from the Department of Computer Science and Information Engineering at National University of Kaohsiung, in 2011. His current research interests include financial computing, artificial intelligence, system-level fault diagnosis and hub location problem. Chih-Wei Hsu received his BS degree from the Department of Information Engineering and Computer Science, Feng Chia University, Taiwan, in 2019. He is currently an MS student at the Department of Computer Science and Information Engineering, National Cheng Kung University, Taiwan.Chia-Wei Lee received his BS and MS degrees from the Department of Computer Science and Information Engineering, National Chi Nan University, Taiwan, in 2003 and 2005, respectively, and his PhD degree from the Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan, Taiwan, in 2009. He then served the compulsory 11-month military service. From December 2011 to July 2017, he was an assistant research fellow at the Department of Computer Science and Information Engineering, National Cheng Kung University. He is currently an assistant professor at the Department of Computer Science and Information Engineering, National Taitung University. His current research interests include graph theory and algorithms, interconnection networks, and system-level diagnosis. Chih-Heng Ke received his BS and PhD degrees in Electrical Engineering from National Cheng Kung University, Tainan, Taiwan, in 1999 and 2007. He is an associate professor at the Department of Computer Science and Information Engineering, National Quemoy University, Kinmen, Taiwan. His current research interests include multimedia communications, wireless networks, and QoS networks. Albert Y. Zomaya is the chair professor of high performance computing and networking at the School of Information Technologies, The University of Sydney. He is also the director of the Centre for Distributed and High Performance Computing, which was established in late 2009. He has published more than 500 scientific papers and articles and has authored, coauthored, or edited more than 20 books. He served as the editor-in-chief of the IEEE Transactions on Computers during 2011–2014. He currently also serves as an associate editor for 22 leading journals. Prof. Zomaya is the recipient of the 2011 IEEE Technical Committee on Parallel Processing Outstanding Service Award, 2011 IEEE Technical Committee on Scalable Computing Medal for Excellence in Scalable Computing, and 2014 IEEE Computer Society Technical Achievement Award. He is a chartered engineer, a fellow of AAAS, IEEE, IET (UK). His current research interests are parallel and distributed computing and complex systems.Sun-Yuan Hsieh received the PhD degree in computer science from National Taiwan University, Taipei, Taiwan, in June 1998. He then served the compulsory two-year military service. From August 2000 to January 2002, he was an assistant professor at the Department of Computer Science and Information Engineering, National Chi Nan University. In February 2002, he joined the Department of Computer Science and Information Engineering, National Cheng Kung University, and now he is a chair professor. His awards include the 2007 K. T. Lee Research Award, President’s Citation Award (American Biographical Institute) in 2007, Engineering Professor Award of Chinese Institute of Engineers (Kaohsiung Branch) in 2008, National Science Council’s Outstanding Research Award in 2009, IEEE Outstanding Technical Achievement Award (IEEE Tainan Section) in 2011, Outstanding Electronic Engineering Professor Award of Chinese Institute of Electrical Engineers in 2013, and Outstanding Engineering Professor Award of Chinese Institute of Engineers in 2014. He is Fellow of the British Computer Society (BCS) and Fellow of Institution of Engineering and Technology (IET). Dr. Hsieh is also an experienced editor with editorial services to a number of journals, including serving as associate editors of IEEE ACCESS, IEEE Transactions on Reliability, Theoretical Computer Science (Elsevier), Discrete Applied Mathematics (Elsevier), Journal of Supercomputing (Springer), International Journal of Computer Mathematics (Taylor Francis Group), Parallel Processing Letters (World Scientific), Discrete Mathematics, Algorithms and Applications (World Scientific), Fundamental Informaticae (Polish Mathematical Society), and Journal of Interconnection Networks (World Scientific). In addition, he has served on organization committee and/or program committee of several dozens international conferences in computer science and computer engineering. His current research interests include design and analysis of algorithms, fault-tolerant computing, bioinformatics, parallel and distributed computing, and algorithmic graph theory.

Abstract

Abstract: Modern data center networks for a fat-tree topology typically adopt a multirooted hierarchical tree structure to achieve multiple-path capability and increase bisection bandwidth. However, the performance of a data center network highly depends on the routing protocols. Conventional routing protocols are unsuitable for modern data center topologies because they lack multiple-path routing support. Another crucial concern in data center networks is load balancing. Certain routing protocol limitations could lead to overloaded or underloaded utilization of a link, thereby considerably reducing the performance of a data center network. Therefore, we present a genetic algorithm (GA)-based dynamic load-balancing routing algorithm, which is heuristic and involves the use of a centralized scheduling technique. This algorithm mainly uses a GA to search for optimal solutions. We implement our algorithm in an OpenFlow controller RYU and Mininet emulator, which is based on software-defined networking architecture. Our evaluation results revealed that our algorithm can effectively achieve load balancing and increase bisection bandwidth.

Key words: data center networks, fat-tree, genetic algorithms, routing algorithms, software -defined networking

Wen-Hsuan Liang, Dun-Wei Cheng, Chih-Wei Hsu, Chia-Wei Lee, Chih-Heng Keand, Albert Y. Zomaya, and Sun-Yuan Hsieh. Dynamic Flow Scheduling Technique for Load Balancing in Fat-Tree Data Center Networks [J]. Int J Performability Eng, 2021, 17(6): 491-503.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

References

1. Al-Fares, M., Loukissas, A., and Vahdat, A., A Scalable, Commodity Data Center Network Architecture. ACM SIGCOMM Computer Communication Review, 38(4), pp.63-74., 2008.
2. Guo C., Lu G., Li D., Wu H., Zhang X., Shi Y., Tian C., Zhang Y., andLu S., BCube: A High Performance, Server-Centric Network Architecture for Modular Data Centers. In Proceedings of the ACM SIGCOMM 2009 Conference on Data Communication, pp. 63-74, August 17-21, 2009.
3. Li D., Guo C., Wu H., Tan K., Zhang Y., andLu S., FiConn: Using Backup Port for Server Interconnection in Data Centers. In Proceedings of IEEE the 28th Conference on Computer Communications (INFOCOM 2009) , pp. 2276-2285, IEEE, April 19-25, 2009.
4. Niranjan Mysore R., Pamboris A., Farrington N., Huang N., Miri P., Radhakrishnan S., Subramanya V., andVahdat A., Portland: a Scalable Fault-Tolerant Layer 2 Data Center Network Fabric. In Proceedings of the ACM SIGCOMM2009 conference on Data communication, pp. 39-50, August 17-21, 2009.
5. Greenberg A., Hamilton J.R., Jain N., Kandula S., Kim C., Lahiri P., Maltz D.A., Patel P., andSengupta S., VL2: A Scalable and Flexible Data Center Network. In Proceedings of the ACM SIGCOMM2009 Conference on Data Communication, pp. 51-62, August 17-21, 2009.
6. Vanini E., Pan R., Alizadeh M., Taheri P., andEdsall T., Let It Flow: Resilient Asymmetric Load Balancing with Flowlet Switching. In14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17), pp. 407-420, 2017.
7. Li W., Chen S., Li K., Qi H., Xu R., andZhang S., Efficient Online Scheduling for Coflow-aware Machine Learning Clusters.IEEE Transactions on Cloud Computing, 2020.
8. Li W., Yuan X., Li K., Qi H., andZhou X., Leveraging Endpoint Flexibility When Scheduling Coflows across Geo-Distributed Datacenters. InIEEE INFOCOM 2018-IEEE Conference on Computer Communications, pp. 873-881, IEEE, April 2018.
9. Jo E., Pan D., Liu J., andButler L., A Simulation and Emulation Study of SDN-Based Multipath Routing for Fat-Tree Data Center Networks. In Proceedings of the Winter Simulation Conference 2014, pp.3072-3083, IEEE, December 7-10, 2014.
10. Al-Fares, M., Radhakrishnan, S., Raghavan, B., Huang, N., and Vahdat, A., Hedera: Dynamic Flow Scheduling for Data Center Networks. In Proceedings of the 7th USENIX Conference on Networked Systems Design and Implementation (NSDI), Vol. 10, No. 8, pp. 89-92, April 28-30, 2010.
11. Analysis of an Equal-Cost Multi-Path Algorithm, RFC 2992,IETF, 2000.
12. Akyildiz I.F., Lee A., Wang P., Luo M., andChou W., A Roadmap for Traffic Engineering in SDN-OpenFlow Networks. Computer Networks, 71, pp.1-30, October 2014.
13. Scott-Hayward, S., Design and Deployment of Secure, Robust,Resilient SDN Controllers. In Proceedings of the2015 1st IEEE Conference on Network Softwarization (NetSoft), pp. 1-5, IEEE, April 13-17, 2015.
14. Kreutz D., Ramos F.M., Verissimo P.E., Rothenberg C.E., Azodolmolky S., andUhlig S., Software-Defined Networking: A Comprehensive Survey. Proceedings of the IEEE, 103(1), pp.14-76, January 2015.
15. Xia W., Wen Y., Foh C.H., Niyato D., andXie H., A Survey on Software-Defined Networking.IEEE Communications Surveys & Tutorials, 17(1), pp.27-51, 2015.
16. Benson T., Anand A., Akella A., andZhang M., MicroTE: Fine Grained Traffic Engineering for Data Centers. In Proceedings of the Seventh Conference on Emerging Networking EXperiments and Technologies, pp.1-12, December 6-9, 2011.
17. Benson T., Akella A., andMaltz D.A., Network Traffic Characteristics of Data Centers in the Wild. In Proceedings of the 10th ACM SIGCOMM Conference on Internet Measurement, pp.267-280, November 1-3, 2010.
18. Kaya, Y. and Uyar, M., A Novel Crossover Operator for Genetic Algorithms: Ring Crossover. InProceedings of Computing Research Repository (CoRR), 2011.
19. Li, Y. and Pan, D., OpenFlow Based Load Balancing for Fat-Tree Networks with Multipath Support. In Proceedings of 12th IEEE International Conference on Communications (ICC’13), Budapest, Hungary, pp.1-5, June 9-13, 2013.
20. Kumar R., Gopal G., andKumar R., Novel Crossover Operator for Genetic Algorithm for Permutation Problems. International Journal of Soft Computing and Engineering (IJSCE), 3(2), pp.252-258, May 2013.
21. Goldberg, D.E. and Lingle, R., Alleles, Loci,the Traveling Salesman Problem. In Proceedings of an International Conference on Genetic Algorithms and Their Applications, Vol. 154, pp. 154-159, Hillsdale, NJ: Lawrence Erlbaum, July 1985.
22. iPerf - The ultimate speed test tool for TCP, UDP and SCTP, https://iperf.fr/, 2003 (Last accessed in June 2021).

Dynamic Flow Scheduling Technique for Load Balancing in Fat-Tree Data Center Networks

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 0

Recommended 0