Real-Time Message Routing and Scheduling

Research Area: Algorithm Engineering for Real-time Scheduling and Routing Year: 2009
Type of Publication: In Proceedings Keywords: Iterative Rounding, Job Shop Scheduling, Approximation Algorithms
Authors: Ronald Koch; Britta Peis; Martin Skutella; Andreas Wiese
Volume: 5687
Book title: 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2009)
Series: LNCS Pages: 217-230
Exchanging messages between nodes of a network (e.g., embedded computers) is a fundamental issue in real-time systems involving critical routing and scheduling decisions. In order for messages to meet their deadlines, one has to determine a suitable (short) origin-destination path for each message and resolve conflicts between messages whose paths share a communication link of the network. With this paper we contribute to the theoretic foundations of real-time systems. On the one hand, we provide efficient routing strategies yielding origin-destination paths of bounded dilation and congestion. In particular, we can give good a priori guarantees on the time required to send a given set of messages which, under certain reasonable conditions, implies that all messages can be scheduled to reach their destination on time. Finally, for message routing along a directed path (which is already NP-hard), we identify a natural class of instances for which a simple scheduling heuristic yields provably optimal solutions.
[ Back ]