Ch.

4 Routing Protocols
Contents:
1. Forwarding

2. Structure of a Router

3. Routing Tables

4. Intra – And Inter-Domain Routing

5. Distance Vector Routing

6. RIP - Routing Information Protocol (RIP)

7. OSPF - Open Shortest Path First

8. BGP - Border Gateway Protocol

9. Multicast Routing
Introduction to router
A Router is a networking device that forwards data packets between computer networks. One or
more packet-switched networks or subnetworks can be connected using a router. By sending data
packets to their intended IP addresses, it manages traffic between different networks and permits
several devices to share an Internet connection.

Let us understand this by a very general example, suppose you search for www.google.com in
your web browser then this will be a request which will be sent from your system to google`s
server to serve that webpage, now your request which is nothing but a stream of packets don`t
just go to the google`s server straightaway they go through a series of networking devices known
as a router which accepts this packets and forwards them to correct path and hence it reaches to
the destination server. A router has several interfaces by which it can connect to several host
systems.
Types of Router
There are several types of routers available in the market. Some of them are mentioned
below
1. Broadband Routers: These are one of the important kinds of routers. It is used to do
different types of things. it is used to connect computers or it is also used to connect to
the internet.
2. Wireless routers: These routers are used to create a wireless signal in your office or
home. Wireless routers receive data packets over wired broadband, convert the packets
written in binary code into radio signals that are picked up by electronic devices, and
then convert them back into previous packets.
3. Edge Routers: As the name indicates, these are located at the edges usually connected
to an Internet Service Provider, and distribute packets across multiple packets.
4. Core Routers: Core routers distribute packets within the same network. The main task is
to carry heavy data transfers
Functions of a Router
1. Forwarding: The router receives the packets from its input ports, checks its header, performs some basic
functions like checking checksum, and then looks up to the routing table to find the appropriate output
port to dump the packets onto, and forwards the packets onto that output port.
2. Routing: Routing is the process by which the router ascertains what is the best path for the packet to
reach the destination, It maintains a routing table that is made using different algorithms by the router
only.
3. Network Address Translation (NAT): Routers use NAT to translate between different IP address
ranges. This allows devices on a private network to access the internet using a single public IP address.
4. Security: Routers can be configured with firewalls and other security features to protect the network
from unauthorized access, malware, and other threats.
5. Quality of Service (QoS): Routers can prioritize network traffic based on the type of data being
transmitted. This ensures that critical applications and services receive adequate bandwidth and are not
affected by lower-priority traffic.
6. Virtual Private Network (VPN) connectivity: Routers can be configured to allow
remote users to connect securely to the network using a VPN.

7. Bandwidth management: Routers can be used to manage network bandwidth by

controlling the amount of data that is allowed to flow through the network. This can
prevent network congestion and ensure that critical applications and services receive
adequate bandwidth.

8. Monitoring and diagnostics: Routers can be configured to monitor network traffic

and provide diagnostics information in the event of network failures or other issues.
This allows network administrators to quickly identify and resolve problems.
Forwarding
The process of packet forwarding simply implies the forwarding of incoming packets to their
intended destination.
● Internet is made up of generally two terms- Interconnection and Network. So, it is a
connection to a large collection of networks. A packet that is to be forwarded may be
associated with the same network as the source host or may belong to a destination host
in a different network. Thus, it depends on the destination how much a packet may need to
travel before arriving at its destination.
● The router is responsible for the process of packet forwarding. It accepts the packet from
the origin host or another router in the packet’s path and places it on the route leading to
the target host.
● The routing table is maintained by the router which is used for deciding the packet
forwarding.
Packet Forwarding in Router:
Routers are used on the network for forwarding a packet from the local network to the remote network. So, the
process of routing involves the packet forwarding from an entry interface out to an exit interface.

Working:

The following steps are included in the packet forwarding in the router-
● The router takes the arriving packet from an entry interface and then forwards that packet to another
interface.
● The router needs to select the best possible interface for the packet to reach the intended destination as
there exist multiple interfaces in the router.
● The forwarding decision is made by the router based on routing table entries. The entries in the routing
table comprise destination networks and exit interfaces to which the packet is to be forwarded.
● The selection of exit interface relies on- firstly, the interface must lead to the target network to which
the packet is intended to send, and secondly, it must be the best possible path leading to the destination
network.
Packet Forwarding Techniques:
● Next-Hop Method: By only maintaining the details of the next hop or next router in the packet’s
path, the next-hop approach reduces the size of the routing table. The routing table maintained
using this method does not have the information regarding the whole route that the packet must
take.
● Network-Specific Method: In this method, the entries are not made for all of the destination
hosts in the router’s network. Rather, the entry is made of the destination networks that are
connected to the router.
● Host-Specific Method: In this method, the routing table has the entries for all of the destination
hosts in the destination network. With the increase in the size of the routing table, the efficiency
of the routing table decreases. It finds its application in the process of verification of route and
security purposes.
● Default Method: Another technique to simplify routing is called the default method. Host A is connected
to a network with two routers. Router R1 routes the packets to hosts connected to network N2. However,
for the rest of the Internet, router R2 is used. So instead of listing all networks in the entire Internet, host A
can just have one entry called the default (normally defined as network address 0.0.0.0).
Default method:
Architecture of a Router
A Generic router consists of the following components:
1. Input Port: This is the interface by which packets are admitted into the router, it performs
several key functions as terminating the physical link at the router, this is done by the
leftmost part in the below diagram, and the middle part does the work of interoperating
with the link-layer like decapsulation, in the last part of the input port the forwarding table
is looked up and is used to determine the appropriate output port based on the
destination address.
1. Switching Fabric: This is the heart of the Router, It connects the input ports with the output ports.
It is kind of a network inside a networking device. The switching fabric can be implemented in
several ways some of the prominent ones are:
● Switching via memory: In this, we have a processor which copies the packet from input
ports and sends it to the appropriate output port. It works as a traditional CPU with input
and output ports acting as input and output devices
● Switching via bus: In this implementation, we have a bus that connects all the input
ports to all the output ports. On receiving a packet and determining which output port it
must be delivered to, the input port puts a particular token on the packet and transfers it
to the bus. All output ports can see the packets but they will be delivered to the output
port whose token has been put in, the token is then scraped off by that output port and
the packet is forwarded
● Switching via interconnection network: This is a more sophisticated network, here
instead of a single bus we use a 2N bus to connect n input ports to n output ports.
3. Output Port: This is the segment from which packets are transmitted out of the router. The output port
looks at its queuing buffers (when more than one packets have to be transmitted through the same output
port queuing buffers are formed) and takes packets, does link layer functions, and finally transmits the
packets to an outgoing link

4. Routing Processor: It executes the routing protocols, and it works like a traditional CPU. It employs various routing
algorithms like the link-state algorithm, distance-vector algorithm, etc. to prepare the forwarding table, which is looked up
to determine the route and the output port.
Routing Protocols
Routing Protocols are the set of defined rules used by the routers to communicate between source &
destination. They do not move the information from source to a destination, but only update the routing
table that contains the information.
Network Router protocols helps you to specify way routers communicate with each other. It allows the
network to select routes between any two nodes on a computer
Types of Routing Protocols
There are mainly two types of Network Routing Protocols
● Static
● Dynamic
Static Routing Protocols
● Static routing protocols are used when an administrator manually assigns the
path from source to the destination network. It offers more security to the
network.
● Static Routing is also known as Nonadaptive Routing.
● It is a technique in which the administrator manually adds the routes in a
routing table.
● A Router can send the packets for the destination along the route defined by
the administrator.
● In this technique, routing decisions are not made based on the condition or
topology of the networks.
Advantages Of Static Routing

Following are the advantages of Static Routing:

○ No Overhead: It has ho overhead on the CPU usage of the router.

Therefore, the cheaper router can be used to obtain static routing.
○ Bandwidth: It has not bandwidth usage between the routers.
○ Security: It provides security as the system administrator is allowed
only to have control over the routing to a particular network.
Disadvantages
Following are the disadvantages of Static Routing:

○ For a large network, it becomes a very difficult task to add each route
manually to the routing table.
○ The system administrator should have a good knowledge of a topology as
he has to add each route manually.
○ Whenever link fails all the network goes down which is not feasible in small
networks.
Dynamic Routing Protocols

● Dynamic routing is a networking technique that provides optimal data routing. Unlike static routing, dynamic
routing enables routers to select paths according to real-time logical network layout changes.

● Dynamic routing uses multiple algorithms and protocols. The most popular are Routing Information Protocol
(RIP) and Open Shortest Path First (OSPF).

● Dynamic routing protocols allow routers to share information about the network with other routers to allow them
to select the best path to reach a destination.
Advantages of Dynamic Routing:
○ Beneficial in Performance as well as scalable networking with a high frequency of data on nodes.
○ Makes fewer mistakes as it reroutes itself compared to other routing protocols.
○ No need to be manually configured by the admin.
○ Shares information about the network with each other makes them more reliable to work efficiently.

Disadvantages of Dynamic Routing:

○ It is more expensive in terms of CPU and bandwidth usage.

○ It is less secure as compared to default and static routing.
What Are Routing Tables?
Before we dive into routing tables, let’s first define routers. A router is a device that acts as a gateway to a network
and is also responsible for forwarding packets or messages to destination addresses. In addition, a router
determines the best routes for forwarding packets based on the information stored in its routing table:
A routing table is a table or database that stores the location of routers based on their IP addresses. This
table acts as an address map to various networks, and is usually stored in the RAM of most routers or forwarding
devices. As such, a routing table contains information about various networks, and how to get to them.

We can generate routing tables dynamically or statically. We usually achieve dynamic generation with the help of
routing protocols. In contrast, we achieve static generation by manually entering routes into a routing table. With the
dynamic generation of entries, the routing protocols share information with different routes on how to get to different
networks.
Routing Table Entries

Now that we’ve defined routing tables, let’s take a look at the content in routing table entries:
Components of Routing Table Entries

An entry in a routing table is usually a route to a specific network. The basic components of
each entry in the routing table are:

● Destination address: this refers to the IP address of the destination network.

● Subnet mask/Netmask: this refers to the class or range of the destination address. It’s
used to map the destination address to the right network.
● Gateway/Next Hop: this refers to the next IP address to which the packet is forwarded.
● Interface: this refers to the outgoing interface that connects to the destination.
● Metric: this assigns a value to each route to ensure that optimal routes are chosen for
sending packets. In some instances, the metric is the number of hops or number of routers
to be crossed to get to the destination network. If multiple routes exist, the route with the
lowest metric is usually chosen.
A Routing Table Entry Example

Now that we’ve listed the components of a routing table entry, let’s dive into understanding an entry based on an
example. We’ll use the routing table given previously.

Looking at the first entry below, suppose PC1 would like to send a packet to PC3 on the destination at 101.25.67.0.
However, PC3 is not on PC1’s network, so PC1 forwards this packet to Router A. Upon arrival at Router A, the router
checks its routing table for a path to destination 101.25.67.0:
Since a path exists, the packet will be forwarded to the gateway at 10.0.0.2 through interface eth3 on Router A.

Now let’s consider the second entry. Suppose a user on PC1 wants to send a packet to PC25 on the network
200.0.2.0. Router A will check its routing table for an entry to the address on which PC25 is located. Since there is no
recorded entry, Router A forwards this packet to the default gateway at 10.0.0.1 through the interface eth0 to other
networks connected to it:
The default gateway route is always present in any routing table. It’s used when there is no entry for a specific network
on the routing table. The default gateway usually connects to other remote networks. For example, in a home
environment, the default gateway is connected to the Internet.

In the third and final entry, just like the first entry, a packet addressed to destination 192.25.67.0 will be forwarded to
the gateway at 10.0.0.3 through interface eth5:
Types of Routing Table Routes

Additionally, it’s important to note that some routing entries also capture information on the type of route
present. In routing, several types of routes exist. For instance, a route can be one of the following:

● Directly connected route: refers to a route to a network that is directly connected to a router’s interface
● Remote routes: refers to a route to a remote network usually learned dynamically through routing
protocols
Entries of an IP Routing Table:
A routing table contains the information necessary to forward a packet along the best path toward its
destination. Each packet contains information about its origin and destination. Routing Table provides the
device with instructions for sending the packet to the next hop on its route across the network.
Each entry in the routing table consists of the following entries:
1. Network ID:
The network ID or destination corresponding to the route.
2. Subnet Mask:
The mask that is used to match a destination IP address to the network ID.
3. Next Hop:
The IP address to which the packet is forwarded
4. Outgoing Interface:
Outgoing interface the packet should go out to reach the destination network.
5. Metric:
A common use of the metric is to indicate the minimum number of hops (routers crossed) to the
Routing table entries can be used to store the following types of routes:
● Directly Attached Network IDs
● Remote Network IDs
● Host Routes
● Default Route
● Destination

When a router receives a packet, it examines the destination IP address, and looks up into its
Routing Table to figure out which interface packet will be sent out.
Distance Vector Routing
Distance vector routing algorithm is also called as Bellman-Ford algorithm or Ford
Fulkerson algorithm as this algorithm is used to find the shortest route from one node to
another node in the network.

The routing protocol is used to calculate the best route from source to destination based
on the distance or hops as its primary metric to define an optimal path. The distance
vector refers to the distance to the neighbor nodes, where routing defines the routes to
the established node.

The Distance Vector routing algorithm(DVR) shares the information of the routing table
with the other routers in the network and keeps the information up-to-date to select an
optimal path from source to destination.
The Bellman-Ford algorithm is defined as :
Note :

● In the distance vector routing protocol, only distance vector information is

exchanged next-hop values are not exchanged.
● while creating a new routing table, only the distance vector information sis
hared that to its neighbor which has a direct link. The old router tables are not
taken into consideration only newly updated router information is used.
● The process of updating the routing table keeps on repeating periodically to
update the shortest path in case the link goes down or there is a topology
change.
● Distance vector routing faces an account-to-infinityproblem.
Routing information protocol
RIP stands for Routing Information Protocol. RIP is an intra-domain routing protocol used
within an autonomous system. Here, intra-domain means routing the packets in a defined
domain, for example, web browsing within an institutional area. To understand the RIP
protocol, our main focus is to know the structure of the packet, how many fields it contains,
and how these fields determine the routing table.
Before understanding the structure of the packet, we first look at the following points:

○ RIP is based on the distance vector-based strategy, so we consider the entire structure as a
graph where nodes are the routers, and the links are the networks.
○ In a routing table, the first column is the destination, or we can say that it is a network address.
○ The cost metric is the number of hops to reach the destination. The number of hops available
in a network would be the cost. The hop count is the number of networks required to reach the
destination.
○ In RIP, infinity is defined as 16, which means that the RIP is useful for smaller networks or
small autonomous systems. The maximum number of hops that RIP can contain is 15 hops,
i.e., it should not have more than 15 hops as 16 is infinity.
○ The next column contains the address of the router to which the packet is to be sent to reach
the destination.
How is hop count determined?
RIP Message Format
Now, we look at the structure of the RIP message format. The message format is used to share information among different routers.
The RIP contains the following fields in a message:
○ Command: It is an 8-bit field that is used for request or reply. The value of the
request is 1, and the value of the reply is 2.
○ Version: Here, version means that which version of the protocol we are using.
Suppose we are using the protocol of version1, then we put the 1 in this field.
○ Reserved: This is a reserved field, so it is filled with zeroes.
○ Family: It is a 16-bit field. As we are using the TCP/IP family, so we put 2 value in
this field.
○ Network Address: It is defined as 14 bytes field. If we use the IPv4 version, then we
use 4 bytes, and the other 10 bytes are all zeroes.
○ Distance: The distance field specifies the hop count, i.e., the number of hops used
to reach the destination.
How does the RIP work?

If there are 8 routers in a network where Router 1 wants to send the data to Router 3. If the network
is configured with RIP, it will choose the route which has the least number of hops. There are three
routes in the above network, i.e., Route 1, Route 2, and Route 3. The Route 2 contains the least
number of hops, i.e., 2 where Route 1 contains 3 hops, and Route 3 contains 4 hops, so RIP will
choose Route 2.
Disadvantages of RIP

The following are the disadvantages of RIP:

○ In RIP, the route is chosen based on the hop count metric. If another route of better bandwidth is available, then that
route would not be chosen. Let's understand this scenario through an example.
We can observe that Route 2 is chosen in the above figure as it has the least hop count. The Route 1 is free and data can
be reached more faster; instead of this, data is sent to the Route 2 that makes the Route 2 slower due to the heavy traffic.
This is one of the biggest disadvantages of RIP.

○ The RIP is a classful routing protocol, so it does not support the VLSM (Variable Length Subnet Mask). The classful
routing protocol is a protocol that does not include the subnet mask information in the routing updates.
○ It broadcasts the routing updates to the entire network that creates a lot of traffic. In RIP, the routing table updates
every 30 seconds. Whenever the updates occur, it sends the copy of the update to all the neighbors except the one
that has caused the update. The sending of updates to all the neighbors creates a lot of traffic. This rule is known as
a split-horizon rule.
○ It faces a problem of Slow convergence. Whenever the router or link fails, then it often takes minutes to stabilize or
take an alternative route; This problem is known as Slow convergence.
○ RIP supports maximum 15 hops which means that the maximum 16 hops can be configured in a RIP
○ The Administrative distance value is 120 (Ad value). If the Ad value is less, then the protocol is more reliable than
the protocol with more Ad value.
○ The RIP protocol has the highest Ad value, so it is not as reliable as the other routing protocols.
Advantages of RIP

The following are the advantages of a RIP protocol:

○ It is easy to configure
○ It has less complexity
○ The CPU utilization is less.
OSPF:
OSPF stands for Open Shortest Path First and it is an intradomain protocol. This protocol is used for
exchanging information between the dynamic routers. OSPF protocol is based on the link state
routing algorithm. OSPF is used within the autonomous system and it divides the autonomous system
into different areas.

Introduction
● OSPF stands for Open Shortest Path First and it is an Interior Gateway Protocol which is mainly
used for exchanging the routing information between the dynamic routers.
● It is generally used within the autonomous system of the Internet and used in large TCP/IP
networks.
● In the corporate networks, OSPF replaced the old Routing Information Protocol.
● OSPF is one of the intradomain protocols. Intradomain protocol means that this protocol is used
within the network or an area.
● OSPF protocol is the protocol that works based on the link state routing algorithm in which each
router has the information about each domain and uses this information to determine the
shortest path.
1. Router Id – It is the highest active IP address present on the router. First, the highest loopback address is
considered. If no loopback is configured then the highest active IP address on the interface of the router is
considered.
2. Router priority – It is an 8-bit value assigned to a router operating OSPF, used to elect DR and BDR in a broadcast
network.
3. Designated Router (DR) – It is elected to minimize the number of adjacencies formed. DR distributes the LSAs to
all the other routers. DR is elected in a broadcast network to which all the other routers share their DBD. In a
broadcast network, the router requests for an update to DR, and DR will respond to that request with an update.
4. Backup Designated Router (BDR) – BDR is a backup to DR in a broadcast network. When DR goes down, BDR
becomes DR and performs its functions.
5. DR and BDR election – DR and BDR election takes place in the broadcast network or multi-access network. Here
are the criteria for the election:
● The router having the highest router priority will be declared as DR.
● If there is a tie in router priority then the highest router I’d be considered. First, the highest loopback
address is considered. If no loopback is configured then the highest active IP address on the interface of
the router is considered.
Border Gateway Protocol

Border Gateway Protocol (BGP) is used to Exchange routing information for the
internet and is the protocol used between ISP which are different ASes.
The protocol can connect together any internetwork of autonomous system using
an arbitrary topology. The only requirement is that each AS have at least one
router that is able to run BGP and that is router connect to at least one other AS’s
BGP router. BGP’s main function is to exchange network reach-ability information
with other BGP systems. Border Gateway Protocol constructs an autonomous
systems’ graph based on the information exchanged between BGP routers.
Characteristics of Border Gateway Protocol (BGP):
● Inter-Autonomous System Configuration: The main role of BGP is to provide communication between two
autonomous systems.
● BGP supports Next-Hop Paradigm.
● Coordination among multiple BGP speakers within the AS (Autonomous System).
● Path Information: BGP advertisement also include path information, along with the reachable destination
and next destination pair.
● Policy Support: BGP can implement policies that can be configured by the administrator. For ex:- a router
running BGP can be configured to distinguish between the routes that are known within the AS and that
which are known from outside the AS.
● Runs Over TCP.
● BGP conserve network Bandwidth.
● BGP supports CIDR.
● BGP also supports Security.
Functionality of Border Gateway Protocol (BGP):
BGP peers performs 3 functions, which are given below.
1. The first function consist of initial peer acquisition and authentication. both the peers established a TCP
connection and perform message exchange that guarantees both sides have agreed to communicate.
2. The second function mainly focus on sending negative or positive reach-ability information.
3. The third function verifies that the peers and the network connection between them are functioning correctly.

BGP Route Information Management Functions:

● Route Storage: Each BGP stores information about how to reach other networks.
● Route Update: In this task, Special techniques are used to determine when and how to use the information
received from peers to properly update the routes.
● Route Selection: Each BGP uses the information in its route databases to select good routes to each network on
the internet network.
● Route advertisement: Each BGP speaker regularly tells its peer what is known about various networks and
methods to reach them.
Multicast routing protocol
Multicast routing is a protocol that sends one copy of data to multiple users simultaneously on a closed network. The most
popular uses of multicasting include videoconferencing and streaming media on organizational networks such as hotels or
campuses.

Multicast routing has numerous other uses, though. Here’s a look at some of the most common ones, how it operates, the
classifications of multicast routing, and the most well-known protocols and examples that solidify it as a timeless technique.
Top 3 multicast routing protocols
Several routing protocols enhance multicasting capabilities, but the most widely used are dense
mode, sparse mode, and reverse path forwarding.

Dense mode

In dense mode, the source will distribute the data to every subnet included in the multicast
network. This is also called flooding because it sends packets with less discretion than other
protocol variants.

Not every router has to accept the package, though. Prune messages can notify the sending nodes
to exclude them from receiving information, which helps trim unnecessary data emissions.

PIM protocol can work in a dense mode multicast routing type because it creates as many short
pathways to recipients as possible.
Sparse mode

Whereas dense mode mass-releases data to connected networks, sparse mode only takes the time to do so if there’s a
request.

Protocols like this reduce bandwidth usage and allow nodes joining the multicast group to receive data over time when
they initiate a specific request.

Like dense mode, there is also a PIM sparse model.

Reverse Path Forwarding

Reverse path forwarding implements a self-check so nodes can’t receive the same information they sent, because the
sender won’t look at that interface.

Though multicast routing optimizes for short paths, it can sometimes lead to loops when packets continually find other
connected nodes. In such cases it can unintentionally waste resources by sending data back to the original sender.
Reverse path forwarding allows for more intentional sending and receiving of data.
Example of multicast routing:
● Streaming: This is one of the most widely used multicasting applications, allowing video
or other media to be delivered to users across a corporate campus, school, or hotel
property. Live streaming of events and concerts is also sometimes done via multicast.
● Videoconferencing: From Zoom calls to mass video training sessions, multicasting
allows many entrants to participate in the same event without overwhelming the server.
● File distribution: Over-the-air patch management, operating system imaging, and even
financial stock tickers can all be multicast over corporate networks.
● IoT devices: The sensors embedded into IoT devices translate and send information to
databases, AI, and countless other sources when it collects info. These systems may rely
on multicasting to keep tabs on cybersecurity and ensure the correct recipients.