Relative Traffic Density and Network Topological Design

Since network topological design has been shown to be NP-hard, we turn to heuristics for solution. However, heuristics may perform differently given different input data. In this report, relative traffic density is defined in terms of sustainable cell rate and fiber capacity for the purpose of predicting the performance of a heuristic for network topological design presented in [1]. Key Words: relative traffic density, network topological design 1 Network Topological Design Given traffic demand and cost information of network components, what is the most cost effective network topology? This question is answered by network topological design. Since network topological design has been shown to be NP-hard, we turn to heuristics for solution. In [1], we model network topological design problem as a non-linear integer programming problem and use a row-generation based heuristic to solve the problem. Since the heuristic can only provide an approximate solution, we developed a lower bound ..