An Efficient and Low Overhead Random Forwarding Table Construction Method for Deadlock-Free Routing Algorithms in Infiniband Networks

H.-T. Kuo, J. Zhou, X.-Y. Lin, and Y.-C. Chung (Taiwan)


Forwarding table, InfiniBand, irregular topology and interconnect network.


The InfiniBand architecture (IBA) defines a switch-based interconnect network with point-to-point links to support arbitrary topology for server I/O and inter-server communication. The IBA forwarding table forwards packets to output ports by only considering the destination of packets. However, the forwarding tables computed by many irregular routing algorithms consider both the input port and the destination of the packet. Therefore, these routing algorithms can not be used in IBA network. There are two types of IBA forwarding table: Linear forwarding table (LFT) and Random forwarding table (RFT). In this thesis, we propose a two-phase method, partial renaming method, to construct the deadlock-free RFT according to the paths computed by any irregular deadlock-free routing algorithm. The partial renaming is an efficient and low overhead forwarding table construction method for IBA and does not modify the original paths computed by the routing algorithm before. We compare our method with the renaming scheme on a simulator to evaluate the forwarding table overhead and the computation time of both methods in different network size and different switch settings. The results show that the computation time and the forwarding table overhead introduced by our method are much less in all test cases.

Important Links:

Go Back