Complexity-Feedback Tradeoffs and Capacity Results for Packet Erasure Networks

Many communication networks are well-modeled as 'packet erasure' networks, as packets transmitted over these networks are either received correctly at the destination or are 'erased'; a packet erasure occurs when an error-corrupted packet is detected and discarded, or when a packet is dropped due to congestion in the network. This dissertation investigates two problems related to communicating reliably over packet erasure networks, adopting two different views of the network, viz., (i) a point-to-point erasure channel (that models either a single link or end-to-end communication), and (ii) a network of erasure links. Reliable communication over a point-to-point erasure channel can be accomplished in one of two ways: 1) incorporating redundant packets in the transmitted packet sequence, i.e., via forward-error-correction (FEC) techniques, or 2) using feedback to request re-transmission of erased packets, i.e., automatic-repeat-request (ARQ) protocols. This dissertation presents new constructions of hybrid ARQ protocols (i.e., protocols combining FEC and ARQ) for the point-to-point erasure channel. These protocols use Tornado codes (a class of LDPC codes) for erasure correction. The focus is on enabling and characterizing trade-offs between costs associated with FEC (i.e., computational complexity of encoding/decoding) and ARQ (the amount of feedback utilized). The described protocols provide efficient trade-offs and can offer significant savings in computational/feedback requirements in several situations, compared to simple time-sharing between FEC and ARQ. The second topic of this dissertation deals with reliable communication over two wireless relay networks - the multiple access relay channel (MARC) and the multiple relay channel (MRC) - wherein the links are memoryless erasure channels, and individual nodes time-share the use of the medium. The MARC is comprised of M independent sources that communicate with a common destination with the help of a single relay, while the MRC consists of a single source communicating with a single destination with the aid of M parallel relays. The capacity region of the MARC and the capacity of the MRC are derived, assuming the destination has perfect knowledge of erasure patterns on all the links. Optimal bandwidth allocation strategies are obtained in closed-form as functions of the link parameters. These serve to highlight the utility of the relay(s) in various scenarios. Also, it is shown that easily-implemented capacity-approaching codes for the binary erasure channel, such as LDPC or Tornado codes, can be used at the link level to attain any achievable rate(s). Finally, these capacity results are unchanged in the presence of feedback of erasure location information to all nodes.