An important evolution of the users’ needs is represented by the on-demand access to the network, storage, and compute resources in order to dynamically match the level of resource consumption with their service requirements. The response of the network providers is to transition to an architecture based on softwarization and cloudification of the network functions. This is the rationale for the deployment of network functions virtualization (NFV) where virtual network functions (VNFs) may be chained together to create network services. Efficient online routing of demand across nodes handling the functions involved in a given service chain is the novel problem that we address in this paper. We provide an original formulation of this problem that includes link and CPU capacity constraints and is based on the construction of an expanded network. We derive the exact mathematical formulation and propose several heuristic algorithms taking into account the main system’s parameters. We conclude by deriving some interesting insights both about the algorithms and the network performance by comparing the heuristics with the exact solutions.

Network service providers have to cope with the growing on-demand need from end-users as well as the diversity of usage. The softwerization and cloudification of the network components offer an interesting solution to achieve the agility necessary to dynamically match the requirement with the level of resource consumption. This materializes with the deployment of Network Functions Virtualization (NFV) where Virtual Network Functions (VNFs) may be chained together to create network services. This paper explores important design and architectural issues related to this approach. We study the resource allocation problem in an NFV system for minimizing its cost under constraints on interconnectivity among VNFs, system resources, and service requirements. We formalize the problem in a comprehensive manner taking into account a broad set of relevant parameters. The static (offline) and dynamic (online) cases are considered. We propose and analyze three heuristic algorithms: two for handling large dimensions of the offline problem and one designed to address the online scenario. The evaluation shows that our solutions outperform the state of the art [1] with respect to critical performance index. Finally, we focus on the online scenario, evaluate the impact of migrating a set of running demands, and propose a simple migration technique.