Depth-First Worst-Fit Search based multipath routing for data center networks

Modern data center networks (DCNs) often use multi-rooted topologies, which offer multipath capability, for increased bandwidth and fault tolerance. However, traditional routing algorithms for the Internet have no or limited support for multipath routing, and cannot fully utilize available bandwidth in such DCNs. In this paper, we study the multipath routing problem for DCNs. We first formulate the problem as an integer linear program, but it is not suitable for fast on-the-fly route calculation. For a practical solution, we propose the Depth-First Worst-Fit Search based multipath routing algorithm. The main idea is to use depth-first search to find a sequence of worst-fit links to connect the source and destination of a flow. Since DCN topologies are usually hierarchical, our algorithm uses depth-first search to quickly traverse between hierarchical layers to find a path. When there are multiple links to a neighboring layer, the worst-fit link selection criterion enables the algorithm to make the selection decision with constant time complexity by leveraging the max-heap data structure, and use a small number of selections to find all the links of a path. Further, worst-fit also achieves load balancing, and thus generates low queueing delay, which is a major component of the end-to-end delay. We have evaluated the proposed algorithm by extensive simulations, and compared its average number of link selections and average end-to-end delay with competing solutions. The simulation results fully demonstrate the superiority of our algorithm and validate the effectiveness of our designs.