The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Neste artigo, estudamos o problema de atribuição de capacidade de enlace em redes comutadas por pacotes (problema CA) com foco no caso em que a função custo do enlace é uma função côncava linear por partes. Este tipo de função de custo surge em muitos problemas de projeto de redes de comunicação, como aqueles decorrentes do desenvolvimento de tecnologias de transmissão de comunicação. Já se sabe que o método de atribuição de conjunto de links é aplicável para resolver o problema de CA com função de custo convexa linear por partes. Ou seja, cada link na rede é atribuído a um grupo de conjuntos específicos e verificado quanto à contradição do conjunto de links. Ao estender o método de atribuição de conjunto de links para o caso de função de custo côncava linear por partes, uma característica importante da solução ótima do problema de CA é derivada. Com base nesta característica, a função de custo do enlace não diferenciável pode ser tratada como uma função diferenciável, e um algoritmo heurístico derivado do método do multiplicador de Lagrange é então proposto. Embora seja difícil determinar o ótimo global do problema de CA devido à sua não convexidade, mostra-se pelos resultados numéricos que a solução obtida a partir do algoritmo proposto está muito próxima do ótimo global. Além disso, o tempo de cálculo depende linearmente do número de links no problema. Esses desempenhos mostram que o algoritmo proposto é muito eficiente na resolução do problema de CA, mesmo no caso de redes de grande porte.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Suwan RUNGGERATIGUL, Sawasd TANTARATANA, "Link Capacity Assignment in Packet-Switched Networks: The Case of Piecewise Linear Concave Cost Function" in IEICE TRANSACTIONS on Communications,
vol. E82-B, no. 10, pp. 1566-1576, October 1999, doi: .
Abstract: In this paper, we study the link capacity assignment problem in packet-switched 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 non-differentiable 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 non-convexity, 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 large-scale networks.
URL: https://global.ieice.org/en_transactions/communications/10.1587/e82-b_10_1566/_p
Copiar
@ARTICLE{e82-b_10_1566,
author={Suwan RUNGGERATIGUL, Sawasd TANTARATANA, },
journal={IEICE TRANSACTIONS on Communications},
title={Link Capacity Assignment in Packet-Switched Networks: The Case of Piecewise Linear Concave Cost Function},
year={1999},
volume={E82-B},
number={10},
pages={1566-1576},
abstract={In this paper, we study the link capacity assignment problem in packet-switched 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 non-differentiable 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 non-convexity, 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 large-scale networks.},
keywords={},
doi={},
ISSN={},
month={October},}
Copiar
TY - JOUR
TI - Link Capacity Assignment in Packet-Switched Networks: The Case of Piecewise Linear Concave Cost Function
T2 - IEICE TRANSACTIONS on Communications
SP - 1566
EP - 1576
AU - Suwan RUNGGERATIGUL
AU - Sawasd TANTARATANA
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Communications
SN -
VL - E82-B
IS - 10
JA - IEICE TRANSACTIONS on Communications
Y1 - October 1999
AB - In this paper, we study the link capacity assignment problem in packet-switched 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 non-differentiable 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 non-convexity, 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 large-scale networks.
ER -