An approach to introducing adaptive routing into a communication approach for passing messages between nodes over links between the nodes includes forming virtual channels over the links of the system and defining a deterministic routing function over the virtual channels such that the deterministic routing function is deadlock free. Adaptive routing is then permitted at nodes using the existing virtual channels by introducing a constraint on the available virtual channels used to forward communication that arrives at a node for a particular destination. The constraint on the virtual channels is such that the adaptive system is also deadlock free.