Author
Baruch Awerbuch, Reza Curtmola, David Holmer, Cristina Nita-Rotaru, Herbert Rubens
Abstract
A common technique used by routing protocols for ad hoc wireless networks is to establish the routing
paths on-demand, as opposed to continually maintaining a complete routing table. Since in an ad hoc
network nodes not in direct range communicate via intermediate nodes, a significant concern is the
ability to route in the presence of Byzantine failures which include nodes that drop, fabricate, modify,
or mis-route packets in an attempt to disrupt the routing service.
We propose the first on-demand routing protocol for ad hoc wireless networks that provides resilience
to Byzantine failures caused by individual or colluding nodes. The protocol relies on an adaptive
probing technique that detects a malicious link after log n faults have occurred, where n is the length
of the path. Problematic links are avoided by using a weight-based mechanism that multiplicatively
increases their weights and by using an on-demand route discovery protocol that finds a least weight
path to the destination. Our protocol bounds the amount of damage that an attacker or a group of
colluding attackers can cause to the network.
