Stability of Interacting Queues in Random-Access Systems
Wei Qiang Luo, Anthony Ephremides · 1999
We revisit the problem of systems consisting of buffered terminals accessing a common receiver over the collision channel by means of the standard ALOHA protocol. We find that in the slotted ALOHA system queues have insta- bility based on their individual average arrival rates and transmission probabilities. If a queue is stable, then the queue with lower instability is stable as well. The instability is used to intelligently set up the dominant systems. And the inner and outer bounds can be found by bounding the idle probability of some queues in the dominant system. Through analyzing those dominant systems one by one, we are able to obtain inner and outer bounds for stability. These bounds are tighter than the known ones although they still fail to identify the exact region for cases of . The methodology used is new and holds promise for successfully addressing other similar problems. have stability ranks. By using this property, we intelligently set up the dominant system and obtain the improved bounds. The system we consider is a discrete-time slotted ALOHA system with terminals. Each terminal has a buffer of infinite capacity to store the incoming packets. Time is slotted. Transmission time of a packet is one slot. The packet arrival process at each terminal is Bernoulli, 1 and arrival processes at different terminals are independent. In each slot, the terminal attempts to transmit the packet with probability , if its buffer is not empty. If two or more terminals transmit in the same slot, a collision occurs. The packets involved in the collision wait to be retransmitted in the next slot with the same respective probabilities. In Section II, we briefly set up the problem and describe the mathematical foundations which our later discus- sions are based on. In Section III, we investigate the problem. We use the concept of dominance to derive a lower bound in Section III-A. In Section III-B, we identify the relative rank of of the individual queues, and we obtain an upper bound. In Section III-C, we proceed to obtain the inner and outer regions by using the ranking technique, and we obtain an improved lower bound. Finally, in Section III-D, numerical results show the improvement of our bound over the previously obtained ones.