Routing Protocol in Computer Network

Delivery

The network layer examines the handling of packets by the underlying networks. This handling is referred to as delivery of a packet.

The delivery of packet (source to final destination) can be achieved by two methods:
       
1. Direct delivery

• In this method, the source and destination of the packets are located on the same network.
• The sender can determine, if the delivery is direct. With the help of masking, the sender can extract the network address of the destination and compares this address with the addresses of the connected networks.
• If the match is found, then the delivery is direct.

2. Indirect Delivery

• In this method, the destination host is not on the same network as the deliverer. The packet is delivered directly.
• The packet moves from router to router until it reaches the same physical network as its final destination.

Routing

• To route IP packets, a host or a router has a routing table with entries for each destination or a combination of destinations.
• A static routing table contains information, which is entered manually. The administrator enters the route for each destination into the table.
• Dynamic routing table is updated periodically by using dynamic protocols like RIP, OSEP or BGP.
• The main function of the network is to route the packets from source to destination. More than one route is possible in every network, however the shortest route should be selected.
• The shortest route means, a route which passes through the least number of nodes to reach the destination.
• The routing algorithm is designed to find the shortest root and it is part of a network software.

The routing algorithm can be classified into two types:

1. Static (non-adaptive) routing algorithms

• In this type, the network topology determines the final path. All the possible paths which are already calculated are loaded into the routing table.
• Static routing is suitable for small networks.
• The disadvantage of static routing is, inability to respond quickly in case of network failure.

2. Dynamic (Adaptive) routing algorithms

• The dynamic routing algorithms can change their routing decision on the basis of  some changes made in the topology.
• Each router can check the network status by communicating with the neighbors. So, the changes in the topology are reflected to all routers.
• Finally, the router can calculate the suitable path to the final destination.
• The disadvantage of this type is, its complexity in the router.

Intra-domain Routing vs Inter-domain Routing

• An autonomous system is a group of the networks and the routers, which are operated by the network administrator. Internet can be divided into autonomous systems. Distance vector and link state routing are the examples of Intra-domain routing.
• Routing inside an autonomous system is referred to as intra-domain routing.
• Routing between two or more autonomous systems can be referred to as inter-domain routing. Path vector is an example of an inter-domain routing.

Intra-domain Routing	Inter-domain Routing
Routing takes place within an autonomous network.	Routing takes place between the two   autonomous networks.
This protocol ignores the internet outside the autonomous system.	This protocol assumes that internet consists of a collection of interconnected autonomous systems.
Protocols for Intra-domain routing are called as interior gateway protocols.	rotocol for Inter-domain routing are also called as exterior gateway protocols.
Examples: RIP and OSPF etc.	Example: BGP

Distance Vector Routing

• Distance vector routing is the dynamic routing algorithm and also known as Bellman-Ford routing algorithm and Ford- Fulkerson algorithm.
• It was designed for small network topologies.
• In this algorithm, node router constructs a table containing the distance (total cost of path) to all other nodes and distributes that vector to its immediate neighbors.
• For distance vector routing, it is assumed that each node knows the cost of the link to each of its directly connected neighbors.
• A link, which is 'down' (which is not working) is assigned as an infinite cost.



The shortest path can be computed as:




• Every node sends a message to its directly connected neighbors For example: A sends its information to B and F.
• After communicating to each directly connected node the shortest path can be easy to compute (as shown in above table).

Some issues with the Distance Vector Routing are:
1. Vulnerability to the 'Count-to-Infinity' problem is a serious issue with the distance vector.
2. It takes long time for convergence due to growth in the network.

Link State Routing

• It is a dynamic type routing algorithm.
• In this method, one or more routers can be connected by using LAN.
• When a router is booted, it sends a special request (HELLO packet) message on each point-to-point line. Then second router sends back a reply and asks who is it and the communication starts.
• To determine the cost of line or path, the router sends an ECHO packet over the line which the other router is required to send back immediately. By measuring the round-trip time and dividing it by two, the router (sender) can get a reasonable estimate of the delay.
• Link state packet can be constructed periodically or after the occurrence of some significant event. For example:  if a line or neighbor is down or it may be coming back.

Basic algorithm to distribute the link state packets:

• Each state packet has a sequence number and it is incremented for each sent packet.
• Routers can track all the source routers and sequence.
• When a new link state packet arrives, it is checked against the list of packets already entered. If the packet is new, it is forwarded on all lines (except on which it is arrived ie flooding) and discarded, if the packet is duplicate. If the sequence number is lower (than the highest one), it is rejected.

Some changes to improve the basic algorithm:

• Once  the router accumulates full set of link state packets, it can construct the entire subnet graph and Dijkshtra's algorithm can be used to construct the shortest path to all possible destination.
• Link state routing protocol uses event driven updates rather than periodic updates.
• Link state routing protocol is widely used in actual networking system.