A New Allocation Scheme for Parallel Applications with Deadline and Security Constraints on Clusters
Tao Xie and Xiao Qin
IEEE International Conference on Cluster Computing (Cluster 2005)
Boston, Massachusetts, USA, September 27 - 30, 2005
Abstract
Parallel applications with deadline and security constraints are emerging in various areas like education, information technology, and business. However, conventional job schedulers for clusters generally do not take security requirements of real-time parallel applications into account when making allocation decisions. In this regard, we address in this paper the issue of allocating tasks of parallel applications on clusters subject to timing and security constraints in addition to precedence relationships. A task allocation scheme, or TAPADS (Task Allocation for Parallel Applications with Deadline and Security Constraints), is developed to find an optimal allocation that maximizes quality of security and the probability of meeting deadlines for parallel applications running on clusters. A parallel application within a planning cycle is formally described as a task flow graph in which computation and communication requirements are accurately modelled. The proposed TAPADS scheme factors in security and timing correctness in a way that the probabilities of being risk free and meeting deadlines are used as the performance objectives for clusters. To facilitate the presentation of TAPADS, we propose mathematical models to describe a system framework, parallel applications with deadline and security constraints, and security overheads. These models are used by the TAPADS scheme to measure security overheads caused by an array of security services, including encryption, authentication, integrity check, etc. To quantitatively evaluate the effectiveness and practicality of the proposed TAPADS scheme, we conducted extensive experiments using a real world application as well as synthetic benchmarks. Our experimental results show that TAPADS significantly improves the performance of clusters in terms of quality of security and schedulability over three existing allocation schemes.