Network Routing Algorithms and Their Types
Network routing and Types of Routing Algorithms – In a wireless network routing system a base station reaches all mobile nodes with the support of present infrastructure, but in the case of an ad-hoc network routing system, the situation is different due to dynamic topology.
A destination node might be out of the scope of the source node that transmitting packet.
Therefore routing is required to find a correct path between the source node and the destination node and also to forward a packet correctly.
In a wireless network routing system with the help of an infrastructure, where cells are defined, a base station can reach all the mobile nodes through broadcasting without the need for routing process, but in the ad-hoc network routing system, each node forwards the packet to the other node in order to find the correct root.
The main differences between wired network routing and ad-hoc network routing system are as below-
- Asymmetric Links
- Redundant Links
- Interference
- Dynamic Topology
Asymmetric Links Network Routing
Asymmetric links mean links quality is different from Link A to B and link B to A.
Suppose node A gets a signal from node B but node B doesn’t get signal from B or vice versa. B node might get nothing due to weal link or B may have a better link.
Routing data collected for one side is of no value for the other side.
Redundant Links Network Routing
Wired networks have redundant links to avoid link failure also redundancy easily controlled by the network administrator in the wired network topology.
In the wireless network system to avoid network failure more redundancy is needed to survive in the situation of network disconnection.
Much redundancy incurs more overhead and costs in the wireless network.
Interference in Network Routing
In a wired network, link exists where wire exists hence no chance of interference because every connection is planned and under strict control.
But in the case of wireless network transmission is ad-hoc and highly dynamic links can create interference in the transmission of information.
Dynamic Topology
In ad-hoc network system, networking topology is highly dynamic and based on the medium characteristics those change frequently. Routing tables change frequently according to the current traffic and the current nodes.
Considering the scenario of ad-hoc networking various routing algorithms are developed and used. Some of the important routing algorithms commonly used are as follows-
-
Destination sequence distance vector
Destination sequence distance vector (DSDV) routing is an enrichment to distance vector routing for ad-hoc networks given by Perkins, 1994.
The distance vector routing algorithm is used as a routing information protocol (RIP) in wired networks. DSR works poorly with certain network changes because of the count-to-infinity problem.
In DSR each node exchanges its neighbor table from time to time with its neighbors.
Changes at one node in the network broadcast slowly through the network (step-by-step with every exchange).
This strategy do not work well in wireless ad-hoc networks, because of speedily changing network topology. This technique may create loops or inaccessible nodes within the ad-hoc network.
Therefore, DSDV now adds two techniques to the distance vector algorithm as mentioned below-
- Sequence numbers
Each routing announcement comes with a sequence number in the wireless network.
Each announcement may spread along many paths in the ad-hoc network.
The sequence order number keeps the announcement in the right order and avoids framing loops.
- Damping
Short-lived changes in the topology should not threaten the routing mechanisms. Announcement consisting of changes in the network topology currently stored are therefore not distributed further. A node waits with broadcasting if these changes are probably very temporary.
This waiting time depends on the time between the first and the best declaration of a path to a certain routed destination.
-
Dynamic source routing
In an ad-hoc network, nodes exchange packets from time to time. DSDV and distance vector algorithms update their table frequently. Nodes exchange routing data to keep a record of the current topology.
These algorithms manage routes between all the nodes, although there may be no data exchange at all. This creates useless traffic and also prevents nodes from saving battery power.
To avoids the above-mentioned overheads Dynamic source routing (DSR), therefore, divides the task of routing into two separate activities route discovery and route maintenance –
- Route discovery
A node tries to find a route to a destination only if the node has to send some information to the destination node and there is at present no well-known route.
- Route maintenance
If a node is constantly sending packets through well-known route, the node has to make sure that the route is correct. As soon as the node feels any problems with the existing route, the node has to find an alternative route.
Dynamic source routing algorithms removes all time to time routing updates and do the work as mentioned below.
If a node wants to find a route, it sends a route request with a unique identifier with the destination address as parameters.
Any node that gets the route request does the following tasks –
- If the node has already got the request that is recognized using the unique identifier, the node drops the request packet it received.
- If the node finds its own address as the destination address, it means the request has reached its target point.
- Otherwise, the node adds its own address to the list of traversed hops in the packet and broadcasts this updated route request list.
With this process, the route request collects a list of addresses showing a possible path on its way towards the destination node.
As soon as the request reaches to the destination point, the node can return the request packet containing the list to the receiver node in reverse order.
In this approach, the links work bi-directionally. If this approach is not applied, and the destination node does not maintain the route back to the initiator of the request, the destination node has to start a route discovery by itself.
In this algorithm, the destination node may receive a variety of lists containing different paths from the initiator node. It could return the best path from all the received paths.
Types of Network Routing Algorithms
Recently vast research is done on ad-hoc network routing protocols. All the routing algorithms or protocols are categorized into three categories-
- Flat routing,
- Hierarchical routing,
- Geographic-position-assisted routing
Flat routing
Flat routing protocols include all those routing protocols that do not set up a hierarchical approach in which one node works as the head of the region. In flat routing protocols, all the nodes work at the same level.
Flat routing is further divided into two subcategories:
- Proactive Network Routing
- Reactive Network Routing Protocols
Proactive Network Routing Protocols
It set up tables required for routing not considering any traffic that would require routing functions.
DSDV is a proactive protocol. Many other routing protocols belonging to this category are based on a link-state algorithm that is used for fixed networks.
Link-state algorithms flood their information about neighbors from time to time or when needed.
In mobile ad-hoc environments, this method exhibits severe drawbacks related to extra overhead on the nodes due to flooding.
Reactive Network Routing Protocols
Reactive protocols try to avoid this problem by setting up a path between the sender and the receiver only if communication is waiting.
The two most important protocols are dynamic source routing and ad-hoc on-demand distance vector protocol.
AODV acquires and maintains routes only on-demand as DSR does.
Hierarchical Network Routing
Routing algorithms like DSDV, AODV, and DSR suitable for a smaller number of
nodes and they depend on the mobility of the nodes.
For larger networks, clustering of nodes and using different routing algorithms between and within clusters can be a scalable and efficient solution to routing problems in the ad-hoc network.
The inspiration behind this technique is the locality property. Locality property means that if a cluster can be established, nodes remain within the cluster, only some nodes change the clusters.
If the topology within a cluster changes, only nodes of the cluster have to be informed about the change, and nodes of other clusters only required to know how to route the cluster.
Geographic position assisted routing approach
Geographic-position-assisted routing scheme based on the geographic position of the mobile nodes. If mobile nodes know their geographical position this can be used for routing algorithms also. It improves the overall performance of routing algorithms.
One way to obtain geographic position information is via the global positioning system (GPS).
Therefore various schemes are there to create and maintain network routing. Still, more optimization is needed to save time and space, particularly in the ad-hoc network routing.