A Layered Network Flow Algorithm for the Tunnel Design Problem in Virtual Private Networks with QoS Guarantee
Sang Hwa Song, Chang Sup Sung · Management Science and Financial Engineering · 2006
This paper considers the problem of designing logical tunnels in virtual private networks considering QoS guarantee which restricts the number of tunnel hops for each traffic routing. The previous researches focused on the design of logical tunnel itself and Steiner-tree based solution algorithms were proposed. However, we show that for some objective settings it is not sufficient and is necessary to consider both physical and logical connectivity at the same time. Thereupon, the concept of the layered network is applied to the logical tunnel design problem in virtual private networks. The layered network approach considers the design of logical tunnel as well as its physical routing and we propose a modified branch-and-price algorithm which is known to solve layered network design problems effectively. To show the performance of the proposed algorithm, computational experiments have been done and the results show that the proposed algorithm solves the given problem efficiently and effectively.