LIFE: a limited injection, fully adaptive, recovery-based routingalgorithm

摘要

Networks using wormhole switching have traditionally relied upondeadlock avoidance strategies for the design of deadlock-freealgorithms. The past few years have seen a rise in popularity ofdeadlock recovery strategies, that are based on the property thatdeadlocks are quite rare in practice and happen only at or beyond thenetwork saturation point. In fact, recovery-based routing algorithmshave a higher potential performance over the deadlock avoidance-basedones which allow less routing freedom. We present a recovery-based fullyadaptive routing algorithm, LIFE, which is based on an innovativeinjection policy that reduces the probability of deadlocks to negligiblevalues, both with uniform and non-uniform traffic patterns. Theexperimental results, conducted on an 8-ary 3-cube with 512 nodes, showthat it is possible to implement true fully adaptive routing using onlytwo virtual channels. Also, LIFE outperforms state-of-the-art avoidance-and recovery-based algorithms of the same cost both in terms ofthroughput and message latency under uniform traffic and provides stablethroughput under non-uniform traffic patterns