Resource Assignment Strategies for Bags-of-Tasks in Distributed Systems

One of the key challenges in distributed systems is the effective and efficient resource assignment for the incoming workload. To this end, two novel task routing strategies are proposed and compared to two well-known policies, Probabilistic and Shortest Queue routing. The proposed techniques aim to provide substantially better performance than the Probabilistic policy and incur significantly less overhead than the Shortest Queue strategy. The performance of the four routing techniques is evaluated via simulation, by taking also into account the implementation effort and the routing overhead required in each case. The performance of the resource assignment strategies is examined under different cases of system load and task service time variability. The simulation results reveal that the proposed routing strategies perform significantly better than the Probabilistic policy. Furthermore, the proposed heuristics could be used in large-scale distributed systems, where the Shortest Queue strategy, even though in theory outperforms other policies, in practice does not scale well, due to the excessive amount of information it requires for each routing decision.