Optimal Node Routing
Optimal Node Routing
复制标题
最优节点路由
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Yoel Chaiutin
中科院分区：
文献类型：
--
作者：
Y. Azar;Yoel Chaiutin
本文研究了竞争吞吐量模型下的分组交换路由选择问题。在以前的论文中，考虑竞争力的分组调度算法相比，我们认为分组路由问题（在一个节点的输出端口选择）。我们对节点路由问题建模如下：一个节点有任意数量的输入端口和任意数量的输出队列。在每个时间单元，任意数量的新分组可以到达，每个分组与输出端口的子集（其对应于分组的允许路径上的下一个边缘）相关联。每个输出队列以某种任意方式传输分组。到达和传输是任意的，并由对手控制。节点路由算法必须将每个数据包路由到允许的输出端口之一，而不超过队列的大小。目标是最大化传输的数据包的数量。在本文中，我们证明了所有的非拒绝算法是2-竞争。我们的主要结果是一个几乎最优的$frac{e}{e-1}约1.58$竞争力的算法，一个足够大的队列大小。对于具有任意值的数据包（允许抢占），我们提出了一个2-竞争算法，任何队列大小。
We study route selection for packet switching in the competitive throughput model. In contrast to previous papers which considered competitive algorithms for packet scheduling, we consider the packet routing problem (output port selection in a node). We model the node routing problem as follows: a node has an arbitrary number of input ports and an arbitrary number of output queues. At each time unit, an arbitrary number of new packets may arrive, each packet is associated with a subset of the output ports (which correspond to the next edges on the allowed paths for the packet). Each output queue transmits packets in some arbitrary manner. Arrival and transmission are arbitrary and controlled by an adversary. The node routing algorithm has to route each packet to one of the allowed output ports, without exceeding the size of the queues. The goal is to maximize the number of the transmitted packets. In this paper, we show that all non-refusal algorithms are 2-competitive. Our main result is an almost optimal $frac{e}{e-1} approx 1.58$-competitive algorithm, for a large enough queue size. For packets with arbitrary values (allowing preemption) we present a 2-competitive algorithm for any queue size.