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 mu-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 maxstretch 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 Aow time and max.stretch within a constant factor of optimum. all the requests. Since the bandwidth of the links in the network is limited, it makes sense to try to schedule the transmissions in a way that utilizes the available resources optimally. In this paper we consider the online ftp problem, which is a formal abstraction of the above file transfer problem. We assume that each ftp request specifies source/destination nodes and the size of the file. The goal of the online algorithm is to choose a path that will be used for transmitting each file, and to dec:" on the transmission rate. The main difference between this model and the (well-studied) models for online routing and admission control 111, 1, 12,2] is that here we do not assume that the sources have prespecified transmission rate requirements, i.e. we can deal with non-streaming types of information. There are two related measures of performance that can be used to compare different algorithms for the online ftp problem. The first measure is the total flow time, i.e. the sum over all jobs of the time that elapses between the instant the ftp request is submitted and the time it is satisfied (including the transmission time). The other measure is the rn~~-stretch, which is the max. imum over all ratios of the flow time of each request and the smallest time needed to satisfy this request. The second quantity is determined by the link bandwidth and the size of the file. Both mezzures are useful since they are directly related to the performance of the network perceived by the end-user. Let n be the number of requests and P the maximum ratio between the sizes of the files. Assume that the smallest request can be processed in one time unit. Let FL,, denote the optimum max-flow i.e. the smalest value for the maximum time a request spends in the system. The main results of the paper are algorithms that achieve the optimum maz-stretch and the optimum total j%w time using resource augmentation'. For the max.stretch algorithm we need to increase capacities by a factor of O(log P), whereas the total flow time algorithm needs a factor of O(log FGAx) increased 189
Competitive algorithms for advanced reservation networks is the focus of REF .
Scheduling data transfers in a network and the set scheduling problem
STOC '99
Computer Science