Optimal buffer management for 2-frame throughput maximization
Optimal buffer management for 2-frame throughput maximization
复制标题
DOI：
10.1016/j.comnet.2015.08.046
复制
发表时间：
2013-07
期刊：
影响因子：
--
通讯作者：
J. Kawahara;Koji M. Kobayashi
中科院分区：
文献类型：
--
作者：
J. Kawahara;Koji M. Kobayashi
我们考虑一个变种的网络交换机中的在线缓冲区管理问题，称为k帧吞吐量最大化问题（K-FTM）。互联网上携带的大数据（称为帧）被发送方分成小的k个数据包，只有当接收方接受帧的所有k个组成数据包时，他/她才能重建每个帧。数据包通过互联网上的网络交换机，每个交换机都配备了FIFO缓冲区，以临时存储到达的数据包。由于缓冲区的大小是有界的，因此如果缓冲区已满，则必须丢弃一些数据包。不可能再重构包括丢弃的分组的帧。我们的目标是最大化重建帧的数量。Kesselman等人提出了这个问题，并证明了任何在线算法即使在k= 2时也具有无限的竞争比。因此，他们考虑了k-FTM的“尊重顺序”变体。他们证明了对于任何B≥ k，他们的算法的竞争比至多为（2 k B B/k + k），其中B是缓冲区的大小。当2 B ≥ k且k为2的幂时，给出了竞争比的下界为B = 2 B/k.此外，他们证明了贪婪算法的竞争比至多是（11+ 8 B− 1），对于任何B≥ 2和k= 2。分析了k= 2的贪婪算法，证明了对任意B，其竞争比至多为3，改进了以前的4 B的上界为B/2 + 2（≥ 10）.此外，我们表明，任何确定性算法的竞争比至少是3的任何B，如果k= 2，这符合我们的上限。
We consider a variant of the online buffer management problem in network switches, called the k-frame throughput maximization problem (k-FTM). Large data, called frames, carried on the Internet are split into small k packets by a sender, and the receiver can reconstruct each frame only if he/she accepts all the k constituent packets of the frame. Packets pass through network switches on the Internet, and each switch is equipped with a FIFO buffer to temporarily store arriving packets. Since the size of the buffer is bounded, some packets must be discarded if it is full. It is impossible to reconstruct frames including discarded packets any more. Our goal is to maximize the number of reconstructed frames. Kesselman et al. proposed this problem, and showed that any online algorithm has an unbounded competitive ratio even when k= 2. Hence, they considered the “order-respecting” variant of k-FTM. They showed that the competitive ratio of their algorithm is at most (2 k B⌊ B/k⌋+ k) for any B≥ k, where B is the size of the buffer. Also, they gave a lower bound of B⌊ 2 B/k⌋ on the competitive ratio when 2B≥ k and k is a power of 2. Furthermore, they proved that the competitive ratio of a greedy algorithm is at most (11+ 8 B− 1) for any B≥ 2 and k= 2. We analyze a greedy algorithm for k= 2, and show that its competitive ratio is at most 3 for any B, improving the previous upper bound of 4 B⌊ B/2⌋+ 2 (≥ 10). Moreover, we show that the competitive ratio of any deterministic algorithm is at least 3 for any B if k= 2, which matches our upper bound.