Lossless data transfer over communication networks has traditionally been achieved by means of ARQ protocols. However, the last ten years have seen an increasing interest in using erasure-correcting codes as an alternative, with the goal of reducing latency, feedback overhead, etc. Since these two approaches possess advantages as well as drawbacks, several hybrid ARQ schemes have also been proposed as good compromise solutions, in order to attain the “best of both worlds”. Extending this principle, this paper develops new classes of hybrid ARQ protocols for erasure channels that allow for flexible trade-offs between two important cost metrics, viz., thecomputational complexity of coding, and theamount of feedbackneeded. Our hybrid schemes make use of Tornado codes – a class of low-complexity capacity-achieving erasure codes – whose coding structure is well-suited for feedback-based communications. These schemes demonstrate significant cost reductions versus coding-only and feedback-only approaches over a wide region of interest. Moreover, these schemes are easily tuned to achieve different operating points on a trade-off curve. Finally, the proposed schemes showcase novel means of interweaving coding and feedback.

This paper considers two simple wireless network configurations - the multiple access relay channel (MARC) and the multiple relay channel (MRC) - in which the links making up the network time-share the medium and the assumed loss mechanisms are memoryless packet erasures. The capacity region of the MARC and the capacity of the MRC are derived as functions of the link erasure rates. This is done assuming (i) optimal sharing of bandwidth among the transmitters, and (ii) perfect knowledge at the destination of erasure patterns on all the links. Moreover, it is shown that easily-implemented capacity-approaching codes for the binary erasure channel, such as LDPC or Tornado codes, can be used to attain any achievable rate(s). Finally, these capacity results are unchanged in the presence of feedback of erasure location information to all nodes. For the erasure MARC, the results imply a simple strategy, viz., that the relay should help only those sources that have a weaker direct channel to the destination than the relay itself - regardless of the quality of the source-to-relay channels. For the erasure MRC, the solution has a more complex, inductive structure: the participation of a relay r in the optimal strategy depends on the best throughput that can be achieved using only those relays with a better link to the destination than r.

This paper introduces hybrid ARQ protocols for the packet erasure channel - protocols that enable tradeoffs between complexity of encoding/decoding redundant packets and the amount of feedback needed for re-transmission requests. These protocols use adaptations of Tornado codes for erasure-correction on the forward link, and rate-distortion codes on the reverse link for feeding back the status of received packets. The resulting complexity-feedback tradeoffs are shown to be substantially better (in regimes of practical interest) than a naive protocol that simply time-shares between coding-only and feedback-only approaches.

This paper considers a simple wireless network - the multiple relay channel (MRC) - wherein a single source communicates with a single destination with the aid of M parallel relays. The links between the communicating nodes are non-interfering and subject to erasures. The capacity of this network is derived under the assumption that the destination has access to perfect side information on the erasure locations at the relays. This is done by first establishing an upper bound on the capacity by enumerating bounds on information transfer across various cut-sets and solving for the highest achievable rate using tools from linear programming; subsequently, it is shown that this rate can be achieved using low-complexity capacity-achieving codes designed for the point-to-point erasure channel, e.g., low-density parity-check codes. The paper concludes with a discussion of specific examples of MRCs.

This paper considers a simple network consisting of a source, a destination, and a relay. In this model, the source- relay and relay-destination links are lossless, while the source- destination link is subject to erasures. Four coding schemes for reliably conveying k symbols from the source to the destination are described. Three of these techniques are adapted directly from well-known point-to-point coding schemes - viz., the use of maximum-distance separable (MDS) codes and Luby Transform (LT) codes. The fourth approach is a new technique using uncoded transmission from the source in conjunction with a relay that transmits a sequence with this property: When the destination subtracts the effects of the unerased symbols from the sequence, what remains is an "LT-like" code for the erased symbols - and this property holds regardless of which symbols were erased on the source-destination link. The four approaches are compared in terms of their complexity and performance.

This paper describes techniques to decompose LT codes (a class of rateless erasure-correcting codes) into distributed LT (DLT) codes. DLT codes can be used to independently encode data from multiple sources in a network in such a way that, when the DLT-encoded packets are combined at a common relay, the resulting bit stream (called a modified LT (MLT) code) has a degree distribution approximating that of an LT code, with simulations indicating comparable performance. In essence, DLT codes are designed so that the final stage of encoding for erasure correction can be carried out by a low-complexity relay that selectively xors the bit streams generated at each source and transmits the result to the sink. This paper presents results for two-source and four-source networks. It is shown that, when the relay-to-sink link is the bottleneck, the DLT/MLT approach can yield substantial performance benefits compared with a competing strategy wherein each of the sources uses its own independent LT encoder and the resulting bit streams are time-multiplexed through the relay.

This paper proposes a novel distributed encoding procedure to realize codes that resemble LT codes (rateless codes for erasure correction) in both structure and performance. For the case of two sources communicating with a single sink via a common relay, this technique separately encodes k/2 symbols of information onto slightly more than k code symbols at each source. These two codewords are then selectively XOR-ed at the relay, such that the result can be decoded by the sink to recover all k information symbols. It is shown that, for the case of four sources communicating to a single sink, the use of a similar distributed LT code leads to a 50% reduction in overhead at the sink, compared to the use of four individual LT codes