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, the authors study the multipath routing problem for DCNs. They 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, they 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.