Efficient response time prediction by exploiting application and resource state similarities

In large-scale Grids with many possible resources (clus-ters of computing elements) to run applications, it is use-ful that the resources can provide predictions of job re-sponse times so users or resource brokers can make bet-ter scheduling decisions. Two metrics need to be estimated for response time predictions: one is how long a job exe-cutes 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 in-troduce policy attributes in representing and comparing re-source states, which is defined as the pool of running and queued jobs on the resource at the time to make a predic-tion. The policy attributes reflect the local resource schedul-ing policies and they can be automatically discovered us-ing 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 pre-diction accuracy can be obtained, where the relative predic-tion errors for response times are between 0.35 and 0.70.