Better Bounds for Online k-Frame Throughput Maximization in Network Switches

الأصل · EN

We consider a variant of the online buffer management problem in network switches, called the k-frame throughput maximization problem (k-FTM). This problem models the situation where a large frame is fragmented into k packets and transmitted through the Internet, and the receiver can reconstruct the frame only if he/she accepts all the k packets. Kesselman et al.introduced this problem and showed that its competitive ratio is unbounded even when k=2. They also introduced an "order-respecting" variant of k-FTM, called k-OFTM, where inputs are restricted in some natural way. They proposed an online algorithm and showed that its competitive ratio is at most 2kB/ B/k + k for any B ≥ k, where B is the size of the buffer. They also gave a lower bound of B/ 2B/k for deterministic online algorithms when 2B ≥ k and k is a power of 2. 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(k²) 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.