Better bounds for online k-frame throughput maximization in network switches

In this paper, we improve upper and lower bounds on the competitive ratio of k-OFTM. Our main result is to improve an upper bound of O(k2) by Kesselman et al. to 5B+⌊B/k⌋−4⌊B/2k⌋=O(k) for B≥2k. Note that this upper bound is tight up to a multiplicative constant factor since the lower bound given by Kesselman et al. is Ω(k). We also give two lower bounds. First we give a lower bound of 2B⌊B/(k−1)⌋+1 on the competitive ratio of deterministic online algorithms for any k≥2 and any B≥k−1, which improves the previous lower bound of B⌊2B/k⌋ by a factor of almost four. Next, we present the first nontrivial lower bound on the competitive ratio of randomized algorithms. Specifically, we give a lower bound of k−1 against an oblivious adversary for any k≥3 and any B. Since a deterministic algorithm, as mentioned above, achieves an upper bound of about 10k, this indicates that randomization does not help too much.