Subscribe by Email

Thursday, August 8, 2013

Flooding - a kind of static algorithm

An algorithm designed for the distribution of the material to each and every part of the graph is referred to as the flooding algorithm. 
- The algorithm has got its name from the concept that involves inundation caused by a flood. 
- The main application of these algorithms is in graphics and computer networking. 
- These algorithms also come very handy in solving a number of mathematical problems. 
- Examples of such problems that are graph theory problems, maze problems and so on. 
- Flooding algorithm though it sounds complicated is quite a simple one. 
- Here, every incoming packet is sent via every outgoing link. 
- Only the link through which the packet arrived is saved. 

This algorithm has many applications in the following:
  1. Systems that require bridging, systems like use net.
  2. Peer to peer file sharing.
  3. Used as a part of the routing protocols such as the DVMRP, OSPF etc.
  4. Used in protocols used for the adhoc wireless networks.
Nowadays the flooding algorithm is available with its many variants. The following are two main steps that each variant follows while working:
  1. Each node in the network might act as both receiver and the transmitter.
  2. The incoming message is forwarded by the receiving node to each of its neighboring nodes except the one which is the source code.
- This causes the message to be delivered to each and every part of the network that is reachable. 
- Algorithms are required as a precaution for avoiding the wastage of the infinite loops and the duplicate deliveries and for allowing the messages for expiring. 
- All these issues are addressed partially by a variant of the flooding algorithm called the selective flooding.
- The usual flooding algorithm sends the packets to all the routers that lie in the same direction. 
- But the selective flooding algorithm does not send the packet to each router rather it selects only few of them which lie in the right direction approximately. 

Advantages and Disadvantages of Flooding Algorithm

  1. If it is possible for delivering the packet, it will be delivered but a number of times.
  2. In flooding algorithm every path in the network is naturally utilized and so the shortest path is also used.
  3. The implementation of the flooding algorithm is quite simple.
  1. The cost of the flooding algorithm can be very high because a lot of bandwidth is wasted. Even if there is one destination of the message, it will be sent to all the hosts on the network unnecessarily. If in case there occurs a denial of service attack or a ping flood, the reliability of the whole network will be affected badly.
  2. In the computer network, the message might get duplicated. This in turn can increase the load on the bandwidth of the network. This will call for increasing the complexity of the processing for rejecting the duplicates of the messages.
  3. The packets that are duplicate might keep on circulating forever, if the following precautions are not taken:
Ø  Using a time to live count or a hop count to be included with every packet. The value of the count has to include the number of the nodes through which the packets have to be passed while on the way to destination.
Ø  Each and every node should be used for keeping track of every packet that passes through it and a packet should be forwarded only once.

Ø  The network topology must be enforced without any loops. 

No comments:

Facebook activity