  Network coding increases throughput and is robust against failures and
erasures. However, since it allows mixing of information within the network, a
single corrupted packet generated by a Byzantine attacker can easily
contaminate the information to multiple destinations.
  In this paper, we study the transmission overhead associated with three
different schemes for detecting Byzantine adversaries at a node using network
coding: end-to-end error correction, packet-based Byzantine detection scheme,
and generation-based Byzantine detection scheme. In end-to-end error
correction, it is known that we can correct up to the min-cut between the
source and destinations. However, if we use Byzantine detection schemes, we can
detect polluted data, drop them, and therefore, only transmit valid data. For
the dropped data, the destinations perform erasure correction, which is
computationally lighter than error correction. We show that, with enough
attackers present in the network, Byzantine detection schemes may improve the
throughput of the network since we choose to forward only reliable information.
When the probability of attack is high, a packet-based detection scheme is the
most bandwidth efficient; however, when the probability of attack is low, the
overhead involved with signing each packet becomes costly, and the
generation-based scheme may be preferred. Finally, we characterize the tradeoff
between generation size and overhead of detection in bits as the probability of
attack increases in the network.
