TY - JOUR
T1 - Providing fault-tolerant Ad hoc routing service in adversarial environments
AU - Xue, Yuan
AU - Nahrstedt, Klara
N1 - Funding Information:
We thank Nitin Vaidya and Pradeep Kyasanur for their comments and helpful suggestions. This research was supported by the ONR MURI NAVY CU 37515-6281 grant, and the NSF EIA 99-72884EQ grant. Any opinions, findings, and conclusions are those of the authors and do not necessarily reflect the views of the above agencies.
PY - 2004/6
Y1 - 2004/6
N2 - Most existing designs of ad hoc networks are based on the assumption of non-adversarial environments, where each node in the network is cooperative and well-behaved. When misbehaving nodes exist in the network, the performance of current routing protocols degrades significantly. Since ad hoc networks, consisting of autonomous nodes, are open and distributed in nature, maintaining a fault-free network environment is extremely difficult and expensive. In this paper, we propose a new routing service named best-effort fault-tolerant routing (BFTR). The design goal of BFTR is to provide packet routing service with high delivery ratio and low overhead in presence of misbehaving nodes. Instead of judging whether a path is good or bad, i.e., whether it contains any misbehaving node, BFTR evaluates the routing feasibility of a path by its end-to-end performance (e.g. packet delivery ratio and delay). By continuously observing the routing performance, BFTR dynamically routes packets via the most feasible path. BFTR provides an efficient and uniform solution for a broad range of node misbehaviors with very few security assumptions. The BFTR algorithm is evaluated through both analysis and extensive simulations. The results show that BFTR greatly improves the ad hoc routing performance in the presence of misbehaving nodes.
AB - Most existing designs of ad hoc networks are based on the assumption of non-adversarial environments, where each node in the network is cooperative and well-behaved. When misbehaving nodes exist in the network, the performance of current routing protocols degrades significantly. Since ad hoc networks, consisting of autonomous nodes, are open and distributed in nature, maintaining a fault-free network environment is extremely difficult and expensive. In this paper, we propose a new routing service named best-effort fault-tolerant routing (BFTR). The design goal of BFTR is to provide packet routing service with high delivery ratio and low overhead in presence of misbehaving nodes. Instead of judging whether a path is good or bad, i.e., whether it contains any misbehaving node, BFTR evaluates the routing feasibility of a path by its end-to-end performance (e.g. packet delivery ratio and delay). By continuously observing the routing performance, BFTR dynamically routes packets via the most feasible path. BFTR provides an efficient and uniform solution for a broad range of node misbehaviors with very few security assumptions. The BFTR algorithm is evaluated through both analysis and extensive simulations. The results show that BFTR greatly improves the ad hoc routing performance in the presence of misbehaving nodes.
KW - Ad hoc networks
KW - Misbehaving node
KW - Routing protocol
UR - http://www.scopus.com/inward/record.url?scp=9144231402&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=9144231402&partnerID=8YFLogxK
U2 - 10.1023/B:WIRE.0000047071.75971.cd
DO - 10.1023/B:WIRE.0000047071.75971.cd
M3 - Review article
AN - SCOPUS:9144231402
SN - 0929-6212
VL - 29
SP - 367
EP - 388
JO - Wireless Personal Communications
JF - Wireless Personal Communications
IS - 3-4 SPEC.ISS.
ER -