Optimal Rate Delay Tradeoffs for Multipath Routed and Network Coded Networks

Abstract

Via multiterminal information theory, we present fundamental rate delay tradeoffs that delay mitigating codes must have when utilized over multipath routed and network coded networks. We formulate plotting the rate delay tradeoff as a calculus problem on a capacity region of a related abstracted broadcast channel. This calculus problem simplifies to an integer programming problem, which for small numbers of packets may be solved explicitly, or for larger values of packets, may be accurately approximated through the calculus of variations by relaxing the integer constraint. We prove the utility of our techniques by plotting the rate delay tradeoff for networks in which the packets experience independent exponentially distributed propagation and queuing delays while traversing the network.