The average CRI-length of a controlled ALOHA collision resolution algorithm

DOI10.1016/0304-3975(93)90195-YMaRDI QIDQ1208718zbMATH OpenFDO

Authors Ulrich Schmid

Publication date 16 May 1993

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(93)90195-Y

zbMATH Keywords

asymptotic analysisconflict resolution algorithmcontrolled \(S\)-ALOHACRI lengthMellin transform

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Communication networks in operations research (90B18) Communication theory (94A05)

Review text

The paper investigates some properties of a hybrid conflict resolution algorithm proposed for a network with a controlled ALOHA protocol. The algorithm adjusts the retransmission probability to the number of colliding stations. It consists of two steps, namely, the estimation of the number \(n\) of collisions and the collision resolution phase, being the ordinary S-ALOHA algorithm which the retransmission probability \(p=1/n\) and delayed transmissions of newly generated packets. The author estimates the number of collisions and gives the average conditional length of CRI for a given number \(n\) of colliding stations. Next, using the Mellin transform technique he proposes an asymptotic analysis of the average value of CRI. The author proves that the average CRI length is of order \(O(n\log n)\) as \(n\) tends to infinity. This result gives some insight to the instability of the described controlled ALOHA algorithm, namely, it shows that even controlling the retransmission probability is not sufficient to guarantee the stability of the considered protocol.

Recommendations

• On the asymptotics of the average CRI length of the slotted ALOHA collision resolution algorithm
• On a functional equation arising in the analysis of a protocol for a multi-access broadcast channel
• The average CRI-length of a tree collision resolution algorithm in presence of multiplicity-dependent capture effects
• An analysis of a contention resolution algorithm. Another approach
• An access algorithm for a communication channel

Cites work

• <tex>Q</tex>-ary collision resolution algorithms in random-access systems with free or blocked channel access
• A perspective on multiaccess channels
• Estimating the multiplicities of conflicts to speed their resolution in multiple access channels
• scientific article; zbMATH DE number 3814037 (Why is no real title available?)
• scientific article; zbMATH DE number 3932385 (Why is no real title available?)
• scientific article; zbMATH DE number 3176961 (Why is no real title available?)
• scientific article; zbMATH DE number 3111409 (Why is no real title available?)
• On the asymptotics of the average CRI length of the slotted ALOHA collision resolution algorithm

Cited in

(3)

• On the asymptotics of the average CRI length of the slotted ALOHA collision resolution algorithm
• ALOHA With Collision Resolution (ALOHA-CR): Theory and Software Defined Radio Implementation
• The average CRI-length of a tree collision resolution algorithm in presence of multiplicity-dependent capture effects

This page was built for publication: The average CRI-length of a controlled ALOHA collision resolution algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1208718)