How physical network topologies affect virtual network embedding quality: A characterization study based on ISP and datacenter networks


Network virtualization is a mechanism that allows the coexistence of multiple virtual networks on top of a single physical substrate. Due to its well-known potential benefits (e.g., lower CAPEX/OPEX expenditures), it has been embraced by the IT sector, specially by Internet Service Providers (ISPs) and cloud computing/datacenter companies. One of the research challenges addressed recently in the literature is the efficient mapping of virtual resources on physical infrastructures. Although this challenge has received considerable attention, state-of-the-art approaches present, in general, a high rejection rate, i.e., the ratio between the number of denied virtual network requests and the total amount of requests is considerably high. In this work, we investigate the relationship between the quality of virtual network mappings and the topological structures of the underlying substrates. Exact solutions of an online embedding model are evaluated under different classes of ISP and datacenter network topologies. The obtained results demonstrate that the employment of physical topologies that contain regions with high connectivity significantly contributes to the reduction of rejection rates and, therefore, to improved resource usage. Additionally, through an extensive analysis of denied requests, we assess the main rejection causes related to both ISP and datacenter networks and provide strong evidence of each one. In summary, through the embedding of virtual requests, available resources in ISP networks tend to be more partitioned in comparison to datacenter networks. Such differences on partitioning levels lead to a different percentage of rejection causes in each topology class.