  Virtual network services that span multiple data centers are important to
support emerging data-intensive applications in fields such as bioinformatics
and retail analytics. Successful virtual network service composition and
maintenance requires flexible and scalable 'constrained shortest path
management' both in the management plane for virtual network embedding (VNE) or
network function virtualization service chaining (NFV-SC), as well as in the
data plane for traffic engineering (TE). In this paper, we show analytically
and empirically that leveraging constrained shortest paths within recent VNE,
NFV-SC and TE algorithms can lead to network utilization gains (of up to 50%)
and higher energy efficiency. The management of complex VNE, NFV-SC and TE
algorithms can be, however, intractable for large scale substrate networks due
to the NP-hardness of the constrained shortest path problem. To address such
scalability challenges, we propose a novel, exact constrained shortest path
algorithm viz., 'Neighborhoods Method' (NM). Our NM uses novel search space
reduction techniques and has a theoretical quadratic speed-up making it
practically faster (by an order of magnitude) than recent branch-and-bound
exhaustive search solutions. Finally, we detail our NM-based SDN controller
implementation in a real-world testbed to further validate practical NM
benefits for virtual network services.
