Routing messages with release time and deadline constraint

Joseph Y.T. Leung, Tommy W. Tam, C. S. Wong, Gilbert H. Young

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

The problem of determining whether a set of real-time messages can be routed in a network is considered. Each message has five parameters-origin node, destination node, length, release time, and deadline. The complexity of the problem is considered under various restrictions of four parameters-origin node, destination node, release time, and deadline. 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 unidirectional ring. For nonpreemptive transmission, it is shown that the problem 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, except for the following two cases: (1) identical origin nodes and release times and (2) identical destination nodes and deadlines. The complexity of these two cases remains open. The issue of whether there is an optimal on-line algorithm is also considered. It is shown that no such algorithm can exist unless all of the remaining three parameters are fixed.

Original languageEnglish (US)
Pages (from-to)65-76
Number of pages12
JournalJournal of Parallel and Distributed Computing
Volume31
Issue number1
DOIs
StatePublished - Nov 15 1995

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Routing messages with release time and deadline constraint'. Together they form a unique fingerprint.

Cite this