Next: Determining Deadlock Freedom Up: Routing Algorithms Previous: Deadlock

Dimension Order Routing

Common approach to routing for k-ary n-cubes.

Known as:

Dimensions of k-ary n-cube placed into order.

Packet first routed to correct position in higher dimension before attempting to route in next dimension.

For example in a 2D mesh, route first in X dimension, then in Y dimension.

Consider routing from (2,0) to (1,2):

Is it minimal?

Is it deadlock free?

Paul H J Kelly Fri Apr 24 19:49:58 BST 1998