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 poly-logarithmic lower bounds on the resource augmentation factor necessary in order to keep the total flow time and max-stretch within a constant factor of optimum.
- View record in Scopus
Keywords: Bandwidth ; Channel capacity ; Congestion control (communication) ; Constraint theory ; Data communication systems ; Data structures ; Online systems ; Optimization ; Polynomials ; Telecommunication networks ; Telecommunication traffic ; Theorem proving ; Offline algorithms ; Online algorithms ; Poly-logarithmic lower bounds ; Algorithms
Record created on 2007-01-18, modified on 2016-08-08