Master Flooding in Computer Networks: Key Algorithms Explained

Flooding is a well-known technique in computer networks that is widely used for packet routing and communication. Despite its simplicity, flooding has proven to be a valuable tool in network protocols and applications.

In this article, we will explore flooding in computer networks, its algorithms, and its practical applications, while explaining the different types of flooding techniques, their advantages and limitations, and how they are optimized for better performance.

What is Flooding in Computer Networks?

In computer networking, flooding refers to the process of sending a packet to every node in a network without any regard to the path the packet takes. This technique is often used to ensure that messages reach all parts of a network or to facilitate the discovery of paths in routing protocols.

How Flooding Works:

In flooding, when a node receives a packet, it simply sends that packet to all its neighbors. Each neighbor, in turn, repeats this process, resulting in the propagation of the message to all connected nodes in the network. While this guarantees delivery, it also leads to redundancy, as packets may be sent multiple times across the same network.

When and Why Flooding is Used:

Flooding is typically employed in scenarios where there is no predefined route to the destination, or when it is essential to reach all nodes within a network. It serves several purposes, ensuring broad message delivery and facilitating network discovery. Below are the main use cases for flooding:

• Network Discovery: Flooding is used to discover all the nodes in a network when the network’s topology is unknown or dynamic.
• Routing Protocol Initialization: Flooding helps initialize routing tables when network nodes are first brought online or when network topology changes.
• Broadcasting Messages: Flooding ensures that messages reach every part of a network, particularly in situations such as system updates, network announcements, or alerts.
• Path Discovery in Routing Protocols: In protocols such as Distance-Vector Routing and Link-State Routing, flooding enables nodes to discover the best route by distributing information about the network topology.
• Multicast and Anycast Communication: Flooding ensures that multicast and anycast messages are delivered to relevant nodes efficiently, especially in large, distributed networks.

Types of Flooding Techniques in Computer Networks

Flooding techniques in computer networks vary depending on the specific needs of the network, such as controlling the number of hops or ensuring efficient use of bandwidth. These techniques help optimize performance, reduce redundancy, and address specific network conditions. Below are the 2 main types of flooding used in computer networks:

Uncontrolled Flooding

In uncontrolled flooding, every router sends the incoming packet to all its neighbors except the one it received from, without any checks or limits.

Example Network:

   A
  /|\
 B C D
 /| |\
E F G H

Packet Flow Example:

Suppose a packet arrives at router A:

• A sends to B, C, D.
• B sends to A (but skips, since packet came from A), C (if connected), E, F.
• C sends to A (skips), B, D, G.
• D sends to A (skips), C, H.
• E, F, G, H continue similarly, sending to all neighbors except the source.

Result:
Packets are sent endlessly to all possible neighbors, potentially causing broadcast storms.

Controlled Flooding

In controlled flooding, routers use algorithms to avoid infinite loops and duplication. The two main algorithms are:

• Sequence Number Controlled Flooding (SNCF): Each packet has a unique sequence number. Routers remember seen packets and drop duplicates.
• Reverse Path Forwarding (RPF): Packets are only forwarded if received from the “correct” neighbor (the one on the shortest path back to the source).

Example Network: ages reach all necessary nodes.

   A
  /|\
 B C D
 /| |\
E F G H

Packet Flow Example with SNCF:

• A sends to B, C, D (with sequence number 1).
• B receives from A, remembers (A,1), and forwards to E, F (not back to A).
• If B receives (A,1) again from another router, it drops it.

Packet Flow Example with RPF:

• A sends to B, C, D.
• B only forwards to E, F if it believes A is its best path to the source. If B receives a packet from E or F that should have come from A, it does not forward it.

Result:
Packets are controlled, and duplicates are minimized.

Flooding Algorithm in Computer Networks Explained

Flooding relies on a simple yet effective algorithm that enables message propagation throughout a network. Here’s a breakdown of the flooding algorithm in computer networks:

Step 1: Initialization

When a source node initiates the flooding process, it sends the message to its neighbors. Each node that receives the message marks it as “received” to avoid handling the same packet multiple times.

Step 2: Propagation of the Flooded Packet

Upon receiving a message, a node forwards it to all its neighboring nodes. These neighbors also forward the message to their neighbors, and this process continues.

Step 3: Handling Redundant Messages

To avoid infinite loops and redundancy, nodes keep track of messages they have already received, typically by maintaining a list of message IDs. If a node has already processed a message, it will not forward it again.

Step 4: Termination of the Flooding Process

The flooding process terminates once the message has reached all possible nodes in the network or after a set time or hop count limit. This is usually managed through mechanisms like TTL (Time to Live) or hop count.

Flooding is widely used in routing protocols and network discovery methods, especially in situations where it is essential to reach every part of the network, such as during initial network setup or when network topology changes.

Applications of Flooding in Computer Networks

Flooding plays a crucial role in various network protocols and applications:

Routing Protocols:

Flooding is used in Distance Vector Routing and Link-State Routing algorithms to exchange routing information between routers. For example, in Link-State Routing, routers flood the network with their current routing tables to keep all routers updated about network topology changes.

Broadcasting:

Flooding is used to broadcast messages across all nodes in a network. It is a simple method to ensure that all nodes in the network receive the message, such as in network announcements or alerts.

Multicast and Anycast:

Flooding is also employed in multicast and anycast communication. In multicast, flooding ensures that a message reaches a specific group of nodes, while in anycast, the message is sent to the nearest or most responsive node in a group.

Check Out | Understanding Simple Network Management Protocol Essentials {SNMP Port}

Advantages and Disadvantages of Flooding in Computer Networks

Flooding offers several advantages that make it a valuable technique in specific network environments. It is particularly beneficial when simplicity and scalability are key. However, despite its advantages, flooding also presents significant drawbacks, particularly in terms of resource consumption and network efficiency. Below are the main advantages and disadvantages of using flooding in computer networks:

Preventing Flooding Loops in Computer Networks

Flooding loops can be catastrophic in networks, as they cause redundant packet transmission, consuming valuable resources and potentially crippling network performance. To prevent flooding loops and enhance the efficiency of message propagation, several techniques are employed:

Sequence Numbers and Timers:

Using sequence numbers and timers ensures that a node does not reprocess the same message multiple times. Each message is assigned a unique sequence number when it is first sent. When a node receives a message, it checks if it has already seen the same message by comparing sequence numbers. If the message has been processed before, it is discarded.

This method prevents infinite loops and ensures that packets are not redundantly forwarded across the network. Timers can also help in limiting how long a message stays in the network, further reducing loop risks.

Packet Tracing and Hop Count:

Flooding can be limited by a hop count (TTL – Time to Live), which restricts the number of hops a packet can take before it is discarded. This mechanism prevents the packet from circulating endlessly in the network. Each time the packet is forwarded, the TTL value decreases by one.

When it reaches zero, the packet is discarded. This approach helps avoid situations where the packet might get stuck in a cycle of looping nodes.

Flooding with History Tracking:

In addition to sequence numbers, maintaining a history list or a cache of previously visited nodes can help prevent loops. Each node keeps track of the IDs of nodes that have already received the packet.

If a node encounters a packet from a previously visited node, it will not forward the packet, thus preventing a loop from forming.

Reverse Path Forwarding (RPF):

Reverse Path Forwarding (RPF) is a method where a packet is forwarded only if it arrives from a node that is on the reverse path back to the source. In this technique, the forwarding node checks if the packet is received from the correct direction and matches the reverse route back to the sender.

If the packet doesn’t come from the expected direction, it is not forwarded, which helps prevent loops from forming in the first place.

Flooding with Adaptive Routing:

Adaptive routing algorithms can dynamically adjust the path a packet follows based on real-time network conditions, such as congestion or failure. By continuously monitoring the state of the network, adaptive flooding techniques can re-route messages, helping to avoid loops and optimize the flow of data.

These techniques adaptively switch between different routing algorithms (e.g., from flooding to distance-vector or link-state routing), depending on the network’s performance and topology changes.

Flooding vs. Other Routing Algorithms

While flooding is simple, other routing algorithms are more efficient in certain network configurations. Some of the key differences include:

Link-State Routing vs Flooding:

In Link-State Routing, routers exchange their complete routing table via flooding, whereas other algorithms, such as Distance Vector Routing, use a more controlled method to disseminate routing information.

Flooding vs. Distance Vector Routing:

Distance Vector Routing minimizes the flooding overhead by sending routing information only to neighboring nodes, rather than flooding it throughout the network.

Conclusion

Flooding in computer networks remains a fundamental technique for broadcasting, routing, and message propagation. Despite its simplicity, it provides reliable network communication, especially in the absence of predefined routing paths. By understanding the flooding algorithm, its applications, and optimizations, network engineers can leverage this technique effectively in both small and large-scale networks. As technology evolves, the continued optimization of flooding algorithms will enhance their efficiency and performance in modern distributed systems.