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.
