Packet Buffering: Randomization Beats Deterministic Algorithms
Packet Buffering: Randomization Beats Deterministic Algorithms
复制标题
数据包缓冲：随机化击败确定性算法
DOI：
10.1007/978-3-540-31856-9_24
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Markus Schmidt
中科院分区：
文献类型：
--
作者：
Markus Schmidt
我们考虑在多队列网络交换机中的每个交换机的输入端口配备有一个容量有限的缓冲区的缓冲单元值数据包的问题。在这些端口，数据包在线到达，可以存储在空间限制内，或者必须丢弃。我们的目标是转发数据包的数量最大化，每个时间步，最多一个数据包从一组缓冲区可以发送到输出端口。
在本文中，我们给出了一种技术，将任何随机化算法的单位缓冲区到一个随机化算法的缓冲区与任意容量，同时保持竞争力。我们提出了第一个随机在线算法，击败了确定性下限的e/（e - 1）1.58。它是3/2竞争性的，因此几乎匹配随机下限1.46。对于具有2个队列的大容量缓冲区，我们显示了任何在线算法的下限为16/13 <$1.23，并证明了贪婪算法的竞争比为9/7 <$1.29，改进了以前已知的最佳上限3/2。
We consider the problem of buffering unit value data packets in multi-queue network switches where each of the switch's input ports is equipped with a buffer of limited capacity. At these ports, packets arrive online and can be stored within the space limitations or must be discarded. Our objective is the maximization of the number of forwarded packets where, per time step, at most one packet from the set of buffers can be transmitted to the output port.
In this paper, we give a technique for transforming any randomized algorithm for unit buffers into a randomized algorithm for buffers with arbitrary capacities while maintaining the competitiveness. We present the first randomized online algorithm that beats the deterministic lower bound of e/(e – 1) ≈ 1.58. It is 3/2-competitive and thus nearly matches the randomized lower bound of 1.46. For buffers with 2 queues having large capacities, we show a lower bound of 16/13 ≈ 1.23 for any online algorithm and prove that the competitive ratio of greedy algorithms is 9/7 ≈ 1.29, improving the best previously known upper bound of 3/2.