Hard real-time communication in bus-based networks

Sathish Gopalakrishnan, Lui Sha, Marco Caccamo

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


Route selection is an important aspect of the design of real-time systems in which messages might have to travel over multiple hops to reach their destination and multiple paths exist between a source and a destination. The length of a route affects the ability to meet deadlines and greedy routing might leave certain messages with no feasible route. We consider bus-based networks on which periodic message transmissions need to be scheduled and present a technique for synthesizing routes such that all messages meet their deadlines. Our offline technique enables system designers to configure routes in a large-scale embedded system. In our solution, we allow message fragmentation and utilize multiple paths to satisfy the requirements of each message. The routing problem is NP-complete and our approximation algorithm is based on a linear programming formulation. In our methodology, we deal with both earliest deadline first and rate monotonie scheduling at each bus in the system. Apart from point-to-point messages, we discuss scheduling multicast messages to facilitate the publisher/subscriber model. Finally, we also mention some heuristics for online routing which might be of value in soft real-time systems.

Original languageEnglish (US)
Title of host publicationProceedings - 25th IEEE International Real-Time Systems Symposium, RTSS 2004
Number of pages10
StatePublished - 2004
Event25th IEEE International Real-Time Systems Symposium, RTSS 2004 - Lisbon, Portugal
Duration: Dec 5 2004Dec 8 2004

Publication series

NameProceedings - Real-Time Systems Symposium
ISSN (Print)1052-8725


Other25th IEEE International Real-Time Systems Symposium, RTSS 2004

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Hard real-time communication in bus-based networks'. Together they form a unique fingerprint.

Cite this