Routing Algorithms

Routing is process of establishing the routes that data packets must follow to reach the destination. In this process, a routing table is created which contains information regarding routes which data packets follow. Various routing algorithm are used for the purpose of deciding which route an incoming data packet needs to be transmitted on to reach destination efficiently. 

1. Non-Adaptive / Static Routing algorithm:

Non Adaptive routing algorithm is also known as a static routing algorithm. When booting up the network, the routing information stores to the routers. Non Adaptive routing algorithms do not take the routing decision based on the network topology or network traffic.

The Non-Adaptive Routing / Static algorithm is of two types:

Flooding: In case of flooding, every incoming packet is sent to all the outgoing links except the one from it has been reached. The disadvantage of flooding is that node may contain several copies of a particular packet.

Random walks: In case of random walks, a packet sent by the node to one of its neighbors randomly. An advantage of using random walks is that it uses the alternative routes very efficiently.

2. Adaptive / Dynamic Routing algorithm

An adaptive routing algorithm is also known as dynamic routing algorithm. This algorithm makes the routing decisions based on the topology and network traffic. The main parameters related to this algorithm are hop count, distance and estimated transit time.

An adaptive routing algorithm can be classified into three types:

Centralized algorithm: It is also known as global routing algorithm as it computes the least-cost path between source and destination by using complete and global knowledge about the network. This algorithm takes the connectivity between the nodes and link cost as input, and this information is obtained before actually performing any calculation. Link state algorithm is referred to as a centralized algorithm since it is aware of the cost of each link in the network.

Isolation algorithm: It is an algorithm that obtains the routing information by using local information rather than gathering information from other nodes.

Distributed algorithm: It is also known as decentralized algorithm as it computes the least-cost path between source and destination in an iterative and distributed manner. In the decentralized algorithm, no node has the knowledge about the cost of all the network links. In the beginning, a node contains the information only about its own directly attached links and through an iterative process of calculation computes the least-cost path to the destination. A Distance vector algorithm is a decentralized algorithm as it never knows the complete path from source to the destination, instead it knows the direction through which the packet is to be forwarded along with the least cost path.

Comparison of Adaptive and Non-adaptive Routing algorithms:

Basis Of Comparison	Adaptive Routing algorithm	Non-Adaptive Routing algorithm
Define	Adaptive Routing algorithm is an algorithm that constructs the routing table based on the network conditions.	The Non-Adaptive Routing algorithm is an algorithm that constructs the static table to determine which node to send the packet.
Usage	Adaptive routing algorithm is used by dynamic routing.	The Non-Adaptive Routing algorithm is used by static routing.
Routing decision	Routing decisions are made based on topology and network traffic.	Routing decisions are the static tables.
Categorization	The types of adaptive routing algorithm are Centralized, isolation and distributed algorithm.	The types of Non Adaptive routing algorithm are flooding and random walks.
Complexity	Adaptive Routing algorithms are more complex.	Non-Adaptive Routing algorithms are simple.

Network Devices - Switch,Hub

Switch – A switch is a multiport bridge with a buffer and a design that can boost its efficiency (a large number of ports imply less traffic) and performance. A switch is a data link layer device. The switch can perform error checking before forwarding data that makes it very efficient as it does not forward packets that have errors and forward good packets selectively to correct port only.  In other words, switch divides collision domain of hosts, but broadcast domain remains same. 

Hub – A hub is basically a multiport repeater. A hub connects multiple wires coming from different branches, for example, the connector in star topology which connects different stations. Hubs cannot filter data, so data packets are sent to all connected devices.  In other words, collision domain of all hosts connected through Hub remains one.  Also, they do not have the intelligence to find out best path for data packets which leads to inefficiencies and wastage. 

 Types of Hub 

• Active Hub: - These are the hubs which have their own power supply and can clean, boost, and relay the signal along with the network. It serves both as a repeater as well as wiring centre. These are used to extend the maximum distance between nodes.
• Passive Hub: - These are the hubs which collect wiring from nodes and power supply from active hub. These hubs relay signals onto the network without cleaning and boosting them and can’t be used to extend the distance between nodes.
• Intelligent Hub: - It work like active hubs and include remote management capabilities. They also provide flexible data rates to network devices. It also enables an administrator to monitor the traffic passing through the hub and to configure each port in the hub.

Network Devices - Router

Routers – A router is a device like a switch that routes data packets based on their IP addresses. Router is mainly a Network Layer device. Routers normally connect LANs and WANs together and have a dynamically updating routing table based on which they make decisions on routing the data packets. Router divide broadcast domains of hosts connected through it.

A router is more capable as compared to other network devices, such as a hub, switch, etc., as these devices are only able to execute the basic functions of the network. For example, a hub is a basic networking device that is mainly used to forward the data between connected devices, but it cannot analyze or change anything with the transferring data. On the other hand, the router has the capability to analyze and modify the data while transferring it over a network and it can send it to another network.

A router analyzes a destination IP address of a given packet header and compares it with the routing table to decide the packet's next path. The list of routing tables provides directions to transfer the data to a particular network destination. They have a set of rules that compute the best path to forward the data to the given IP address.

Networking Devices - Gateways

Gateway – A gateway, as the name suggests, is a passage to connect two networks together that may work upon different networking models. They basically work as the messenger agents that take data from one system, interpret it, and transfer it to another system. Gateways are also called protocol converters and can operate at any network layer. Gateways are generally more complex than switch or router.

The gateways are used to connect two networks that do not communicate with the same network protocol, so it is necessary to translate these protocols between both networks.

Characteristics of Gateways

1. Gateways provide full protocol conversion from one proprietary LAN technology to another, i.e. Ethernet to token ring or FDDI (Fiber Distributed Data Interface) or any other standard or protocol rather than encapsulation.

2. Uses higher layers of the OSI model, perhaps through layer 7, the application layer. IBM SNA(Systems Network Architecture), DECnet, Internet TCP/IP and other protocols can be converted from network-to-network.

3. Unlike bridges and routers, gateways operate slowly because of protocol conversion. So, they may create bottlenecks of congestion during periods of peak usage.

Networking Devices - Bridge

Bridge – A bridge operates at data link layer. A bridge is a repeater, with add on functionality of filtering content by reading the MAC addresses of source and destination.

Bridges can examine MAC addresses (also called hardware addresses or physical addresses) in each data packet that circulates through the segments of the network that connects the bridge. By knowing which MAC addresses reside in each of the segments of the network, the bridge can prevent data traffic from a specific segment from passing to another segment of the network that also connected to the bridge.

It passes information from one LAN segment to another based on the destination address of the packet. When a bridge receives data through one of its ports, it checks the data for a MAC address. If this address matches that of the node connected to other port, the bridge sends this data through this port. This action is called forwarding. If the address does not match with any node connected to other port, the bridge discards it. This action is called filtering.

Unlike repeaters, bridges have buffers to store and forward packets in the event that the destination link is congested with traffic.

It is also used for interconnecting two LANs working on the same protocol. It has a single input and single output port.

Types of Bridges:

Transparent Bridges: - A transparent bridge is a common type of bridge that observes incoming network traffic to identify media access control (MAC) addresses. These bridges operate in a way that is transparent to all the network's connected hosts. A transparent bridge records MAC addresses in a table that is much like a routing table and evaluates that information whenever a packet is routed toward its location. A transparent bridge may also combine several different bridges to better inspect incoming traffic. Transparent bridges are implemented primarily in Ethernet networks.

Source Routing Bridges: - Source routing bridge decides the route between two hosts. Source routing bridge uses the MAC destination address of a frame to direct it by the source routing algorithm. In source routing, the route over which the frame is to send is known to every station on the extended LAN. The routing information is stored in the frames. 

Difference between Transparent Bridge and Source Routing Bridge:

S.NO.

TRANSPARENT BRIDGE

SOURCE ROUTING BRIDGE

1.	Transparent bridge service is connectionless.	Source Routing Bridge service is connection oriented.
2.	In transparent bridge mechanism bridges automatically develop a routing table.	In source routing bridge, bridges do not maintain any routing information.
3.	Transparent bridge does not support multipath routing.	Source routing bridge can make use of multiple path to same destination.
4.	The path used by transparent bridge between any two hosts may not be the optimal path.	Source route bridge always uses the optimal path.
5.	Failures are handled by the transparent bridge on its own.	Host handles the failure of bridge on its own.
6.	Transparent bridges are fully transparent to the users.	Source routing bridges are not visible to the hosts.
7.	The frame processing delay is more.	The frame processing delay is less.
8.	Load sharing is not possible through blocked routes.	Load sharing is possible by judicious choice of routes.

Networking Devices - Repeater

Hardware devices that are used to connect computers, printers, fax machines and other electronic devices to a network are called network devices. These devices transfer data in a fast, secure and correct way over same or different networks. Network devices may be inter-network or intra-network.

Repeater – A repeater operates at the physical layer. Repeater’s job is to regenerate the signal over the same network before the signal becomes too weak or corrupted so as to extend the length to which the signal can be transmitted over the same network.

Repeaters do not amplify the signal. When the signal becomes weak, they copy the signal bit by bit and regenerate it at the original strength.

It is a network device used to regenerate or replicate a signal. Repeaters are used in transmission systems to regenerate analog or digital signals distorted by transmission loss. Analog repeaters frequently can only amplify the signal while digital repeaters can reconstruct a signal to near its original quality.

In a data network, a repeater can relay messages between subnetworks that use different protocols or cable types. Hubs can operate as repeaters by relaying messages to all connected computers. A repeater cannot do the intelligent routing performed by bridges and routers.