TY - JOUR

T1 - On-line routing of real-time messages

AU - Leung, Joseph Y.T.

AU - Tam, Tommy W.

AU - Young, Gilbert H.

N1 - Funding Information:
1Research supported in part by ONR Grant N00014-87-K-0833 and in part by a grant from Texas Instruments, Inc.
Funding Information:
2Research supported by CUHK Grant 220500610. Gilbert Young is with Department of Computer Science & Engineering, the Chinese University of Hong Kong, Shatin, Hong Kong.

PY - 1996/5/1

Y1 - 1996/5/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0030140616&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030140616&partnerID=8YFLogxK

U2 - 10.1006/jpdc.1996.0057

DO - 10.1006/jpdc.1996.0057

M3 - Article

AN - SCOPUS:0030140616

SN - 0743-7315

VL - 34

SP - 211

EP - 217

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

IS - 2

ER -