Patent ID: 7280526

Claim:
A method for determining routing in a network to achieve an objective value within a prescribed bound from its minimum value, the network comprising a plurality of nodes interconnected through links, the method comprising: concurrently routing demands for each of a plurality of commodities on a set of paths having a minimum cost with respect to an iteratively changing cost function, each set of paths comprising at least one primary path and a secondary path, wherein each of the demands is routed from a primary path to a secondary path of the set during a failure; adjusting link costs using an exponential function based on an amount of flow through links over which each demand is routed and based on said at least one primary path and said secondary path; performing the step of adjusting for each of a number of potential failures; and iterating the steps of routing, adjusting, and performing until an objective value is reached which is within a prescribed bound of a pre-determined value, such that flow for each of the links in the network is determined.