Dynamic Parallel Flow Algorithms With Centralized Scheduling for Load Balancing in Cloud Data Center Networks
Wei-Kang Chung, Yun Li, Chih‐Heng Ke, Sun‐Yuan Hsieh, Albert Y. Zomaya, Rajkumar Buyya
Abstract
BCube is a well-known recursively defined network structure. It provides multiple low-diameter paths and good fault-tolerance for data center networks (DCNs). Its distributed routing algorithm, BCube Source Routing (BSR), can be deployed rapidly and conveniently to build multiple parallel path sets. But in the worst case, BSR may suffer from flow collisions and waste <inline-formula><tex-math notation="LaTeX">$50\%$</tex-math></inline-formula> of the capacity of each BCube link. In this paper, to decrease collisions and improve bandwidth utilization, we supplement the BCube topology with a central master computer and design two centralized dynamic parallel flow scheduling algorithms: CDPFS and CDPFSMP, for single-path and multi-path respectively. We focus on finding the least congested path for each flow by analyzing the information about the state of the global network. Furthermore, we allocate those paths to each flow in parallel. The simulation result shows that our proposed algorithms take advantage of BCube structure and deliver high-performance solutions for load balancing problems, which have improved 44.1% of the throughput in random bijective traffic pattern and 36.2% of throughput in data shuffle compared with BSR algorithm.