Advertisement
Published in:
2009 | OriginalPaper | Chapter
Real-Time Message Routing and Scheduling
Authors : Ronald Koch, Britta Peis, Martin Skutella, Andreas Wiese
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 arrive on time, 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. 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. Our algorithm uses a path-based LP-relaxation and iterative rounding. Finally, for message routing along a directed path (which is already
$\mathcal{NP}$
-hard), we identify a natural class of instances for which a simple scheduling heuristic yields provably optimal solutions.