What are applications of flooding algorithm?

- Flooding algorithm and its many other variants are used as material distributing algorithm.

- This algorithm distributes the messages to all the hosts in the entire graph. 

- This algorithm since it acts like a flood and therefore has been named so. 

- In this simple yet useful distribution or routing algorithm, every packet that a node receives is transmitted to every other outgoing link. 

This algorithm is available in many variants but in every variant the following two things are common:

1. Each node acting as receiver and transmitter.

2. Each node responsible for forwarding received message to all its neighboring nodes except the one from which the message came. 

- Thus, the messages are eventually delivered to the hosts spread across the network. 

- Flooding algorithm might have been more useful if it would have been more complex. 

- Also, then it would have been possible to avoid the duplicate messages and infinite loops that occur because of them. 

Applications of Flooding Algorithm

In this article we list some of the application of the flooding algorithm.

1. Used in computer networking

2. Used in graphics

3. These algorithms are quite useful for solving numerous mathematical problems such as the maze problems.

4. Used for solving problems in the graph theory. 

5. Used in systems which make use of bridging. 

6. Used in systems like usenet.

7. Implemented in peer – to – peer file sharing

8. Flooding algorithms are often implemented as a part of some of the routing protocols as in OSPF, DVMRP and so on. 

9. It is also used in the protocols used in the ad hoc wireless networks.

10.There is a variant of flooding algorithm called the selective flooding which is capable on addressing various issues of flooding algorithm partially by allowing the packets to be sent only in the appropriate right direction. The packets are not sent on each and every line. 

11. Another variant of the flooding algorithm called the similarity algorithm is used graph matching algorithm. 

- This variant of the flooding algorithm is quite versatile and has got an application in the schema matching. 

- Matching the contents of the two data schemas has got an important role to play in many biochemical applications, e – business and other data warehousing applications etc. 

- The similarity flooding algorithm is based on a computation that is fixed and can be used across a number of scenarios. 

- Two graphs are passed to the algorithm as the input parameters. 

- These graphs might be of catalogs, schemas or even data structures etc. 

- The algorithm then produces a mapping between the corresponding nodes of the two graphs as output. 

- It depends on the goal of the matching what subset of the mapping has to be chosen using filters. 

- After the algorithm has been executed, a human tester is expected is expected to check and verify the results. 

- The results might be adjusted by the tester if required. 

- In this method, the accuracy of the algorithm is evaluated by number of the adjustments that are necessary.

- In some cases, an accuracy metric might be used for the estimation of the labor savings that could be obtained by the users by means of this similarity flooding algorithm for obtaining a first matching pair.

- Finally, this algorithm can be deployed as an operator of very high level in a test bed that has been implemented for the management of the output mappings and the information models. 

- There are different types of matching problems and thus each type requires following a different approach. 

- For example, the relational schemas can only be matched using SQL data types.

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

Advantages:

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.

Disadvantages:

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. 

How does a definition use association play a role in data flow testing?

Definition use association is one of the terms that appear at the scene of data flow testing and quite many of us are unaware of it. This article is all about the concepts of the definition use associations and what role does they have got to play in the data flow testing. 

The definition use association forms quite an important part of the data flow testing. Let us see how! 

First we are going to discuss some concepts of the data flow testing in regard with the definition use associations and then we will discuss the role of the definition use associations in the data flow testing. 

About Data Flow Testing

- A control flow graph is an important tool that is used by the data flow testing so that the anomalies related to the data can be explored. 

- A proper path selection strategy is what that is required for detection of such anomalies. 

- The path strategy which is to be used can be decided on the basis of the data flow anomalies discovered earlier. 

- Data flow testing is nothing but a family of path testing strategies through the control of a software program or application. 

- The path testing is required so that the sequence of possible events associated with the objects’ status can be explored.

- It is necessary that you keep the number of paths sufficient and sensible so that no object is left without initialization and without being used at least once in its life time without carrying out unnecessary testing. 

- Data flow testing is comprised of two types of anomaly detection namely:

1. Static analysis: It is carried out on the program code without its actual execution. It involves finding syntax errors.

2. Dynamic analysis: It is carried out on a program while it is in a state of execution. It involves finding the logical errors.

- The data objects have been categorized in to several categories so as to make data flow testing much easy:

1. Defined, created, initialized (d)
2. Killed, undefined, released (k)
3. Used (u): in calculations (c)
4. In predicates (p)

Anomalies discovered by the static analysis are meant to be handled by the compiler itself. But the static analysis and the dynamic analysis do not suffice altogether. A rigorous path testing is required. 

About Definition Use Associations

- The definition use associations or the “du segments” are the path segments whose last links have a use of variable X and are simple and definition clear. 

- Typically  a definition use association is a combination of triple elements (x, d, u) where:

1. X is the variable
2. D is the node consisting of a definition of variable x
3. U is either a predicate node or a statement depending up on the case and consists of a use of x.

- A sub path from d to u is also included in the flow graph with no definition of variable x occurring in between the d and u. 

- Below mentioned are some examples of the def use associations:

1. (x, 3, 4)
2. (x, 1, 4)
3. (y, 2, (4, t))
4. (z, 2, (3, t)) etc.

- Some of the most common data flow testing strategies are:

1. All uses (AU)
2. All DU paths (ADUP) and many more.

- First advice for effective data flow testing would be to resolve all the data flow anomalies discovered above. 

- Carrying out data flow operations on the same variable and within the same routines can also reap you good results. 

- It is advisable to use defined types and strong typing wherever it is possible in the program. 

Cause-Effect Graphing is a black box testing - Explain?

So many testing techniques have been categorized under the black box testing and the cause effect graphing is one of them and that is what the whole article is all about.

- A directed graph created for the purpose of mapping of the set of causes to a set of effects is nothing but a cause effect graph.
- The causes mapped in the graph are merely the input to a software system or application and the effects can be thought of as the corresponding outputs.
- The right of the cause effect graph houses all the effects with their corresponding nodes and the left side shelters all the causes and along with their corresponding nodes.
- A graph representing causes and effects in such a way is said to be a typical cause effect graph.
- It may also make use of certain intermediate nodes for the representation of the relation between the input and the output using the logical operators like AND, OR etc.
- The constraints can be effectively added to the effects and causes in the graph and these represented as the labelled edges using a dashed line along with the symbol of the constraint.

Constraint Symbols for the Causes:
1. E – exclusive
2. OaOO – one and only one
3. I – at least one

- The first constraint is used to state that at any instant any two causes (say cause 1 and cause 2) cannot be true simultaneously.
- The second constraint i.e., the inclusive constraint is used to state that at least one of the two or more numbers of causes must be true.
- The third constraint “one and only one” is used to state that the only one among all the constraints can be true.

Constraints for the Effects

1. R – requires
2. M – mask

- These are the only two valid constraints for the effects.
- The first one states that if one of the causes is true, then it implies that the other one also must be true and it also states that only one of the two constraints can be true and other can be false.
- The second constraint i.e., the mask constraint states just the opposite of the first constraint i.e., if one of the effects is true, then the other must be false.

"One point to be noted here is that the mask constraint only relates to the effects rather than relating to the causes like other constraints."

The direction of the graph is represented as shown below:
Causes -> Intermediate nodes -> Effects

Normal Forms of Cause Effect Graph

The cause effect graph is always rearranged in such a way that at any point between any input and output there lays only one node. Two normal forms of the cause effect graph have been identified:

- Conjunctive normal form
- Disjunctive normal form

When is Cause Effect Graphing performed?

One of the main purposes of the cause effect graph is the generation of the reduced decision table. The cause effect graphing is performed after the following tasks have been completed:

1. All the requirements have been reviewed to check out for any ambiguity.
2. All the requirements have been reviewed for their content.
3. It has been ensured that the requirements are complete and correct.

Cause effect graphing is basically used for hardware testing, but now it has been adopted for the use in the software testing.

It takes in to consideration only the desired external behaviour of the system and therefore it has been categorized as a black box testing technique and only selects the test cases that represent a logical relation between the causes and effects for the production of the test cases.

Methods of black box testing - Graph based testing methods and Equivalence Partitioning

Black Box Testing is testing without knowledge of the internal workings of the item being tested. There are four black box testing methods:

Graph-based Testing Methods
Basic idea: A "cause" is an input condition, and an "effect" is a specific sequence of computations to be performed. A cause-effect graph is basically a directed graph that describes the logical combinations of causes and their relationship to the effects to be produced.
- Black-box methods based on the nature of the relationships (links) among the program objects (nodes), test cases are designed to traverse the entire graph.
- A graph is created between the objects and the relationships.
- From the graph, each object relationship is identified and test cases written accordingly to discover the errors.

Equivalence Partitioning
This method divides the input domain of a program into classes of data from which test cases can be derived. It reduces the number of test cases. The guidelines of Equivalence Partitioning are :
- If an input condition specifies a range, one valid and two invalid equivalence classes are defined.
- If an input condition requires a specific value, then one valid and two invalid equivalence classes are defined.
- If an input condition specifies a member of a set, then one valid and one invalid equivalence class are defined.
- If an input condition is boolean, then one valid and one invalid equivalence class are defined.