Estimating the multiplicities of conflicts in multiple access channels
- 1 November 1983
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 383-392
- https://doi.org/10.1109/sfcs.1983.14
Abstract
A conflict of multiplicity k occurs when k stations transmit simultaneously to a multiple access channel. As a result, all stations receive feedback indicating whether k is 0, 1, or is ≥ 2. If k = 1 the transmission succeeds, whereas if k ≥ 2 all the transmissions fail. In general, no a priori information about k is available. We present and analyze an algorithm that enables the conflicting stations to cooperatively compute a statistical estimate of k, at small cost, as a function of the feedback elicited during its execution. An algorithm to resolve a conflict among two or more stations controls the retransmissions of the conflicting stations so that each eventually transmits singly to the channel. Combining our estimation algorithm with a binary tree algorithm leads to a hybrid algorithm that resolves conflicts faster on average than any other reported to date.Keywords
This publication has 5 references indexed in Scilit:
- On the time complexity of broadcast communication schemes (Preliminary Version)Published by Association for Computing Machinery (ACM) ,1982
- Tree algorithms for packet broadcast channelsIEEE Transactions on Information Theory, 1979
- An Adaptive Technique for Local DistributionIEEE Transactions on Communications, 1978
- EthernetCommunications of the ACM, 1976
- Packet Switching in a Multiaccess Broadcast Channel: Performance EvaluationIEEE Transactions on Communications, 1975