
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Link Capacity Assignment in PacketSwitched Networks: The Case of Piecewise Linear Concave Cost Function
Suwan RUNGGERATIGUL Sawasd TANTARATANA
Publication
IEICE TRANSACTIONS on Communications
Vol.E82B
No.10
pp.15661576 Publication Date: 1999/10/25
Online ISSN:
DOI:
Print ISSN: 09168516 Type of Manuscript: PAPER Category: Communication Networks and Services Keyword: communication networks and services, packetswitched networks, network design, link capacity assignment, nonlinear programming, algorithm,
Full Text: PDF(787.3KB)>>
Summary:
In this paper, we study the link capacity assignment problem in packetswitched networks (CA problem) focusing on the case where link cost function is a piecewise linear concave function. This type of cost function arises in many communication network design problems such as those arising from developments in communication transmission technologies. It is already known that the method of link set assignment is applicable for solving the CA problem with piecewise linear convex cost function. That is, each link in the network is assigned to one of a group of specific sets, and checked for link set contradiction. By extending the method of link set assignment to the case of piecewise linear concave cost function, an important characteristic of the optimal solution of the CA problem is derived. Based on this characteristic, the nondifferentiable link cost function can be treated as a differentiable function, and a heuristic algorithm derived from the Lagrange multiplier method is then proposed. Although it is difficult to determine the global optimum of the CA problem due to its nonconvexity, it is shown by numerical results that the solution obtained from the proposed algorithm is very close to the global optimum. Moreover, the computation time is linearly dependent on the number of links in the problem. These performances show that the proposed algorithm is very efficient in solving the CA problem, even in the case of largescale networks.

