Journal of Software, Vol 6, No 8 (2011), 1395-1402, Aug 2011
doi:10.4304/jsw.6.8.1395-1402

Two-Dimension Relaxed Reservation Policy for Independent Tasks in Grid Computing

Peng Xiao, Zhigang Hu

Abstract


As an effective technique for QoS provision, reservation service has been widely applied in various grids. However, plenty of studies have shown that reservation service will bring about many negative effects on system performance, i.e. higher rejection rate and lower resource utilization. To mitigate these negative effects, a relaxed reservation policy is proposed in this paper. It allows grids accepting reservation requests that overlapping with existing ones in two dimensions (temporal and space). In addition, the proposed policy is completely compatible with conventional reservation service, which means it can be applied in all kinds of practical grids. Extensive experiments have been conducted by using real workloads, and the experimental results show that the relaxed reservation policy can achieve higher resource utilization and lower rejection rate comparing to other policies. Also, It shows better adaptiveness when grids are in presence of higher reservation rate.


Keywords


grid computing; resource reservation; relaxed policy; quality of service; reservation violation; time slot

References


A. Roy, V. Sander. “Advance Reservation API”. GFD-E.5, Scheduling Working Group, Global Grid Forum, 2002.

I. Foster, I. Kesselman. “The Grid: Blueprint for a New Computing Infrastructure”. Singapore: Elsevier Inc. 2004.

I. Foster, C. Kesselman, C. Lee, et al. “A Distributed Resource Management Architecture that Supports Advance Reservation and Co-Allocation”. Proc. of Int’l Workshop on Quality of Service, 1999:27-36.

I. Foster, A. Roy, V. Sander. “A Quality of Service Architecture that Combines Resource Reservation and Application Adaptation”. Proceedings of International Workshop on Quality of Service, 2000:181-188.

T. Rölitz, A. Reinefeld. “Co-Reservation with the Concept of Virtual Resources”. Proceeding of International Symp. on Cluster Computing and the Grid, 2005:254-261.

L. O. Burchard, B. Linnert, J. Schneider. “A Distributed Load-Based Failure Recovery Mechanism for Advance Reservation Environments”. Proc of Int’l Symp. on Cluster Computing and the Grid, 2005:1071-1078.

J. W. Cao, F. Zimmermann. “Queue Scheduling and Advance Reservations with COSY”. Proc. of the Int’l Parallel and Distributed Processing Symposium, 2004.

A. C. Sodan, C. Doshi, L. Barsanti, D. Taylor. “Gang Scheduling and Adaptive Resource Allocation to Mitigate Advance Reservation Impact”. Proc. of Int.l Symp. on Cluster Computing and the Grid, 2006:649-653.

W. Smith, I. Foster, V. Taylor. “Scheduling with Advanced Reservations”. Proceedings of International Symp. on Parallel and Distributed Processing, 2000:127-132.

M. Wu, X. H. Sun, Y. Chen. “QoS Oriented Resource Reservation in Shared Environments ”. Proc. of Int.l Symp. on Cluster Computing and the Grid, 2006:601-608.

C. Barz, M. Pilz, A. Wichmann. “Temporal Routing Metrics for Networks with Advance Reservations”. Proceedings of IEEE International Symp. on Cluster Computing and the Grid, 2008:710-715.

A. Sulistio, K. H. Kim, R. Buyya. “Managing Cancellations and No-shows of Reservations with Overbooking to Increase Resource Revenue”. Proc. of Int.l Symp. on Cluster Computing and the Grid, 2008:267-276.

A. W. Mu'alem, D. G. Feitelson. “Utilization, Predictability, Workloads, and User Runtime Estimates in Scheduling the IBM SP2 with Backfilling”. IEEE Trans. on Parallel and Distributed Systems, 2001, 12(5):529-543.
http://dx.doi.org/10.1109/71.932708

A. Sulistio, W. Schiffmann, R. Buyya. “Advanced Reservation-based Scheduling of Task Graphs on Clusters”. Proceedings of International Conf. on High Performance Computing, 2006:60-71.

N. R. Kaushik, S. M. Figueira, S. A. Chiappari. “Flexible Time-Windows for Advance Reservation Scheduling”. Proc. of Int.l Symp. on Modeling, Analysis, and Simulation of Computer and Tele. Systems, 2006:218-225.

L. Wu, C. Wu, J. Cui, J. Xing. “An Adaptive Advance Reservation Mechanism for Grid Computing”. Proceedings of International Conf. on Parallel and Distributed Computing, Applications and Technologies, 2005:400-403.

M. H. Alsuwaiyel. “Algorithms Design Techniques and Analysis”. U.S.A: World Scientific Publishing Co., 1999.
http://dx.doi.org/10.1142/9789812386397

F. Berman, R. Wolski, et al. “Adaptive Computing on the Grid Using AppLeS”. IEEE Trans. on Parallel and Distributed Systems, vol.14, no.4, 2003:369-382.
http://dx.doi.org/10.1109/TPDS.2003.1195409

H. Casanova, F. Berman. “Parameter Sweeps on the Grid with APST”. Wiley Publishers, Inc., 2002.

A. Al-Saidi, N. J. Avis, I. J. Grimstead, O. F. Rana. “Distributed Collaborative Visualization Using Light Field Rendering”. Proc of Intl Symp. on Cluster Computing and the Grid, 2009:609-614.

N. Jacq, J. Salzemann, F. Jacq, Y. Legré, E. Medernach, et al. “Grid-enabled Virtual Screening Against Malaria”. Journal of Grid Computing, vol.6, no.1, 2008:29-43.
http://dx.doi.org/10.1007/s10723-007-9085-5

H. Bal, R. R. Bhoedjang, R. Hofman, et al. “The Distributed ASCI Supercomputer Project”. ACM Operating Systems Review, vol.34, no.4, 2000:76-96.
http://dx.doi.org/10.1145/506106.506115

U. Lublin, D. G. Feitelson. “The Workload on Parallel Supercomputers: Modeling the Characteristics of Rigid Jobs”. Journal of Parallel and Distributed Computing, vol.63, no.11, 2003:1105-1122.
http://dx.doi.org/10.1016/S0743-7315(03)00108-4

C. M. Hu, J. P. Huai, T. Y. Wo. “Flexible Resource Capacity Reservation Mechanism for Service Grid Using Slack Time”. Journal of Computer Research and Development, vol.44, no.1, 2007:20-28.
http://dx.doi.org/10.1360/crad20070103


Full Text: PDF


Journal of Software (JSW, ISSN 1796-217X)

Copyright @ 2006-2013 by ACADEMY PUBLISHER – All rights reserved.