Performance of resource management algorithms for "Processable Bulk Data Transfer" Tasks in Grid Environments
Pages 177 - 188
Abstract
Processable Bulk Data Transfer (PBDT) tasks are resource intensive concurrent tasks which involve transfer of a very large amount of data that has to be processed in some way before it can be used at a remote set of destination nodes called the sink nodes. A distributed computing environment, such as the Grid is a popular way to perform these tasks. Focusing on the execution of PBDT tasks in a Grid computing environment, this paper presents an efficient resource allocation mechanism. Due to the resource thirsty nature of these tasks, an efficient resource allocation is essential to perform these tasks while achieving satisfactory performance. The time-complexity of the resource allocation algorithm rises sharply as the available number of resources in the given Grid computing environment is increased making efficient resource allocation a challenge. To meet this challenge, this paper investigates the use of approximate algorithms for the resource allocation. The benefits obtained by using the reduced complexity of the algorithm are weighed against the increased costs incurred during the task execution (due to the inaccuracies in resource allocation introduced by the approximations). This paper describes a number of approximations and discusses under which circumstances such approximations are to be used. The techniques presented in this research can be extended to non-PBDT tasks and other distributed computing environments.
References
[1]
http://enterprise.amd.com/Downloads/Industry/Multimedia
[2]
http://www.gridtoday.com/grid/638845.html.
[3]
Abbas A. Grid Computing: A Practical Guide to Technology and Applications, Charles River Media, 2004.
[4]
Ahmad I. and Majumdar S. Policies for Efficient Allocation of Grid Resources using a Bi-level Decision-making Architecture of "Processable" Bulk Data. Department of Systems and Computer Engineering, Carleton University, 2007.
[5]
Ahmad I. and Majumdar S. An adaptive high performance architecture for "processable" bulk data transfers on a Grid. In 2nd International Conference on Broadband Networks (Broadnets). (3-7 Oct. 2005). IEEE, Boston, MA, USA, 2005, 1482--91.
[6]
Ahmad I. and Majumdar S. Efficient Allocation of Grid Resources Using a Bi-level Decision-Making Architecture for "Processable" Bulk Data. On the Move to Meaningful Internet Systems 2007: CoopIS, DOA, ODBASE, GADA, and IS, (2007), 1313--1321.
[7]
Allcock B., Chervenak A., Foster I., Kesselman C. and Livny M. Data Grid tools: enabling science on big distributed data. Journal of Physics: Conference Series, 16, 1 (2005), 571--5.
[8]
Bunn J. and Newman H. Data-intensive Grids for high energy physics. In Berman G. and Hey E. eds.Grid Computing: Making the Global Infrastructure a Reality. John Wiley & Sons, Inc., New York, 2003.
[9]
Berman F., Casanova H., Chien A., Cooper K., Dail H., Dasgupta A., Deng W., Dongarra J., Johnsson L., Kennedy K., Koelbel C., Liu B., Liu X., Mandal A., Marin G., Mazina M., Mellor-Crummey J., Mendes C., Olugbile A., Patel M., Reed D., Shi Z., Sievert O., Xia H. and YarKhan A. New Grid scheduling and rescheduling methods in the GrADS project. International Journal of Parallel Programming, 33, 2-3 (06 2005), 209--29.
[10]
Candler W. and Townsley R. A linear two-level programming problem, Computers & Operations Research, 9, 1 (1982), 59--76.
[11]
Chvatal V. Linear Programming. W.H. Freeman and Company Press, 1980.
[12]
Devpura A. Scheduling Parallel and Single Batch Machines to Minimize Total Weighted Tardiness. Ph.D. Dissertation, Computer Science Department, Arizona State University, 2003.
[13]
Dimitris Bertsimas, John N. Tsitsiklis. Introduction to Linear Programming. Athena Scientific, Belmont, Massachusetts, 1998.
[14]
Downey A. B. Lognormal and Pareto distributions in the Internet. Comput. Commun., 28, 7 (05/02 2005), 790--801.
[15]
Foster I. and Kesselman C. The Grid: Blueprint for a Future Computing Infrastructure. Morgan Kaufmann Publishers, USA, 1999.
[16]
Gzara F. Large scale integer programming: A novel solution method and application. McGill University, 2004.
[17]
Jeong S., Chan-Hyun Youn and Hyoug-Jun Kim. Optimal file replication scheme (CO-RLS) for data Grids. In Anonymous 6th International Conference on Advanced Communication Technology. (9-11 Feb. 2004). IEEE, Phoenix Park, South Korea, 2004, 1055--9.
[18]
Foster I., Kesselman C., Lee C., Lindell B., Nahrstedt K. and Roy A. A distributed resource management architecture that supports advance reservations and co-allocation. In Anonymous Proceedings of IWQoS'99 - Seventh International Workshop on Quality of Service. (31 May-4 June 1999). IEEE, London, UK, 1999, 27--36.
[19]
M. Elayeb. Efficient Data Scheduling For Real-Time Large Scale Data Intensive Distributed Applications. (Masters Dissertation, The Ohio State University).
[20]
Mathur K. and Puri M. C. A bilevel bottleneck programming problem. European Journal of Operational Research, 86, 2 (10/19 1995), 337--344.
[21]
Sander V., Adamson W. A., Foster I. and Roy A. End-to-end provision of policy information for network QoS. In 10th IEEE International Symposium on High Performance Distributed Computing. (7-9 Aug. 2001). IEEE Comput. Soc, San Francisco, CA, USA, 2001, 115--26.
[22]
Sundaram B. and Chapman B. M. XML-based policy engine framework for usage policy Allocation in Grids. In Proceedings. (18 Nov. 2002). Springer-Verlag, Baltimore, MD, USA, 2002, 194--8.
[23]
Vazhkudai S. Enabling the co-allocation of Grid data transfers. In Fourth International Workshop on Grid Computing. (17 Nov. 2003). IEEE Comput. Soc, Phoenix, AZ, USA, 2003, 44--51.
[24]
Venugopal S. Scheduling Distributed Data-Intensive Applications on Global Grids. Ph.D. Dissertation, Department of Computer Science and Software Engineering, The University of Melbourne, 2006.
[25]
Verma D., Sahu S., Calo S., Beigi M. and Chang I. A policy service for Grid computing. In Proceedings (18 Nov. 2002). Springer-Verlag, Baltimore, MD, USA, 2002, 243--55.
[26]
Wu J., Savoie M., Campbell S., Zhang H., Bachmann G. V. and St Arnaud B. Customer-managed end-to-end lightpath provisioning. International Journal of Network Allocation, 15, 5 (2005), 349--62.
[27]
Yang K., Galis A. and Todd C. Policy-based active Grid Allocation architecture. In Towards Network Superiority. (27-30 Aug. 2002). IEEE, Singapore, 2002, 243--8.
Index Terms
- Performance of resource management algorithms for "Processable Bulk Data Transfer" Tasks in Grid Environments
Recommendations
A Two Level Approach for Managing Resource and Data Intensive Tasks in Grids
OTM '08: Proceedings of the OTM 2008 Confederated International Conferences, CoopIS, DOA, GADA, IS, and ODBASE 2008. Part I on On the Move to Meaningful Internet Systems:In recent years, Grid computing has emerged as an attractive platform to tackle various large-scale problems, especially in the field of science and engineering. Scheduling Grid resources involves a number of challenging issues, mainly due to the ...
Survey on Grid Resource Allocation Mechanisms
Grid is a distributed high performance computing paradigm that offers various types of resources (like computing, storage, communication) to resource-intensive user tasks. These tasks are scheduled to allocate available Grid resources efficiently to ...
Efficient management of grid resources using a bi-level decision-making architecture for "processable" bulk data
OTM'07: Proceedings of the 2007 OTM confederated international conference on On the move to meaningful internet systems: CoopIS, DOA, ODBASE, GADA, and IS - Volume Part IIThe problem of efficient assignment of resources to perform a given bag-of-tasks in a distributed computing environment has been extensively studied by research communities. To develop an efficient resource assignment mechanism, this paper focuses on a ...
Comments
Information & Contributors
Information
Published In
June 2008
218 pages
ISBN:9781595938732
DOI:10.1145/1383559
- General Chair:
- Alberto Avritzer,
- Program Chairs:
- Elaine Weyuker,
- Murray Woodside
Copyright © 2008 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]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 23 June 2008
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
WOSP '08
Sponsor:
Acceptance Rates
Overall Acceptance Rate 149 of 241 submissions, 62%
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 196Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 05 Mar 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in