Network Virtualization (NV), considered as a key enabler for overcoming the ossification of the Internet allows multiple heterogeneous virtual networks to co-exist over the same substrate network. Resource allocation problems in NV have been extensively studied for single layer substrates such as IP or Optical networks. However, little effort has been put to address the same problem for multi-layer IP-over-Optical networks. The increasing popularity of multi-layer networks for deploying backbones combined with their unique characteristics (e.g., topological flexibility of the IP layer) calls for the need to carefully investigate the resource provisioning problems arising from their virtualization. In this paper, we address the problem of MUlti-Layer virtual network Embedding (MULE) on IP-overOptical networks. We propose two solutions to MULE: an Integer Linear Program (ILP) formulation for the optimal solution and a heuristic to address the computational complexity of the optimal solution. We demonstrate through extensive simulations that on average our heuristic performs within ≈1.47× of optimal solution and incurs ≈66% less cost than the state-of-the-art heuristic.