ODSBR: An On-Demand Secure Byzantine Routing Protocol
Baruch Awerbuch, Reza Curtmola, David Holmer, Cristina Nita-Rotaru, Herbert Rubens · 2003
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.