Q-ary collision resolution algorithms in random-access systems with free or blocked channel access
P. Mathys, Philippe Flajolet · IEEE Transactions on Information Theory · 1985
The throughput characteristics of contention-based random-access systems (RAS's) which useQ-ary tree algorithms (whereQ \geq 2is the number of groups into which contending users are split) of the Capetanakis-Tsybakov-Mikhailov-Vvedenskaya type are analyzed for an infinite population of identical users generating packets according to a Poisson process. Both free and blocked channel-access protocols are considered in combination withQ-ary collision resolution algorithms that exploit either binary ("collision/no collision") or ternary ("collision/ success / idle") feedback. For the resulting RAS's, functional equations for transformed generating functions of the first two moments of the collision resolution interval length are obtained and solved. The maximum stable throughput as a function ofQis given. The results of a packet-delay analysis are also given, and the analyzed RAS's are compared among themselves and with the slotted ALOHA system in terms of both system throughput and packet delay. It is concluded that the "practical optimum" RAS (in terms of ease of implementation combined with good performance) uses free (i.e., immediate) channel access and ternary splitting (i.e.,Q = 3) with binary feedback.