Concurrent scheduling: Efficient heuristics for online large-scale data transfers in distributed real-time environments

Abstract

The static staging heuristics proposed in the literature for staging the data items associated with real-time distributed applications adhere to a method by which only one data item is transferred in each communication step to optimize a specific cost function. In this paper, we first propose the Extended Partial Path (EPP) algorithm based on the same method. In terms of maximizing the number of satisfied requests, we have analytically shown that EPP has a performance that is equal to or greater than the Partial Path Heuristic (PPH) introduced previously [1], thanks to excluding the data items that cannot be satisfied by PPH from scheduling and scheduling the satisfiable data-items along their extended paths. In contrast to EPP and other data staging heuristics proposed, we develop the concurrent scheduling (CS) heuristic which allows simultaneous transfer of more than one data item in an organized fashion, thereby improving the overall performance of the staging system. At the heart of the CS heuristic are EPP and the local priority assignment method devised for solving the conflicts between data items at the intermediate nodes. The extensive simulation results further confirm the superiority of the CS heuristic over PPH.