Backbone network design with QoS requirements
Journal
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Journal Volume
2094
Pages
148-157
Date Issued
2001
Author(s)
Yen, H.-H
Abstract
In this paper, we consider the backbone network design problem with a full set of QoS requirements. Unlike previous researches, we consider both the transmission line cost and the switch cost. And the QoS requirements that we considered include the average packet delay, end-to-end packet delay and node disjoint paths. We formulate the problem as a combinatorial optimization problem where the objective function is to minimize the total network deployment cost subject to the aforementioned QoS constraints. Besides the integrality constraints, the nonlinear and the nonconvex properties associated with the problem formulation make it difficult. Lagrangean relaxation in conjunction with a number of optimization-based heuristics are proposed to solve this problem. From the computational experiments, the proposed algorithms calculate creditable solutions in minutes of CPU time for moderate problem sizes. © Springer-Verlag Berlin Heidelberg 2001.
Other Subjects
Combinatorial optimization; Optimization; Average packet delays; Combinatorial optimization problems; Computational experiment; Integrality constraints; Lagrangean Relaxation; Network deployment cost; Objective functions; Problem formulation; Quality of service
Type
conference paper