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
고속 네트워크 환경에서 효율적인 QoS(Quality of Service) 라우팅 알고리즘을 개발하는 것은 매우 중요하면서도 동시에 여러 QoS 요구 사항을 지닌 다양한 서비스를 제공해야 하기 때문에 매우 어려운 작업입니다. 최근에는 시간 복잡도와 해의 품질 간의 모순을 해결하기 위해 라그랑주 완화 기법을 기반으로 한 휴리스틱 알고리즘이 제안되었습니다. 본 논문에서는 지연 제약이 있는 최소 비용(DCLC) 라우팅 문제에 대해 두 가지 휴리스틱 알고리즘인 LR_DCLC와 NR_DCLC의 성능을 조사합니다. 알고리즘 LR_DCLC는 선형 완화를 기반으로 하며, 본 논문에서 제안하는 알고리즘 NR_DCLC는 비선형 완화를 기반으로 합니다. 많은 시뮬레이션을 통해 두 알고리즘 모두 매우 우수한 성능을 갖고 있음에도 불구하고 특히 최적의 솔루션을 찾기 어려운 경우 Dijkstra 알고리즘을 평균 몇 번 더 실행하여 NR_DCLC가 LR_DCLC보다 훨씬 더 나은 솔루션을 얻을 수 있음을 보여줍니다.
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.
부
Gang FENG, Christos DOULIGERIS, Kia MAKKI, Niki PISSINOU, "Linear and Nonlinear Lagrange Relaxation Algorithms for Delay-Constrained Least-Cost QoS Routing" in IEICE TRANSACTIONS on Communications,
vol. E85-B, no. 11, pp. 2437-2446, November 2002, doi: .
Abstract: The development of efficient quality of service (QoS) routing algorithms in a high-speed network environment is a very important and at the same time very difficult task due to the need to provide divergent services with multiple QoS requirements. Recently heuristic algorithms based on Lagrange relaxation techniques have been proposed to resolve the contradiction between the time complexity and the quality of solution. In this paper, we investigate the performance of two heuristic algorithms, LR_DCLC and NR_DCLC, for the delay-constrained least-cost (DCLC) routing problem. Algorithm LR_DCLC is based on linear relaxation, while algorithm NR_DCLC, which is proposed in this paper, is based on nonlinear relaxation. A large number of simulations demonstrate that even though both algorithms have very good performance, NR_DCLC can obtain much better solutions than LR_DCLC by running Dijkstra's algorithm on average a few more times, especially in the case when the optimal solutions are hard to find.
URL: https://global.ieice.org/en_transactions/communications/10.1587/e85-b_11_2437/_p
부
@ARTICLE{e85-b_11_2437,
author={Gang FENG, Christos DOULIGERIS, Kia MAKKI, Niki PISSINOU, },
journal={IEICE TRANSACTIONS on Communications},
title={Linear and Nonlinear Lagrange Relaxation Algorithms for Delay-Constrained Least-Cost QoS Routing},
year={2002},
volume={E85-B},
number={11},
pages={2437-2446},
abstract={The development of efficient quality of service (QoS) routing algorithms in a high-speed network environment is a very important and at the same time very difficult task due to the need to provide divergent services with multiple QoS requirements. Recently heuristic algorithms based on Lagrange relaxation techniques have been proposed to resolve the contradiction between the time complexity and the quality of solution. In this paper, we investigate the performance of two heuristic algorithms, LR_DCLC and NR_DCLC, for the delay-constrained least-cost (DCLC) routing problem. Algorithm LR_DCLC is based on linear relaxation, while algorithm NR_DCLC, which is proposed in this paper, is based on nonlinear relaxation. A large number of simulations demonstrate that even though both algorithms have very good performance, NR_DCLC can obtain much better solutions than LR_DCLC by running Dijkstra's algorithm on average a few more times, especially in the case when the optimal solutions are hard to find.},
keywords={},
doi={},
ISSN={},
month={November},}
부
TY - JOUR
TI - Linear and Nonlinear Lagrange Relaxation Algorithms for Delay-Constrained Least-Cost QoS Routing
T2 - IEICE TRANSACTIONS on Communications
SP - 2437
EP - 2446
AU - Gang FENG
AU - Christos DOULIGERIS
AU - Kia MAKKI
AU - Niki PISSINOU
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Communications
SN -
VL - E85-B
IS - 11
JA - IEICE TRANSACTIONS on Communications
Y1 - November 2002
AB - The development of efficient quality of service (QoS) routing algorithms in a high-speed network environment is a very important and at the same time very difficult task due to the need to provide divergent services with multiple QoS requirements. Recently heuristic algorithms based on Lagrange relaxation techniques have been proposed to resolve the contradiction between the time complexity and the quality of solution. In this paper, we investigate the performance of two heuristic algorithms, LR_DCLC and NR_DCLC, for the delay-constrained least-cost (DCLC) routing problem. Algorithm LR_DCLC is based on linear relaxation, while algorithm NR_DCLC, which is proposed in this paper, is based on nonlinear relaxation. A large number of simulations demonstrate that even though both algorithms have very good performance, NR_DCLC can obtain much better solutions than LR_DCLC by running Dijkstra's algorithm on average a few more times, especially in the case when the optimal solutions are hard to find.
ER -