Patent ID: 7313095
Filing Date: 2007-12-25
Classification: H04L

Abstract:
1. A method for altering link weights in an IP network and estimating the mean traffic and the variance of traffic between origin-destination node pairs of the IP network, the IP network comprising a plurality of nodes connected by a plurality of links, each link being assigned a weight used to determine the shortest path route between a pair of nodes, the traffic matrix describing the total traffic between each origin-destination node pair in the IP network over a given time period k being X(k), such that Y(k)=A(k)X(k) where Y(k) is a vector of measured utilization values for each link at a time k and A(k) is a routing matrix describing the routing of traffic between origin-destination node pairs on links of the shortest path route between the origin node and the destination node, the shortest path route being the set of links between the origin node and the destination node having the lowest sum of link weights, each set of link weights being a snapshot, the method for altering link weights and estimating the mean traffic and the variance of traffic 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 candidate snapshots to those that comply with predetermined network performance parameters; ordering the candidate snapshots based upon the amount of new link utilization information a candidate snapshot is likely to provide, the candidate snapshots being ordered from those likely to provide the most new link utilization data to those likely to provide the least new link utilization data; evaluating the candidate snapshots in order, from those likely to provide the most new link utilization data to those likely to provide the least new link utilization data, 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 IP network's routing matrix full rank; applying each remaining candidate snapshot to the IP network at predetermined times k, with the initial IP network link weights being the snapshot for time k=0, and with subsequent snapshots being snapshots for times k=0,12, . . . ,K−1; collecting link utilization values at times k=0,12, . . . , K−1, so that link utilization values are collected for each applied snapshot; constructing link count vectors Y(k) using the collected link utilization values; constructing routing matrices A(k) using the IP network's topological information and the weight assigned to each link in the IP network at each time k, such that Y(k)=A(k)X(k); deleting missing and redundant rows in Y(k) and in A(k) to produce Y′(k) and A′(k), such that Y′(k)=A′(k)X(k); modeling the traffic matrix X(k) as stationary, such that X(k)=x+W(k), wherein W(k) is a traffic fluctuation matrix and x is a vector describing the mean traffic between each origin-destination node pair in the IP network; defining, in block matrix notation: defining B as the covariance matrix of W, such that B=E[WW iteratively estimating x, the vector describing the mean traffic between each origin-destination node pair in the IP network, and B, the covariance of the fluctuation traffic matrix.