The problem of determining whether a set of real-time messages can be
routed in a network is considered. Each message has five parameters-or
igin node, destination node, length, release time, and deadline. The c
omplexity of the problem is considered under various restrictions of f
our parameters-origin node, destination node, release time, and deadli
ne. It is shown that if the network is a arbitrary directed graph, the
problem is NP-complete even when all four parameters are fixed; i.e.,
the messages have identical values in all four parameters. Motivated
by the complexity of the problem, we consider a simple network-a unidi
rectional ring. For nonpreemptive transmission, it is shown that the p
roblem is solvable in polynomial time if three of the four parameters
are fixed, but becomes NP-complete if only two of them are fixed. The
same kind of complexity results hold for preemptive transmission, exce
pt for the following two cases: (1) identical origin nodes and release
times and (2) identical destination nodes and deadlines. The complexi
ty of these two cases remains open. The issue of whether there is an o
ptimal on-line algorithm is also considered. It is shown that no such
algorithm can exist unless all of the remaining three parameters are f
ixed. (C) 1995 Academic Press Inc.