Multiple-resource partial order scheduling policy

Abstract

The present invention provides a multi-resource partial order scheduling policy. A large number of tasks with a multi-resource demand and a complicated structure exist in NFV, and in actual task scheduling, task scheduling completion time affects user experience; traditional scheduling mostly focuses on stream scheduling study, and is incapable of considering a task structure, however, when a task has a partial order structure, the stream scheduling cannot ensure task scheduling time to be optimized; according to the multi-resource partial order scheduling policy provided by the present invention, in an NFV network architecture, a multi-resource task scheduling problem based on a partial order structure is formalized into a model of the multi-resource task scheduling problem based on the partial order structure; and a policy of simultaneously optimizing average and tail scheduling time is provided, and according to the policy, a task scheduling order is determined in a dominant resource priority (DRP) based mode, and resources are allocated with a maximum utilization allocation (MUA) method; and the DRP policy involved in the present invention has polynomial time complexity, a resource utilization rate close to 100%, and excellent fairness.

Description

technical field [0001] The invention relates to the technical field of the Internet, is particularly suitable for new architecture environments such as NFV (including SDN), and relates to a multi-resource partial order scheduling strategy. Background technique [0002] Whether it is NFV, SDN, cloud computing, or data center, tasks play a very important role. The so-called task refers to the smallest application unit from the user sending a request to the final response, which is equivalent to an application instance response. For example, in an NFV network, the NFV infrastructure (referred to as NFVI) abstracts hardware into a series of virtual resources, and the virtual network function (referred to as VNF) forms a service chain according to different task requirements. As an NFV orchestrator with a global perspective, it will manage these services in a unified manner, and optimize each task that needs to be scheduled by making full use of these virtual resources as much a...

AI Technical Summary

Problems solved by technology

The limitation of multiple resources will lead to the failure of traditional solution methods, such as the critical path method (CPM for short), which increases the difficulty of scheduling algorithms. Theory proves that this problem is an NP-hard problem and cannot be completed in polynomial time.

Images