TY - GEN
T1 - Real-time message routing and scheduling
AU - Koch, Ronald
AU - Peis, Britta
AU - Skutella, Martin
AU - Wiese, Andreas
N1 - Funding Information:
This work was partially supported by Berlin Mathematical School, by DFG research center Matheon and by the DFG Focus Program 1307 within the project “Algorithm Engineering for Real-time Scheduling and Routing”.
PY - 2009
Y1 - 2009
N2 - 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 NP-hard), we identify a natural class of instances for which a simple scheduling heuristic yields provably optimal solutions.
AB - 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 NP-hard), we identify a natural class of instances for which a simple scheduling heuristic yields provably optimal solutions.
UR - http://www.scopus.com/inward/record.url?scp=70350603049&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-03685-9_17
DO - 10.1007/978-3-642-03685-9_17
M3 - Conference contribution
AN - SCOPUS:70350603049
SN - 3642036848
SN - 9783642036842
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 217
EP - 230
BT - Approximation, Randomization, and Combinatorial Optimization
T2 - 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009
Y2 - 21 August 2009 through 23 August 2009
ER -