Near-optimal delay constrained routing in virtual circuit networks
Resource
INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE
Journal
INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies
Pages
Proceeding-s
Date Issued
2001-04
Date
2001-04
Author(s)
Yen, Hong-Hsu
Lin, Frank Yeong-Sung
DOI
N/A
Abstract
An essential issue in designing, operating and managing a modern network is to assure end-to-end quality-of-service (QoS) from users' perspective, and in the meantime to optimize a certain "average" performance objective from the system's perspective. We consider the problem of minimizing the average cross-network packet delay in virtual circuit networks subject to an end-to-end delay constraint for each origin-destination user 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. The difficulties of this problem result from the integrality nature and particularly the nonconvexity associated with the end-to-end delay constraints. The basic approach to the algorithm development is Lagrangean relaxation in conjunction with number of optimization-based heuristics. In the computational experiments, it is shown that the proposed algorithm calculates solutions which are within 1% and 3% of optimal solutions under lightly and heavily loaded conditions, respectively, in minutes of CPU time for networks with up to 26 nodes.
Type
other
File(s)![Thumbnail Image]()
Loading...
Name
00916265.pdf
Size
474.81 KB
Format
Adobe PDF
Checksum
(MD5):365efc6d20b4a68b127a5f0e8bd0c7b4