TIME: 1:30-2:20 pm,  November 14, 2006

PLACE: CSE 403

TITLE: Optimal Node Routing

SPEAKER: Yossi Azar
         Microsoft Research and Tel Aviv University
 

ABSTRACT:

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 (specifically, output port selection in a node). We
model the node routing problem as follows: a node has some number of
input ports and some number of output queues. At each time unit, any
number of new packets may arrive, each packet is associated with a
subset of the output ports. 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. We show that all non-refusal algorithms are
2-competitive. Our main result is an almost optimal e/(e-1}
(approximately 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. Joint work with
Yoel Chaiutin.