Evaluating Algorithms for Composable Service Placement in Computer Networks

Novel network architectures with distributed service components on both routers and end-systems have been proposed to provide the necessary flexibility in the next-generation Internet. Such architectures allow services to be composed along the data path to satisfy different communication requirements. A major operational challenge in such systems is to determine where to perform the required services along the data path. This problem, which the authors call as the "Service placement problem" is proven to be NP-complete when considering resource (e.g., link and processing capacity) constraints. In this paper, they present an evaluation of several existing and newly developed heuristic algorithms for solving the problem.