Load-Balancing Routing Algorithms for Reducing Packet Latency and Avoiding Deadlock in Datacenter Interconnection Networks

Torus and hypercube are widely adopted as interconnection networks in parallel supercomputers and datacenters because of their powerful performance. However, when the communication traffic is heavy, many packets are buffered in the routers and wait to be sent to their destinations. Due to the limited buffers of routers and network scale, deadlocks can be prone. That is, all packets cannot advance toward their destinations because all of them are waiting on one another to release buffers. To solve this problem, this paper proposes two load-balancing routing algorithms, cycle-check and waiting-time, to avoid deadlocks and reduce packet delays. As a result, the two algorithms reduce the packet latency under heavy traffic load and the probability of deadlock through a more reasonable forwarding load allocation.