Flooding and broadcasting during operation of a data network, it is often necessary to broadcast some information, that is, to send this information from an origin node to all other nodes. An example is when there are changes in the network topology due to link failures and repairs and these changes must be transmitted to the entire network. Broadcasting could also be used as a primitive form of routing packets from a single transmitter to a single receiver or, more generally, to a subset of receivers; this use is generally rather inefficient, but may be sensible because it is simple or because the receivers' locations within the network are unknown.
A widely used broadcasting method, known as flooding, operates as follows. The origin node sends its information in the form of a packet to its neighbours (the nodes to which it is directly connected with a link). The neighbours relay it to their neighbours and so on, until the packet reaches all nodes in the network. Two additional rules are also observed, which limit the number of packet transmissions. First, a node will not relay the packet back to the node from which the packet was obtained. Second, a node will transmit the packet to its neighbours at most once ; this can be ensured by including on the packet the ID number of the origin node and a sequence number, which is incremented with each new packet issued by the origin node. By storing the highest sequence number received for each origin node and by not relaying packets with sequence numbers that are less than or equal to the one stored, a node can avoid transmitting the same packet more than once on each of its incident links. Note that with these rules, links need not preserve the order of packet transmissions; the sequence numbers can be used to recognize the correct order. Fig. 5.7 (a) gives an example of flooding and illustrates that the total number of packet transmissions per packet broadcast lies between Land 2L, where L is the number of bidirectional links of the network. We note also that one can implement a flooding-like algorithm without using sequence numbers.