Special Issue – Advances in Parallel and Distributed Computational Models (APDCM 2009)No Access

RESOURCE ALLOCATION STRATEGIES FOR CONSTRUCTIVE IN-NETWORK STREAM PROCESSING

ANNE BENOIT

École Normale Supérieure de Lyon, 46 allée d'Italie, 69364 Lyon Cedex 07, France

Search for more papers by this author

VERONIKA REHN-SONIGO

École Normale Supérieure de Lyon, 46 allée d'Italie, 69364 Lyon Cedex 07, France

Search for more papers by this author

YVES ROBERT

École Normale Supérieure de Lyon, 46 allée d'Italie, 69364 Lyon Cedex 07, France

Search for more papers by this author

, and

HENRI CASANOVA

University of Hawai'i at Manoa, 1680 East-West Road, Honolulu, HI 96822, USA

Search for more papers by this author

https://doi.org/10.1142/S012905411100826XCited by:1 (Source: Crossref)

Abstract

In this paper we consider the operator mapping problem for in-network stream processing applications. In-network stream processing consists in applying a tree of operators in steady-state to multiple data objects that are continually updated at various locations on a network. Examples of in-network stream processing include the processing of data in a sensor network, or of continuous queries on distributed relational databases. We study the operator mapping problem in a "constructive" scenario, i.e., a scenario in which one builds a platform dedicated to the application by purchasing processing servers with various costs and capabilities. The objective is to minimize the cost of the platform while ensuring that the application achieves a minimum steady-state throughput. The first contribution of this paper is the formalization of a set of relevant operator-placement problems, and a proof that even simple versions of the problem are NP-complete. Our second contribution is the design of several polynomial time heuristics, which are evaluated via extensive simulations and compared to theoretical bounds for optimal solutions.

Note that a short version of this paper appeared in the proceedings of APDCM'09, the 11th Workshop on Advances in Parallel and Distributed Computational Models, in conjunction with IPDPS 2009, Rome, Italy, May 2009. IEEE Computer Society Press.

Keywords:

References

B. Badcocket al., Models and issues in data stream systems, Proceedings of the Intl. Conf. on Very Large Data Bases pp. 456–467. Google Scholar
U. Srivastava , K. Munagala and J. Widom , Operator Placement for In-Network Stream Query Processing , Proceedings of the 24th Intl. Conf. on Principles of Database Systems . Google Scholar
C. Cranoret al., Gigascope: high-performance network monitoring with an SQL interface, Proceedings of the ACM SIGMOD International Conference on Management of Data pp. 623–633. Google Scholar
R. van Rennesse et al. , Scalable Management and Data Mining Using Astrolabe , Proceedings from the First Intl. Workshop on Peer-to-Peer Systems . Google Scholar
E. Cooke et al. , Reclaiming Network-wide Visibility Using Ubiquitous End System Monitors , Proceedings of the USENIX Annual Technical Conf. . Google Scholar
J. Chen , D. J. DeWitt and J. F. Naughton , Design and Evaluation of Alternative Selection Placement Strategies in Optimizing Continuous Queries , Proceedings of ICDE . Google Scholar
B. Plale and K. Schwan, IEEE Transactions on Parallel and Distributed Systems 14(4), 422 (2003), DOI: 10.1109/TPDS.2003.1195413. Crossref, Web of Science, Google Scholar
J. Kräme and B. Seeger, A Temporal Foundation for Continuous Queries over Data streams, Proceedings of the Intl. Conf. on Management of Data pp. 70–82. Google Scholar
M. Cherniack et al. , Scalable distributed stream processing , Proc. of the CIDR Conf. . Google Scholar
L. Chen, K. Reddy and G. Agrawal, GATES: a grid-based middleware for processing distributed data streams, High performance Distributed Computing, 2004. Proceedings. 13th IEEE International Symposium on (2004) pp. 192–201. Google Scholar
D. Logothetis and K. Yocum , Wide-Scale Data Stream Management , Proceedings of the USENIX Annual Technical Conference . Google Scholar
Y. Ahmad and U. Cetintemel, Network aware query processing for stream-based applications, Proceedings of the International Conference on Very Large Data Bases pp. 456–467. Google Scholar
P. Pietzuch et al. , Network-Aware Operator Placement for Stream-Processing Systems , Proceedings of the 22nd International Conference on Data Engineering (ICDE'06) . Google Scholar
"Amazon Elastic Compute Cloud (Amazon EC2)," , http://aws.amazon.com/ec2/ . Google Scholar
A. Benoit et al. , Resource Allocation for Concurrent In-Network Stream-Processing Applications , Algorithms, Models and Tools for Parallel Computing on Heterogeneous Platforms, HeteroPar'09 . Google Scholar
Y. E. Ioannidis, ACM Computing Surveys 28(1), 121 (1996), DOI: 10.1145/234313.234367. Crossref, Web of Science, Google Scholar
B. Hong and V. K. Prasanna, IEEE Trans. Parallel Distributed Systems 18(10), 1420 (2007), DOI: 10.1109/TPDS.2007.1042. Crossref, Web of Science, Google Scholar
O. Beaumontet al., Int. J. of Foundations of Computer Science 16(2), 163 (2005). Link, Web of Science, Google Scholar
A. Benoit, H. Casanova, V. Rehn-Sonigo, and Y. Robert, "Resource Allocation Strategies for In-Network Stream Processing," LIP, ENS Lyon, France, Research Report 2008-20, June 2008. Available at , http://graal.ens-lyon.fr/$\sim$abenoit/ . Google Scholar
M. R. Garey and D. S. Johnson , Computers and Intractability, a Guide to the Theory of NP-Completeness ( W. H. Freeman and Company , 1979 ) . Google Scholar
"Source Code for the Heuristics," , http://graal.ens-lyon.fr/$\sim$vsonigo/code/query-streaming/ . Google Scholar
V. Pandit and H. Ji , Efficient in-network evaluation of multiple queries , HiPC . Google Scholar
K. Munagala , U. Srivastava and J. Widom , Optimization of continuous queries with shared expensive filters , PODS '07: Proc. of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems ( ACM , 2007 ) . Google Scholar