Optimal Rate–Delay Tradeoffs and Delay Mitigating Codes for Multipath Routed and Network Coded Networks

Abstract

Via multiterminal information theory, a framework is presented for deriving fundamental rate–delay tradeoffs that delay mitigating codes must have when utilized over multipath routed and random linear network coded networks. The rate–delay tradeoff is formulated as a calculus problem on a capacity region of a related abstracted broadcast channel. Given this general framework for studying such rate–delay tradeoffs, the extreme case of uniform networks, in which each possible received packet arrival order is equally likely, is considered. For these networks, the rate–delay calculus problem is simplified to an integer programming problem, which for small numbers of packets may be solved explicitly, or for larger numbers of packets, may be accurately approximated through the calculus of variations by appropriate relaxation of an integer constraint. Explicit expressions for the rate–delay tradeoff in uniform networks are presented in the special cases of i) constant packet inter-arrival times, and ii) exponential independent and identically distributed (i.i.d.) packet arrival times. Finally, the delay mitigating codes achieving these rate–delay tradeoffs are discussed.