2023/11/09 by Sergey Pankratov, Vitaly Aksenov, Pankratov, Sergey +3
Computer Science · Engineering · #Advanced Optical Network Technologies #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Interconnection Networks and Systems #Networking and Internet Architecture (cs.NI) #Software-Defined Networks and 5G
paper · pdf · doi:10.48550/arxiv.2311.05474
openalex publication_date 2023/11/09 · openalex created_date 2023/11/11 · openalex updated_date 2026/07/28
Virtual networks are an innovative abstraction that extends cloud computing concepts to the network: by supporting bandwidth reservations between compute nodes (e.g., virtual machines), virtual networks can provide a predictable performance to distributed and communication-intensive cloud applications. However, in order to make the most efficient use of the shared resources, the Virtual Network Embedding (VNE) problem has to be solved: a virtual network should be mapped onto the given physical network so that resource reservations are minimized. The problem has been studied intensively already and is known to be NP-hard in general. In this paper, we revisit this problem and consider it on specific topologies, as they often arise in practice. To be more precise, we study the weighted version of the VNE problem: we consider a virtual weighted network of a specific topology which we want to embed onto a weighted network with capacities and specific topology. As for topologies, we consider most fundamental and commonly used ones: line, star, 2-tiered star, oversubscribed 2-tiered star, and tree, in addition to also considering arbitrary topologies. We show that typically the VNE problem is NP-hard even in more specialized cases, however, sometimes there exists a polynomial algorithm: for example, an embedding of the oversubscribed 2-tiered star onto the tree is polynomial while an embedding of an arbitrary 2-tiered star is not.