Network control by Bayesian broadcast

• Published in: IEEE transactions on information theory 1987-05, Vol.33 (3), p.323-328
• Main Author: Rivest, R.
• Format: Article
• Language: English
• Subjects: Applied sciences; Exact sciences and technology; Telecommunications; Telecommunications and information theory; Teleprocessing networks. Isdn
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.1987.1057315

A transmission control strategy is described for slotted-ALOHA-type broadcast channels with ternary feedback. At each time slot, each station estimates the probability that n stations are ready to transmit a packet for each n , using Bayes' rule and the observed history of collisions, successful transmissions, and holes (empty slots). A station transmits a packet in a probabilistic manner based on these estimates. This strategy is called Bayesian broadcast. An elegant and very practical strategy--pseudo-Bayesian broadcast--is then derived by approximating the probability estimates with a Poisson distribution with mean \nu and further simplifying. Each station keeps a copy of \nu , transmits a packet with probability 1/\nu , and then updates \nu in two steps: For collisions, increment \nu by (e-2)^{-l}=1.39221 \cdots . For successes and holes, decrement \nu by 1 . Set \nu to \max (\nu + \hat{\lambda}, 1) , where \hat{\lambda} is an estimate of the arrival rate \lambda of new packets into the system. Simulation results are presented showing that pseudo-Bayesian broadcast performs well in practice, and methods that can be used to prove that certain versions of pseudo-Bayesian broadcast are stable for \lambda < e^{-1} are discussed.