Algorithms for Integrated Routing and Scheduling for Aggregating Data from Distributed Resources on a Lambda Grid

摘要

In many e-science applications, there exists an important need to aggregate information from data repositories distributed around the world. In an effort to better link these resources in a unified manner, many lambda-grid networks, which provide end-to-end dedicated optical circuit-switched connections, have been investigated. In this context, we consider the problem of aggregating files from distributed databases at a (grid) computing node over a lambda grid. The challenge is (i) to identify routes (i.e., circuits) in the lambda-grid network along which files should be transmitted and (ii) to schedule the transfers of these files over their respective circuits. To address this challenge, we propose a hybrid approach that combines off-line and on-line scheduling. We define the Time-Path Scheduling Problem (TPSP) for off-line scheduling. We prove that TPSP is NP-complete, develop a Mixed Integer Linear Program (MILP) formulation for TPSP, and then propose a greedy approach to solve TPSP because the MILP does not scale well. We compare the erformance of the greedy approach on a few representative lambda-grid network topologies. One key input to the off-line schedule is the file transfer time. Due to dynamics at the receiving end host which is hard to model precisely, the actual file transfer time may vary. We first propose a model for the estimating the file transfer time. Then, we propose on-line reconfiguration algorithms, so that, as files are transferred, the off-line schedule may be modified on-line depending on the amount of time that it actually took to transfer the file. This helps to reduce the total time to transfer all the files, which is an important metric. To demonstrate the effectiveness of our approach, we present results on an emulated lambda-grid network testbed.