A hard real-time system is usually subject to stringent reliability and timing constraints. One way to avoid missing deadlines is to trade the quality of computation results for timeliness, and software fault tolerance is often achieved with the use of redundant programs. A deadline mechanism which combines these two methods is proposed to provide software fault tolerance in hard real-time periodic task systems. We consider the problem of scheduling a set of real-time periodic tasks each of which has two versions: primary and alternate. The primary version contains more functions and produces good quality results, but its correctness is more difficult to verify. The alternate version contains only the minimum required functions and produces less precise results and its correctness is easy to verify. We propose a scheduling algorithm which 1) guarantees either the primary or alternate version of each critical task to be completed in time and 2) attempts to complete as many primaries as possible. Our basic algorithm uses a fixed priority-driven preemptive scheduling scheme to preallocate time intervals to the alternates and, at runtime, attempts to execute primaries first. An alternate will be executed only if necessary because of time or bugs.

One of the key issues in tailoring the timed-token MAC protocol for real-time applications is synchronous bandwidth allocation (SBA), whose objective is to meet both the protocol and deadline constraints. The former constraint requires that the total time allocated to all nodes for transmitting synchronous messages should not exceed the target token rotation time. The latter constraint requires that the minimum time available for a node to transmit its synchronous messages before their deadlines should be no less than the maximum message transmission time. Several nonoptimal local SEA schemes and an optimal global SBA scheme have been proposed. Local SBA schemes use only information available locally to each node and are thus preferred to global schemes because of their lower network-management overhead. If optimal local SBA schemes, if any, can be devised, they will be superior to their global counterparts both in performance and in ease of network management. In this paper, we formally prove that there does not exist any optimal local SBA scheme. We also propose an optimal global SBA scheme which has an O(nM) polynomial-time worst-case complexity, where n is the number of synchronous message streams in the system and M is the time complexity for solving a linear programming problem with 3n constraints and n variables.

In this paper, we devise a preallocation-based single-hop wavelength division multiple access (WDMA) scheme to support temporal quality of service (QoS) in star-coupled optical networks, We consider a star-coupled broadcast-and-select network architecture in which N stations are connected to a star coupler with W different wavelength channels. Each of the W wavelength channels is slotted and shared by the !V stations by means of time division multiplexing. Depending on the tunability characteristics (tunable or fixed tuned) of the transmitters/receivers, we classify the network architecture as tunable transmitter/fixed tuned receiver (TT-FR), fixed tuned transmitter/tunable receiver (FT-TR), and tunable transmitter/tunable receiver (TT-TR). We first characterize each real-time message stream M/sub i/, with two parameters, the relative message deadline D/sub i/ and the maximum (total) message size C/sub i/ that can arrive within any time interval of length D/sub i/. We then discuss a restricted case in a TT-FR (or FT-TR) system in which the message streams from a source station are assumed to be all destined for the same destination station. Under this assumption, no source destination conflicts may occur. We propose a preallocation-based slot assignment scheme to preallocate slots to a set of isochronous message streams, (M/sub i/=(C/sub i/, D/sub i/)|1/spl les/i/spl les/n) in such a way that, in any time window of size D/sub i/ slots, at least C/sub i/ slots on a wavelength channel are allocated to M/sub i/ for all i. With the solution derived in the restricted case as a basis, we then consider slot assignment in a (general) TT-TR system and propose a binary splitting scheme to assign each message stream sufficient and well-spaced slots to fulfil its temporal requirement, subject to the source/destination conflict constraints. We rigorously prove the invariance properties, and the correctness, of the binary splitting scheme.

Several medium access control (MAC) schemes have been developed for dual-bus networks such as DQDB, Fasnet, CRMA, and Simple. However, how to guarantee the timely delivery of isochronous (real-time) messages with hard deadline constraints is one of the open issues yet to be solved. In Han, Hou and Shin (1997), we laid a formal basis for allocating prearbitrated slots to isochronous message streams in dual-bus networks and devised a slot allocation scheme to statically establish a set of isochronous message streams at system initialization. In this paper, we complement our work in Han, Hou and Shin (1997) and propose, with the necessary theoretical base established, a dynamic message stream setup and tear-down scheme for dual-bus networks. The resulting channel establishment and termination procedures are simple and can be easily implemented in dual-bus networks.

For multicomputer or distributed systems that use circuit switching, wormhole routing, or virtual cut-through (the last two are collectively called the cut-through switching), the communication overhead and the message delivery time depend largely upon link contention rather than upon the distance between the source and the destination. That is, a larger communication overhead or a longer delivery delay occurs to a message when it traverses a route with heavier traffic than the one with a longer distance and lesser traffic. This characteristic greatly affects the selection of routes for interprocessor communication and/or load balancing. We consider the load-balancing problem in these types of systems. Our objective is to find the maximum load imbalance that can be eliminated without violating the (traffic) capacity constraint and the route to eliminate the imbalance while keeping the maximum link traffic as low as possible. We investigate the load-balancing problem under various conditions. First, we consider the case in which the excess load on each overloaded node is divisible. We devise a network flow algorithm to solve this type of load balancing problem optimally in polynomial time. Next, we impose the realistic assumption that the system uses a specific routing scheme so that the excess load transferred from an overloaded node to an underloaded node must use the route found by the routing scheme. For this case, we use a graph transformation technique to transform the system graph to another graph to which the same network flow algorithm can be applied to solve the load balancing problem optimally. Finally, we consider the case in which the excess load on each overloaded node is indivisible, i.e., the excess load must be transferred as an entity. We show that the load-balancing problem of this type becomes NP-complete and propose a heuristic algorithm as a solution.

We propose a novel MAC protocol, called quality-of-service guarantee multiple access (QGMA), in wireless local area networks to support the quality-of-service required by embedded real-time applications and multimedia-integrated distributed control. As compared to other existing MAC protocols, QGMA achieves high system utilization, and provides a deterministic bound on the connection establishment delay and temporal QoS for real-time applications. In particular by having the base station handle resource arbitration and utilize different scheduling algorithms to arbitrate access to data slots on a wireless channel, mobile hosts (MHs) are relieved from the burden of coordinating all the ongoing activities, and moreover different levels of temporal QoS can be easily achieved.

There has been an increasing need of highly predictable, timely, and dependable communication services with QoS guarantees on an end-to-end basis either for embedded real-time applications or for multimedia-integrated distributed control. Performance objectives used in conventional networks-such as maximizing the throughput, minimizing the response time, or providing fairness to users-are not of the most important concern for both types of applications. Instead, resources should be appropriately reserved and managed to support multidimensional quality of service (QoS) on an end-to-end basis, as well as application-specific tradeoffs among them. The main intent of the paper is thus to address and demonstrate an environment-an integrated set of network resource management techniques, middleware layers, and network software-for supporting multi-dimensional QoS on an end-to-end basis in distributed real-time environments. The authors first provide an analytic QoS framework Then, they elaborate on the algorithms and mechanisms to provide such network services. To empirically analyze the behavior of the proposed components, they are currently implementing them as software layers on top of the Sun Solaris operating system, and comment on the implementation status.

To complement the prior work of Kung-Ying Tyan, Chao-Ju Hou, Bin Wang and Ching-Chih Han (see Proc. IEEE 17th Real-Time Systems Symposium, Washington DC, 1996), we address the problem of dynamically establishing/terminating real-time message streams in response to call setup/clear requests in single-hop star-coupled WDMA-based optical networks. We consider a network architecture in which N stations are connected to a star coupler with W data channels (W/spl les/N) and one control channel. Each of the W data channels is slotted and shared by the N stations by means of time division multiplexing. The control channel is used for stations to coordinate the call establishment and termination operations. We propose a distributed, dynamic slot allocation scheme to allocate/deallocate, in response to call setup/clear requests, time slots on the W data channels to message streams, with the objective of meeting message deadlines. We formally prove the properties, and the correctness of, the proposed dynamic slot allocation scheme.

The problem of scheduling real-time periodic task has been studied extensively since its first introduction by C.L. Liu and J.W. Layland in their classic paper (1973). Due to several merits of the fixed-priority scheduling scheme, a lot of research work has focused on the analysis of fixed-priority scheduling algorithms. For the case that the deadlines of the executions of all the tasks coincide with the ends of their corresponding periods. Liu and Layland derived a worst-case utilization bound for a task set to be schedulable by the rate-monotonic (RM) algorithm. A. Burchard et al. (1995) presented another schedulability condition for RM, which has a higher utilization bound under a certain task condition. Although their closed-form utilization bounds provide a convenient way for testing the schedulability of a task set under the RM algorithm, the schedulability test using their bounds is too pessimistic since a lot of task sets with total utilizations larger than their bounds (and less than or equal to 1) are still schedulable by RM. In this paper, we propose a polynomial-time schedulability test and prove that it is better than Liu and Layland's and Burchard's utilization bounds in the sense that as long as the total utilization of a task set is less than or equal to their bounds, our schedulability test will always answer positively for the schedulability of the task set under RM and even if a feasible task set has a total utilization larger than their bounds, our schedulability test will still answer positively with a high probability. We also show how to generalize our polynomial-time schedulability test to handle general task sets scheduled by arbitrary fixed-priority scheduling algorithms.

Several access schemes have been suggested for dual-bus network topology, e.g., DQDB, Fasnet, CRMA, and Simple. It is therefore important to provide various services in this type of networks. This paper addresses the issue of guaranteeing the timely delivery of isochronous (real-time) messages with hard deadlines in slotted dual-bus networks. We propose a slot allocation scheme which can allocate bandwidth for a set of isochronous message streams and provide deterministic deadline guarantees. The proposed slot allocation scheme is guaranteed to find a feasible slot allocation in the sense that all messages can be transmitted in a timely manner as long as the total message density is less than or equal to a certain threshold, where the total message density is defined as the summation of the ratio of maximum message size to message deadline over all streams. We also discuss the implementation details of this scheme, and compare our scheme with another bandwidth allocation scheme proposed by D. Saha et al. (1994).

Based on the POPSMAC protocol proposed in Chung-Sheng Li et al. (1993), we propose an improved medium access protocol for wavelength division multiple access (WDMA) photonic networks. Using the same set of photonic devices as in POPSMAC, the proposed protocol alleviates the drawbacks of the POPSMAC protocol, e.g., invalid data transmissions following receiver collisions and possible acknowledgement packet collisions with header/data packets, while retaining many advantages of POPSMAC. As a result, the network performance in terms of the throughput and the packet delay is improved. Analytical models based on the timing diagram analysis, the continuous-time Markov chain, and the randomization technique are developed to assess the performance of the proposed protocol. The performance is evaluated in terms of channel utilization, mean packet delay, and packet delay distribution with variations in the number of nodes, the offered traffic, the size of data packets, and the network propagation delay. Numerical results show that the proposed protocol achieves better channel utilization and incurs lower packet delays than POPSMAC.

We consider the message transmission problem in unidirectional slotted ring networks. We consider two operation modes: 1) the evacuation mode, in which all messages arrive before system initialization and no new message arrives during system operation; and 2) the continuation mode, in which new messages may arrive after system initialization. We study the performance of several message scheduling policies with respect to three performance measures: meeting all message deadlines, minimizing the maximum delay or the total length of busy periods, and minimizing the average delay. We show that the least-slack-time-first (LSF) scheduling policy is optimal in evacuation mode operation with respect to meeting all message deadlines, while no optimal scheduling policy can possibly exist for continuation mode operation. For the other two performance measures, we show that in the case when messages may be of variable lengths: 1) the farthest-destination-first (FDF) policy is optimal in terms of minimizing the maximum delay and minimizing the total length of busy periods for evacuation mode and for continuation mode operation, respectively, and 2) no optimal scheduling policy can possibly exist in terms of minimizing the average delay under either evacuation mode or continuation mode operation.

We devise a preallocation based single hop wavelength division multiple access (WDMA) scheme to support time constrained communication in star coupled optical networks. We consider a star coupled broadcast and select network architecture in which N stations are connected to a star coupler with W different wavelength channels. Each of the W wavelength channels is slotted and shared by the N stations by means of time division multiplexing. Networks with different transceiver configurations, i.e., TT-FR, FT-TR, and TT-TR systems, are investigated. We characterize each real time message stream M, with two parameters, relative message deadline D/sub i/ and maximum (total) message size C/sub i/ that can arrive within any time interval of length D/sub i/. We then discuss a restricted case in a TT-FR system in which the message streams from a source station are assumed to be all going to the same destination station. Under this assumption, no source/destination conflicts may occur. We propose a preallocation based slot assignment scheme to allocate slots to a set of isochronous message streams, {M/sub i/=(C/sub i/, D/sub i/))|1/spl les/i/spl les/n}, so that in any time window of size D/sub i/ slots, at least C/sub i/ slots on a wavelength channel are allocated to M/sub i/ for all i. With the solution derived in the restricted case as a basis, we then consider slot assignment in a (general) TT-TR system, and propose a binary splitting scheme to assign each message stream sufficient and well spaced slots to fulfill its timing requirement, subject to source/destination conflict constraints. We rigorously prove the invariant properties and the correctness of the binary splitting scheme.

In hard real time systems, each task must not only be functionally correct but also meet its timing constraints. A common approach to characterizing hard real time tasks with repetitive requests is the periodic task model. In the periodic task model, every task needs to be executed once during each of its periods. The execution of a task in one period is independent of the execution of the same task in another period. Hence, the executions of the same task in two consecutive periods may be right next to each other, or at the far ends of the two periods. While the periodic task model can serve as a simple paradigm for scheduling tasks with repetitive requests, it may not be suitable for all real time applications. For example, in some real time systems, the temporal distance between the finishing times of any two consecutive executions of the same task must be less than or equal to a given value. In other words, each execution of a task has a deadline relative to the finishing time of the previous execution of the same task. Scheduling algorithms designed for the periodic task model may not provide efficient solutions for tasks with temporal distance constraints. We propose the (preemptive) distance constrained task system model which can serve as a more intuitive and adequate scheduling model for "repetitive" task executions. We design an efficient scheduling scheme for the model, and derive a schedulability condition for the scheduling scheme. We also discuss how to apply the scheduling scheme to real time sporadic task scheduling and to real time communications.

In 1993, the authors described the design of the AN2 switch which supports high-performance distributed computing. The switch's operation is based on the parallel iterative matching algorithm to find a maximal matching between the inputs and the outputs of the switch. The number of iterations needed to find a maximal matching in their algorithm is N in the worst case, and of time complexity O(log N) in the average case, where N is the size of the switch. We propose an improved parallel iterative matching algorithm which uses the priority lists, instead of randomness, to determine the input/output pairs that can be matched in each iteration. We show that tire proposed algorithm does not suffer from the starvation problem, and needs at most [N/2] iterations to find a maximal matching. We also show via probability analysis and simulation that the proposed algorithm outperforms the original one in the average case, especially when the switch size is large, e.g., for N/spl ges/32. All these merits make it attractive to apply the algorithm to large switches used in ATM networks with high QoS requirements.

No abstract available.

DQDB is a MAC protocol jointly adopted by IEEE and ANSI as the candidate protocol for MANs, and has been studied by many researchers. Previously, we laid a formal basis for guaranteeing the timely delivery of isochronous (real-time) messages with hard deadlines, and devised a slot allocation scheme for allocating pre-arbitrated (PA) slots to isochronous message streams in DQDB networks. In this paper, we extend our work and address on how to improve the performance (in terms of bandwidth utilization) of the slot allocation scheme using the concept of slot reuse. We devise several slot reuse schemes to assign spatially non-intersecting message streams to the same virtual connections (i.e., the sets of PA slots identified by the same VCI numbers). The proposed slot reuse schemes are simple, can be easily incorporated into the slot allocation scheme described previously, and require only a minor change in the current DQDB standards.

The job scheduling problems for real-time jobs with temporal distance constraints (JSD) are presented. In JSD, the start times of two related jobs must be within a given distance. The general JSD problem is NP-hard. We define the multilevel unit-time JSD (MUJSD) problem for systems with m chains of unit-time jobs in which neighboring jobs in each chain must be scheduled within c time units. We present an $O(n^{2})$-time algorithm, where n is the total number of jobs in the system, and also an $O(m^{2}c^{2})$-time algorithm. Some other variations of the JSD problems are also investigated.

A novel model of real-time task systems with temporal distance constraints is presented. In such systems, the distance between any two consecutive finishing times of the same task must be less than or equal to a given value. Using the periodic task model for such tasks may not provide an efficient solution. The authors discuss the scheduling approaches for this distance-constrained task model and propose several scheduling algorithms. They also study the schedulability conditions for these algorithms.>

The effect of parallel execution on the complexity of scheduling hard real time jobs on multiprocessors is analyzed. Studied is the scheduling problem in which a job may be parallelized and executed on any number of processors concurrently. In hard real-time systems, each job must be completed before a deadline. Parallelization gives a scheduler the flexibility to allocate more processors to a job whose deadline is near. Unfortunately, with this flexibility some of the multiprocessor scheduling problems are very difficult. The NP-hardness of scheduling parallelizable jobs where each job has a fixed priority is proved. A heuristic algorithm is proposed for finding an approximate job partition on two processors. Simulation results show that the heuristic algorithm usually has a very good performance.>