Bandwidth Minimization Algorithms
Prudence W. H. Wong · 2007
We study a bandwidth assignment problem in which each request (job) j has a given size sj and the algorithm has to allocate a bandwidth bj and a continuous time interval Ij such that sj = bj × |Ij |, where |Ij | denotes the duration of the interval I. Moreover, the interval I has to be within the release date and the due date specified for the job. The goal is to minimize the maximum bandwidth used at any time. Bandwidth reservation is common in a lot of applications over computer networks, such as content distribution networks or mobile clients, which need bandwidth reservations to support hangovers for streaming video [1, 2]. Bandwidth reservations can be distinguished into immediate reservations which are made in a just-in-time manner and advance reservations which allow to reserve bandwidth before they are actually used. Immediate reservations can be considered as on-line version of the problem while advance reservations off-line version. The off-line problem can easily be shown to be NP -hard by a reduction from the 3-Partition problem. A log n/ log log n-approximation follows by randomized rounding of an LP-relaxation. The related problem in which the bandwidth of any job is one, i.e., we only need to specify the start times, has been well studied [3, 4]. No constant approximation algorithm is known for that problem. We believe that our problem does have an efficient constant factor approximation algorithm. Here, we summarize some preliminary results for the off-line and on-line variant. Given an instance, let B(t1, t2) be the total size of all jobs with release date and due date between t1 and t2. Then, B∗ = maxt1≤t2 B(t1, t2)/(t2 − t1) is a lower bound on the bandwidth needed. In general this lower bound can be arbitrarily bad.