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.

SWITCHING - Circuit, Packet, Message Switching

Switched communication networks are those in which data transferred from source to destination is routed between various intermediate nodes. Switching is the technique by which nodes control or switch data to transmit it between specific points on a network.

In large networks, there can be multiple paths from sender to receiver. The switching technique will decide the best route for data transmission. Switching technique is used to connect the systems for making one-to-one communication.

Various switching techniques are-

1. Circuit Switching

The Circuit Switching technique establishes a dedicated path or channel between the sender and receiver for data transmission, and once a dedicated path is established then it does not terminate it until and unless the connection between the two data transmission point terminates.

Circuit switching in a network operates in a similar way as the telephone works. A complete end-to-end path must exist before the communication takes place.

In case of circuit switching technique, when any user wants to send the data, a request signal is sent to the receiver then the receiver sends back the acknowledgment to ensure the availability of the dedicated path. After receiving the acknowledgment, dedicated path transfers the data.

Circuit switching is used in public telephone network. It is used for voice transmission. Fixed data can be transferred at a time in circuit switching technology.

Communication through circuit switching has 3 phases:

• Circuit establishment
• Data transfer
• Circuit Disconnect

Advantages of Circuit Switching:

• Establishment of a dedicated channel
• Improves data transmission rate
• Improves data loss
• Improves delay in the data flow

Disadvantages of Circuit Switching:

• Establishing a dedicated channel sometimes takes a very long duration of time.
• The amount of bandwidth required is more for establishing a dedicated channel.
• Even if a channel is free, it cannot be used to transmit any other data from any other source.

2. Packet Switching

The packet switching technique transmits data through the network by breaking it down into several data packets for more efficient transfer and it also utilizes multiple vacant resources, these network devices direct or route the data packets to the destination where the receiving device then collects all of them and reassembles to get the proper orientation of the message.

The packet switching is a switching technique in which the message is sent in one go, but it is divided into smaller pieces, and they are sent individually.

The message splits into smaller pieces known as packets and packets are given a unique number to identify their order at the receiving end. Every packet contains some information in its headers such as source address, destination address and sequence number.

Packets will travel across the network, taking the shortest path as possible. All the packets are reassembled at the receiving end in correct order.

If any packet is missing or corrupted, then the message will be sent by receiver to resend the message.

If the correct order of the packets is reached, then the acknowledgement message will be sent by the receiver.

There are two approaches to Packet Switching:

Datagram Packet switching:

• It is a packet switching technology in which packet is known as a datagram, is considered as an independent entity. Each packet contains the information about the destination and switch uses this information to forward the packet to the correct destination.
• The packets are reassembled at the receiving end in correct order.
• In Datagram Packet Switching technique, the path is not fixed.
• Intermediate nodes take the routing decisions to forward the packets.
• Datagram Packet Switching is also known as connectionless switching.

Virtual Circuit Switching

• Virtual Circuit Switching is also known as connection-oriented switching.
• In the case of Virtual circuit switching, a preplanned route is established before the messages are sent.
• Call request and call accept packets are used to establish the connection between sender and receiver.
• In this method the path is fixed for the duration of a logical connection.

Advantages of Packet Switching:

• Cost-effective: In packet switching technique, switching devices do not require massive secondary storage to store the packets, so cost is minimized to some extent. Therefore, we can say that the packet switching technique is a cost-effective technique.
• Reliable: If any node is busy, then the packets can be rerouted. This ensures that the Packet Switching technique provides reliable communication.
• Efficient: Packet Switching is an efficient technique. It does not require any established path prior to the transmission, and many users can use the same communication channel simultaneously, hence makes use of available bandwidth very efficiently.

Disadvantages of Packet Switching:

• Packet Switching technique cannot be implemented in those applications that require low delay and high-quality services.
• The protocols used in a packet switching technique are very complex and requires high implementation cost.
• If the network is overloaded or corrupted, then it requires retransmission of lost packets. It also lead to the loss of critical information if errors are nor recovered.

3. Message Switching

The Message Switching Technique was developed to act as an alternative to circuit switching, this was before packet switching was introduced.

Message Switching is a switching technique in which a message is transferred as a complete unit and routed through intermediate nodes at which it is stored and forwarded.

In Message Switching technique, there is no establishment of a dedicated path between the sender and receiver.

The destination address is appended to the message. Message Switching provides a dynamic routing as the message is routed through the intermediate nodes based on the information available in the message.

Message switches are programmed in such a way so that they can provide the most efficient routes. Each and every node stores the entire message and then forwards it to the next node. This type of network is known as store and forward network.

Message switching treats each message as an independent entity. These message switched data networks are also known as a hop-by-hop system.

Advantages of Message Switching

• Data channels are shared among the communicating devices that improve the efficiency of using available bandwidth.
• Traffic congestion can be reduced because the message is temporarily stored in the nodes.
• Message priority can be used to manage the network.
• The size of the message which is sent over the network can be varied. Therefore, it supports the data of unlimited size.

Disadvantages of Message Switching

• The message switches must be equipped with sufficient storage to enable them to store the messages until the message is forwarded.
• The Long delay can occur due to the storing and forwarding facility provided by the message switching technique.

Token Ring, Token Bus

Token Ring

Token ring (IEEE 802.5) is a communication protocol in a local area network (LAN) where all stations are connected in a ring topology and pass one or more tokens for channel acquisition. A token is a special frame of 3 bytes that circulates along the ring of stations. A station can send data frames only if it holds a token. The tokens are released on successful receipt of the data frame.

Token Passing Mechanism in Token Ring

If a station has a frame to transmit when it receives a token, it sends the frame and then passes the token to the next station; otherwise it simply passes the token to the next station. Passing the token means receiving the token from the preceding station and transmitting to the successor station. The data flow is unidirectional in the direction of the token passing. In order that tokens are not circulated infinitely, they are removed from the network once their purpose is completed. 

This is shown in the following diagram −

Token Bus

Token Bus (IEEE 802.4) is a standard for implementing token ring over virtual ring in LANs. The physical media has a bus or a tree topology and uses coaxial cables. A virtual ring is created with the nodes/stations and the token is passed from one node to the next in a sequence along this virtual ring. Each node knows the address of its preceding station and its succeeding station. A station can only transmit data when it has the token. The working principle of token bus is similar to Token Ring.

Token Passing Mechanism in Token Bus

A token is a small message that circulates among the stations of a computer network providing permission to the stations for transmission. If a station has data to transmit when it receives a token, it sends the data and then passes the token to the next station; otherwise, it simply passes the token to the next station. 

This is depicted in the following diagram −

Differences between Token Ring and Token Bus

Token Ring	Token Bus
The token is passed over the physical ring formed by the stations and the coaxial cable network.	The token is passed along the virtual ring of stations connected to a LAN.
The stations are connected by ring topology, or sometimes star topology.	The underlying topology that connects the stations is either bus or tree topology.
It is defined by IEEE 802.5 standard.	It is defined by IEEE 802.4 standard.
The maximum time for a token to reach a station can be calculated here.	It is not feasible to calculate the time for token transfer.

CSMA/CD (carrier sense multiple access/collision detection)

In ETHERNET, CSMA is used on a tapped coaxial cable to which all the communicating devices are connected. On the coaxial cable, in addition to sensing carrier, it is possible for the transceivers to detect collisions. 

This variation of CSMA is referred to as carrier sense multiple access with collision detection (CSMA-CD).

CSMA/CD (carrier sense multiple access/collision detection) is a MAC (media access control) protocol. It defines how network devices respond when two devices attempt to use a data channel simultaneously and encounter a data collision. The CSMA/CD rules define how long the device should wait if a collision occurs.

CSMA/CD is a modification of pure carrier-sense multiple access (CSMA). CSMA/CD is used to improve CSMA performance by terminating transmission as soon as a collision is detected, thus shortening the time required before a retry can be attempted.

The collision detection technology detects collisions by sensing transmissions from other stations. On detection of a collision, the station stops transmitting, sends a jam signal, and then waits for a random time interval before retransmission.

The algorithm of CSMA/CD is:

• When a frame is ready, the transmitting station checks whether the channel is idle or busy.
• If the channel is busy, the station waits until the channel becomes idle.
• If the channel is idle, the station starts transmitting and continually monitors the channel to detect collision.
• If a collision is detected, the station starts the collision resolution algorithm.
• The station resets the retransmission counters and completes frame transmission.

The algorithm of Collision Resolution is:

• The station continues transmission of the current frame for a specified time along with a jam signal, to ensure that all the other stations detect collision.
• The station increments the retransmission counters.
• If the maximum number of retransmission attempts is reached, then the station aborts transmission.
• Otherwise, the station waits for a backoff period which is generally a function of the number of collisions and restart main algorithm.

This algorithm detects collisions but it does not reduce the number of collisions. It is not appropriate for large networks; performance degrades exponentially when more stations are added.