Bibliographic information: In submission. (BibTeX)
Network coding has been shown to achieve optimal throughput in multicast networks. However, it relies on network nodes or routers to code correctly; a Byzantine node can introduce junk packets into the network, thus polluting downstream packets, causing the sinks to receive incorrect data, and/or significantly reducing the throughput of the network. Most previous work has focused on checking if a Byzantine node transmitted polluted packets. However, even if a Byzantine node does not introduce a junk packet, he can still significantly affect the throughput of the network: he may simply forward a packet from the ones received (without coding), not use random coding coefficients, or choose coefficients such that their packets bring the least additional in- formation at the receivers. No previous work attempted to verify if a certain node did code correctly using random coefficients over all of the packets it was supposed to code over.
We provide a novel protocol for detecting whether a node coded correctly over all the packets received according to a random linear network coding algorithm. Our protocol enables any node in the network to examine a packet received from another node by running a "verification test". The worst an adversary can do and still pass the packet verification test is equivalent to random linear network coding, which has been shown to be optimal in multicast networks. Our protocol resists collusion among nodes and is applicable to a variety of settings.
Our topology simulations show that the throughput in the best adversarial strategy for our protocol is 2 to 3 times larger than the throughput in various adversarial strategies allowed by previous work. We implemented and ran our protocol in C/C++ and Java as well as on an Android platform (Nexus One) to be used for smartphone P2P file sharing. Our C/C++ evaluation shows that the protocol is fast: the running time at a node to prepare the data for transmission is < 0.3 ms and the time to verify a packet is 2.8 ms with PIP and 0.4 ms with Log-PIP.
Last modified: Sun, 16 Jan 2011 17:30:00 -0500