Network-aware HEFT scheduling for grid

Area of Science:

• Computer Science
• Distributed Computing
• Network Engineering

Background:

• The original Heterogeneous Earliest Finish Time (HEFT) algorithm is widely used for task scheduling in distributed systems.
• HEFT does not explicitly consider the impact of parallel network flows on data transfer times, especially in geographically distributed environments.
• Ignoring network contention can lead to unrealistic schedule makespans and suboptimal resource allocation.

Purpose of the Study:

• To propose a network-aware adaptation of the HEFT scheduling algorithm.
• To accurately model the completion time of data transfers considering network bottlenecks.
• To demonstrate the benefits of incorporating network awareness into scheduling for Grid applications.

Main Methods:

• Modification of the original HEFT algorithm to incorporate network-aware data transfer time estimations.
• Simulation of parallel data transfers sharing network links to assess their impact on completion times.
• Comparison of scheduling makespans between the original HEFT and the proposed network-aware HEFT.

Main Results:

• The network-aware HEFT accurately stretches data transfer times to reflect realistic completion durations.
• Schedules generated by the network-aware HEFT provide a more realistic makespan compared to the original HEFT.
• Ignoring parallel data transfer impacts leads to misleadingly optimistic schedule makespans.

Conclusions:

• Network-aware HEFT provides a more accurate scheduling solution for distributed computing environments with distant nodes.
• The proposed approach mitigates the inaccuracies caused by neglecting network contention in parallel data transfers.
• This enhanced HEFT algorithm offers significant benefits for optimizing Grid applications by improving schedule realism.