Stability and Performance of Containment Resolution Protocols

Abstract

Abstract : The stability of contention resolution protocols for a multiple-access channel is investigated. We start by outlining the different definitions used for the stablity of such protocols. Then we present sufficient conditions for the positive recurrence of countable state-space Markov chains using a potential function defined on their state space. By adding a new condition to the usual negative drift requirement, we show a stronger form of stability which ensures that the expected value of the potential is bounded in the steady state. These conditions are then used to prove stability for various contention resolution protocols in the time-slotted, Bernoulli arrivals, finite model. We study several acknowledgement-based protocols under this model because of their practicality and the minimal assumptions required by this class of protocols. Let n be the number of users in the system, and suppose that each user has a mean arrival rate A₁, and the total system arrival rate is 1 = Σιλί We start by examining the c-ary exponential backoff protocol which works as follows. For any constant c > 1, user i with a message that encountered bi collisions so far transmits with probability c. This class includes binary exponential backoff (a variant of the Ethernet protocol), and we show that for symmetric arrivals and sufficiently large n, c-ary exponential backoff is positive recurrent for any 0. Furthermore, we prove for c ≥ 2 that the protocol is unstable (i.e., not positive recurrent) for any λ > λο + 1/(4η – 2), where do is the solution to the equation o = e. For the special case when n = 2 and c = 2, we present new conditions on the arrival rates which are sufficient for instability. Next, the stability of age-based protocols (also acknowledgement-based) is studied. In age-based protocols, a message waiting at the head of the queue for t steps is transmitted with probability pt. We show that the age-based protocol where pt = 4/(t + 4) is strongly stable (in the sense that there exists a stationary distribution and the expected load of the system is finite) for symmetric arrivals and any arrival rate x = 1/(an³/4). We also show that any age-based protocol sending with probability p₁ = t for some 0