Flooding, Gossiping and the Broadcast Storm

Flooding's three faults

The SPIN paper names them.

Implosion. "In classic flooding, a node always sends data to its neighbors, regardless of whether or not the neighbor has already received the data from another source." In its Figure 1, A floods to B and C, which both pass the data to D: "The protocol thus wastes resources by sending two copies of the data to D. It is easy to see that implosion is linear in the degree of any node." A node with ten neighbours may hear the same packet ten times.

Overlap. "Sensor nodes often cover overlapping geographic areas, and nodes often gather overlapping pieces of sensor data." Two sensors watching the same spot flood the same observation, and their common neighbour receives it twice. "Overlap is a harder problem to solve than the implosion problem" because "implosion is a function only of network topology, whereas overlap is a function of both topology and the mapping of observed data to sensor nodes."

Resource blindness. "In classic flooding, nodes do not modify their activities based on the amount of energy available to them at a given time." A node nearly out of energy forwards as eagerly as a fresh one.

Figure 56.1 Implosion (after SPIN's Fig. 1), and how little of B's disc a rebroadcast newly reaches (after the storm paper's Fig. 2)

Gossiping

Gossiping "is an alternative to the classic flooding approach that uses randomization to conserve energy. Instead of indiscriminately forwarding data to all its neighbors, a gossiping node only forwards data on to one randomly selected neighbor." It may even send the data straight back to the neighbour it came from, which the paper allows on purpose, since otherwise a node reachable only through that neighbour might never receive it.

Because each node makes only one copy, "Gossiping avoids such implosion". The price is speed: "While gossiping distributes information slowly, it dissipates energy at a slow rate as well." With a single source, the data reaches at most one new node per round. Al-Karaki and Kamal agree: selecting one random node instead of broadcasting "causes delays in propagation of data through the nodes."

The word gossip is used more loosely too: many papers mean probabilistic flooding, where each node rebroadcasts with some probability p. The broadcast storm paper calls that the probabilistic scheme, below.

The broadcast storm

Ni, Tseng, Chen and Sheu studied flooding in dense ad hoc networks and found that, used blindly, it causes "serious redundancy, contention, and collision", which together they call the broadcast storm problem.

• Redundant rebroadcasts. "When a mobile host decides to rebroadcast a broadcast message to its neighbors, all its neighbors already have the message."
• Contention. "After a mobile host broadcasts a message, if many of its neighbors decide to rebroadcast the message, these transmissions (which are all from nearby hosts) may severely contend with each other."
• Collision. With no RTS/CTS dialogue, no acknowledgement and no collision detection for broadcasts, collisions are both likelier and more damaging ([Hidden and Exposed Terminals, and RTS and CTS] explained why broadcasts get no handshake).

How little a rebroadcast adds. Let A broadcast and B, at distance d, rebroadcast; both have range r. The only area that can benefit from B's rebroadcast is the part of B's disc outside A's. It is largest when B is at the edge of A's range, d = r, where it equals r squared × (π/3 + half the square root of 3), about 0.61 πr squared: a rebroadcast can add at most 61 per cent new coverage, and anything from nothing upwards. Averaged over all positions of B within A's range, it is about 0.41 πr squared: "a rebroadcast can cover only additional 41% area in average." And a node that has already heard the message from two neighbours can add, on average, only about 0.19 of its disc. The paper calls the expected share after k copies EAC(k), the expected additional coverage.

The first program reproduces the analysis. It places k senders at random within a node's range and measures, with random points, how much of the node's disc none of them covered.

# Part 1: how little a rebroadcast adds. A node X (range 1, at the origin) has
# heard the same broadcast from k senders placed at random within its range.
# EAC(k) is the expected share of X's disc that none of them covered: what X's
# own rebroadcast could add. Estimated by random points, as Ni and colleagues did.
import random
from math import pi, sqrt

rnd = random.Random(56)

def in_disc(r=1.0):
    while True:
        x, y = rnd.uniform(-r, r), rnd.uniform(-r, r)
        if x * x + y * y <= r * r:
            return x, y

def eac(k, trials=2000, points=200):
    total = 0.0
    for _ in range(trials):
        senders = [in_disc() for _ in range(k)]
        new = 0
        for _ in range(points):
            px, py = in_disc()
            if all((px - sx) ** 2 + (py - sy) ** 2 > 1 for sx, sy in senders):
                new += 1
        total += new / points
    return total / trials

print("a single rebroadcast adds at most %.3f of the disc" % ((pi / 3 + sqrt(3) / 2) / pi))
for k in range(1, 7):
    print("heard %d times: expected additional coverage %.3f" % (k, eac(k)))

a single rebroadcast adds at most 0.609 of the disc
heard 1 times: expected additional coverage 0.416
heard 2 times: expected additional coverage 0.192
heard 3 times: expected additional coverage 0.093
heard 4 times: expected additional coverage 0.047
heard 5 times: expected additional coverage 0.025
heard 6 times: expected additional coverage 0.014

Reading it. The maximum, 0.609, and the averages after one and two copies, about 0.41 and 0.19, are the paper's 61, 41 and 19 per cent. After three copies a rebroadcast can add about 9 per cent, after four about 5: the paper's statement that for four or more copies "the expected additional coverage is below 0.05%" is right once the percent sign is read as a slip for a fraction of 0.05 of the disc, which its own Figure 3 plots. A node that has heard a broadcast three or four times has almost nothing to add, and its rebroadcast mostly adds contention and collisions.

The cures

The paper's schemes all ask one question before rebroadcasting: is this node likely to reach anyone new?

• Probabilistic. Rebroadcast with probability P. In dense networks a small P reaches nearly everyone; in sparse ones P must be larger.
• Counter-based. Wait a random number of slots before rebroadcasting, counting the copies heard meanwhile; if the count reaches a threshold C, the rebroadcast is inhibited. The paper finds that "a threshold C of 3 or 4 is an appropriate choice", which the EAC curve explains.
• Distance-based. Rebroadcast only if every sender heard is farther than a threshold D, since a near sender leaves little new area; D is matched to the coverage, for example to EAC(2), about 0.187.
• Location-based. With positions known, compute the additional coverage directly and rebroadcast only if it exceeds a threshold.
• Cluster-based. Only cluster heads and gateways rebroadcast; ordinary members stay silent.

The random wait before rebroadcasting matters in every scheme: it spreads neighbours' rebroadcasts in time, reducing contention, and gives a node time to count the copies it hears.

One broadcast, four ways

The second program sends one broadcast from a corner node of a random field of 100 nodes (100 m by 100 m, range 20 m), four ways: flooding; probabilistic rebroadcast with P = 0.6; counter-based with C = 3; and SPIN's one-neighbour gossiping, counted until every reachable node has the data. Each rebroadcast waits a random 0 to 7 slots. Collisions are not modelled, so what is counted is redundancy alone. It reports, averaged over 200 random fields, the sends, the duplicate receptions, the share of reachable nodes reached, and the slots taken.

Reading it: flooding. Every reachable node sends once, 96 sends on average, and they cause about 888 duplicate receptions, some nine for every node: implosion counted. The broadcast finishes in about 31 slots.

Reading it: the cures. The counter-based scheme with C = 3 reaches 98.4 per cent of the nodes with 41.9 sends, less than half of flooding's, and about a third of the duplicates. The probabilistic scheme with P = 0.6 sends about as little (44.3) but reaches only 77.2 per cent: a random decision ignores whether the node has anything to add, while the counter measures it. At this density the counter is the better rule, as the EAC curve predicts.

Reading it: gossiping. One-neighbour gossiping reaches everyone in the end, but needs about 1,590 sends, one at a time, some sixteen times flooding's total and some fifty times as long: cheap per step, costly and slow overall, because a random walk revisits nodes it has already covered.

Collisions would make flooding look worse still: its rebroadcasts, bunched in time among close neighbours, are the ones most likely to collide.

Broadcast in the practical

The paired practical broadcasts among the motes of a small TOSSIM network. The principles above are what its code must implement: a sequence number with each broadcast so that a mote forwards each message once; optionally a hop count; and a small random delay before rebroadcasting, so that neighbours do not all transmit in the same instant. [TOSSIM: Simulating Motes, Radio Gain and Packet Loss] showed how the simulator's radio model loses packets, which is why a broadcast that works on a clean channel may not reach every mote in the simulated one.

Distinctions

What it does not mean

Flooding is not useless. It is robust and needs no state, which is why route discovery, interests and queries use it; the cures limit it rather than replace it.

Duplicate suppression does not stop implosion. It stops a node forwarding a packet twice; it does not stop the node receiving the packet from every neighbour.

Gossiping is not cheap overall. Each step is one send, but covering the network takes many steps.

The broadcast storm is not only about energy. Redundant rebroadcasts also cause contention and collisions, which can make a broadcast reach fewer nodes than a more careful scheme.

Quick revision

• Flooding: forward every new packet to all neighbours; duplicates dropped by (source ID, sequence number); optional hop limit; no state, robust, fast.
• Three faults (SPIN): implosion (duplicates by several paths, linear in degree), overlap (overlapping sensors send the same data), resource blindness (ignores energy).
• Gossiping: forward to one random neighbour; avoids implosion; slow (about one node per round).
• Broadcast storm (Ni, Tseng, Chen, Sheu 1999): redundant rebroadcasts, contention, collision. A rebroadcast adds at most 61 per cent, on average 41 per cent; after two copies about 19, after four about 5.
• Cures: probabilistic (P), counter-based (C = 3 or 4), distance-based (D), location-based, cluster-based; always a random delay before rebroadcasting.
• Program (100 nodes): flooding 96 sends, 888 duplicates; counter-based C = 3: 41.9 sends, 98.4 per cent reach; probabilistic P = 0.6: 77.2 per cent; gossiping about 1,590 sends.

Test yourself

1. Explain flooding and its advantages. A source sends a packet to all its neighbours, and every node that receives a packet for the first time sends it on to all of its neighbours, recognising and dropping copies it has already seen by a source ID and sequence number, and optionally stopping at a hop limit. It needs no routing tables or knowledge of the topology, reaches every reachable node, and tries all paths at once, so it is simple and robust to failures.

2. What are implosion, overlap and resource blindness? Implosion: a node receives several copies of the same packet because several neighbours forward it, wasting a send and a receive for each extra copy. Overlap: nodes whose sensing areas overlap produce the same data and send it to the same neighbour, which receives it twice. Resource blindness: nodes forward without regard to their remaining energy, so nearly exhausted nodes are used as freely as full ones.

3. What is gossiping, and how does it compare with flooding? A gossiping node forwards a packet to one randomly chosen neighbour rather than to all of them. This avoids implosion, since each node makes only one copy, and uses little energy per step, but the data spreads slowly, about one node per round, and covering the whole network can take many transmissions. In the program, gossiping needed about 1,590 sends to reach every node, against flooding's 96.

4. What is the broadcast storm problem? When flooding is used in a dense network, many nodes rebroadcast the same message close together in space and time, causing redundant rebroadcasts (the neighbours already have the message), contention for the channel among the rebroadcasting neighbours, and collisions, which are likely because broadcasts use no RTS/CTS, no acknowledgement and no collision detection.

5. Show why a rebroadcast is often redundant. If A broadcasts and B, within A's range, rebroadcasts, only the part of B's disc outside A's disc can gain new receivers. This area is largest when B is at the edge of A's range, about 61 per cent of B's disc, and averages about 41 per cent over all positions of B. After a node has heard the message twice, a rebroadcast adds on average only about 19 per cent, and after four times about 5 per cent.

6. Explain the counter-based scheme and why a threshold of 3 or 4 works. After first hearing a broadcast, a node waits a random number of slots and counts how many more copies it hears. If the count reaches the threshold C before its turn, it cancels its rebroadcast. Since the expected additional coverage after three or four copies is only about 9 or 5 per cent, a node that has heard the message that often has almost nothing to add. In the program, C = 3 reached 98.4 per cent of nodes with less than half of flooding's sends.