IJPAM: Volume 14, No. 1 (2004)

STABILITY CONDITIONS OF A RECURSIVE
ROUTING ALGORITHM

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


Abstract.In this paper, we prove formally the conditions under which recursive algorithms like the proposed study scheme can be considered stable. Such algorithms are of great use especially in network routers. Their main job is to select which packet is needed to be forwarded from the input ports to the output ports of the device. The stability property ensures that the algorithm will not drop any packets even if the incoming normalized traffic load is maximum.

Received: April 4, 2004

AMS Subject Classification: 68R10

Key Words and Phrases: recursive algorithms, bipartite graphs, matching, queuing system stability, schedulling

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