%0 Journal Article
%T Optimizing Virtual Private Network Design Using a New Heuristic Optimization Method
%A Hongbing Lian
%A Andr¨˘s Farag¨®
%J ISRN Communications and Networking
%D 2012
%R 10.5402/2012/914953
%X In virtual private network (VPN) design, the goal is to implement a logical overlay network on top of a given physical network. We model the traffic loss caused by blocking not only on isolated links, but also at the network level. A successful model that captures the considered network level phenomenon is the well-known reduced load approximation. We consider here the optimization problem of maximizing the carried traffic in the VPN. This is a hard optimization problem. To deal with it, we introduce a heuristic local search technique called landscape smoothing search (LSS). This study first describes the LSS heuristic. Then we introduce an improved version called fast landscape smoothing search (FLSS) method to overcome the slow search speed when the objective function calculation is very time consuming. We apply FLSS to VPN design optimization and compare with well-known optimization methods such as simulated annealing (SA) and genetic algorithm (GA). The FLSS achieves better results for this VPN design optimization problem than simulated annealing and genetic algorithm. 1. Introduction In the VPN setting the goal is to implement a logical overlay network on top of a given physical network. We consider here the optimization problem of maximizing the carried traffic in the VPN. In other words, we want to minimize the loss caused by blocking some of the offered traffic, due to insufficient capacity in the logical links. A key feature in the VPN setting is that the underlying physical network is already given. Thus, our degree of freedom lies only in dimensioning the logical (virtual) links. However, since the given physical link capacities must be obeyed and a physical link may be shared by several logical links, we can reduce the blocking on a logical link possibly only by taking away capacity from other logical links. Therefore, we may be able to improve a logical link only by degrading others. The above described situation leads to a hard optimization problem. Mitra et al. [1] analyzed a network loss probability caused by blocking with fixed point equations (FPEs). They derived the loss probability only based on assumption of link independence. Actual difficulty is posed by the fact that we need to model the traffic loss caused by blocking not only on isolated links, but also at the network level. This means we also need to take into account that the loss suffered on a link reduces the offered traffic of other links and vice versa, so a complex system of mutual influences arise. This situation calls for a more sophisticated machinery than blocking
%U http://www.hindawi.com/journals/isrn.communications.networking/2012/914953/