A real-time stream is said to have (m, k)-firm deadlines if at least m out of any k-consecutive customers from the stream must meet their respective deadlines. Such a stream is said to have encountered a dynamic failure if fewer than m out of any k consecutive customers meet their deadlines. Hamdaoui and Ramanathan recently proposed a scheduling policy called Distance Based Priority (DBP) in which customers are serviced with a higher priority if their streams are closer to a dynamic failure. In terms of reducing the probability of dynamic failure, Hamdaoui and Ramanathan also showed, using simulation, that the DBP policy is better than a policy in which all customers are serviced at the same priority level. In this paper, an analytic model is developed for computing the probability of dynamic failure of a real-time stream for the DBP and the single priority schemes. This model is useful for providing statistical quality of service guarantees to real-time streams. The probability of dynamic failure computed using this model is compared to the results from a discrete-event simulator. The comparison shows that the model is accurate for low and moderate loads.

The fiber distributed data interface (FDDI) is suitable for real-time communication because of the high speed and the performance guarantees it provides. However, these guarantees are achieved at the expense of non-real-time traffic because the real-time messages are given higher priority over non-real-time messages,resulting in excessive delays for non-real-time messages. In this paper, we propose a scheme for reducing the response time of non-real-time messages while still providing the same guarantees to real-time messages. In particular, the proposed approach gives higher priority to real-time messages only when it is absolutely necessary in order for them to meet their deadlines. Non-real-time messages are thus transmitted ahead of real-time messages whenever possible. We present an algorithm for determining when and by how much the transmission of a real-time message can be deferred without jeopardizing its deadline. The proposed approach is evaluated through simulation. The simulation results show that a substantial reduction in the mean response time of non-real-time messages is achieved when using the proposed approach.

The problem of scheduling multiple streams of real-time customers, is addressed in this paper. The paper first introduces the notion of (m, k)-firm deadlines to better characterize the timing constraints of real-time streams. More specifically, a stream is said to have (m, k)-firm deadlines if at least m out of any k consecutive customers must meet their deadlines. A stream with (m, k)-firm deadlines experiences a dynamic failure if fewer than m out of any k consecutive customers meet their deadlines. The paper then proposes a priority-based policy for scheduling N such streams on a single server to reduce the probability of dynamic failure. The basic idea is to assign higher priorities to customers from streams that are closer to a dynamic failure so as to improve their chances of meeting their deadlines. The paper proposes a heuristic for assigning these priorities. The effectiveness of this approach is evaluated through simulation under various customer arrival and service patterns. The scheme is compared to a conventional scheme where all customers are serviced at the same priority level and to an imprecise computation model approach. The evaluation shows that substantial reductions in the probability of dynamic failure are achieved when the proposed policy is used.

Networks that use the timed token protocol (such as the 100 Mbit/s FDDI network) are well suited for real-time applications because they guarantee, to each node, an average bandwidth and a bounded access time to the communication network. This guarantee is necessary but not sufficient for the timely delivery of deadline-constrained messages; protocol parameters must be carefully selected to ensure that these messages meet their deadlines. This paper addresses the issue of selecting the protocol parameters TTRT (target token rotation time) and the synchronous capacities assigned to each node. The objective is to guarantee that each synchronous message is transmitted before its deadline. An upper bound is derived on the worst case achievable utilization (WCAU) of any parameter selection scheme. The WCAU of a scheme is defined as the maximum utilization U such that the scheme guarantees all synchronous messages as long as their utilization is less than U. An algorithm for selecting the above parameters is proposed, The algorithm is shown to have a WCAU that is very close to the upper bound.>

The fiber distributed data interface (FDDI) is suitable for real-time communication. A scheme for reducing the response time of non-real-time messages while still providing the same quality of service to real-time messages is proposed. In the proposed approach, non-real-time messages are transmitted ahead of real-time messages unless it is absolutely necessary to transmit real-time messages first in order to meet their deadlines. Simulation results show that a substantial reduction in the mean response time of non-real-time messages is achieved when using the proposed approach.