An essential issue in designing, operating and managing a modern network is to assure end-to-end QoS from users perspective, and in the meantime to optimize a certain average performance objective from the systems perspective. So in the first part of this paper, we address the above issue by using the rerouting approach, where the objective is to minimize the average cross-network packet delay in virtual circuit networks with the consideration of an end-to-end delay constraint (DCR) for each O-D pair. The problem is formulated as a multicommodity network flow problem with integer routing decision variables, where additional end-to-end delay constraints are considered. As the traffic demands increases over time, the rerouting approach may not be applicable, which results in the necessity of capacity augmentation. Henceforth, the second part of this paper is to jointly consider the link capacity assignment and the routing problem (JCR) at the same time where the objective is to minimize the total link installation cost with considering the average and end-to-end delay constraints. Unlike previous research tackling this problem with a two-phase approach, we propose an integrated approach to considering the routing and capacity assignment at the same time. The difficulties of DCR and JCR result from the integrality nature and particularly the nonconvexity property associated with the end-to-end delay constraints. We propose novel Lagrangean relaxation based algorithms to solve the DCR and the JCR problems. Through computational experiments, we show that the proposed algorithms calculate near-optimal solutions for the DCR problem and outperform previous two-phase approach for the JCR problem under all tested cases.
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
Hong-Hsu YEN, FrankYeong-Sung LIN, "Delay Constrained Routing and Link Capacity Assignment in Virtual Circuit Networks" in IEICE TRANSACTIONS on Communications,
vol. E88-B, no. 5, pp. 2004-2014, May 2005, doi: 10.1093/ietcom/e88-b.5.2004.
Abstract: An essential issue in designing, operating and managing a modern network is to assure end-to-end QoS from users perspective, and in the meantime to optimize a certain average performance objective from the systems perspective. So in the first part of this paper, we address the above issue by using the rerouting approach, where the objective is to minimize the average cross-network packet delay in virtual circuit networks with the consideration of an end-to-end delay constraint (DCR) for each O-D pair. The problem is formulated as a multicommodity network flow problem with integer routing decision variables, where additional end-to-end delay constraints are considered. As the traffic demands increases over time, the rerouting approach may not be applicable, which results in the necessity of capacity augmentation. Henceforth, the second part of this paper is to jointly consider the link capacity assignment and the routing problem (JCR) at the same time where the objective is to minimize the total link installation cost with considering the average and end-to-end delay constraints. Unlike previous research tackling this problem with a two-phase approach, we propose an integrated approach to considering the routing and capacity assignment at the same time. The difficulties of DCR and JCR result from the integrality nature and particularly the nonconvexity property associated with the end-to-end delay constraints. We propose novel Lagrangean relaxation based algorithms to solve the DCR and the JCR problems. Through computational experiments, we show that the proposed algorithms calculate near-optimal solutions for the DCR problem and outperform previous two-phase approach for the JCR problem under all tested cases.
URL: https://global.ieice.org/en_transactions/communications/10.1093/ietcom/e88-b.5.2004/_p
Copy
@ARTICLE{e88-b_5_2004,
author={Hong-Hsu YEN, FrankYeong-Sung LIN, },
journal={IEICE TRANSACTIONS on Communications},
title={Delay Constrained Routing and Link Capacity Assignment in Virtual Circuit Networks},
year={2005},
volume={E88-B},
number={5},
pages={2004-2014},
abstract={An essential issue in designing, operating and managing a modern network is to assure end-to-end QoS from users perspective, and in the meantime to optimize a certain average performance objective from the systems perspective. So in the first part of this paper, we address the above issue by using the rerouting approach, where the objective is to minimize the average cross-network packet delay in virtual circuit networks with the consideration of an end-to-end delay constraint (DCR) for each O-D pair. The problem is formulated as a multicommodity network flow problem with integer routing decision variables, where additional end-to-end delay constraints are considered. As the traffic demands increases over time, the rerouting approach may not be applicable, which results in the necessity of capacity augmentation. Henceforth, the second part of this paper is to jointly consider the link capacity assignment and the routing problem (JCR) at the same time where the objective is to minimize the total link installation cost with considering the average and end-to-end delay constraints. Unlike previous research tackling this problem with a two-phase approach, we propose an integrated approach to considering the routing and capacity assignment at the same time. The difficulties of DCR and JCR result from the integrality nature and particularly the nonconvexity property associated with the end-to-end delay constraints. We propose novel Lagrangean relaxation based algorithms to solve the DCR and the JCR problems. Through computational experiments, we show that the proposed algorithms calculate near-optimal solutions for the DCR problem and outperform previous two-phase approach for the JCR problem under all tested cases.},
keywords={},
doi={10.1093/ietcom/e88-b.5.2004},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - Delay Constrained Routing and Link Capacity Assignment in Virtual Circuit Networks
T2 - IEICE TRANSACTIONS on Communications
SP - 2004
EP - 2014
AU - Hong-Hsu YEN
AU - FrankYeong-Sung LIN
PY - 2005
DO - 10.1093/ietcom/e88-b.5.2004
JO - IEICE TRANSACTIONS on Communications
SN -
VL - E88-B
IS - 5
JA - IEICE TRANSACTIONS on Communications
Y1 - May 2005
AB - An essential issue in designing, operating and managing a modern network is to assure end-to-end QoS from users perspective, and in the meantime to optimize a certain average performance objective from the systems perspective. So in the first part of this paper, we address the above issue by using the rerouting approach, where the objective is to minimize the average cross-network packet delay in virtual circuit networks with the consideration of an end-to-end delay constraint (DCR) for each O-D pair. The problem is formulated as a multicommodity network flow problem with integer routing decision variables, where additional end-to-end delay constraints are considered. As the traffic demands increases over time, the rerouting approach may not be applicable, which results in the necessity of capacity augmentation. Henceforth, the second part of this paper is to jointly consider the link capacity assignment and the routing problem (JCR) at the same time where the objective is to minimize the total link installation cost with considering the average and end-to-end delay constraints. Unlike previous research tackling this problem with a two-phase approach, we propose an integrated approach to considering the routing and capacity assignment at the same time. The difficulties of DCR and JCR result from the integrality nature and particularly the nonconvexity property associated with the end-to-end delay constraints. We propose novel Lagrangean relaxation based algorithms to solve the DCR and the JCR problems. Through computational experiments, we show that the proposed algorithms calculate near-optimal solutions for the DCR problem and outperform previous two-phase approach for the JCR problem under all tested cases.
ER -