Abstract

Softwarization is the current trend of networking based on the success of technologies like Software Defined Networking (SDN) and Network Virtualization. Network as a Service (NaaS) is a new paradigm based on virtualization that enables customers to instantiate their virtual networks over a physical substrate network, mapping necessary resources by a Virtual Network Embedding (VNE) algorithm. Each VNE algorithm defines a resource allocation strategy of the NaaS provider, and determines its expenditures and revenues. Even though the problem of VNE has been widely investigated in recent years, virtualization in SDN introduces new challenges due to the new role of the controller and additional architectural constraints. In this paper, we investigate the VNE problem where both virtual and substrate networks are software defined. We propose a mathematical programming formulation that considers both the objectives of the NaaS provider (profit maximization) and the customers (switch-controller delay minimization). Proposing new design metrics (i.e., k-hop delay, correlation, and distance), we develop a heuristic algorithm, and prove its effectiveness through extensive simulations in the well-known VNE evaluation tool, ALEVIN, and comparisons with other algorithms and mathematical bounds. aaS).

INTRODUCTION

In recent years, two technologies had major impact on computer networks, namely Software Define Networking (SDN) [1] and Network Virtualization [2]. SDN has introduced a new networking paradigm where the control plane is fully programmable and located in a logically centralized entity called the controller, while switches are simple packet forwarding devices (the data plane) where forwarding rules are programmed via an open interface e.g., ForCES [3], SoftRouter [4], and OpenFlow [5] in their flow tables. In software-defined networks, the switch-controller delay is a new important issue due to its impact on the network performance [6]. Network Virtualization or “Network as a Service” (NaaS) allows to flexibly organize network functions and to deploy multiple virtual networks on a shared physical substrate network, where functions and resources are logically separated. Allocation of resources to virtual network (VN) requests, the key issue in NaaS, is commonly referred to as the Virtual Network Embedding (VNE) problem. In this problem, a set of VNs with given resource and topology requests should be mapped on a resource-limited substrate network optimizing specific efficiency objectives. A solution of the problem by a VNE algorithm is a resource allocation mechanism of the NaaS provider that directly impacts expenditures (since it determines substrate network resource consumption) and revenue (since it determines the VN requests that can be accommodated). Hence, from business point of view, efficient VNE algorithms are vital tools to manage the business of the NaaS providers. The VNE problem can be divided into two sub-problems namely the virtual nodes mapping (VNoM) and virtual links mapping (VLiM) problems. These sub-problems can be dealt with separately, in a coordinated way, or jointly. More coordination leads to higher efficiency, however at the cost of significant computational complexity. Embedding virtual networks with nodes and links constraints has been proven to be a NP-Hard problem [7]. This has motivated researchers to focus on the development of heuristic methods able to provide good quality solutions for large instances in a reasonable time. Isolating the virtual tenant networks is a major implementation issue in network virtualization.