CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

On queuing lengths in on-line switching

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)) ; Zhen Zhou
Theoretical Computer Science (0304-3975). Vol. 339 (2005), 2-3, p. 333-343.
[Artikel, refereegranskad vetenskaplig]

Queues that temporarily store fixed-length packets are ubiquitous in network switches. Scheduling algorithms that prevent 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.

Nyckelord: online switching, queuing, parameterized competitive ratio



Denna post skapades 2006-08-25. Senast ändrad 2015-02-11.
CPL Pubid: 5907