Link set sizing for networks supporting SMDS

To size networks that support switched multimegabit data service (SMDS), one must determine how much additional capacity is needed and where it is needed so as to minimize the total capacity augmentation cost. Two combinatorial optimization problem formulations are considered and compared for their relative applicability and complexity. A solution procedure based on Lagrangean relaxation is proposed for one of the formulations. In computational experiments, the proposed algorithm determines solutions that are within a few percent of an optimal solution in minutes of CPU time for networks with 10-26 nodes. The proposed algorithm is compared with a most congested first (MCF) heuristic. For the test networks, it achieves up to 152% improvement in the total cost over the MCF heuristic