Low latency group communication over broadcast erasure channels

Group communication allows a collection of transceivers to mutually share messages, from either a single or multiple sources to multiple sinks. This form of communication has numerous applications, including vehicular networking, content distribution and multimedia streaming. Reliability and low latency are highly desirable for these applications. This thesis addresses the problem of low latency group communication by developing lightweight distributed algorithms. Most previous work in this area focuses on wired point-to-point links. Motivated by the increased prevalence of wireless networks, this thesis focuses on broadcast channels. The first problem addressed in this thesis is broadcasting from a single source to large numbers of receivers. The channels to distinct receivers are assumed to be independent discrete memoryless erasure channels. Random Linear Network Coding (RLNC) is shown to achieve non-vanishing throughput, unachievable by ARQ, in exchange for delay scaling with the number of receivers n as O(log(n)). The tradeoff between its throughput and delay is quantified. The next problem considered is all-to-all (allcast) communication in which agents take it in turns to broadcast packets. Each broadcast is received correctly by only a subset of the agents, and is erased at the others. The network of correct receptions at each time-step is modelled by a random graph, and these graphs are correlated over time. Three algorithms to address this problem are proposed: one in which messages are randomly forwarded, and two RLNC algorithms in which random linear combinations of messages are broadcast. A rigorous mathematical analysis of these algorithms is presented for graphs which are constant over time. The RLNC algorithms are shown to complete in a constant number of time-steps, as opposed to O(log(n)) for the baseline, enabling better scalability to large networks. Finally the analysis is supplemented by simulations, which add