Maximizing the number of satisfied subscribers in pub/sub systems under capacity constraints

Vinay Setty, Gunnar Kreitz, Guido Urdaneta, Roman Vitenberg, Maarten van Steen

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

8 Citations (Scopus)

Abstract

Publish/subscribe (pub/sub) is a popular communication paradigm in the design of large-scale distributed systems. A provider of a pub/sub service (whether centralized, peer-assisted, or based on a federated organization of cooperatively managed servers) commonly faces a fundamental challenge: given limited resources, how to maximize the satisfaction of subscribers? We provide, to the best of our knowledge, the first formal treatment of this problem by introducing two metrics that capture subscriber satisfaction in the presence of limited resources. This allows us to formulate matters as two new flavors of maximum coverage optimization problems. Unfortunately, both variants of the problem prove to be NP-hard. By subsequently providing formal approximation bounds and heuristics, we show, however, that efficient approximations can be attained. We validate our approach using real-world traces from Spotify and show that our solutions can be executed periodically in real-time in order to adapt to workload variations.

Original languageEnglish
Title of host publicationIEEE INFOCOM 2014 - IEEE Conference on Computer Communications
Place of PublicationPiscataway, NJ
PublisherIEEE
Pages2580-2588
Number of pages9
ISBN (Print)9781479933600
DOIs
Publication statusPublished - 1 Jan 2014
Externally publishedYes
Event33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014 - Toronto, Canada
Duration: 27 Apr 20142 May 2014
Conference number: 33
http://infocom2014.ieee-infocom.org/

Conference

Conference33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014
Abbreviated titleIEEE INFOCOM 2014
CountryCanada
CityToronto
Period27/04/142/05/14
Internet address

Fingerprint Dive into the research topics of 'Maximizing the number of satisfied subscribers in pub/sub systems under capacity constraints'. Together they form a unique fingerprint.

Cite this