Weak Bloom Filtering for Large-Scale Dynamic Networks
Krishna Siva · 2012
In order to forward decisions in networks where protocols play an important role we need to provide the information about the destination nodes provided by routing table states. When dynamic networks are considered the path to reach the destination may change, and corresponding states become invalid and need to be refreshed . In large, complex and highly dynamic networks, this is quite cumbersome. For such networks, we propose the concept of weak state, associated with a bloom filter which is interpreted as a probabilistic hint. Bloom filters provide space efficient storage of sets at the cost of a probability of false positives on membership queries. Weak Bloom Filtering (WBF) is a novel routing protocol that uses weak state along with random directional walks for forwarding packets. When a packet reaches a node that contains a weak state about the destination with higher confidence than that held by the packet, the walk direction is biased. The packet reaches the destination via a sequence of directional walks, punctuated by biasing decisions.