Tadashi Ae, Masafumi Yamashita, Hiroshi Matsumoto

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


The authors discuss the problem of determining the maximum response time for any messages in the network. In the model presented, the network consists of input ports at which messages are originated and channels to transmit messages. The authors first consider the case in which a message is originated at every input port only once and prove the problem to be NP-hard. Under additional conditions, it is shown that the problem is solvable on O(n) time, where n is the number of input ports. Based on this polynomial case, the authors extend the problem to the case in which messages are repeatedly originated at every input port and prove that the maximum response time for a sequence of consecutive messages originated at any input port can be computed in polynomial time.

Original languageEnglish
Title of host publicationUnknown Host Publication Title
Number of pages10
ISBN (Print)0818608153
Publication statusPublished - 1987
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'RESPONSE TIME ESTIMATION OF REAL-TIME NETWORKS.'. Together they form a unique fingerprint.

Cite this