Optimal locations of switches and interconnections for asynchronous transfer mode local area networks

Setting up an ATM LAN with such equipment as ATM switches and cables is known to be of high price. The setup cost can be minimized with optimal design while providing the required bandwidths for all demand pairs to maintain the quality of service (QoS) requirement. In this paper, we suggest a combined optimization problem for determining optimal locations of switches, interconnections, and their capacities which can be utilized in designing ATM LAN. Two integer programming (IP) formulations are provided for the optimal network design problem. Also, the well-known Lagrangean relaxation technique is applied to solve the IP formulations. With the algorithms, we can also obtain time-efficiency as well as upper and lower bounds of the optimal objective value. To validate our design approach, various test examples are shown. High-quality solutions for ATM LANs with average error range of about 2.2% are generated.