Virtual Network Functions Scheduling under Delay-Weighted Pricing

• We consider a cost minimization problem for High Volume Servers (HVS) equipped with Virtual Machines (VMs) to serve Virtual Network Functions (VNF) demands for resources. Given a scheduling period, a central scheduler decides which VM to use for each VNF demand. Each VM can be activated or disabled with different costs. Each VNF has a delay-weighted pricing function to indicate its completion time tolerance. We prove the NP-completeness of the problem and develop an algorithm based on Lagrangian relaxation and subgradient optimization to deal with this computational complexity. Finally, our numerical results demonstrate our algorithm’s effectiveness compared to two benchmarks.

Subject headings

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datorteknik (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Engineering (hsv//eng)

Keyword

Optimization

Linear programming

Resource management

Pricing

Network function virtualization

Complexity theory

Servers

Publication and Content Type

ref (subject category)

art (subject category)