Patent ID: 7313630

Claim:
A method for altering link weights in an IP network having a plurality of nodes connected by a plurality of links to increase the rank of the IP network's routing matrix, wherein traffic in the IP network is described as Y=AX, Y being a link count vector obtained by measuring link utilization, A being a routing matrix derived from IP network topological information and the weights assigned to links in the IP network, and X being a traffic matrix describing the traffic between each origin-destination node pair, traffic being routed between an origin-destination node pair along the shortest path route between the nodes, the shortest path route being the set of links connecting the nodes having the lowest possible sum of weights, each set of link weights being a snapshot for which link utilization data may be collected, the method comprising: limiting the candidate snapshots to those with link weight changes that will create a new shortest route path between at least one origin-destination node pair; evaluating the candidate snapshots to determine: whether a candidate snapshot will increase the rank of the IP network's routing matrix; and whether a candidate snapshot will make the IP network's routing matrix full rank; discarding candidate snapshots that will not increase the rank of the IP network's routing matrix; discarding unevaluated candidate snapshots when a candidate snapshot is identified that will make the IP network's routing matrix full rank; applying the link weight changes of the remaining candidate snapshots to the IP network at predetermined time intervals; and collecting link utilization data for each applied snapshot.