The problem of routing unit-length, real-time messages in a distribute
d system is considered. An on-line routing algorithm is one, that rout
es messages without any knowledge of future arrivals of messages. An o
n-line algorithm is said to be optimal if it produces a feasible route
whenever one exists. In this article, we study the issue whether it i
s possible to have an optimal on-line algorithm for the following netw
orks-unidirectional ring, out-tree, in-tree, bidirectional tree, and b
idirectional ring. The problem is considered under various restriction
s of the four parameters-origin node, destination node, release time,
and deadline. We show that: (1) for a unidirectional ring, no such alg
orithm can exist unless one of the four parameters is fixed (i.e., all
messages have identical values for that parameter); (2) for an out-tr
ee, no such algorithm can exist unless one of the three parameters-ori
gin node, destination node, and release time-is fixed; (3) For an in-t
ree, no such algorithm can exist unless one of the three parameters-or
igin node, destination node, and deadline-is fixed; (4) for a bidirect
ional tree, no such algorithm can exist unless the origin node or the
destination node is fixed; (5) for a bidirectional ring, no such algor
ithm can exist unless the origin node and either the destination node
or the release time are fixed. Our results give a sharp boundary delin
eating those instances for which an optimal algorithm exists and those
for which no such algorithm can exist. (C) 1996 Academic Press, Inc.