Optimal Latency-Oriented Scheduling in Parallel Queuing Systems

Today, more and more interactive applications, such as augmented/virtual reality, haptic Internet, and Industrial Internet of Things, require communication services with guaranteed end-to-end latency limits, which are difficult to provide over shared communication networks, particularly in the presence of wireless links. Robustness against disturbances affecting individual links can be obtained by coding the information flow in multiple streams to be forwarded across parallel transmission links. This approach, however, requires coding and scheduling algorithms that can adapt to the state of links to take full advantage of path diversity and avoid self-induced congestion on some links. To gain some fundamental insights on this challenging problem, in this paper we resort to Markov Decision Process (MDP) theory and abstract the parallel paths as independent queuing systems, whose arrival processes are managed by a common controller that determines the amount of redundancy to be applied to the source messages and the number of (coded) packets to be sent to each queue. The objective is to find the joint coding and scheduling policy that maximizes a certain utility function, e.g., the fraction of source blocks delivered to the destination within a predetermined deadline, despite the variability of the individual connections. We find the optimal redundancy and scheduling strategies by using policy iteration methods. We then analyze the optimal policy in a series of scenarios, highlighting its most important aspects and analyzing ways to improve existing heuristics from the literature.