  Distributed cloud networking builds on network functions virtualization (NFV)
and software defined networking (SDN) to enable the deployment of network
services in the form of elastic virtual network functions (VNFs) instantiated
over general purpose servers at distributed cloud locations. We address the
design of fast approximation algorithms for the NFV service distribution
problem (NSDP), whose goal is to determine the placement of VNFs, the routing
of service flows, and the associated allocation of cloud and network resources
that satisfy client demands with minimum cost. We show that in the case of
load-proportional costs, the resulting fractional NSDP can be formulated as a
multi-commodity-chain flow problem on a cloud augmented graph, and design a
queue-length based algorithm, named QNSD, that provides an O(\epsilon)
approximation in time O(1/\epsilon). We then address the case in which resource
costs are a function of the integer number of allocated resources and design a
variation of QNSD that effectively pushes for flow consolidation into a limited
number of active resources to minimize overall cloud network cost.
