Task scheduling in heterogeneous distributed systems with security and QoS requirements
Naeem Al-Oudat, Manimaran Govindarasu · International Journal of Communication Networks and Distributed Systems · 2012
Heterogeneous distributed systems are continuously being deployed, e.g., P2P and military command, control, communications, computers, and intelligence (C4I). Many of these applications trade-off quality of service (QoS) and security. In this paper, we study the problem of allocating and scheduling a set of dependent tasks with security and QoS requirements on a set of heterogeneous sites. This problem is at least as hard as the basic NP-hard problem of scheduling a directed acyclic graph (DAG) on multiple processors. In particular, we make the following contributions: 1 we formulate the problem as an optimisation problem 2 we use a branch and bound (B&B) method guided by an upper bound on total QoS value (TQV) to find the optimal solution if one exist 3 we propose a heuristic algorithm to provide a near optimal solution for the scheduling of the assigned tasks on a site to maximise the QoS provided by this site in a polynomial time 4 we evaluate the heuristic algorithm and compare it with some baseline algorithms using variations of synthetic workloads.