Approximation Algorithms for the Optimal Distribution of Real-Time Stream-Processing Services
Michael M, Llorca J, Tulino A (2019)
Publication Type: Conference contribution
Publication year: 2019
Journal
Publisher: Institute of Electrical and Electronics Engineers Inc.
Book Volume: 2019-May
Conference Proceedings Title: IEEE International Conference on Communications
Event location: Shanghai
ISBN: 9781538680889
Abstract
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.
Authors with CRIS profile
Marcelo Michael
Lehrstuhl für Informationstechnik mit dem Schwerpunkt Kommunikationselektronik (Stiftungslehrstuhl)
Involved external institutions
United States (USA) (US)How to cite
APA:
Michael, M., Llorca, J., & Tulino, A. (2019). Approximation Algorithms for the Optimal Distribution of Real-Time Stream-Processing Services. In IEEE International Conference on Communications. Shanghai, CN: Institute of Electrical and Electronics Engineers Inc..
MLA:
Michael, Marcelo, Jaime Llorca, and Antonia Tulino. "Approximation Algorithms for the Optimal Distribution of Real-Time Stream-Processing Services." Proceedings of the 2019 IEEE International Conference on Communications, ICC 2019, Shanghai Institute of Electrical and Electronics Engineers Inc., 2019.
BibTeX: Download