Matching and Scheduling in Mobile Agent Systems

Joint work with Daniela Rus and Cliff Stein

Objectives A mobile agent system is a single, unified framework in which many distributed applications can be easily designed using agents. The goal of this research is to develop the matching and scheduling algorithms that allow multiple distributed applications to effectively share the resources within a mobile agent system. We propose to build a hierarchical scheduling framework, in which a global (or local) resource manager is a special agent that provides matching and scheduling services to applications, in heterogeneous environment. This kind of multi-agent-multi-resource scheduling problem has several major differences compared with scheduling in traditional computation systems: a mobile agent system has much larger data transfer delay, more diversified network links and wider spectrum of machine speeds.

Problem Definition Given a multi agent application in which each agent has to visit multiple resources in order to complete a task, find a schedule for giving agents access to resources that optimizes the system throughput. The agents may have sequential or parallel constraints on accessing resources. This suggests a natural representation of the problem as a DAG scheduling problem. Given a weighted Directed Acyclic Graph (DAG) G = (J, E) that represents a distributed application, where J is the set of agents (tasks) and E is the set of weighted edges that represents precedence constraints and data paths among tasks, find a schedule of minimal makespan that allocates tasks onto a set of machines M.

Technical Approach The challenge in this research is to develop scheduling algorithms that are effective in the context of mobile agent system, where many assumptions used in traditional scheduling algorithms become unrealistic. Scheduling algorithms for mobile agent system must work in a heterogeneous environment where (1) the number of machines is limited; (2) the task graph structure is general; (3) the data transfer delay is general; and (4) the task duplication is not allowed. This problem is NP_Complete. We have already developed two offline scheduling algorithms. We proved an upper bound for these algorithms in homogeneous environment and showed their good performance in heterogeneous environment by extensive simulations. Our results show that our algorithm outperforms one major existing algorithm ([1]) that attempts to address data transfer delays in homogeneous networks when the data transfer delays are large. We have also shown a performance improvement for our extension of ([1]) over heterogeneous environments.

Open Problems Many aspects of this multi-agent-multi-resource scheduling problem are remained for our future work, including: (1) expanding our model to represent a wider range of mobile-agent-based distributed applications; (2) developing some local adjustment techniques to improve performance; (3) computing an upper bound in heterogeneous environment; (4) developing an online scheduling algorithm; (4) developing a distributed version of these algorithms.

[1] G.C.Sih and E.A. Lee, "A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures", IEEE Trans. Parallel and Distributed Systems, vol.4, pp175-187, Feb.1993.