Flooding

Flooding is the static routing algorithm. In this algorithm, every incoming packet is sent on all outgoing lines except the line on which it has arrived.

One major problem of this algorithm is that it generates a large number of duplicate packets on the network.

Several measures are taken to stop the duplication of packets. These are:

1. One solution is to include a hop counter in the header of each packet. This counter is decremented at each hop along the path. When this counter reaches zero the packet is discarded. Ideally, the hop counter should become zero at the destination hop, indicating that there are no more intermediate hops and the destination is reached. This requires the knowledge of an exact number of hops from a source to a destination. 

2. Another technique is to keep the track of the packet that has been flooded, to avoid sending them a second time. For this, the source router put a sequence number in each packet it receives from its hosts. Each router then needs a list per source router telling which sequence numbers originating at that source have already been seen. If an incoming packet is on the list, it is not flooded.

3. Another solution is to use selective flooding. In selective flooding, the routers do not send every incoming packet out on every output line. Instead, the packet is sent only on those lines which are approximately going in the right direction.

Characteristics –

• Requires no network information like topology, load condition, cost of diff. paths

• Every incoming packet to a node is sent out on every outgoing like except the one it arrived on.

• All possible routes between Source and Destination are tried. A packet will always get through if the path exists

• As all routes are tried, the will be at least one route which is the shortest

• All nodes directly or indirectly connected are visited

• A hop counter may be contained in the packet header which is decremented at each hop.

• with the packet being discarded when the counter becomes zero

• The sender initializes the hop counter. If no estimate is known, it is set to the full diameter of the subnet.

• Keep track of the packets which are responsible for flooding using a sequence number. Avoid sending them out a second time.

Limitations 

• Flooding generates a vast number of duplicate packets
• Suitable damping mechanism must be used

Hop-Count –

Selective Flooding: Routers do not send every incoming packet out on every line, only on those lines that go in approximately in the direction of the destination.

Advantages of Flooding :

• Highly Robust, emergency or immediate messages can be sent (eg military applications)

• Set up the route in the virtual circuit

• Flooding always chooses the shortest path

• Broadcast messages to all the nodes