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

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

$\frac{ 2kB }{ \lfloor B/k \rfloor } + k$

for any

B

 ≥ 

k

, where

B

is the size of the buffer. They also gave a lower bound of

$\frac{ B }{ \lfloor 2B/k \rfloor }$

for deterministic online algorithms when 2

B

 ≥ 

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

2

) by Kesselman et al. to

$\frac{5B + \lfloor B/k \rfloor - 4}{\lfloor B/2k \rfloor} = O(k)$

for

B

 ≥ 2

k

. 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

$\frac{2B}{\lfloor{B/(k-1)} \rfloor} + 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

$\frac{B}{ \lfloor 2B/k \rfloor }$

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 10

k

, this indicates that randomization does not help too much.