  As the virtualization of networks continues to attract attention from both
industry and academia, the Virtual Network Embedding (VNE) problem remains a
focus of researchers. This paper proposes a one-shot, unsplittable flow VNE
solution based on column generation. We start by formulating the problem as a
path-based mathematical program called the primal, for which we derive the
corresponding dual problem. We then propose an initial solution which is used,
first, by the dual problem and then by the primal problem to obtain a final
solution. Unlike most approaches, our focus is not only on embedding accuracy
but also on the scalability of the solution. In particular, the one-shot nature
of our formulation ensures embedding accuracy, while the use of column
generation is aimed at enhancing the computation time to make the approach more
scalable. In order to assess the performance of the proposed solution, we
compare it against four state of the art approaches as well as the optimal
link-based formulation of the one-shot embedding problem. Experiments on a
large mix of Virtual Network (VN) requests show that our solution is near
optimal (achieving about 95% of the acceptance ratio of the optimal solution),
with a clear improvement over existing approaches in terms of VN acceptance
ratio and average Substrate Network (SN) resource utilization, and a
considerable improvement (92% for a SN of 50 nodes) in time complexity compared
to the optimal solution.
