论文标题
打破2的障碍，以获得最长的队列下降的竞争力
Breaking the Barrier of 2 for the Competitiveness of Longest Queue Drop
论文作者
论文摘要
我们考虑管理传输单位值数据包的共享内存开关的缓冲区的问题。共享内存开关由输入端口，许多输出端口和具有特定容量的缓冲区组成。在每个时间步骤中，任意数量的数据包到达输入端口，每个数据包指定为一个输出端口。将每个数据包添加到相应输出端口的队列中。如果数据包总数超过缓冲区的容量，则必须不可撤销地驱逐一些数据包。在每个时间步长的结尾，每个输出端口在其队列中传输一个数据包，目标是最大化传输数据包的数量。 最长的队列滴（LQD）在线算法接受到缓冲区的任何到达数据包。但是，如果这导致缓冲区超过其内存能力，则LQD将从当前最长的排队中删除一个数据包，并任意打破纽带。 LQD算法于1991年首次引入，自2001年以来被众所周知$ 2 $竞争。尽管LQD仍然是该问题的最著名在线算法，并且具有实际兴趣，但确定其真正的竞争力是一个长期的开放问题。我们表明，LQD是1.6918竞争力，建立了第一个$（2- \ Varepsilon）$上限，以持续的$ \ varepsilon> 0 $。
We consider the problem of managing the buffer of a shared-memory switch that transmits packets of unit value. A shared-memory switch consists of an input port, a number of output ports, and a buffer with a specific capacity. In each time step, an arbitrary number of packets arrive at the input port, each packet designated for one output port. Each packet is added to the queue of the respective output port. If the total number of packets exceeds the capacity of the buffer, some packets have to be irrevocably evicted. At the end of each time step, each output port transmits a packet in its queue and the goal is to maximize the number of transmitted packets. The Longest Queue Drop (LQD) online algorithm accepts any arriving packet to the buffer. However, if this results in the buffer exceeding its memory capacity, then LQD drops a packet from whichever queue is currently the longest, breaking ties arbitrarily. The LQD algorithm was first introduced in 1991, and is known to be $2$-competitive since 2001. Although LQD remains the best known online algorithm for the problem and is of practical interest, determining its true competitiveness is a long-standing open problem. We show that LQD is 1.6918-competitive, establishing the first $(2-\varepsilon)$ upper bound for the competitive ratio of LQD, for a constant $\varepsilon>0$.
