Better bounds for online k-frame throughput maximization in network switches
Better bounds for online k-frame throughput maximization in network switches
复制标题
DOI：
10.1016/j.tcs.2016.10.009
复制
发表时间：
2013-09
期刊：
影响因子：
--
通讯作者：
J. Kawahara;Koji M. Kobayashi;S. Miyazaki
中科院分区：
文献类型：
--
作者：
J. Kawahara;Koji M. Kobayashi;S. Miyazaki
我们考虑一个变种的网络交换机中的在线缓冲区管理问题，称为k帧吞吐量最大化问题（K-FTM）。该问题模拟了一个大帧被分成k个数据包并通过互联网传输的情况，并且接收者只有接受所有k个数据包才能重建该帧。Kesselman等人引入了这个问题，并证明了即使当k = 2时，它的竞争比也是无界的。他们还引入了k-FTM的一个“尊重顺序”的变体，称为k-OFTM，其中输入以某种自然的方式受到限制。他们提出了一种在线算法，并证明了对于任何B ≥ k，其竞争比至多为2 k B B/k + k，其中B是缓冲区的大小。当2 B ≥ k且k是2的幂时，他们还给出了确定性在线算法的下界B = 2 B/k。本文改进了k-OFTM竞争比的上下界。我们的主要结果是将Kesselman等人的O（k 2）的上界改进为5 B + B/k − 4 B/2 k = O（k），其中B ≥ 2 k.注意，这个上界紧到乘法常数因子，因为Kesselman等人给出的下界是Ω（k）。我们也给出了两个下界。首先，我们给出了确定性在线算法的竞争比的一个下界2 B B/（k − 1）+1，对于任意k ≥ 2和任意B ≥ k − 1，这将以前的下界B B/k提高了近四倍。其次，我们给出了随机算法竞争比的第一个非平凡下界。具体地说，我们给出了一个下界k − 1对一个不经意的对手，任何k ≥ 3和任何B。如上所述，由于确定性算法达到约10k的上限，这表明随机化没有太大帮助。
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 10k, this indicates that randomization does not help too much.