An algebraic watchdog for wireless network coding
Authors:
- 1 June 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1159-1163
Abstract
In this paper, we propose a scheme, called the algebraic watchdog for wireless network coding, in which nodes can detect malicious behaviors probabilistically, police their downstream neighbors locally using overheard messages, and, thus, provide a secure global self-checking network. Unlike traditional Byzantine detection protocols which are receiver-based, this protocol gives the senders an active role in checking the node downstream. This work is inspired by Marti et al.'s watchdog-pathrater, which attempts to detect and mitigate the effects of routing misbehavior. As the first building block of a such system, we focus on a two-hop network. We present a graphical model to understand the inference process nodes execute to police their downstream neighbors; as well as to compute, analyze, and approximate the probabilities of misdetection and false detection. In addition, we present an algebraic analysis of the performance using an hypothesis testing framework, that provides exact formulae for probabilities of false detection and misdetection.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- On coding for reliable communication over packet networksPhysical Communication, 2008
- Resilient network coding in the presence of Byzantine adversaries2007
- An algebraic approach to network codingIEEE/ACM Transactions on Networking, 2003
- Practical byzantine fault tolerance and proactive recoveryACM Transactions on Computer Systems, 2002
- The quest for security in mobile ad hoc networks2001
- Network information flowIEEE Transactions on Information Theory, 2000
- Authentication theory and hypothesis testingIEEE Transactions on Information Theory, 2000
- Routing in Ad Hoc Networks of Mobile Hosts1994
- Polynomial hash functions are reliable1992
- The Byzantine Generals ProblemACM Transactions on Programming Languages and Systems, 1982