Novel High-Performance Broadcast Algorithms for Crowded Multiple Access Channels
By Bader Aldawsari

Friday, April 16, 2021
2:00 pm MT

Doctoral Thesis Committee:
Dr. Haadi Jafarian, Advisor
Dr. Ellen Gethner, Committee Chair
Dr. Ashis Kumer Biswas, Committee Member
Dr. Liang He, Committee Member
Dr. Ersin Dincelli, Committee Member

ABSTRACT

Networks have become a vital part of the modern world, allowing for seamless communication between computing devices and serving as the building blocks of the Internet. Today's networks are either wired Local area networks (LAN) and Wireless LANs (WLAN). These networks are primary examples of multiple access channel (MAC) networks where stations communicate through broadcasting on a shared channel. A broadcast algorithm, called Binary Exponential Backoff (BEB), is used for these networks to allow stations to communicate on the shared channel without collisions. However, the BEB suffers from performance bottlenecks that hinder communication performance, especially as networks' sizes increase. In such highly congested networks, the communication becomes unstable, and messages experience significantly high delays due to frequent collisions. Furthermore, their performances are severely affected by adversarial jamming attacks where communication is disrupted via transmitted radio signals.

In this research, we propose several new broadcasting algorithms to improve MAC networks' performance. We first design a new randomized adversary with individual injection rates that simulate a network traffic behavior exhibited by real-world networks. The new adversarial model complements existing models and is used to evaluate broadcast algorithms' performance under a network traffic behavior that is different from the worst-case adversary.

Then, we introduce three novel broadcast algorithms: k-tuple, k-tuple withholding, and k-tuple full withholding (KTFW). Through experimentation and theoretical analysis, we demonstrate that the k-tuple and k-tuple withholding have the highest performance in their class of broadcast algorithms. Further, we show that the KTFW, a higher-performing broadcast algorithm, is scalable and more resilient to jamming attacks than both the BEB and other alternative algorithms introduced in the literature.

            Moreover, we propose the polynomial backoff (PB) function that offers higher performance than the BEB algorithm. Simulation and theoretical analysis results show the PB algorithm achieves higher throughput than the BEB algorithm under jamming attacks, while maintaining significantly lower average packet latency for both jamming and non-jamming scenarios. The newly proposed broadcast algorithms enhance MAC networks' communication performance and increase their resilience and robustness in addressing the emerging needs of networks for accommodating more stations and maintaining operation in the face of adversarial jamming attacks.