Efficient response time predictions by exploiting application and resource state similarities

In large-scale grids with many possible resources (clusters of computing elements) to run applications, it is useful that the resources can provide predictions of job response times so users or resource brokers can make better scheduling decisions. Two metrics need to be estimated for response time predictions: one is how long a job executes on the resource (application run time), the other is how long the job waits in the queue before starting (queue wait time). In this paper we propose an instance based learning technique to predict these two metrics by mining historical workloads. The novelty of our approach is to introduce policy attributes in representing and comparing resource states, which is defined as the pool of running and queued jobs on the resource at the time to make a prediction. The policy attributes reflect the local resource scheduling policies and they can be automatically discovered using a genetic search algorithm. The main advantages of this approach compared with scheduler simulation are two-folds: Firstly, it has a better performance to meet the real time requirement of Grid resource brokering; secondly, it is more general because the scheduling policies are learned from past observations. Our experimental results on the NIKHEF LCG production cluster show that acceptable prediction accuracy can be obtained, where the relative prediction errors for response times are between 0.35 and 0.70.