Enforcing In-Order Packet Delivery in PC Clusters using Adaptive Routing
Michihiro Koibuchi, Juan Carlos Martínez, José Flich, Antonio Robles, Pedro López, José F. Duato · 2004
Adaptive routing has been widely studied for interconnection networks in massively parallel computers and system area networks (SAN). Adaptive routing dynamically selects the path followed by packets, thus providing high network throughput. However, it may deliver packets out-of-order, which some message passing libraries don’t accept. In this paper, we propose a mechanism for guaranteeing in-order packet delivery. It is based on limiting packet injection at source hosts by using an end-to-end flow control. This mechanism may require certain amount of buffer resources at destination hosts to sort out-of-order delivered packets. This amount depends on the limitation injection degree of packets imposed by the mechanism. Evaluation results under NAS Parallel Benchmarks show that the proposed mechanism achieves a similar throughput to that achieved by the original adaptive routing, even without using sorting buffers at destination hosts. Keywords Adaptive routing, in-order packet delivery, interconnection networks, System Area Networks, PC clusters 1