Forwarding fault detection in Wireless Community Networks

The most important service a Wireless community network (WCN) offers is connectivity. However, WCN's connectivity is fragile because of their intrinsic characteristics: inexpensive hardware that can be easily accessed; decentralized management, sometimes by non-experts, and open to everyone; making it prone to hardware failures, misconfigurations and malicious attacks. The goal of this thesis is to increase routing robustness in WCN using forwarding fault detection, so that we can find and fix problematic routers. Forwarding fault detection can be explained as a four-step process: first, nodes monitor and summarize the traffic on the network; then, those traffic summaries are shared among peers, so that, by analyzing the relevant ones, we can asses the behavior of a given node. Finally, when we find a faulty router, a response mechanism is triggered to solve the issue. On this thesis we focus on the first three subproblems.  First, on monitoring, 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 that has better statistical guarantees than sampling. 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. KDet is a solution adapted to WCN, because it can be deployed without the need of modifying its current network stack. 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.