Upgrading links for performance

Author

Lim, Andrew ; Yoew Meng Chen ; Hsu, Wynne

Author_Institution

Inst. of Inf. Technol., Nat. Univ. of Singapore, Singapore

fYear

1995

fDate

3-7 Jul 1995

Firstpage

398

Lastpage

402

Abstract

The performance of a computer network is commonly measured by the maximum minimum time required to move certain amount of data between any 2 nodes in the network. Due to the advances in technology, links in the network may now be upgraded, for instance to optical fibre links, so that better performance can be achieved. We study the link upgrade problem for networks. We first show that the link upgrade problem is NP-complete. We also show that, a closely related problem, the minimum cost link upgrade problem is NP-complete even if the underlying topology of the network is a linear array. However, for certain classes of networks, the link upgrade problem can be solved in polynomial time. For general networks, we provide effective heuristics for the above problems

Keywords

computational complexity; computer networks; graph theory; network topology; optical fibre networks; performance evaluation; polynomials; telecommunication links; NP-complete; computer network performance; heuristics; linear array; link performance; link upgrade problem; minimum cost link upgrade problem; network nodes; network topology; optical fibre links; polynomial time; Computer networks; Costs; Drives; ISDN; Information technology; Large-scale systems; Network topology; Optical fibers; Polynomials; Time measurement;

fLanguage

English

Publisher

ieee

Conference_Titel

Networks, 1995. Theme: Electrotechnology 2000: Communications and Networks. [in conjunction with the] International Conference on Information Engineering., Proceedings of IEEE Singapore International

Print_ISBN

0-7803-2579-6

Type

conf

DOI

10.1109/SICON.1995.526316

Filename

526316