UNIT :-II

Routing Protocols
2.1 Routing Architecture:-
Explanation:-
• A router has four components namely, input ports,
output ports, the routing processor, and the switching
fabric.
• A router is a networking device that forwards data
packets between computer networks. It performs two
main functions namely, switching and queuing to
ensure efficient packet delivery.
• 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.
Following are the major uses of a router:

1.Multiple Network Connection:

It connects multiple networks and forwards data packets that are destined for
direct or remotely attached network.
2.Managing Congestion:
It manages traffic between networks by forwarding data packets to the destination
address. It also allows multiple addresses to use the same internet connecton.
3.Providing Connectivity:
Large routers interconnect several Internet Service Providers (ISPs). Small routers
provide connectivity for homes and office networks.
4.Connecting Subnets:
Routers are used for connecting multiple logical groups
ofcomputer devices called subnets with the different network prefixes.
5. Port Forwarding:
They are also used for port forwarding among private ISPs.
6.Trafic Classification:
A router with the help of QoS, takes the decision on which data packet should be
first processed.
It performs the physical and data link layer functions of the router. The bits are constructed from the received signal. The packet is
decapsulated from the frame.
Errors are detected and corrected, The packet is ready to be forwarded by the network layer.
• It performs the same functions as the input port, but in the reverse order.
First the outgoing packets are queued, then the packet is encapsulated in
a frame, and finally the physical layer functions are applied to the frame
to create the signal to be sent on the line.
Routing Processor:-
• It executes routing protocols. It maintains routing information
and forwarding tables.
• It also performs network management functions within the
router.
Switching Fabric:-
• The switching fabric connects the router's input ports to
its output ports.
• Switching fabric is the combination of hardware and
software which moves data coming in to a network
node out by the correct port to the next node in the
network
• Today, routers use a variety of switching tabrics such
as crossbar switch, banyan switch and so on.
Types of Routers:-
1.Edge Router
2.Wireless Router
3.Virtual Router
4.Distribution Router
5.Core Router
Advantages :-
• Dynamic Routing
• Scalability
• Redundancy
• Efficient Routing
• Network Reliability
• Disadvantages :-
• Complexity
• Resource Intensive
• Security Risk
• Convergence Time
• Scalability Limitation
Routing Table:-
• Router table is a set of rules that helps network devices decide the best
path for data packets as they move from their source to a destination.
• A router is a networking device that forwards data packets between
computer network This device is usually connected to two or more
different networks.
• Each entry in the routing table consists of the following entries:
• Network ID: The network ID or destination corresponding to the route.
• Subnet Mask: The mask that is used to match a destination IP address
to the nerwork ID.
• Next Hop: The IP address to which the packet is forwarded
• Outgoing Interface: Outgoing interface the packet should go out to
reach the destination network.
• Metric: . A common use of the metric is to indicate the minimum
number of hops (routers crossed) to the nerwork ID.
Queueing and Switching:-
Queuing in Router:-
• The purpose of Queuing is to store packets temporarily
when the arrival rate exceeds the departure
rate,preventing packet loss due to congestion.
• Queuing is the process of storing packets in buffers
before forwarding them.
• Types of Queuing in Routers:-
1.FIFO(First –in-First-out):
The simplest form of queuing
Packets are processed in the order they arrive
No priority mechanism.
 Assigns priority levels to packets.
• 2.Priority Queuing(PQ):-

Higher priority packets are transmitted first.

Risk:low priority packets
3.Weighted Fair Queuing(WFQ):-
Bandwidth is distribution among different flows.
Multimedia applications.
4.Round Robin Queuing:-
Each queue gets an equal opportunity to send
packets.
Resource allocation
Switching in Router:-

• Switching is the process of moving packets from the input interface

to the appropriate output interface.
• Types of Switching router-
1.Memory Based Switching:-
The router store incoming packets in memory before forwording them
CPU based operation , Slow and limited by memory speed.
2. Bus based Switching:
A shared bus connects input and output ports.
Packets wait for their turn to be transmitted over the bus.
Faster than memory switching but suffers from congestion.
3. Crossbar Based Switching:-
Use a matrix to directly connect input ports to output ports
Multiple packets to be switched simultaneously.
High performance but expensive
2.2 Routing Protocols:-
Intra-Domain Routing:-
• intra-domain routing protocols are used by routers
within a network to determine the best path for
forwarding packets to destinations within that same
network.
• When a packet of data leaves its source, there are many
different paths it can take to its destination.The routing
algorithm is used to determine mathematically the best
path to take.
The routing algorithm can be classified into following two types:

1. Static (Non-Adaptive) Routing Algorithms:

In this are type of algorithms, the network topology
determines the final path. All the possible paths 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.
Advantages:-
• Scalability:-
The ability of a routing protocol to handle large
networks.
Convergence:-
The speed at which a routing protocol can adapt to
changes in the network.
Stability:-
The ability of a routing protocol to maintain a
stable routing table.
Disadvantages:-
1. Scalability Limitation
2. Single point of Failure
3. Limited Flexibility
4.Security Risks
Distance Vector Routing:-
• Distance vector routing algorithm is the dynamic routing algorithm in
computer networks.Distance vector routin algorithm also known as
Bellman-Ford routing algorithm (also called Ford FuIKerSon algorithm)
to find the shortest path between nodes in a graph given the distance
between nodes.
• It was designed for small network topologies. Distance Vector Routing
(DVR) method sees an AS,with all routers and networks as a graph a
set of nodes and lines connected the nodes.
• A router can normally be represented by a node and a network by a
link Connecting two nodes,although other representations are also
possible.
• In distance vector routing 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.
The shortest path can be computed as:-
• Distance vector routing protocols are like road signs
because routers must make preferred path decisions based
on a distance or metric to a network.
• Just as travelers trust a road sign to accurately state the
distance to the next town, a distance vector router trusts
that another router is advertising the true distance to the
destination network.
• In distance vector routing, the least-cost route between any
two nodes is the route with minimum distance (mi).
• In this protocol, as the name implies, each node maintains
a vector (table) of minimum distances to every node. The
table at each node also guides the packets to the desired
node by showing the next Stop in the route(next hop
routing)
Initialization:-
Explanation:-

• The tables in Fig. 2.7 are stable: each node knows how
to reach any other node and the cost. At the beginning,
however, this is not the case. Each node can know only
the distance between itself and its immediate
neighbors, those directly connected to it. So, for the
moment, we assume that each node can send a
message to the immediate neighbors and find the
distance between itself and these neighbors. The
distance for any entry that is not a neighbor is marked
as infinite (unreachable).
Sharing:-
Explanation:-
• 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:-
• Updating: When a node receives a two-column table
from a neighbor, it needs to update its routing table
Updating takes following three steps:
• Step 1: The receiving node needs to add the cost
between itself and the sending node to each value in
the second column. The logic is clear. If node C claims
that its distance to a destination is X mi, and the
distance between A andC is y mi, then the distance
between A and that destination, via C, is x + y mi.
• Step 2: The receiving node needs to add the name of
the sending node to each row as the third column if the
receiving node uses information from any row. The
sending node is the next node in the route.
• Step 3: The receiving node needs to compare each row
of its old table with the corresponding row the modified
version of the received table.
• (i) If the next-node entry is different, the receiving node
chooses the row with the smaller cost. If there is a tie,
the old one is kept.
• (ii) If the next-node entry is the same, the receiving
node chooses the new row.
Bellman-Ford Algorithm:-
1.The Bellman-Ford algorithm is an algorithm that computes
shortest paths from a single source vertex to all of the other vertices
in a weighted digraph.
2. Bellman-Ford algorithm solves single shortest path problem in
which edge weight may be negative but no negative cycle exists.
3.The Bellman-Ford algorithm works correctly when some of the
edges of the directed graph G may have negative weight. When
there are no cycles of negative weight, then we can find out the
shortest is path between source and destination.
Recurrence Relation:
distk [u] = [min[distk-1 [u],min[ distk-1 [i]+cost [i,u]]] as i except u.
k -> is the source vertex
u -> is the destination vertex
i -> no of edges to be scanned concerning a vertex.
The sequence of steps in Bellman-Ford Algorithm:-
• BELLMAN-FORD(G, W, S)
1. INITIALIZE-SINGLE-SOURCE(G, s)
2. for i <- 1 to|V[G]| -1
3. do for each edge (u, v) E[G]
4. do RELAX(u, v, w)
5. for each edge (u, v) E[G]
6. do if d[v] > d[u] + w(u,v)
7. then return FALSE
8. return TRUE
Routing Information Protocol(RIPv2):-
• The Routing Information Protocol (RIP) is an intra-
domain (interior) routing protocol used inside an
autonomous system
• . The RIP is a protocol used to propagate routing
information inside an autonomous System. Today the
internet is so large that one routing protocol cannot
handle the task of updating the routing table of all
routers.
• Routing Information Protocol (RIP) is a dynamic routing
protocol which uses hop count as a routing metric to
find the best path between the source and the
destination network.
Diagram:-
Concept of Hop Count:

1. A hop is one portion of the path between source and

destination. Data packets pass through bridges, routers
and gateways as they travel between source and
destination. Each time packets are passed to next
network device a hop occurs .
2. Hop count is the number of routers occurring in
between the source and destination network. The path
with the lowest hop count is considered as the best route
to reach a network and therefore placed in the routing
table.
3. In other words, the hop count refers to the number of
intermediate devices through which data must pass
between source and destination.
Features of RIP:-

1. Updates of the network are exchanged periodically.

2. Updates (routing information) are always broadcast.
3. Full routing tables are sent in updates.
4. Routers always trust on routing information received
from neighbor routers.
RIP Messaage Format of RIP:-
Various fields in message format of RIP are explained below:

• 1. Command: This 8-bit field specifies the type of message i.e.,

request (1) or response (2).
• 2. Version: This 8-bit field defines the version.

• 3. Family: This 16-bit field defines the family of the protocol

used. For TCP/IP the value is 2.

• 4. Network Address: The address field defines the address of

the destination network. RIP has allocated 14 bytes for this field
to be applicable to any protocol. However, IP currently uses only
4 bytes. The rest of the address is filled with 0s.

• 5 .Distance: This 22-bit field defines the hop count (cost) from
the advertising router to the destination network.
RIP has two types of messages:-
• I. Request:
• A request message is sent by a router that has just
come up or by a router that has some time-out entries.
A request can ask about specific entries or all entries.
• Response:
• A response can be either solicited or unsolicited. A
solicited response is sent only in answer to a request. It
contains information about the destination specified in
the corresponding request. An unsolicited response, is
sent periodically, every 20 seconds or when there is a
change in the routing table.
Message Format of RIP version 2:-
• Route Tag: This field carries information such as the
autonomous system number. It can be used to enable
RIP to receive information from an inter-domain routing
protocol.
• Subnet Mask: This is a 4-byte field that carries the
subnet mask (or prefix). This means that RIP version 2
supports classless addressing and CIDR.
• Next-hop Address: This field shows the address of the
next hop. This is particularly useful if two autonomous
systems share a network . Then the message can define
the router, in the same autonomous system or another
autonomous system, to which the packet next goes.
Link State Routing:-
• Link-state routing is a type of routing protocol used in computer
• networks to determine the best path for forwarding packets between
• nodes. It is a dynamic routing protocol that uses the state of links
between nodes to calculate the shortest path.
• Link-state routing works by:
• 1. Building a Topology Map:
• Each node in the network builds a map of the network topology,
including the state of links between nodes.
• 2. Sharing Link-State Information:
• Nodes share their link-state information with neighboring nodes, which
helps to build a consistent view of the network topology.
• 3. Calculating Shortest Paths:
• Each node uses the topology map to calculate the shortest path to
other nodes in the network.
Advantages of Link-State Routing

• Fast Convergence
• Scalability
• Support for Variable-Length Subnet Masks (VLSMs)
• Disadvantages:-
• Complexity
• Resource Requirements
• Features :-
• Traffic Engineering
• Multi-Topology Routing
Open Shortest Path First(OSPF):-
• OSPF (Open Shortest Path First) is a link-state routing
protocol used in computer networks to determine the best
path for forwarding packets between nodes. It is a dynamic
routing protocol that uses the state of links between nodes
to calculate the shortest path.
• 1. Building a Topology Map: Each router in the network
builds a map of the network topology, including the state of
links between routers.
• 2. Sharing Link-State Information: Routers share their
link-state information with neighboring routers, which helps
to build a consistent view of the network topology.
• 3. Calculating Shortest Paths: Each router uses the
topology map to calculate the shortest path to other routers
in the network.
Advantages of OSPF
• 1. Scalability: OSPF can scale to large networks with
many routers and links.
• 2. Fast Convergence: OSPF can converge quickly after
a network change, minimizing downtime and improving
network stability.
• 3. Support for VLSMs: OSPF supports VLSMs, which
allows for more efficient use of IP address space.
• Diadvantages:-
• Link-State Routing Overhead
• Distance-Vector Routing Loops
Types of Links:-

• 1.Point-to-point Link:-
• A Point-to-point link connects two routers without any other
host or router in between. In other words, the purpose of the
link (network) is just to connect the two routers.
• Point-to-point links between routers do not need an IP address
at each end.Unnumbered links can save IP addresses.
Transient Link:-
A transient link is a network with several routers attached to it.
A stub link is a network that is Connected to only one router. A
transient link is a network with several routers attached to it.
The data can enter through any of the routers and leave
through any router. All LANS and some WANS with two or more
routers are of this type
Stub Link:
A stub link is a network that is connected to only one router. The data packets enter the network through this single router
and leave the network through this same router. This is a special case of the transient network.
• Virtual Link:
• When the link between two routers is broken, the
administration may create a virtual link between them
using a longer path that probably goes through several
routers
Inter domain routing:-
Inter-domain routing refers to the routing of packets between different autonomous systems (AS) or domains on the internet.

• Path Vector Routing:-

• Path vector routing is a type of routing protocol used in inter-domain
routing to determine the best path for forwarding packets between
different autonomous systems (AS).
• Path vector routing works by:
• 1. Maintaining a Path Vector:
• Each router maintains a path vector that lists the sequence of AS
numbers that a packet will traverse to reach a particular destination
network.
• 2. Exchanging Path Vectors:
• Routers exchange path vectors with neighboring routers to build a map
of the network topology.
• 3. Selecting the Best Path:
• Each router selects the best path to forward packets based on the path
vector information.
Advantages of Path Vector Routing
• Scalability
• Flexibility
• Loop Prevention
• Disadvantages:-
• Complexity
• Resource Requirements
Border Gateway Protocol:-(BGPv4)
BGPv4 (Border Gateway Protocol version 4) is a path vector routing protocol used for inter-domain routing on the internet.
• BGP can have two types of sessions namely. external
BGP and internal BGP Sessions.

• The E-BGP session in BGP is used to exchange

information between two speaker nodes belonging to
two different autonomous systems.

• The session established between AS1 and AS2 is an E-

BGP session. The two speaker routers exchange
information they know about networks in the internet.
• BGPv4 uses several message types,
• 1. OPEN:
• Used to establish a BGP session between two routers.
• 2. UPDATE:
• Used to exchange routing information between BGP
routers.
• 3. NOTIFICATION:
• Used to notify a BGP router of an error or to close a BGP
session.
• 4. KEEPALIVE:
• Used to maintain a BGP session and ensure that the
connection is still active.
Internet control message protocol(ICMP):-
• ICMP is one of the simplest protocols in the TCP/IP
protocol.
• facilitate basic operation of a part of the network stack
or an application.
• ICMP is used for reporting errors and management
queries.
• network device likes routers for sending errors message
and operations information.
Types of ICMP messages:-
ICMP packet Format:-
• Type (8-bit): The initial 8-bit of the packet is for message type, it
provides a brief description of message so that receiving network would
know what kind of message it is receiving and how to respond to it.
• Some common message types are as follows:
• Type 0- Echo Reply
• Type 3- Destination Unreachable
• Type 5 - Redirect Message
• Type 8- Echo Request
• Type 11- Time Exceeded
• Type 12- parameter problem
• Code (8-bit): Code is the next 8 bits of the ICMP packet format, this
field carries some additional information about the error message and
type.
• Checksum (16-bit): Last 16 bits are for the checksum field in the
ICMP packet header.
• Extended Header:
• The next 32 bits of the ICMP Header are Extended
Header which has the work of pointing out the problem
in IP Message.
• Data or Payload:
• The last part of the ICMP packet is Data or Payload of
variable length.
ICMP basic Error Message Format:-
• Type:
• The type field identifies the type of the message.
• Code:
• The code field in ICMP describes the purpose of the message.
• Checksum:
• The checksum field is used to validate ICMP messages.
• Unused:
• Reserved for future use and is set to zero. The computer that
receives an ICMP message must not use the value in this field.
• Data:
• Includes the IP header of the datagram that was received and
also the first eight bytes of data in the IP datagram.