Evaluating Algorithms for Composable Service Placement in Computer Networks

Abstract—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 we 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, we present an evaluation of several existing and newly developed heuristic algorithms for solving the problem. We explore the quality of the achieved placement in terms of effective use of system resources, end-to-end delay, connection drop rate, and load balancing. Our results show the design trade-offs of these different algorithms. I