Optimization of Network Service Scheduling with Resource Sharing and Preemption

This paper proposes an optimization model to schedule network services (NSes) in virtual networks with resource sharing and preemption. Inefficient NS scheduling can severely degrade the acceptance ratio of arriving NSes of the network. Conventional NS scheduling models do not consider sharing computational resources of a node among different virtual network function (VNF) instances deployed on this node. In the proposed model, NSes mapped to the same VNF instance on the same node share computational resources of the VNF instance, and VNF instances deployed on the same node share computational resources of the node. The proposed model allows preemption, which means that rescheduling the process order of NSes in runtime is possible and the process duration of each function of an NS is allowed to be discrete. We formulate the proposed model as an integer linear programming problem to maximize the number of admissible NSes. The numerical results show that the proposed model outperforms conventional models in terms of the acceptance ratio of arriving NSes.