In this chapter, we have presented an efficient implementation of complete exchange operation on the Ethernet-based hierarchical network. The example hierarchical network is based on a Gigabit switch as the backbone, which interconnects all Fast Ethernet switches. We believe that the hierarchical network model is a practical design to construct large-scale clusters. With this system configuration, clusters can be scaled up to hundreds or thousands of nodes, and support enough bandwidth for high-speed communication. Our research can be used in any combination of Ethernet-based switched networks, which we belief, over 60% of the self-made clusters are based on. And the concept is applicable to future technologies, such as 10 Gigabit Ethernet, which simply extends the topology to multi-level hierarchy.
We have demonstrated that the contention problems on such network, such as the link, the node, and the switch contention, can severely affect the overall performance of the clusters. To avoid congestion loss on this type of network, we propose the use of synchronous shuffle exchange algorithm with congestion control scheme and contention-aware permutation. With the proactive approach in handling congestion, this algorithm makes use of architectural characteristics to avoid congestion build-up in the first place and reduces congestion whenever it happens. We derive a global window scheme from information on the network buffer capacity, which forces each node to limit their traffic loads and ensures a fair sharing of network resources that avoids congestion overflow. We also make use of information on the network topology to derive a contention-aware permutation in generating a communication schedule, which avoids contention at the node and at the switch, as well as creating a more evenly distributed traffic pattern on the network. This improves the synchronism of the traffic information exchange between cluster nodes, and hence, improves the effectiveness of the global windowing scheme in monitoring the network. The proposed algorithm is implemented on a 32-node cluster with different network configurations. And the results have showed that it can efficiently utilize the network as well as effectively control the congestion problem.