Link capacity assignment in packet-switched networks: The case of piecewise linear concave cost function

In this: paper, we study the link capacity assignment problem in packet-swi tched networks (CA problem) focusing an the case where link coat function i s a piecewise linear concave function. This type of cost function arises in many communication network design problems such as those arising from deve lopments in communication transmission technologies, It is already known th at the method of link set assignment is applicable for solving the CA probl em with piecewise linear convex cost function. That is, each link in the ne twork is as;signed to one of a, group of specific sets, and checked for lin k 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 charac teristic, the non-differentiable link cost function can he treated as a dif ferentiable function, and a heuristic algorithm derived from the Lagrange m ultiplier method is then proposed. Although it is difficult to determine th e global optimum of the CA problem due to its non-convexity, it is shown by numerical results that the solution obtained from the proposed algorithm i s very close to the global optimum. However, the computation time is linear ly dependent on the number of links in the problem. These performances that the proposed algorithm is very efficient in solving the CA problem, even i n the case of large-scab networks.