Simulated annealing for traffic matrix estimation
AssigneeAlcatel
InventorsPeter Rabinovitch, Brian McBride
Life of this patent
Estimating the term…
Abstract
The SATME method and system estimates 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, and the case where there are no feasible solutions can be diagnosed by the objective function not converging to zero.
Claims16
A method for estimating a traffic matrix for a communication network based on given link counts, 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 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 less 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 reaches a minimum;
- and
- f) selecting the temporary SD traffic matrix estimated in step e) as a potential SD traffic matrix and repeating steps b) to e) for a pre-selected number of times.
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 less 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 reaches a minimum, and selecting the SD traffic matrix corresponding to the minimum as a potential SD traffic matrix.
Dependencies are inferred from the claim text.