Search

In this paper, we consider the online buffer management problem, which formulates the problem of managing network switches supporting Quality of Service guarantee. We improve competitive ratios of the 2-value multi-queue switch model, where the value of a packet is restricted to 1 or α ( ≥ 1 ) . We use a similar approach as Azar and Richter (STOC 2003 and Algorithmica 43(1-2), 2005) did for the multi-value multi-queue switch model. Namely, we show that the competitive ratio of “the relaxed model” of the 2-value multi-queue switch model is at most x = min ⁡ { c + 2 − c α ( 2 − c ) + c − 1 , c α } , if the competitive ratio of an online algorithm for the unit-value multi-queue switch model is at most c . Azar and Richter's technique implies that if the competitive ratio of the 2-value single-queue switch model is x ′ , then the competitive ratio of the 2-value multi-queue switch model is at most x x ′ . We obtain several results using known c and x ′ . [ABSTRACT FROM AUTHOR]

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 2 k B ⌊ B / k ⌋ + k for any B ≥ k , where B is the size of the buffer. They also gave a lower bound of B ⌊ 2 B / k ⌋ 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 5 B + ⌊ B / k ⌋ − 4 ⌊ B / 2 k ⌋ = 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 2 B ⌊ 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 ⌊ 2 B / 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 10 k , this indicates that randomization does not help too much. [ABSTRACT FROM AUTHOR]