Patent ID: 7633867

Claim:
A method of allocating demands of a plurality of connections transferring data through a network of nodes connected by links, the method comprising the steps of: (a) initializing a weight of each link based on a capacity of the link; (b) routing a demand for a current connection by the steps of: (b1) generating a minimum path weight for paths through nodes and links of the network for the current connection, wherein the minimum path weight is the least sum of link weights for links of each length-bounded path between a source node and a destination node of the current connection, (b2) determining an optimal length-bounded path through nodes and links of the network for the current connection based on the minimum path weight, (b3) routing a portion of a remainder of the demand as one or more flows over the length-bounded path, wherein the portion is based on a lesser value of the remainder of the demand and a minimum capacity of links in the length-bounded path, (b4) updating i) the link weight of each link based on the routed portion and a capacity of the link and ii) the remainder of the demand, and (b5) repeating steps (b1)-(b4) until the demand is routed; (d) repeating step (b) for each of the plurality of connections; (e) solving a linear programming problem having primal and dual sets of constraints to generate a scaling value based on a maximum ratio of a flow over a link and a capacity of the link; and (f) scaling, based on the scaling value, either i) each capacity of the plurality of links or ii) each demand of the plurality of connections.