Patent ID: 7313629

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 may be 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 route path between the nodes, the shortest route path 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; limiting the candidate snapshots to those that comply with predetermined network performance parameters; ordering the candidate snapshots based upon the amount of network traffic information a candidate snapshot is likely to provide, the candidate snapshots being ordered from those likely to provide the most network traffic information to those likely to provide the least network traffic information; evaluating the candidate snapshots in order, from those likely to provide the most network traffic information data to those likely to provide the least network traffic information, 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 candidate snapshots ordered after the candidate snapshot that will make the IP network's routing matrix full rank; applying the link weight changes of the remaining candidate snapshots to the communication network at predetermined intervals; and collecting link utilization data for each applied snapshot.