Wk. Liao et Ct. King, VALVED ROUTING - EFFICIENT FLOW-CONTROL FOR ADAPTIVE NONMINIMAL ROUTING IN INTERCONNECTION NETWORKS, I.E.E.E. transactions on computers, 44(10), 1995, pp. 1181-1193
Adaptive nonminimal routing (or misrouting) may move messages away fro
m their destinations to temporarily cope with the dynamic load in an i
nterconnection network. In most cases, misrouting is more powerful and
flexible than minimal routing, especially under nonuniform load distr
ibution. However, to take advantage of its misrouting, we have to avoi
d deadlock, livelock, and starvation in the network and to maintain th
e network performance across all levels of loading. In this paper, we
propose a new flow control scheme for misrouting, called valved routin
g. Valved routing controls message injection and transmission through
logical valves associated with the router ports. Designing routers usi
ng valved routing requires a proper choice of design parameters. We wi
ll discuss how to find the range of feasible design parameters, Issues
in implementing routers using valved routing will also be addressed.
We have conducted extensive simulations to compare the performance of
routers with and without valved routing. Our simulation results show t
hat valved routing has promising performance advantages, at light as w
ell as heavy network load. Compared with the voluntary misrouting [15]
, valved routing performs better in network throughput without sacrifi
cing the latency.