Patent ID: 7110389

Claim:
A method for generating routes for routing data packets in a network of interconnected nodes, the nodes being at least partially interconnected by links, the method comprising: generating static path, source-based routes for routing data packets in the network of interconnected nodes, the generating of static path, source-based routes comprising: (i) selecting a source node—destination node (S-D) group with common starting and ending sets of links from the network of interconnected nodes; (ii) selecting shortest static path, source-based routes between at least some S-D nodes of the S-D group so that: (a) selected static path, source-based routes substantially uniformly fan out from the source nodes to a center of the network and fan in from the center of the network to the destination nodes; (b) local balance of static path, source-based routes between selected S-D nodes of the S-D group passing through links that are at the same level of the network is achieved; and (c) global balance of static path, source-based routes passing through links that are at the same level of the network is achieved; wherein said selecting (ii) comprises exploring the network from a source node until a destination node is reached, and for each S-D pair of the group, prioritizing output ports at each stage based on least global weight of links on a node switch board (NSB), and by rank ordering output ports based on next level usage before prioritizing based on global weight of links on an intermediate switch board (ISB); and wherein said rank ordering comprises rank ordering output ports of the ISB such that ports with less traffic have a higher rank, and if more than one output port has a same rank, reordering the ranking so that an output port with a lower global weight on its link receives higher priority.