Title
On the maximum stable throughput of tree algorithms with free access On the maximum stable throughput of tree algorithms with free access
Author
Faculty/Department
Faculty of Sciences. Mathematics and Computer Science
Publication type
article
Publication
New York, N.Y. ,
Subject
Computer. Automation
Source (journal)
IEEE transactions on information theory / Institute of Electrical and Electronics Engineers [New York, N.Y.] - New York, N.Y.
Volume/pages
55(2009) :11 , p. 5087-5099
ISSN
0018-9448
ISI
000271019700022
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Affiliation
University of Antwerp
Abstract
A simple numerical procedure is presented to determine the maximum stable throughput (MST) of various tree algorithms with free access by defining an associated multitype branching process such that the criticality of the branching process corresponds to the stability of the tree algorithm. More precisely, a bisection algorithm is proposed that only requires the computation of the dominant eigenvalue of the expectation matrix of the branching process, the size of which is typically below 20, at each step. Using this novel approach, many existing results on free-access tree algorithms are reproduced without much effort (e.g., channels with/without noise, variable length packets, interference cancellation, etc.). Furthermore, in an almost plug-and-play manner, the MST of the free access equivalent of many existing results on tree algorithms with blocked access is established (e.g., channels with capture, control signals, multireception capabilities, etc.). The method can be applied to the class of independent and identically distributed (i.i.d.) arrival processes, which includes the Poisson process as a special case. Apart from determining the MST, the probability that a sizei collision is resolved in a finite amount of time when the arrival rate exceeds the MST can also be computed. Some limitations of the proposed methodology are discussed as well.
Full text (open access)
https://repository.uantwerpen.be/docman/irua/2b6930/4486.pdf
E-info
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000271019700022&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000271019700022&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000271019700022&DestLinkType=CitingArticles&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
Handle