IJPAM: Volume 19, No. 1 (2005)

STABLE SCHEDULING SCHEMES
FOR PACKET SWITCHES

G. Baklavas$^1$, M. Roumeliotis$^2$
$^{1,2}$Department of Applied Informatics
University of Macedonia
P.O. Box 1591, 156 Egnatia Str., Thessaloniki, 54006, GREECE
$^1$e-mail: grigoris@uom.gr
$^2$e-mail: manos@uom.gr


Abstract.This paper discusses packet scheduling algorithms similar to the ones used in modern IP routers. Two new scheduling techniques (schemes) are proposed. We describe them formally and then prove the conditions under which they keep their stability property, meaning that they do not experience packet loss even under the most severe traffic conditions. It is shown that every packet scheduling algorithm that follows any of the two proposed schemes remains stable under any admissible traffic pattern.

Received: January 27, 2005

AMS Subject Classification: 68R10

Key Words and Phrases: input queue switches, packet scheduling, queuing system stability

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2005
Volume: 19
Issue: 1