Non-FCFS Algorithms for Multiple Access

We consider the classic problem of finding the maximum achievable throughput of an ideal multi-access communication channel. We revisit the state-of-the-art first-come-first-served (FCFS) algorithm proposed by Moseley and Humblet. We also study the first non-FCFS algorithm proposed by Vvedenskaya and Pinsker. We obtain the value iteration equations for the Markov decision process describing the Vvedenskaya-Pinsker algorithm. We obtain an improvement of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{O}(10^{-7})$</tex> packets/slot over the Moseley-Humblet throughput with exploratory search disabled, validating the theoretical calculations of Vvedenskaya and Pinsker. We then quantify the further improvement obtainable using non-FCFS scheduling, as suggested by them.