Patent ID: 7809006

Claim:
A method comprising: configuring a system having communication nodes coupled by communication links according to a non-deterministic deadlock-free routing function, the non-deterministic routing function being defined according to a deterministic deadlock-free routing function that makes use of each of a plurality of virtual channels for passing communication over the communication links, and the plurality of virtual channels having an order for the virtual channels, the order of the channels being defined by an ordered labeling of the channels; wherein the non-deterministic routing function defines permissible virtual channels for routing a message at a node according to application of the deterministic routing function to the message, and additional of the plurality of virtual channels identified according to the result of application of the deterministic routing function and the order for the virtual channels routing a message according to the non-deterministic routing function, including accepting the message at a first node over a first virtual channel; identifying a set of permissible next virtual channels for forwarding a first communication, the set of permissible next virtual channels including a second virtual channel defined by the deterministic routing function for forwarding the first communication, and further including a set of additional virtual channels that satisfy a constraint defined by the order of the virtual channels; and wherein identifying the set of permissible next virtual channels includes identifying the set of additional virtual channels to have labels that precede the label of the second channel according to the ordered labeling of the channels.