Mesh Network Firewalling with Bloom Filters

The nodes of a multi-hop wireless mesh network often share a single physical media for terminal traffic and for the backhaul network, so that the available resources are extremely scarce. Under these conditions it is important to avoid that unwanted traffic may traverse the network subtracting resources to authorized terminals. Packet filtering in wireless mesh networks is an extremely challenging task, since the number of possible connections is quadratic with respect to the number of the terminals of the network; for each connection a rule is needed and the time needed for filtering grows linearly with the number of rules. Moreover nodes can be in possession of end users and the administrator might want to keep the explicit ruleset as much secret as possible while giving the nodes enough data to behave as a firewall. In this article we present a solution for distributed firewalling in multi-hop mesh networks based on the use of Bloom Filters, a powerful but compact data structure allowing probabilistic membership queries.