Abstract:

MapReduce is a distributed computing framework for big data processing, which has been widely used in various fields. It’s a challenge to ensure the deadline of different priority users in the cluster providing MapReduce services. To solve this problem, a queuing network based multipriority scheduling algorithm (MPSA) is proposed. Firstly, the MapReduce based algorithms are summarized and analyzed, three common patterns are proposed, and the Jackson queuing network is used to build a mathematic model of the MapReduce based algorithms. The mathematic model can be used to find the resource demands of different priority queues. Secondly, the AR(1) model is used to predict the numbers of accessing users, and the binary search algorithm is used to calculate the assigned slot numbers of different priority users in map phase and reduce phase. Finally, a real time scheduling algorithm running in the MapReduce framework is implemented. Experimental results show that, compared with the traditional FIFO and fair scheduling algorithm, the proposed scheduling algorithm can ensure the  defined deadlines of different priority users more effectively when the user arrival rates and the task scales change.

Key words: cloud computing;queuing network;MapReduce;scheduling algorithm