BSFS: A Bidirectional Search Algorithm for Flow Scheduling in Cloud Data Centers
Subject Areas : Cloud computingHasibeh Naseri 1 , Sadoon Azizi 2 * , Alireza Abdollahpouri 3
1 - University of Kurdistan
2 - University of Kurdistan
3 - University of Kurdistan
Keywords: Cloud Computing, , Data Center Networks, , Flow Scheduling, , Routing Algorithm, , Load Balancing, , Bidirectional Search, ,
Abstract :
To support high bisection bandwidth for communication intensive applications in the cloud computing environment, data center networks usually offer a wide variety of paths. However, optimal utilization of this facility has always been a critical challenge in a data center design. Flow-based mechanisms usually suffer from collision between elephant flows; while, packet-based mechanisms encounter packet re-ordering phenomenon. Both of these challenges lead to severe performance degradation in a data center network. To address these problems, in this paper, we propose an efficient mechanism for the flow scheduling problem in cloud data center networks. The proposed mechanism, on one hand, makes decisions per flow, thus preventing the necessity for rearrangement of packets. On the other hand, thanks do SDN technology and utilizing bidirectional search algorithm, our proposed method is able to distribute elephant flows across the entire network smoothly and with a high speed. Simulation results confirm the outperformance of our proposed method with the comparison of state-of-the-art algorithms under different traffic patterns. In particular, compared to the second-best result, the proposed mechanism provides about 20% higher throughput for random traffic pattern. In addition, with regard to flow completion time, the percentage of improvement is 12% for random traffic pattern
[1] Zhang, J., Yu, F. R., Wang, S., Huang, T., Liu, Z., Liu, Y.: Load Balancing in Data Center Networks: A Survey, IEEE Communications Surveys & Tutorials, vol. 20, no. 3, pp. 2324-52, 2018.
[2] Al-Fares, M., Loukissas, A., Vahdat, A.: A scalable, commodity data center network architecture, In ACM SIGCOMM Computer Communication Review, vol. 38, no. 4, pp. 63-74, 2008.
[3] Niranjan Mysore, R., Pamboris, A., Farrington, N., Huang, N., Miri, P., Radhakrishnan, S., Subramanya, V. and Vahdat, A.: Portland: a scalable fault-tolerant layer 2 data center network fabric, In ACM SIGCOMM Computer Communication Review, vol. 39, no. 4, pp. 39-50, 2009.
[4] Wu, .X, Yang, X.: Dard: Distributed adaptive routing for datacenter networks, In 32nd International Conference on Distributed Computing Systems (ICDCS), pp. 32-41, 2012, IEEE.
[5] Greenberg, A., Hamilton, J.R., Jain, N., Kandula, S., Kim, C., Lahiri, P., Maltz, D.A., Patel, P. and Sengupta, S.: VL2: a scalable and flexible data center network, In ACM SIGCOMM computer communication review, vol. 39, no. 4, pp. 51-62, 2009.
[6] Zahavi, E., Keslassy, I., Kolodny, A.: Distributed adaptive routing for big-data applications running on data center networks, In Proceedings of the eighth ACM/IEEE Symposium on Architectures for networking and communications systems, pp. 99-110, 2012.
[7] Al-Fares, M., Radhakrishnan, S., Raghavan, B., Huang, N., Vahdat, A.: Hedera: Dynamic Flow Scheduling for Data Center Networks, In NSDI, vol. 10, pp. 19-19, 2010.
[8] Zats, D., Das, T., Mohan, P., Borthakur, D., Katz, R.: DeTail: reducing the flow completion time tail in datacenter networks, In Proceedings of the ACM SIGCOMM conference on Applications, technologies, architectures, and protocols for computer communication, pp. 139-150, 2012.
[9] Sen, S., Shue, D., Ihm, S., Freedman, M.J.: Scalable, optimal flow routing in datacenters via local link balancing, In Proceedings of the ninth ACM conference on Emerging networking experiments and technologies, pp. 151-162, 2013.
[10] Modi, T., Swain, P., FlowDCN: Flow Scheduling in Software Defined Data Center Networks. In IEEE International Conference on Electrical, Computer and Communication Technologies (ICECCT), pp. 1-5, 2019.
[11] Alizadeh, M., Edsall, T., Dharmapurikar, S., Vaidyanathan, R., Chu, K., Fingerhut, A., Matus, F., Pan, R., Yadav, N. and Varghese, G.: CONGA: Distributed congestion-aware load balancing for datacenters, In ACM SIGCOMM Computer Communication Review, vol. 44, no. 4, pp. 503-514, 2014.
[12] He, K., Rozner, E., Agarwal, K., Felter, W., Carter, J. and Akella, A.: Presto: Edge-based load balancing for fast datacenter networks, In ACM SIGCOMM Computer Communication Review, vol. 45, no. 4, pp. 465-478, 2015.
[13] Zhang, J., Ren, F., Huang, T., Tang, L., Liu, Y.: Congestion-aware adaptive forwarding in datacenter networks, Computer Communications, vol. 62, pp. 34-46, 2015.
[14] Cui, W., Qian, C.: Difs: Distributed flow scheduling for adaptive routing in hierarchical data center networks, In Proceedings of the tenth ACM/IEEE Symposium on Architectures for networking and communications systems, pp. 53-64, 2014.
[15] Ghorbani, S., Yang, Z., Godfrey, P., Ganjali, Y. and Firoozshahian, A.: DRILL: Micro load balancing for low-latency data center networks, In Proceedings of the Conference of the ACM Special Interest Group on Data Communication, pp. 225-238, 2017.
[16] Wang, C., Zhang, G., Chen, H. and Xu, H.: An ACO-based elephant and mice flow scheduling system in SDN, In 2nd International Conference on Big Data Analysis (ICBDA), pp. 859-863, 2017, IEEE.
[17] Perry, Perry, Balakrishnan, H., Shah, D.: Flowtune: Flowlet Control for Datacenter Networks, In NSDI, pp. 421-435, 2017.
[18] Hopps, C.E.: Analysis of an equal-cost multi-path algorithm, 2000.
[19] Cui, W., Yu, Y., Qian, C.: DiFS: Distributed Flow Scheduling for adaptive switching in FatTree data center networks, Computer Networks, vol. 105, pp. 166-179, 2016.
[20] Ghorbani, S., Godfrey, B., Ganjali, Y. and Firoozshahian, A.: Micro load balancing in data centers with DRILL, In Proceedings of the 14th ACM Workshop on Hot Topics in Networks, p. 17, 2015.
[21] Azizi, S., Hashemi, N., Khonsari, A.: A flexible and high-performance data center network topology, The Journal of Supercomputing, vol. 73, no. 4, pp. 1484-1503, 2017.
[22] Guo, C., Wu, H., Tan, K., Shi, L., Zhang, Y. and Lu, S.: Dcell: a scalable and fault-tolerant network structure for data centers, In ACM SIGCOMM Computer Communication Review, vol. 38, no. 4, pp. 75-86, 2008.
[23] Wang, W., Sun, Y., Salamatian, K., Li, Z.: Adaptive Path Isolation for Elephant and Mice Flows by Exploiting Path Diversity in Datacenters, IEEE Transactions on Network and Service Management, vol. 13, no. 1, pp. 5-18, 2016.
[24] Li, P., Xu, H., Wang, R., Luo, B.: Data center network flow scheduling mechanism based on HGSAFS algorithm, In Proceedings of the High Performance Computing Symposium, 2019.
[25] Li, D., Wu, J.: On data center network architectures for interconnecting dual-port servers, IEEE Transactions on Computers, vol. 64, no. 11, pp. 3210-3222, 2015.
[26] Marron, J., Hernandez-Campos, F., Smith, F.: Mice and elephants visualization of internet traffic, In Proceedings of Computational Statistics, pp. 47-54, 2002.
[27] Curtis, A.R., Kim, W., Yalagandula, P.: Mahout: Low-overhead datacenter traffic management using end-host-based elephant detection, In Proceedings IEEE INFOCOM, pp. 1629-1637, 2011.
[28] Wischik, D., Raiciu, C., Greenhalgh, A., Handley, M.: Design, Implementation and Evaluation of Congestion Control for Multipath TCP, In NSDI, vol. 11, pp. 8, 2011.
[29] Singla, A., Hong, C.-Y., Popa, L., Godfrey, P.B.: Jellyfish: Networking Data Centers, Randomly, In NSDI, vol. 12, pp. 1-6, 2012.