Title: Task scheduling in heterogeneous distributed systems with security and QoS requirements

Authors: Naeem Al-Oudat; Govindarasu Manimaran

Addresses: Department of Electrical and Computer Engineering, Iowa State University, Ames, IA 50010, USA. ' Department of Electrical and Computer Engineering, Iowa State University, Ames, IA 50010, USA

Abstract: 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.

Keywords: quality of service; QoS; security; peer to peer; P2P; task scheduling; heterogeneous distributed systems; communication networks; branch and bound; task allocation.

DOI: 10.1504/IJCNDS.2012.047894

International Journal of Communication Networks and Distributed Systems, 2012 Vol.9 No.1/2, pp.21 - 36

Published online: 30 Aug 2014 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article