Traffic Constraints Instead of Traffic Matrices: A New Approach to Traffic Characterization

Опубликовано 6 сентября 2016, 5:00

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 Mathematical programming /optimization, Graph theory, Combinatorics, Economics [Joint work with Arun Vishwanath, work partially done while at Lucent Technologies]