In future high-speed networks, provision of diverse multimedia services with strict quality-of-service (QoS) requirements, such as bandwidth, delay and so on, is desired. QoS routing is a possible solution to handle these services. Generally, a path selection for QoS routing is formulated as a shortest path problem subject to multiple constraints. However, it is known to be NP-complete when more than one QoS constraint is imposed. As a result, many heuristic algorithms have been proposed so far. The authors proposed a path selection algorithm Fallback+ for QoS routing, which focuses not only on the path selection with multiple constraints but also on the efficient use of network resources. This paper proposes an enhanced version of Fallback+, named Enhanced Fallback+, where in a shrewd way, it keeps tentative paths produced in the conventional Fallback algorithm with Dijkstra's algorithm. Simulation experiments prove the excellent performance of Enhanced Fallback+, compared with the original Fallback+ and other existing path selection algorithms.
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.
Copy
Kazuhiko KINOSHITA, Hideaki TANIOKA, Tetsuya TAKINE, Koso MURAKAMI, "Enhanced Fallback+: An Efficient Multiconstraint Path Selection Algorithm for QoS Routing" in IEICE TRANSACTIONS on Communications,
vol. E87-B, no. 9, pp. 2708-2718, September 2004, doi: .
Abstract: In future high-speed networks, provision of diverse multimedia services with strict quality-of-service (QoS) requirements, such as bandwidth, delay and so on, is desired. QoS routing is a possible solution to handle these services. Generally, a path selection for QoS routing is formulated as a shortest path problem subject to multiple constraints. However, it is known to be NP-complete when more than one QoS constraint is imposed. As a result, many heuristic algorithms have been proposed so far. The authors proposed a path selection algorithm Fallback+ for QoS routing, which focuses not only on the path selection with multiple constraints but also on the efficient use of network resources. This paper proposes an enhanced version of Fallback+, named Enhanced Fallback+, where in a shrewd way, it keeps tentative paths produced in the conventional Fallback algorithm with Dijkstra's algorithm. Simulation experiments prove the excellent performance of Enhanced Fallback+, compared with the original Fallback+ and other existing path selection algorithms.
URL: https://global.ieice.org/en_transactions/communications/10.1587/e87-b_9_2708/_p
Copy
@ARTICLE{e87-b_9_2708,
author={Kazuhiko KINOSHITA, Hideaki TANIOKA, Tetsuya TAKINE, Koso MURAKAMI, },
journal={IEICE TRANSACTIONS on Communications},
title={Enhanced Fallback+: An Efficient Multiconstraint Path Selection Algorithm for QoS Routing},
year={2004},
volume={E87-B},
number={9},
pages={2708-2718},
abstract={In future high-speed networks, provision of diverse multimedia services with strict quality-of-service (QoS) requirements, such as bandwidth, delay and so on, is desired. QoS routing is a possible solution to handle these services. Generally, a path selection for QoS routing is formulated as a shortest path problem subject to multiple constraints. However, it is known to be NP-complete when more than one QoS constraint is imposed. As a result, many heuristic algorithms have been proposed so far. The authors proposed a path selection algorithm Fallback+ for QoS routing, which focuses not only on the path selection with multiple constraints but also on the efficient use of network resources. This paper proposes an enhanced version of Fallback+, named Enhanced Fallback+, where in a shrewd way, it keeps tentative paths produced in the conventional Fallback algorithm with Dijkstra's algorithm. Simulation experiments prove the excellent performance of Enhanced Fallback+, compared with the original Fallback+ and other existing path selection algorithms.},
keywords={},
doi={},
ISSN={},
month={September},}
Copy
TY - JOUR
TI - Enhanced Fallback+: An Efficient Multiconstraint Path Selection Algorithm for QoS Routing
T2 - IEICE TRANSACTIONS on Communications
SP - 2708
EP - 2718
AU - Kazuhiko KINOSHITA
AU - Hideaki TANIOKA
AU - Tetsuya TAKINE
AU - Koso MURAKAMI
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Communications
SN -
VL - E87-B
IS - 9
JA - IEICE TRANSACTIONS on Communications
Y1 - September 2004
AB - In future high-speed networks, provision of diverse multimedia services with strict quality-of-service (QoS) requirements, such as bandwidth, delay and so on, is desired. QoS routing is a possible solution to handle these services. Generally, a path selection for QoS routing is formulated as a shortest path problem subject to multiple constraints. However, it is known to be NP-complete when more than one QoS constraint is imposed. As a result, many heuristic algorithms have been proposed so far. The authors proposed a path selection algorithm Fallback+ for QoS routing, which focuses not only on the path selection with multiple constraints but also on the efficient use of network resources. This paper proposes an enhanced version of Fallback+, named Enhanced Fallback+, where in a shrewd way, it keeps tentative paths produced in the conventional Fallback algorithm with Dijkstra's algorithm. Simulation experiments prove the excellent performance of Enhanced Fallback+, compared with the original Fallback+ and other existing path selection algorithms.
ER -