Patent ID: 7558209

Claim:
A method of routing traffic in a network of nodes interconnected by links and having at least one ingress point and at least one egress point, the method comprising: solving, using a computer, a polynomial-size linear program derived from a combination of: a first liner program having infinite constraints and adapted to minimize maximum-link utilization of a link in a path between the ingress point and the egress point; and a second linear program adapted to determine whether any constraint of the first linear program is violated; implementing, during a first routing phase, based on the solution to the polynomial-size linear problem, a first routing method for routing a fraction of traffic between the at least one ingress point and at least one intermediate node; and implementing, during a second routing phase, based on the solution to the polynomial-size linear problem, a second routing method for routing a fraction of traffic between the at least one intermediate node and the at least one egress point.