Patent ID: 7957266

Claim:
A computer-implemented method of routing data through a network of nodes interconnected by links and having at least one ingress point and at least one egress point, comprising the steps of: (a) a computer receiving a request for routing data between the ingress point and the egress point; (b) the computer selecting at least first and second intermediate nodes between the ingress point and the egress point; (c) the computer determining, after completion of step (b) and based on a bandwidth of said network, a first, non-zero fraction of the data to send from the ingress point to the first selected intermediate node; (d) the computer determining, after completion of step (b) and based on the bandwidth of said network, a second, non-zero fraction of the data to send from the ingress point to the second selected intermediate node; (e) the computer routing, from the ingress point to the first intermediate node, a first subset of the data corresponding to the determined first, non-zero fraction; (f) the computer routing, from the ingress point to the second intermediate node, a second subset of the data corresponding to the determined second, non-zero fraction; (g) the computer routing the first subset of the data from the first selected intermediate node to the egress point; and (h) the computer routing the second subset of the data from the second selected intermediate node to the egress point; wherein the determinations of the first and second fractions in steps (c) and (d) are made by solving a linear program having primal and dual solutions, wherein flows along said links are augmented in the primal solution, and weights of the links are updated in a multiplicative fashion in the dual solution.