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]