Optimal resource allocation in Virtual Network Embedding

Abstract

Optimal resource allocation has become a focus in the technological environment due to the high costs associated with physical infrastructure and space. Furthermore, Network Operators (NO)s have to keep up with the rate of change in this digital age. This led to the creation of network virtualization. Virtualizing a network means that the functionality of the network becomes independent of the physical hardware that supports it. A significant advantage is that the same physical server can be used for several different purposes - depending on the software installed - to enable faster and more efficient communication. To prevent stagnation of internet infrastructure, Virtual Network Embedding (VNE) has emerged as a promising component of the future Internet. Virtual networks (VNs) still requires a substrate infrastructure and over-provisioning and non-optimal resource allocation are, therefore, still a critical consideration when implementing VNEs. Virtual network embedding refers to the instance where multiple virtual networks are hosted on the same substrate network (SN). VNE is thus the instance where various network nodes are installed on the same infrastructure; this enables shared capacity between them. When a change in demand is observed it is not necessary to purchase new network hardware, it is merely a matter of changing the software to balance the capacity between nodes dynamically. Internet Service Providers (ISPs) are currently viewed as two separate entities in order to provide dedicated networks and services separately. The Infrastructure Provider (InP)and the Service Provider (SP) are the central division in this new business model and rely on modern structures to provide services to clients. In this paper, a Mixed Integer Linear Program is proposed to model a VNE problem which includes off-line stochastic resource allocation (SRA). Two case studies are used in this dissertation. Case study A is used to verify the model and is a simple experiment with only ten nodes and three requests. Each of these requests comprises of two scenarios. The case study is completed for a worst-case version, as well as a stochastic version of the problem. This condensed version is used to ensure the calculations - to verify optimality - are possible by hand. Case study B is a more extensive case study with twenty nodes in the substrate infrastructure. There are fourteen requests with three scenarios each. This case study is used to validate the proposed model and is also performed in the worst case as well as the stochastic version. The reason a worst-case version is performed for each case study is to illustrate the improvement SRA can provide since the worst-case version of the case study is the manner in which many older works complete their VNE. Using the increase in model size the scalability is also tested to some extent, but cannot be proven with such little data. The results conclude that a Mixed Integer Linear Program can be successfully used to implement a stochastic embedding approach considering VNE. It is evident from the results of the study that this approach has the advantage of increased resource allocation which is found to be financially beneficial for a supplier of the service. This highlights the gains that a service provider can obtain, that is preferable in a financial sense, as well as a positive impact on the environment by using less physical resources.