Throughput of Q-Ary Splitting Algorithms for Contention Resolution in Communication Networks
Houdt, B. ; Blondia, C.
Commun. Inf. Syst., Tome 4 (2004) no. 1, p. 135-164 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
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 > 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.
Publié le : 2004-05-14
Classification:  
@article{1119640070,
     author = {Houdt, B. and Blondia, C.},
     title = {Throughput of Q-Ary Splitting Algorithms for Contention Resolution
in Communication Networks},
     journal = {Commun. Inf. Syst.},
     volume = {4},
     number = {1},
     year = {2004},
     pages = { 135-164},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1119640070}
}

Houdt, B.; Blondia, C. Throughput of Q-Ary Splitting Algorithms for Contention Resolution
in Communication Networks. Commun. Inf. Syst., Tome 4 (2004) no. 1, pp.  135-164. http://gdmltest.u-ga.fr/item/1119640070/