IEICE TRANSACTIONS on Communications
Linear and Nonlinear Lagrange Relaxation Algorithms for Delay-Constrained Least-Cost QoS Routing
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Communications Vol.E85-B No.11 pp.2437-2446
- Publication Date
- 2002/11/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Network
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
