Embedding parallelizable virtual networks

Network virtualization has been the focus of intense research interest for the last decade as it provides a promising approach to overcome the ossification of the Internet. An important problem in network virtualization is how to efficiently embed virtual networks with resource constraints into a substrate network (aka. virtual network embedding). Many research results have been reported regarding this problem. However, there has not been any focus on embedding parallelizable virtual networks, i.e., the substrate infrastructure supports parallel computation and allows a virtual node to be mapped into multiple substrate nodes. For example, a map task can be split into several smaller map tasks by simply splitting its input data. To the best of our knowledge, this paper is the first attempt at gaining a better understanding on how parallelization benefits virtual network embedding. We identify the problem of embedding parallelizable virtual networks and propose two algorithms that capitalize parallelism from two different perspectives: proactive and lazy. Several extensions are designed to complement the proposed algorithms. Extensive simulations are conducted to evaluate the proposed algorithms and several design considerations.