System and method for deadlock-free routing on arbitrary network topologies

摘要

A system and method for calculating a deadlock-free free set of paths in a network generates an ordered set of deadlock-free sub-topologies, referred to as “layers.” The ordered set of layers is then used to determine a deadlock-free set of paths through the network by performing a shortest-path route calculation with the following constraint: starting at any given layer, for each node, proceed to calculate a shortest path to every other node in the graph where, at any node being utilized to assess a given minimum path, the path may move to any higher-ordered layer, but may not return to a lower-ordered layer.