Fast simulated annealing for traffic matrix estimation
The FastSATME method and system estimate source-to-destination traffic matrices using a simulated annealing algorithm, the traffic matrix estimation being represented as a probability distribution over the set of all possible matrices that satisfy a set of given constraints. The constraints explicitly encode information that the user knows about the network traffic as components of an objective function (a fitness function), that is then minimized using simulated annealing. With the method according to the invention, arbitrary constraints of any form can be included. FastSATME works over a series of time steps. At the first time step FastSATME acts the same as SATME but in subsequent time steps, the estimate of the traffic matrix at time t is based on the estimate at t-1.
1. A method for estimating a traffic matrix for a communication network, comprising the steps of:
a) establishing a fitness function for the respective network;
b) generating a starting source to destination (SD) traffic matrix and calculating a starting value of the fitness function for the starting SD traffic matrix;
c) modifying the starting SD matrix to obtain a randomly modified SD traffic matrix and calculating a current value of the fitness function for the randomly modified SD traffic matrix;
d) selecting the SD traffic matrix corresponding to the lesser of the starting value and the current value as a temporary SD traffic matrix;
e) changing the temporary SD traffic matrix using a simulated annealing algorithm, until the fitness function of the temporary SD traffic matrix satisfies constraints to within a given tolerance;
f) selecting the temporary SD traffic matrix estimated in step e) as a potential SD traffic matrix; and
g) repeating steps b) to e) in subsequent time steps wherein the potential SD matrix of step f)is the starting SD matrix.
2. The method of claim 1 , wherein step a) comprises:
identifying absolute constraints for the fitness function expressing the actual network configuration and link counts and assigning a hard penalty to each absolute constraint;
establishing soft constraints for the fitness function based on traffic patterns and assigning a soft penalty to each soft constraint; and
calculating the fitness function as a sum of weighted elements, each weight representing a soft or a hard constraint.
3. The method of claim 2 , wherein the soft penalties are smaller than the hard penalties.
4. The method of claim 2 , wherein the absolute constraints include, for each link of the network, the link count for the respective link.
5. The method of claim 2 , wherein the soft constraint includes specified traffic patterns.
6. The method of claim 4 , wherein each element of the fitness function is calculated as a squared difference between one or more observed values.
7. The method of claim 6 , wherein each element of the fitness function accounts for all routes that use the respective link according to the routing protocol used in the network and the respective link count.
8. The method of claim 1 , wherein the elements of the starting SD traffic matrix in step b) are chosen uniformly on minimum: (x ij )=min {total traffic leaving node Ni, total traffic arriving at node Nj}.
9. The method of claim 8 , wherein step c) comprises:
uniformly choosing an element of the starting traffic matrix; and
randomly increasing or decreasing the value of the element with a pre-selected integer.
10. The method of claim 9 , wherein the pre-selected integer is 1.
11. A system for estimating a traffic matrix for a communication network comprising:
a source to destination (SD) traffic matrix generator for generating a starting SD traffic matrix based on network configuration data and on link counts collected for each link of the network;
a random number generator for randomly altering the starting SD traffic matrix to obtain a randomly modified SD traffic matrix;
a fitness function calculating unit for determining a starting fitness function and an updated fitness function for said respective SD traffic matrices and selecting the SD traffic matrix corresponding to the lesser of the starting value and the current value as a temporary SD traffic matrix; and
a simulated annealing (SA) algorithm processor for changing the temporary SD traffic matrix until the fitness function of the temporary SD traffic matrix satisfies constraints within a given tolerance; and selecting the SD traffic matrix corresponding to a minimum as a potential SD traffic matrix,
wherein the potential SD traffic matrix is sent back to the traffic matrix generator for use in generating the new starting SD matrix for a subsequent time step.
12. The system of claim 11 , wherein the fitness function calculating unit calculates the fitness function based on constraints.
13. The system of claim 11 , wherein the fitness function is expressed as a sum of weighted elements.