Scheduling data transfers in a network and the set scheduling problem

In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of the paper is a technique that leads to algorithms that optimize several natural metrics, such as max-stretch, total flow time, max flow time, and total completion time. In particular, we show how to achieve optimum total flow time and optimum max-stretch if we increase the capacity of the underlying network by a logarithmic factor. We show that the resource augmentation is necessary by proving polynomial lower bounds on the max-stretch and total flow time for the case where online and offline algorithms are using same-capacity edges. Moreover, we also give polylogarithmic lower bounds on the resource augmentation factor necessary in order to keep the total flow time and maxstretch within a constant factor of optimum.

Published in:
J Algorithms, 48, 2, 314-332
Other identifiers:
Scopus: 2-s2.0-0042429219

 Record created 2007-01-18, last modified 2018-03-17

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)