direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints

Real-Time Message Routing and Scheduling
Zitatschlüssel Report-006-2009
Autor Ronald Koch and Britta Peis and Martin Skutella and Andreas Wiese
Jahr 2009
Nummer 006
Monat feb
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag