  Network Function Virtualization (NFV) can cost-efficiently provide network
services by running different virtual network functions (VNFs) at different
virtual machines (VMs) in a correct order. This can result in strong couplings
between the decisions of the VMs on the placement and operations of VNFs. This
paper presents a new fully decentralized online approach for optimal placement
and operations of VNFs. Building on a new stochastic dual gradient method, our
approach decouples the real-time decisions of VMs, asymptotically minimizes the
time-average cost of NFV, and stabilizes the backlogs of network services with
a cost-backlog tradeoff of $[\epsilon,1/\epsilon]$, for any $\epsilon > 0$. Our
approach can be relaxed into multiple timescales to have VNFs (re)placed at a
larger timescale and hence alleviate service interruptions. While proved to
preserve the asymptotic optimality, the larger timescale can slow down the
optimal placement of VNFs. A learn-and-adapt strategy is further designed to
speed the placement up with an improved tradeoff
$[\epsilon,\log^2(\epsilon)/{\sqrt{\epsilon}}]$. Numerical results show that
the proposed method is able to reduce the time-average cost of NFV by 30\% and
reduce the queue length (or delay) by 83\%, as compared to existing benchmarks.
