In resource-constrained network function virtualization (NFV) environments, it is expected that data throughput for service chains is maintained by using virtual network functions (VNFs) effectively. In this paper, we formulate an optimization problem for maximizing the total data throughput in resource-constrained NFV environments. Moreover, based on our formulated optimization problem, we propose a heuristic service chain construction algorithm for maximizing the total data throughput. This algorithm also determines the placement of VNFs, the amount of resources for each VNF, and the transmission route for each service chain. It is expected that the heuristic algorithm can construct service chains more quickly than the meta-heuristic algorithm. We evaluate the performance of the proposed methods with simulations, and we investigate the effectiveness of our proposed heuristic algorithm through a performance comparison. Numerical examples show that our proposed methods can construct service chains so as to maximize the total data throughput regardless of the number of service chains, the amount of traffic, and network topologies.

Service chaining (SC) is a method for realizing a service by transferring flows among several service functions (SFs) that process packets. A route among SFs is called a service path (SP). Service chaining is being developed to reduce costs, increase flexibility, and shorten time-to-market. SC technologies are expected to be applied to carrier networks so that large communication carriers benefit from them. We assume that SPs process the traffic of services that treat all users in the same way such as an Internet access service for home users. An SP processes flows from several users. We do not assume that each SP is assigned to a user. Because a carrier network accommodates many users, each service will be heavily utilized. Therefore, it is assumed that the amount of traffic of a service is larger than the resource of an SF apparatus. Several SPs are required to process the traffic. SPs are supposed to meet two requirements. One is guaranteeing minimum bandwidth. The other is reducing the number of SF apparatuses, i.e., high resource utilization. Resource utilization depends on the combination of the resource quantities of SF apparatuses. Network operators have to determine the bandwidth of each SP within the range from the minimum bandwidth to the resource quantities of SF apparatuses to maximize resource utilization. Methods for determining the bandwidth of each SP have not been proposed for meeting the two requirements. Therefore, we propose a resource allocation method for this purpose. The proposed method determines the bandwidth of each SP on the basis of the combination of the resource quantities of SF apparatuses for guaranteeing the minimum bandwidth and maximizing resource utilization and allocates necessary resources to each SP. We also evaluate the proposed method and confirm that it can guarantee the minimum bandwidth of SPs and achieve high resource utilization regardless of the combination of the resource quantities of SF apparatuses. Although SF apparatuses are generally produced without considering the combinations of resource quantities of SF apparatuses in SPs, the proposed method can provide more options for selecting SF apparatuses.