Message routing in distributed real-time systems
Wingcheung Tam, Joseph Y.‐T. Leung · 1990
Real-time systems have been rapidly developing recently. Timing constraints are the crucial concern in real-time systems. Scheduling theory is one of the important areas of study in real-time systems. In a distributed system, processes residing at different nodes in the network communicate by message passing. For a distributed real-time system, the problem of deciding whether a set of messages can be sent on-time becomes an important issue. In this dissertation we study the following three problems. The problem of determining whether a set of real-time messages can be routed in a network is considered. Each message has five parameters associated with it--origin node, destination node, length, release time and deadline. The complexity of the problem is considered under various restrictions of the four parameters: origin node, destination node, release time and deadline. We show that if the network is arbitrary, the problem is NP-complete even when all four parameters are fixed. Motivated by the complexity of the problem, we consider a simple network--an unidirectional ring. For nonpreemptive transmission, we show that the problem is solvable in polynomial time when any one of the four parameters is allowed to be arbitrary, and that it becomes NP-complete when any two of them are fixed. The same kind of complexity results hold for preemptive transmission, except two cases. The existence of an optimal on-line algorithm is also considered. We show that no such algorithm can exist unless all of the remaining three parameters are fixed. The problem of routing unit-length real-time messages in a distributed system is considered. An on-line routing algorithm is a distributed algorithm that routes messages without any knowledge of future arrivals of messages. An on-line algorithm is optimal if it produces a feasible routing whenever one exists. We study the existence of an optimal on-line algorithm for the following networks--unidirectional ring, out-tree, in-tree, bidirectional tree and bidirectional ring. The results are given in Chapter 3 of this dissertation. Finally, the problem of determining whether a set of squares can be orthogonally packed into a larger square is considered. We show that the problem is strongly NP-complete.