Routing Protocol

A routing protocol is a set of rules and conventions used by routers to determine the best path for forwarding network traffic from its source to its destination within a computer network.

Interior Routing

Interior Routing, also known as Interior Gateway Protocol (IGP), involves the exchange of routing information within a single Autonomous System (AS). An Autonomous System is a collection of IP networks and routers under the control of a single organization, presenting a common routing policy to the internet.

Exterior Routing

Exterior Routing, also known as Exterior Gateway Protocol (EGP), involves the exchange of routing information between different Autonomous Systems (ASes). It is used to facilitate routing between separate organizations or networks.

Distance Vector Routing

Distance Vector Routing is a type of routing algorithm used in computer networks to determine the best path for routing data packets from a source to a destination. It is a distributed algorithm where each router in the network maintains a table that contains information about the distance (cost) to reach various destinations.

Distance Vector Routing Table 

Initialization

Sharing

The whole idea of distance vector routing is the sharing of information between neighbors. 

Although node A does not know about node E, node C does. 

So if node C shares its routing table with A, node A can also know how to reach node E. 

On the other hand, node C does not know how to reach node D, but node A does. 

If node A shares its routing table with node C, node C also knows how to reach node D. 

In other words, nodes A and C, as immediate neighbors, can improve their routing tables if they help each other. 

Updating

When to update 

The table is sent  periodically and when there is a change in the table. 

Periodic Update A node sends its routing table, normally every 30 s, in a periodic update. 

The period depends on the protocol that is using distance vector routing.

2. Link State Routing 

Link state routing has a different philosophy from that of distance vector routing.

 In link state routing, each node in the domain has the entire topology of the domain the list of nodes and links, how they are connected including the type, cost (metric), and condition of the links (up or down)-

The node can use Dijkstra's algorithm to build a routing table. 

Concept of Link State Routing

Link State Knowledge

Building Routing Tables

In link state routing, four sets of actions are required to ensure that each node has the routing table showing the least-cost node to every other node. 

1. Creation of the states of the links by each node, called the link state packet (LSP). 

2. Dissemination of LSPs to every other router, called flooding, in an efficient and reliable way.

3. Formation of a shortest path tree for each node. 

4. Calculation of a routing table based on the shortest path tree. 

Creation of Link State Packet (LSP)

A link state packet can carry a large amount of information. 

For the moment, however, we assume that it carries a minimum amount of data: the node identity, the list of links, a sequence nThe first two, node identity and the list of links, are needed to make the topology. 

The third, sequence number, facilitates flooding and distinguishes new LSPs from old ones.

 The fourth age prevents old LSPs from remaining in the domain for a long time. 

LSPs are generated on two occasions:

1. When there is a change in the topology of the domain. 

2. On a periodic basis. The timer set for periodic dissemination is normally in the range of 60 min or 2 h based on the implementation. 

Flooding of LSPs

After a node has prepared an LSP, it must be disseminated to all other nodes, not only to its neighbors. The process is called flooding and based on the following: 

1. The creating node sends a copy of the LSP out of each interface. 

2. A node that receives an LSP compares it with the copy it may already have. 

If the newly arrived LSP is older than the one it has (found by checking the sequence number), it discards the LSP. 

If it is newer, the node does the following: 

a. It discards the old LSP and keeps the new one. 

b. It sends a copy of it out of each interface except the one from which the packet arrived. 

Formation of Shortest Path Tree: Dijkstra Algorithm

After receiving all LSPs, each node will have a copy of the whole topology. 

A tree is a graph of nodes and links; one node is called the root. 

All other nodes can be reached from the root through only one single route. 

A shortest path tree is a tree in which the path between the root and every other node is the shortest. 

Dijkstra’s Algorithm

Formation of shortest path tree