Maximizing throughput in multi-queue switches
Maximizing throughput in multi-queue switches
复制标题
最大化多队列交换机的吞吐量
作者：
Y. Azar;Arik Litichevskey
我们研究多队列交换机中的一个基本问题。开关将 m 个输入端口连接到单个输出端口。每个输入端口都配备有一个容量有限的传入 FIFO 队列 B。交换机通过传输到达这些队列的数据包来为其输入队列提供服务，每个时间单位一个数据包。由于到达速率可能高于传输速率，并且每个队列的容量有限，因此可能会因队列空间不足而发生丢包。目标是最大化传输数据包的数量。这种一般场景对大多数当前网络（例如 IP 网络）进行建模，这些网络仅支持“尽力而为”服务，其中所有数据包流都被平等对待。在[5]中针对任意B 设计了针对该问题的2-竞争算法。最近，[3]中针对 B>1 提出了一种 (17/9 ≈ 1.89) 竞争算法。我们在本文中的主要结果表明，对于不太小的 B，我们的算法可以做得比 1.89 更好，并且接近 e/(e − 1) ≈ 1.58 的竞争比。
We study a basic problem in Multi-Queue switches. A switch connectsm input ports to a single output port. Each input port is equipped with an incoming FIFO queue with bounded capacityB. A switch serves its input queues by transmitting packets arriving at these queues, one packet per time unit. Since the arrival rate can be higher than the transmission rate and each queue has limited capacity, packet loss may occur as a result of insufficient queue space. The goal is to maximize the number of transmitted packets. This general scenario models most current networks (e.g. IP networks) which only support a “best effort” service in which all packet streams are treated equally. A 2-competitive algorithm for this problem was designed in [5] for arbitraryB. Recently, a (17/9 ≈ 1.89)-competitive algorithm was presented forB>1 in [3]. Our main result in this paper shows that forB which is not too small our algorithm can do better than 1.89, and approach a competitive ratio ofe/(e − 1) ≈ 1.58.