Efficient Allocation of Resources in NFV-Enabled Networks

Abstract

The network traffic and number of devices that are connected within a network are increasing, driven by the increase in network coverage as well as the types of network services provisioned. The provisioning of network services requires different network functions that are often chained in specific order. The traditional implementation of network functions is hardwarebased, in which each network function (NF) has its own specific proprietary hardware and software. Besides being costly, this approach has complicated the network management and slowed the pace in which new services are adapted to the market. To address these issues, the networking industry is pursuing Network Function Virtualization (NFV), which enables cost efficient, softwarized and flexible network service provisioning. One of the key challenges in NFV is resource allocation. This thesis work is purposed at addressing the problem of allocating resources efficiently in an NFV-enabled network by striking a balance across multiple objectives and satisfying the performance and availability requirements of service requests. The research contributions of the PhD work are classified into three parts. First, an efficient NFV resource allocation algorithm called ClusPR is proposed. ClusPR is developed based on observations made from the optimal solution obtained by solving an Integer Linear Programming (ILP) model. ClusPR strikes a balance between multiple objectives including minimizing the path stretch, maximizing the utilization of the network and balancing the load among NF instances. Compared to the state-of-the art approaches, ClusPR is able to satisfy the service performance (i.e., delay) requirement of more flows. In addition, an online algorithm called iClusPR that performs dynamic horizontal scaling by creating and/or removing NF instances depending on the traffic demand is proposed. The performance of iClusPR is close to its offline counterpart ClusPR. Second, a set of new network structural dependency measures are proposed to overcome a major shortcoming of the existing measures, which is that they do not take into account network fragmentation caused by failure of a node. The proposed measures referred to as dependency indexes assess the impact failure of a node has on the information communication between two nodes (path), between one node and the other network nodes (node), and between any one of the remaining network nodes (network) by explicitly considering possible fragmentation. The applicability of the network dependency index for correctly identifying the critical nodes of a network is also demonstrated. Third, for ensuring high availability of services redundant or backup service chains should be allocated. The NFV redundancy allocation problem is modeled by using two ILP models referred to as AllOne and AllAny. Although the models give the optimal result the execution time of the models increases exponentially with an increase in the size of the network as the problem is NP-hard. To address this problem, a scalable redundancy allocation scheme called CoShare is proposed. CoShare meticulously select backups to avoid the simultaneous unavailability of both the primary and backup chains due to network structural dependencies. In addition, CoShare uses resources efficiently by adopting an approach referred to as NF shared reservation, in which the reserved capacity at a backup NF instance is shared among service requests or flows that are not expected to fail simultaneously. The results show that by utilizing NF shared reservation, CoShare is able to reduce the resource overbuild, which is measured as the amount of extra capacity (i.e., number of backup NF instances) required as a percentage of the capacity needed without redundancy (i.e., number of primary NF instances). In summary, this thesis work provides algorithms that find efficient allocation of resources in an NFV-enabled network while ensuring the fulfillment of both the performance and availability requirements of service requests.