Patent ID: 7724674

Claim:
A method for establishing a routing scheme defining a path between any given pair of source node and destination node in a network including a plurality of nodes connected by links, said method comprising: defining a plurality of virtual network layers in the network, each virtual network layer including addresses for identifying each node, and channels for communicating between said nodes using said addresses, defining a routing function for each layer in the network, said routing scheme including all routing functions, each routing function having a set of source node/destination node pairs and a path connecting each pair, by repeating the following steps for each pair of source node/destination node: defining a cost function for each layer, said cost function being adapted to assign a high cost to any path creating a deadlock, using said cost function to assign a cost to each path in each layer connecting the source node/destination node pair, selecting the path with the lowest cost, and assigning the pair of source node/destination node and the selected path to the routing function of the layer that contains said selected path, wherein defining a routine function further comprises: defining a set of constraints, defining a set of dependencies, for each pair of source and destination, a) determine a lowest cost path between said source and said destination complying with said set of constraints, b) determine if said path causes a deadlock, c) if a deadlock is caused, identify a connection of two links in a node that causes said deadlock, include said connection in said set of constraints, and return to step a), d) if no deadlock is caused, add any dependencies created by said path to said set of dependencies, and proceed with the next pair of source and destination.