Hard real-time communication in bus-based networks

TitleHard real-time communication in bus-based networks
Publication TypeConference Paper
Year of Publication2004
AuthorsGopalakrishnan, S., L. Sha, and M. Caccamo
Conference NameReal-Time Systems Symposium, 2004. Proceedings. 25th IEEE International
Pagination405 - 414
Date Publisheddec.
Keywordsapproximation algorithm, approximation theory, bus-based networks, computational complexity, earliest deadline first scheduling, embedded systems, field buses, hard real-time communication, large-scale embedded system, linear programming, message fragmentation, message passing, multicast message scheduling, NP-completeness, rate monotonic scheduling, route selection, scheduling, soft real-time systems

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 monotonic 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.


a place of mind, The University of British Columbia

Electrical and Computer Engineering
2332 Main Mall
Vancouver, BC Canada V6T 1Z4
Tel +1.604.822.2872
Fax +1.604.822.5949

Emergency Procedures | Accessibility | Contact UBC | © Copyright 2020 The University of British Columbia