Abstract
The capacity gain of network coding has been extensively studied in wired and wireless networks.
Recently, it has been shown that network coding improves network reliability by reducing the number
of packet retransmissions in lossy networks. However, the extent of the reliability benefit of network
coding is not known. This paper quantifies the reliability gain of network coding for reliable multicasting
in wireless networks, where network coding is most promising. We define the expected number of
transmissions per packet as the performance metric for reliability and derive analytical expressions
characterizing the performance of network coding. We also analyze the performance of reliability
mechanisms based on rateless codes and automatic repeat request (ARQ), and compare them with
network coding. We first study network coding performance in an access point model, where an access
point broadcasts packets to a group of K receivers over lossy wireless channels. We show that the
expected number of transmissions using ARQ, compared to network coding, scales as (logK) as the
number of receivers becomes large. We then use the access point model as a building block to study
reliable multicast in tree and extended access point models. In addition to scaling results, we derive
expressions for the expected number of transmissions for finite multicast groups, and use them to study
the impact of multicast group size and coding block size on the performance of different reliability
schemes. Our results show that network coding significantly reduces the number of retransmissions in
lossy networks compared to an end-to-end ARQ scheme. However, rateless coding and link-by-link
ARQ achieve performance results comparable to that of network coding.
Refereed
Yes
