direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 06-2009

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Real-Time Message Routing and Scheduling
not available
Iterative Rounding, Job Shop Scheduling, Approximation Algorithms
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.
Download as [PDF]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe