Routing messages with release time and deadline constraints

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

The problem of deciding if a set of real-time messages can be transmitted in an unidirectional ring network with m > 1 nodes is considered. Complexity results are given for various restrictions on the four parameters associated with each message: origin node, destination node, release time and deadline. For nonpreemptive transmission, it is shown that the problem is solvable in polynomial time for any case when only one of the four parameters is allowed to be arbitrary. Also shown is that it is NP-complete for each case when any two of the four parameters are fixed. For preemptive transmission, the problem is solvable in polynomial time for any case when only one of the four parameters is allowed to be arbitrary. Also, it is NP-complete for each case when any two of the four parameters are fixed, except the following two cases: (1) same origin node and release time; and (2) same destination node and deadline.

Original languageEnglish (US)
Title of host publicationProc Euromicro Workshop Real Time
Editors Anon
PublisherPubl by IEEE
Pages168-177
Number of pages10
ISBN (Print)0818619562
StatePublished - Dec 1 1989
Externally publishedYes
EventProceedings: Euromicro Workshop on Real Time - Villa Olma, Como, Italy
Duration: Jun 14 1989Jun 16 1989

Other

OtherProceedings: Euromicro Workshop on Real Time
CityVilla Olma, Como, Italy
Period6/14/896/16/89

All Science Journal Classification (ASJC) codes

  • Engineering(all)

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

Cite this