Forwarding fault detection in wireless community networks

Resumen

Wireless community networks (WCN) are specially vulnerable to routing forwarding failures because of their intrinsic characteristics: use of inexpensive hardware that can be easily accessed; managed in a decentralized way, sometimes by non-expert administrators, and open to everyone; making it prone to hardware failures, misconfigurations and malicious attacks. To increase routing robustness in WCN, we propose a detection mechanism to detect faulty routers, so that the problem can be tackled. Forwarding fault detection can be explained as a 4 steps process: first, there is the need of monitoring and summarizing the traffic observed; then, the traffic summaries are shared among peers, so that evaluation of a router's behavior can be done by analyzing all the relevant traffic summaries; finally, once the faulty nodes have been detected a response mechanism is triggered to solve the issue. The contributions of this thesis focus on the first three steps of this process, providing solutions adapted to Wireless Community Networks that can be deployed without the need of modifying its current network stack. First, we study and characterize the distribution of the error of sketches, a traffic summary function that is resilient to packet dropping, modification and creation and provides better estimations than sampling. We define a random process to describe the estimation for each sketch type, which allows us to provide tighter bounds on the sketch accuracy and choose the size of the sketch more accurately for a set of given requirements on the estimation accuracy. Second, we propose KDet, a traffic summary dissemination and detection protocol that, unlike previous solutions, is resilient to collusion and false accusation without the need of knowing a packet's path. Finally, we consider the case of nodes with unsynchronized clocks and we propose a traffic validation mechanism based on sketches that is capable of discerning between faulty and non-faulty nodes even when the traffic summaries are misaligned, i.e. they refer to slightly different intervals of time.