A Methodology for Easing the Congestion in Fat-trees Using Traffic Pattern Detection

Routing in fat-trees is composed of a routing function and a selection function. The selection function was shown to have a great impact on the performance. Different selection functions have different performance under certain traffic patterns. The Stage And Destination Priority (SADP) selection function was shown to have better performance in case of uniform traffic [2] while the Stage And Origin Priority (SAOP) selection function was shown to perform better in case of hot-spot traffic [9]. In this paper, we propose a management mechanism for fat-trees for selecting a certain selection function for certain traffic pattern. The mechanism has the ability to detect the current traffic pattern and switch to a certain selection function that is proved to give better performance under the detected traffic pattern. This would decrease congestion in the network. First, we analyze the hot-spot traffic in fat-trees if SADP function is used. We derive a condition for the existence of hot-spot traffic if SADP selection function is used. We give an implementation for detecting this condition. Once this condition is detected, the network is forced to switch to use the SAOP selection function. Then, we use the work in [9] to detect that a non hot-spot traffic exists in fat trees. We give an implementation for detecting this condition. In turn, we switch back to the SADP selection function. Finally, we use synthetic workloads to show the accuracy of the proposed mechanism for detecting the hot-spot traffic in the network.