Network virtualization has become increasingly popular in recent years. It has the potential to allow timely handling of network infrastructure requests and, after instantiated, their lifecycle. In addition, it enables improved physical resource utilization. However, the use of network virtualization in large-scale, real environments depends on the ability to adequately map virtual routers and links to physical resources, as well as to protect virtual networks against security threats. With respect to security, confidentiality and privacy mechanisms have become essential in light of recent discoveries related to pervasive electronic surveillance. In this paper we propose a heuristic method for virtual network embedding with security support. The method features precise modeling of overhead costs of security mechanisms and handles incoming requests in an online manner. Additionally, we present a detailed performance comparison between the proposed heuristic and an optimization model based on the same problem. The obtained results demonstrate that the heuristic method is able to find feasible mappings in the order of seconds even when dealing with large network infrastructures, while the optimization model is limited to smaller networks. View full abstract