ROUTING MESSAGES WITH RELEASE TIME AND DEADLINE CONSTRAINTS

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.