Traffic Constraints Instead of Traffic Matrices: Capabilities of a New Approach to Traffic Characterization


June 14, 2004


G. N. Srinivasa Prasanna


Indian Institute of Information Technology, Bangalore (IIT-B)


We have developed a reformulation of network design (routing), replacing the traffic matrix, by a set of linear constraints, representing a convex polyhedral traffic ensemble.

Linear programming is used, together with classical design techniques, to globally optimize a variety of metrics over this traffic ensemble. Where applicable, the method yields richer answers than using a traffic matrix. Firstly, network costs can be globally bounded over large scale distribution variations of traffic. This eliminates one of weaknesses of classical network design, in that the answers are dependent on detailed traffic forecasts, which are error-prone (at least for planning purposes). Secondly, inverse problems can be solved, with max/min bounds on network capacity and other metrics being derived from a pre-specified cost. Thirdly, analyses of traffic matrices can be performed, detecting hidden biases in selection. Many other kinds of results can be derived, by appropriate reformulation of the governing LP. To the best of our knowledge, we have obtained the first global bounds on network cost, with very limited knowledge of the traffic – total traffic, mean traversed distance, add-drop at nodes, are sufficient to obtain useful bounds on total network cost. The sufficient set of parameters is often less than 5% of the elements of the entire traffic matrix T and can be specified far more confidently than T. Our work has the potential to evaluate networks based on intrinsic topological and gross easily specified properties of the traffic, as opposed to point evaluations possibly modulated by uncertain traffic matrix data.

Keywords: Mathematical programming /optimization, Graph theory, Combinatorics, Economics

[Joint work with Arun Vishwanath, work partially done while at Lucent Technologies]


G. N. Srinivasa Prasanna

G. N. Srinivasa Prasanna did a B. Tech at IIT, Kanpur, in 1983 and an MS and Ph.d at MIT in 1991. He has worked in Cadence Design Systems, and AT&T/Lucent Microelectronics/Lucent Bell labs for over 11 years. Currently he is at the Indian Institute of Information Technology, in Bangalore. He is interested in a variety of disciplines, including telecommunication software, general network design and analysis, operations research, electromechanical systems, etc. He has contributed to the areas of optical networks, network and general planning under uncertainty, electromechanical systems, communication systems, etc, and has many publications and patents in these fields.