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
References
[1]
D. Mitra, J. A. Morrison, and K. G. Ramakrishnan, “Virtual private networks: joint resource allocation and routing design,” in Proceedings of the 18th Annual Joint Conference of the IEEE Computer and Communications Societie (INFOCOM '99), pp. 480–490, March 1999.
[2]
F. P. Kelly, “Kelly blocking probabilities in large circuit-switched networks,” Advances in Applied Probability, vol. 18, no. 2, pp. 473–505, 1986.
[3]
K. W. Ross, Multiservice Loss Models for Broadband Telecommunication Networks, Springer, New York, NY, USA, 1995.
[4]
W. Whitt, “Blocking when service is required from several facilities simultaneously,” AT&T Technical Journal, vol. 64, no. 8, pp. 1807–1856, 1985.
[5]
H. Lian and A. Faragó, “A heuristic optimization method and its application in cognitive radio networks,” Computer Science Technical Report UTDCS-39-11, University of Texas at Dallas, Dallas, Tex, USA, 2011.
[6]
B. Dengiz, F. Altiparmak, and A. E. Smith, “Local search genetic algorithm for optimal design of reliable networks,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 3, pp. 179–188, 1997.
[7]
O. C. Martin and S. W. Otto, “Combining simulated annealing with local search heuristics,” Annals of Operations Research, vol. 63, pp. 57–75, 1996.
[8]
Y. Leung, G. Li, and Z. B. Xu, “A genetic algorithm for the multiple destination routing problems,” IEEE Transactions on Evolutionary Computation, vol. 2, no. 4, pp. 150–161, 1998.
[9]
M. Pioro and D. Medhi, Routing, Flow, and Capacity Design in Communication and Computer Networks, Morgan Kaufmann, San Fransisco, Calif, USA, 2004.
[10]
H. Lian and A. Faragó, “Optimizing Call Admission Control for Cognitive Radio Networks Using a New Heuristic Optimization Method,” Science Academy Transactions on Computer and Communication Networks (SATCCN), vol. 2, no. 1, pp. 2046–5157, 2012.
[11]
R. B. Cooper and S. Katz, “Analysis of alternate routing networks account taken of the nonrandomness of overflow traffic,” Tech. Rep., Bell Telephone Laboratories Memorandum, 1964.
[12]
A. A. Jagers and E. A. Van Doorn, “On the continued Erlang loss function,” Operations Research Letters, vol. 5, no. 1, pp. 43–46, 1986.
[13]
F. P. Kelly, “Loss networks,” Annals of Applied Probability, vol. 1, no. 3, pp. 319–378, 1991.
[14]
S. P. Chung and K. W. Ross, “Reduced load approximations for multirate loss networks,” IEEE Transactions on Communications, vol. 41, no. 8, pp. 1222–1231, 1993.
[15]
J. Arabas and S. Kozdrowski, “Applying an evolutionary algorithm to telecommunication network design,” IEEE Transactions on Evolutionary Computation, vol. 5, no. 4, pp. 309–322, 2001.
