Producing deadlock-free routes in lossless cartesian topologies with minimal number of virtual lanes

An apparatus, comprising:

• a network interface, to communicate with a network that comprises a plurality of switches interconnected in a Cartesian topology having multiple dimensions;
• and
• a processor, to:
• predefine multiple turn types of turns in the Cartesian topology, wherein each turn type is defined at least by:
• (i) a respective first dimension, of the Cartesian topology, traversed immediately prior to turning in accordance with the turn type;
• and
• (ii) a respective second dimension, of the Cartesian topology, traversed immediately after turning in accordance with the turn type;
• evaluate candidate routes via the network from a source switch to a destination switch based at least on an order in which the turn types appear along sequences of hops that make-up the candidate routes;
• based on evaluation of the candidate routes, select from among the candidate routes at least one preferred route from the source switch to the destination switch, the preferred route minimizing a number of Virtual Lanes (VLs) required for preventing a deadlock condition on the preferred route;
• and
• configure one or more of the switches in the network to route packets from the source switch to the destination switch along the at least one preferred route,
• wherein, in evaluating the candidate routes, the processor is to concatenate a candidate hop to a previously calculated candidate route that ends at the destination switch so as to reach the source switch, and to evaluate the number of VLs required depending on (i) the turn type of a turn created by the candidate hop followed by an initial hop of the candidate route, and (ii) the order in which the turn types appear along the candidate route prior to concatenating the candidate hop.