-a hybrid (combination of adaptive and non adaptive) routing algorithm using Breadth First Search.
Abstract:
(Keywords : Dijkstra, Parallel transmission strategy, Hop Counter method.)
Selective flooding is a more practical version of flooding (static) routing algorithm that selects the outgoing line for data packet transmission on the basis of approximate or near right direction. It is static (non adaptive nature) in the sense that it does not utilizes the estimations or calculations of present traffic and network topology for its routing decisions.
Here I propose a more optimized version of this algorithm that is a hybrid possessing both adaptive and non adaptive nature. This optimized variant will work as follows.
Step 1. First, we use Dijkstra (1959) algorithm to find the shortest path length between the source and destination node. We set this path as the standard path with path length as zero. (Dijkstra is O (vlgv + E) if we implement the minimum-priority queue as Fibonacci Heap in the final relaxation step of the algorithm).
Step 2. Next, using the source node or the source vertex S, we implement the Breadth First Search Algorithm (O (V+E)) to construct the BFS Tree, so that all the possible / reachable vertices from S can be found.
Step 3. Using Hop-counter method for selective flooding (Andrew S. Tanenbaum, Computer Networks, fourth Edition), we find the path length of all the path of the tree generated in step 2 (ie. BFS Tree).
Step 4. Now, since path length of all the routes are known, we sort these paths in increasing order of their path length as shown in figure 1 (assuming each path length to be unity).
B C E A D
.
Route Path length ABCDE 5 ABCE 4 ADE 3 
Fig 1.
To transmit packets along the network, parallel transmission strategy would be followed such that for the variable length long data packets (longer than the maximum packet size), different parts would be sent in parallel to different routes starting from the standard route (path length Zero) and selecting the routes in increasing order of path length. i.e. if we have three parts p1, p2 and p3 of a packet P than p1 would be routed to ADE, p2 to ABCE and p3 to ABCDE simultaneously.
The algorithm is optimized on the basis of network topology information and network load. [1] For network topology, all the routers will have address information of all their adjacent nodes (as given by BFS Tree). And whenever there is a change expected in the topology, the BFS algorithm needs to be run again. [2] We use the link static routing algorithm (a dynamic routing algorithm) to form the routing table of all the paths so that the idea of network load can be accessed for all the active paths transmitting data according to the above parallel transmission strategy.(here we haven’t used the distance vector routing algorithm for constructing the table due to its disadvantages over link vector). The advantages of using BFS to make this approach hybrid is to improve the delay by parallel sending of packets to different routes depending on their increasing path length and so as to also reduce the quantity of the bandwidth consumed. This would improve the throughput as well. Using it, we also eliminated any need whatsoever to consider the worst case, maximum length (diameter of the subnet) from the source S.
