Link set sizing for networks supporting SMDS

Author

Lin, Frank Y S

Author_Institution

Bell Commun. Res., Piscataway, NJ, USA

Volume

1

Issue

6

fYear

1993

fDate

12/1/1993 12:00:00 AM

Firstpage

729

Lastpage

739

Abstract

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

Keywords

computer networks; data communication systems; optimisation; packet switching; telecommunication links; telecommunication traffic; CPU time; LAN; Lagrangean relaxation; MAN; SMDS; WAN; algorithm; combinatorial optimization problem; link set sizing; most congested first heuristic; network capacity; network sizing; nodes; switched multimegabit data service; total capacity augmentation cost; Aggregates; Computer networks; Costs; Lagrangian functions; Linear programming; Monitoring; Routing; Switches; Telecommunication traffic; Testing;

fLanguage

English

Journal_Title

Networking, IEEE/ACM Transactions on

Publisher

ieee

ISSN

1063-6692

Type

jour

DOI

10.1109/90.266060

Filename

266060