  For NFV systems, the key design space includes the function chaining for
network requests and resource scheduling for servers. The problem is
challenging since NFV systems usually require multiple (often conflicting)
design objectives and the computational efficiency of real-time decision making
with limited information. Furthermore, the benefits of predictive scheduling to
NFV systems still remain unexplored. In this paper, we propose POSCARS, an
efficient predictive and online service chaining and resource scheduling scheme
that achieves tunable trade-offs among various system metrics with queue
stability guarantee. Through a careful choice of granularity in system
modeling, we acquire a better understanding of the trade-offs in our design
space. By a non-trivial transformation, we decouple the complex optimization
problem into a series of online sub-problems to achieve the optimality with
only limited information. By employing randomized load balancing techniques, we
propose three variants of POSCARS to reduce the overheads of decision making.
Theoretical analysis and simulations show that POSCARS and its variants require
only mild-value of future information to achieve near-optimal system cost with
an ultra-low request response time.
