Network virtualization enables the co-existence of multiple virtual networks (VNs) on the same substrate network by sharing the available resources. One of the major challenges in network virtualization is the efficient allocation of substrate resources to the VNs - a problem known as Virtual Network Embedding(VNE). In this paper, we propose VNA, an algorithm for VNE that achieves high VN request acceptance ratio while balancing the load across the network. VNA, takes into account the residual capacity of links in the substrate network during node mapping, thereby reducing the possibility of failure during the link mapping phase. For mapping the virtual links, VNA identifies a set of low utilization paths along which resources have to be reserved for the virtual links. Simulation results show that VNA achieves high request acceptance ratio, outperforming many of the existing algorithms for VNE. © 2012 IEEE.