In a cluster system, performance of the interconnection network greatly affects the computation power generated together from all interconnected processing nodes. The network architecture, the interconnection topology, and the routing scheme are three key elements dominating the performance of an interconnection network. InfiniBand architecture (IBA) is a new industry standard architecture. It defines a high-bandwidth, high-speed, and low-latency message switching network that is good for constructing high-speed interconnection networks for cluster systems. Fat-trees are well-adopted as the topologies of interconnection networks because of many nice properties they have. In this paper, we proposed an m-port n-tree approach to construct fat-tree-based InfiniBand networks. Based on the constructed fat-tree-based InfiniBand networks, we proposed an efficient Multiple LID (MLID) routing scheme. The proposed routing scheme is composed of processing node addressing scheme, path selection scheme, and forwarding table assignment scheme. To evaluate the performance of the proposed routing scheme, we have developed a software simulator for InfiniBand networks. The simulation results show that the proposed routing scheme runs well on the constructed fat-tree-based InfiniBand networks and is able to efficiently utilize the bandwidth and the multiple paths that fat-tree topology offers under InfiniBand architecture.