Article

Resource allocation in a middleware for streaming data

Authors:

Gagan AgrawalAuthors Info & Claims

MGC '04: Proceedings of the 2nd workshop on Middleware for grid computing

Pages 5 - 10

https://doi.org/10.1145/1028493.1028494

Published: 18 October 2004 Publication History

Abstract

Increasingly, a number of applications rely on, or can potentially benefit from, analysis and monitoring of <i>data streams.</i> To support processing of streaming data in a grid environment, we have been developing a middleware system called GATES (Grid-based AdapTive Execution on Streams). Our target applications are those involving high volume data streams and requiring distributed processing of data arising from a distributed set of sources.

This paper addresses the problem of resource allocation in the GATES system. Though resource discovery and resource allocation have been active topics in grid community, the pipelined processing and real-time constraint required by distributed streaming applications pose new challenges. We present a resource allocation algorithm that is based on minimal spanning trees. We evaluate the algorithm experimentally and demonstrate that it results in configurations that are very close to optimal, and significantly better than most other possible configurations.

References

[1]

A. Arasu, S. Babu, and J. Widom. An abstract semantics and concrete language for continuous queries over streams and relations. In Proc. of the 9th International Conference on Data Base Programming Languages (DBPL '03), Sep 2003.

[2]

J. Bunn and H. Newman. Data-Intensive Grids for High-Energy Physics. In F. Berman, G. Fox, and T. Hey, editors, Grid Computing: Making the Global Infrastructure a Reality. John Wiley and Sons, 2003.

[3]

D. Carney, U. Etintemel, M. Cherniak, C. Corvey, S. Lee, G. Seidman, M. Stonebraker, N. Tatbul, and S. Zodnik. Monitoring Streams - A New Class of Data Management Applications. In Proceedings of Conference on Very Large DataBases (VLDB), pages 215--226, 2002.

Digital Library

[4]

S. Chandrasekaran, O. Cooper, A. Deshpande, M. J. Franklin, J. M. Hellerstein, W. Hong, S. Krishnamurthy, S. R. Madden, V. Raman, F. Reiss, and Mehul A. Shah. Telegraphcq: Continuous dataflow processing for an uncertain world. In CIDR, pages 269--280, 2003.

[5]

Steve Chapin, Dimitrios Katramatos, John Karpovish, and Andrew Grimshaw. Resource management in Legion. Future Generation Computer System, 15(5-6):583--594, 1999.

Digital Library

[6]

Liang Chen, Kolagatla Reddy, and Gagan Agrawal. GATES: A Grid-Based Middleware for Distributed Processing of Data Streams. In Proceedings of IEEE Conference on High Performance Distributed Computing (HPDC). IEEE Computer Society Press, 2004.

Digital Library

[7]

M. Cherniack, H. Balakrishnan, M. Balazinska, D. Carney, U. Cetintemel, Y. Zing, and S. Zdonik. Scalable Distributed Stream Processing. In Proceedings of the Conference on Innovative Data Systems Research (CIDR), January 2003.

[8]

Byung Kyu Choi, Sangig Rho, and Riccardo Bettati. Dynamic resource discovery for applications survivability in distributed real-time systems. In IPDPS, page 122, 2003.

[9]

K. Czajkowski, S. Fitzgerald, I. Foster, and C. Kesselman. Grid information services for distributed resource sharing. In Proceedings of the Tenth IEEE International Symposium on High-Performance Distributed Computing (HPDC-10), August 2001.

Digital Library

[10]

I. Foster, C. Kesselman, and S. Tuecke. The anatomy of the grid: Enabling scalable virtual organizations. International Journal of Supercomputer Applications, 15(3), 2001.

Digital Library

[11]

Ian Foster, Carl Kesselman, J. Nick, and Steven Tuecke. Grid Services for Distributed Systems Integration. IEEE Computer, 2002.

Digital Library

[12]

Ian Foster, Carl Kesselman, Jeffrey M. Nick, and Steven Tuecke. The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration. In Open Grid Service Infrastructure Working Group, Global Grid Forum, June 2002.

[13]

Phillip B. Gibbons and Yossi Matias. New Sampling-Based Summary Statistics for Improving Approximate Query Answers. In Proc. of the 1998 ACM SIGMOD, pages 331--342. ACM Press, June 1998.

Digital Library

[14]

L. Golab and M. Ozsu. Issues in data stream management. In SIGMOD Record, Vol. 32, No. 2, pages 5--14, June 2003.

Digital Library

[15]

A. Iamnitchi, I. Foster, and D. Nurmi. A peer-to-peer approach to resource discovery in grid environments. In High Performance Distributed Computing, Edinbourgh, UK, July 2002. IEEE.

Digital Library

[16]

K. Jun, L. Boloni, K. Palacz, and D. C. Marinescu. Agent-based resource discovery. In 9th Heterogeneous Computing Workshop, pages 43--52, May 2000.

Digital Library

[17]

L. Moreau. Agents for the grid: A comparison for web services (part 1: the transport layer). In Proceedings of Second IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGRID 2002), pages 220--228, Berlin, Germany, 2002.

Digital Library

[18]

Beth Plale. Leveraging Runtime Knowledge about Event Rates to Improve Memory Utilization in Wide Area Data Stream Filtering. In IEEE High Performance Distributed Computing (HPDC), August 2002.

Digital Library

[19]

Beth Plale and Karsten Schwan. Dynamic Querying of Streaming Data with the dQUOB System. IEEE Transactions on Parallel and Distributed Systems, 14(3), April 2003.

Digital Library

[20]

Rajesh Raman, Miron Livny, and Marvin Solomon. Matchmaking: Distributed resource management for high throughput computing. In Proceedings of the Seventh IEEE International Symposium on High Performance Distributed Computing, Chicago, IL, July 1998.

Digital Library

[21]

O. F. Rana, D. Bunford-Jones, D. W. Walker, M. Addis, M. Surridge, and K. Hawick. Resource discovery for dynamic clusters in computational grid. In Proceedings of 10th IEEE Heterogeneous Computing Workshop, San Francisco, CA, USA, 2001.

Digital Library

[22]

Douglas Thain, Todd Tannenbaum, and Miron Livny. Distributed computing in practice: The condor experience. Concurrency and Computation: Practice and Experience, 2004.

Digital Library

[23]

S. Viglas and J. Naughton. Rate-based query optimization for streaming information sources. In Proc. of the 2002 ACM SIGMOD Intl. Conf. on Management of Data, June 2002.

Digital Library

[24]

D. Xu, K. Nahrstedt, and D. Wichadakul. Qos-aware discovery of wide-area distributed services. In Proceedings of 1st IEEE/ACM International Symposium on Cluster Computing and the Grid, pages 92--99, May 2001.

Digital Library

[25]

L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala. Rsvp: a new resource reservation protocol. IEEE Networks Magazine, 31(9):8--18, September 1993.

Digital Library

Cited By

Nguyen NKhan MAlbayram YWang KGokhale S(2017)Arion: A Model-Driven Middleware for Minimizing Data Loss in Stream Data Storage2017 IEEE 10th International Conference on Cloud Computing (CLOUD)10.1109/CLOUD.2017.14(34-41)Online publication date: Jun-2017
https://doi.org/10.1109/CLOUD.2017.14
Gu YWu C(2016)Performance Analysis and Optimization of Distributed Workflows in Heterogeneous Network EnvironmentsIEEE Transactions on Computers10.1109/TC.2013.6265:4(1266-1282)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1109/TC.2013.62
Yun DWu CGu Y(2015)An integrated approach to workflow mapping and task scheduling for delay minimization in distributed environmentsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2015.07.00484:C(51-64)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1016/j.jpdc.2015.07.004
Show More Cited By

Recommendations

Measurement and resource allocation problems in data streaming systems
A static resource allocation framework for Grid-based streaming applications: Research Articles
Middleware for Grid Computing

A number of applications increasingly rely on, or can potentially benefit from, analysis and monitoring of data streams. To support the processing of streaming data in a Grid environment, we have been developing a middleware system called GATES (Grid-...
Distributed resource allocation for stream data processing
HPCC'06: Proceedings of the Second international conference on High Performance Computing and Communications

Data streaming applications are becoming more and more common due to the rapid development in the areas such as sensor networks, multimedia streaming, and on-line data mining, etc. These applications are often running in a decentralized, distributed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

MGC '04: Proceedings of the 2nd workshop on Middleware for grid computing

October 2004

92 pages

ISBN:1581139500

DOI:10.1145/1028493

Conference Chairs:
Bruno Schulze,
Radha Nandkumar,
General Chair:
Fabio Kon
Sao Paulo

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 October 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 14 of 36 submissions, 39%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
782
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nguyen NKhan MAlbayram YWang KGokhale S(2017)Arion: A Model-Driven Middleware for Minimizing Data Loss in Stream Data Storage2017 IEEE 10th International Conference on Cloud Computing (CLOUD)10.1109/CLOUD.2017.14(34-41)Online publication date: Jun-2017
https://doi.org/10.1109/CLOUD.2017.14
Gu YWu C(2016)Performance Analysis and Optimization of Distributed Workflows in Heterogeneous Network EnvironmentsIEEE Transactions on Computers10.1109/TC.2013.6265:4(1266-1282)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1109/TC.2013.62
Yun DWu CGu Y(2015)An integrated approach to workflow mapping and task scheduling for delay minimization in distributed environmentsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2015.07.00484:C(51-64)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1016/j.jpdc.2015.07.004
Mo H(2014)The Application Study on Choosing Course System Based on JBoss Cache of Distributed Cache TechnologyApplied Mechanics and Materials10.4028/www.scientific.net/AMM.496-500.2121496-500(2121-2126)Online publication date: Jan-2014
https://doi.org/10.4028/www.scientific.net/AMM.496-500.2121
Wu QGu YLiao YLu XLin YRao NBiaz SWu S(2011)Latency modeling and minimization for large-scale scientific workflows in distributed network environmentsProceedings of the 44th Annual Simulation Symposium10.5555/2048370.2048398(205-212)Online publication date: 3-Apr-2011
https://dl.acm.org/doi/10.5555/2048370.2048398
Wu QGu Y(2011)Optimizing end-to-end performance of data-intensive computing pipelines in heterogeneous network environmentsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2010.08.00371:2(254-265)Online publication date: 1-Feb-2011
https://dl.acm.org/doi/10.1016/j.jpdc.2010.08.003
Wu QGu Y(2011)Performance Analysis and Optimization of Linear Workflows in Heterogeneous Network EnvironmentsGrid Computing10.1007/978-0-85729-676-4_4(89-120)Online publication date: 30-May-2011
https://doi.org/10.1007/978-0-85729-676-4_4
Meng MBrooks RWu QRao NSitharama Iyengar SZhu M(2009)An integrated intelligent decision support system based on sensor and computer networksSystems of Systems Engineering10.1201/9781420065893.ch11Online publication date: 30-Dec-2009
https://doi.org/10.1201/9781420065893.ch11
Wu QZhu MRao N(2009)Integration of sensing and computing in an intelligent decision support system for homeland security defensePervasive and Mobile Computing10.1016/j.pmcj.2008.04.0105:2(182-200)Online publication date: 1-Apr-2009
https://dl.acm.org/doi/10.1016/j.pmcj.2008.04.010
Wu QGu YBao LJia WDai HChen P(2009)Optimizing Distributed Execution of WS-BPEL Processes in Heterogeneous Computing EnvironmentsQuality of Service in Heterogeneous Networks10.1007/978-3-642-10625-5_49(770-784)Online publication date: 2009
https://doi.org/10.1007/978-3-642-10625-5_49
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents