Approximation Algorithms for the Optimal Distribution of Real-Time Stream-Processing Services
Michael Marcelo, Jaime Llorca, Antonia Maria Tulino · 2019
Real-time stream-processing (RTSP) services, such as telepresence, augmented reality, and real-time computer vision, allow end users to consume personalized media streams that result from the real-time processing of live sources via possibly multiple service functions (or stream processing operators) distributed throughout a cloud network. We consider the problem of optimizing the distribution of RTSP services over a cloud network, which requires the placement of stream processing operators, the routing of streams through the appropriate sequence of operators and the associated allocation of cloud and network resources. We show that existing formulations based on virtual network embedding cannot capture key features of RTSP services such as flow/function replication, and provide a new cloud network flow based formulation that captures arbitrary function and flow chaining, scaling, and replication. We then design two polynomial-time algorithms with bi-criteria approximation guarantees. To the best of our knowledge, these are the first approximation algorithms for the optimization of distributed computing services with arbitrary function/flow chaining, scaling, and replication. We finally illustrate the performance of our algorithms via simulations in practical cloud network settings.