HRS: A Hierarchical Routing and Scheduling Scheme for Distributed Real-Time and Embedded Systems
Lei Rao, Xue Liu, Zonghua Gu and Wenyo Liu
How to guarantee end-to-end application deadlines is an important research challenge for distributed real-time and embedded systems. Further challenges arise due to varied workloads and the nature of distributed computing. Routing and scheduling are two important design aspects affecting the end-to-end real-time performance of distributed real-time and embedded systems. While most of the previous work has focused on either routing or scheduling, the study of the integration of routing and scheduling has not been well investigated for distributed real-time and embedded systems. In this paper, we propose HRS: a novel two-level hierarchical routing and scheduling scheme. HRS is based on the layering network design principle: at the upper level, HRS’s traffic-aware routing module determines which route to take through the network for each flow; at the lower level, HRS’s weighted deadline scheduling module determines which packet to serve at each time instant for each node. Together this two-level hierarchical design supports lower deadline miss ratios for distributed real-time and embedded systems.We also conduct extensive evaluations on OMNeT++ to demonstrate the efficiency and efficacy of the proposed methods in this paper.
Keywords: Real Time, Routing, Scheduling, Distributed