Analytic evaluation of contention protocols used in distributed real-time systems

Abstract

The probability of a station failing to deliver packets before their deadlines, called the probability of dynamic failure, P dyn , is an important measure for the communication subsystem of a distributed real-time system. Another closely-related performance measure is the ε- bounded delivery time , T ε , which is defined as the least time needed to deliver a packet with probability greater than 1−ε. Using P dyn and T ε , we comparatively evaluate four contention protocols often used in distributed real-time systems: (i) the token passing protocol and its priority-based variation (called the token scheduling protocol ), and (ii) the P i -persistent protocol and a priority-based variation thereof. The communication subsystem equipped with different contention protocols is modeled first as embedded Markov chains. Then, we derive the probability distributions of access delay, from which P dyn and T ε can be calculated. The blocking probability, Q i , can also be derived from the access delay distribution. These measures are derived first under the assumption of a single buffer at each station. The single-buffer model is then extended to the multiple-buffer case. The effects of buffer size on P dyn , T ε , and Q i , and the performance improvement with multiple buffers are analyzed over a wide range of network traffic.