Deterministic k Routing on Meshes With Applications to WormHole Routing

In k routing each of the n processing units of an n n mesh connected computer initially holds packet which must be routed such that any processor is the destination of at most k packets This problem reects practical desire for routing better than the popular routing of permutations k routing also has implications for hotpotato wormhole routing which is of great importance for real world systems We present a nearoptimal deterministic algorithm run ning in p k n O n steps We give a second algo rithm with slightly worse routing time but working queue size three Applying this algorithm considerably reduces the routing time of hotpotato wormhole routing Nontrivial extensions are given to the general lk routing problem and for routing on higher dimensional meshes Fi nally we show that kk routing can be performed in O k n steps with working queue size four Hereby the hotpotato wormhole routing problem can be solved in O k n step