On-Line Routing of Real-Time Messages

✍ Scribed by Joseph Y-T. Leung; Tommy W. Tam; Gilbert H. Young

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 231 KB
• Volume: 34
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1996.0057

✦ Synopsis

The problem of routing unit-length, real-time messages in a distributed system is considered. An on-line routing algorithm is one that routes messages without any knowledge of future arrivals of messages. An on-line algorithm is said to be optimal if it produces a feasible route whenever one exists. In this article, we study the issue whether it is possible to have an optimal on-line algorithm for the following networks-unidirectional ring, out-tree, in-tree, bidirectional tree, and bidirectional ring. The problem is considered under various restrictions of the four parameters-origin node, destination node, release time, and deadline. We show that: (1) for a unidirectional ring, no such algorithm can exist unless one of the four parameters is fixed (i.e., all messages have identical values for that parameter); (2) for an out-tree, no such algorithm can exist unless one of the three parameters-origin node, destination node, and release time-is fixed; (3) For an in-tree, no such algorithm can exist unless one of the three parameters-origin node, destination node, and deadline -is fixed; (4) for a bidirectional tree, no such algorithm can exist unless the origin node or the destination node is fixed; (5) for a bidirectional ring, no such algorithm can exist unless the origin node and either the destination node or the release time are fixed. Our results give a sharp boundary delineating those instances for which an optimal algorithm exists and those for which no such algorithm can exist.