Minimal turn restrictions for designing deadlock-free adaptive routing

A routing algorithm is basically required to be connected and deadlock-free. We can restrict some directions that messages can turn in a network to avoid deadlock. A deadlock-free adaptive routing with fewer turn restrictions is considered to possess a greater degree of adaptiveness. We present two basic strategies for designing feasible routings on networks which have bidirectional channels. Primer investigation of our strategies reveals their ability to obtain minimal turn restrictions on some typical multicomputer networks, like hypercube, mesh and torus