New Routing Algorithm for Improving the Throughput of Fat Tree Interconnection Networks

H. Kariniemi and J. Nurmi (Finland)


Fat tree, micronetwork, single-chip multicomputer,TBWP routing algorithm, performance simulations, SoC


The operation of the routing algorithms has a significant effect on the throughput of packet-switched networks. In typical fat tree interconnection networks the topmost layer of the switches is either removed or the switches have been connected only to their child nodes. This paper presents a new routing algorithm called turn back when possible (TBWP) which improves the performance of the fat tree allowing the topmost switches to be connected to each other. TBWP is able to use more efficiently all of the free available resources of the fat tree than algorithms presented so far. It can flexibly search available free path through the switches of the next upper level of the fat tree, if the packets can be not switched back towards processor nodes, even though they should be. Simulation results show that TBWP approximately doubles the throughput of the fat trees with uniformly distributed random traffic. It was also studied whether the usage of bursts of fixed sized small packets produces higher throughput the usage of variable sized larger packet. If variable packet size is used, the packets will be large, because in future system on-chip (SoC) circuits processors communicate over micronetworks using advanced communication protocols and packets must transfer in one go large parts of the frames of the upper layer protocols. Simulation results show that by using large variable packet size higher effective throughput can be achieved than by using smaller fixed sized packets.

Important Links:

Go Back