Flooding algorithm

A flooding algorithm is an algorithm for distributing material to every part of a graph. The name derives from the concept of inundation by a flood.

Flooding algorithms are used in computer networking and graphics. Flooding algorithms are also useful for solving many mathematical problems, including maze problems and many problems in graph theory. Every incoming packet is sent out on every other link by every router. Super simple to implement, but generates lots of redundant packets. Interesting to note that all routes are discovered, including the optimal one, so this is robust and high performance (best path is found without being known ahead of time). Good when topology changes frequently (USENET example).

Some means of controlling the expansion of packets is needed. It could try to ensure that each router only floods any given packet once. Could try to be a little more selective about what is forwarded and where. The station initiating a packet stores the distance of the destination in the submitted packet (or the largest distance in the network). Each node reduces the counter by one, and resubmits the packet to all the adjacent nodes (but not to the node from where it received the packet). Packets with counter 0 are discarded. The destination node doesn't resubmit the packet .