Header-population based flow control for multicomputer networks

Wormhole routing is a very popular cut-through switching technique used in multicomputers due to its small network latency and simplicity in hardware. Although wormhole routing offers high throughput in an uncongested network, its throughput sharply drops whenever there is a congestion or blocking. In this paper, we present a new flow control technique, called header population based flow control (HP), for direct networks employing wormhole switching. When the traffic of a node increases, HP takes two actions: (1) it prevents the local processor of the node from injecting a new packet if the number of header flits in the router reaches a given injection threshold, and (2) among those header flits requesting the same output channel of the router, it selects the header flit whose buffer is filled with more flits if the number of header flits in the router reaches a given selection threshold. We have conducted extensive simulations to compare the network performance with and without HP in the networks using wormhole switching. Our simulation results show that HP improves network throughput significantly at high network traffic without sacrificing network latency. This paper also introduces an analytical model and derives a closed form expression for network latency when HP is used along with wormhole switching in direct networks. This model is validated through simulations and is found to agree closely with simulations.