  Network Function Virtualization (NFV) is an emerging paradigm that turns
hardware-dependent implementation of network functions (i.e., middleboxes) into
software modules running on virtualized platforms, for significant cost
reduction and ease of management. Such virtual network functions (VNFs)
commonly constitute service chains, to provide network services that traffic
flows need to go through. Efficient deployment of VNFs for network service
provisioning is key to realize the NFV goals. Existing efforts on VNF placement
mostly deal with offline or one-time placement, ignoring the fundamental,
dynamic deployment and scaling need of VNFs to handle practical time-varying
traffic volumes. This work investigates dynamic placement of VNF service chains
across geo-distributed datacenters to serve flows between dispersed source and
destination pairs, for operational cost minimization of the service chain
provider over the entire system span. An efficient online algorithm is
proposed, which consists of two main components: (1) A regularization-based
approach from online learning literature to convert the offline optimal
deployment problem into a sequence of one-shot regularized problems, each to be
efficiently solved in one time slot; (2) An online dependent rounding scheme to
derive feasible integer solutions from the optimal fractional solutions of the
one-shot problems, and to guarantee a good competitive ratio of the online
algorithm over the entire time span. We verify our online algorithm with solid
theoretical analysis and trace-driven simulations under realistic settings.
