Algorithms for the virtual network embedding problem

Author(s)

Igor Rosberg de Medeiros Silva

• Document type: Master's Dissertation
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2014-02-27

Examining board members

Eduardo Candido Xavier; Daniel Macêdo Batista; Fábio Luiz Usberti

• Advisor: Eduardo Candido Xavier; Nelson Luis Saldanha da Fonseca

Abstract

In recent years, network virtualization has gained considerable attention from the scientific community, since it provides mechanisms to overcome the ossification problem of the current Internet architecture. Through separation of Internet Service Providers into Infrastructure Providers and Service Providers, network virtualization allows multiple heterogeneous virtual networks to share the same physical substrate. One of the main problems regarding network virtualization is the Network Embedding Problem, which is NP-Hard. Several algorithms and heuristics to find a set of good mappings that optimize the use of the bandwidth in substrate networks have been proposed. In this work, we present two new embedding heuristics based on the Tabu Search metaheuristic: the VNE-TS and VNE-TS-Clustering. We also propose a virtual network selection policy, the 2ks-VN-Selector, based on the Bidimensional Knapsack Problem, which aims to increase the profit of Infrastructure Providers. We compare the results obtained by using the VNE-TS and VNE-TS-Clustering heuristics, to those obtained by using the VNE-PSO, one of the best heuristics proposed in the literature for the Embedding Problem. We also compare the effects of the 2ks-VN-Selector with those obtained by using another well known selection policy: Most Prize First. Results show that both VNE-TS and VNE-TS-Clustering reject less virtual network requests than VNE-PSO and that the selection algorithm 2ks-VN-Selector is able to increase the profit of Infrastructure Providers when compared to the Most Prize First algorithm (AU)

• FAPESP's process: 12/14845-0 - Algorithms for embedded network problem
• Grantee: Igor Rosberg de Medeiros Silva
• Support Opportunities: Scholarships in Brazil - Master