On Queuing Lengths in On-Line Switching

network switches. Scheduling algorithms that prevents packet-loss
are always desirable. Longest-Queue-First (LQF) is an on-line
greedy algorithm widely exploited because of its simplicity and
efficiency. In this paper, we give improved bounds on the
competitive ratio of LQF in terms of the worst-case queuing length,
parameterized with respect to the optimal queuing length of a
clairvoyant adversary. This gives a better picture of LQF's
performance under heavy traffic than the usual (unparameterized)
competitive ratio. We also discuss randomization, and we conclude
with some intriguing open problems regarding a
two-dimensional generalization of the problem.