×

Real-time message routing and scheduling. (English) Zbl 1255.68047

Dinur, Irit (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 12th international workshop, APPROX 2009, and 13th international workshop, RANDOM 2009, Berkeley, CA, USA, August 21–23, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03684-2/pbk). Lecture Notes in Computer Science 5687, 217-230 (2009).
Summary: 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.
For the entire collection see [Zbl 1173.68008].

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI Link