Throughput of Q-Ary Splitting Algorithms for Contention Resolution in Communication Networks

The throughput characteristics of contention-based random access channels which use Q-ary splitting algorithms (where Q is the number of groups into which colliding users are split) are analyzed. The algorithms considered are of the Capetanakis-Tsybakov- Mikhailov-Vvedenskaya (CTMV) type and are studied for infinite populations of identical users generating packets according to a discrete time batch Markovian arrival process (D-BMAP). D-BMAPs are a class of tractable Markovian arrival processes, which, in general, are non-renewal. Free channel-access is assumed in combination with Q-ary collision resolution algorithms that exploit either binary or ternary feedback. For the resulting schemes, tree structured Quasi-Birth-Death (QBD) Markov chains are constructed and their stability is determined. The maximum achievable throughput is determined for a variety of arrival processes and splitting factors Q. It is concluded that binary (Q=2) and ternary (Q=3) algorithms should be preferred above other splitting factors Q as the throughput for Q \gt 3 quickly degrades when subject to bursty arrival streams. If packets arrivals are correlated and bursty, higher throughput rates can be achieved by making use of biased coins.

Full Text (PDF format)

Published 1 January 2004