Flooding: Contacting Far-Away Nodes

What is flooding?

Flooding is a simple multihop routing protocol. Flooding attempts to deliver each packet to all nodes within a maximum hop count. The algorithm is simple:
  1. A packet arrives.
  2. Has it been seen before? If yes, drop it.
  3. Otherwise, deliver it to our clients if it is addressed to us.
  4. If the hops_remaining is == 0, drop it.
  5. Otherwise, decrement hops_remaining and forward it out all available interfaces, excepting the incoming interface if it is point-to-point
When flooding, each node will retransmit the packet once over each interface. In a point-to-point network, flooding will transmit each packet once over every link.

Flooding is generally very resilient, because the packet can take many different paths to get to the destination.  It is also the routing scheme most resilient to topology change, because it makes no effort to keep or make use of topology information. For similar reasons, floods have very low latency. The drawback of flooding is performance.

Using Flooding

Like other network stack modules, the flood module exposes a link interface. However, in the case of flooding, the src and dst addresses are node ID's, NOT interface IDs. This is because flooding operates as a network layer rather than link layer service.

When flooding, the only header fields that MUST be set are type, dst, and max_hops. To send a flood to all nodes within N hops, set the max_hops field to N, and the dst field to LINK_BROADCAST. To send to a specific node, set the dst field to that node's ID. Note that floods to specfic nodes are implemented by filtering a broadcast flood, so there is no performance improvement.

When you receive a flooded message, the header will be filled with the src Node ID and the dst Node ID. The max_hops field will contain the number of hops remaining. The prev_hop field will contain the interface ID of the previous hop.




Last modified by jelson, 4 February 2003