Routing in network layer

MODULE - 4
DISTANCE VECTOR ROUTING ALGORITHM, LINK STATE ROUTING
ALGORITHM AND Hierarchical Routing concept explained in
class REFER THEORY FROM (FOROUZAN) BOOK.
ROUTING
● A Router is a process of selecting path along which the data can be
transferred from source to the destination. Routing is performed by a
special device known as a router.
● A Router works at the network layer in the OSI model and internet
layer in TCP/IP model
● A router is a networking device that forwards the packet based on the
information available in the packet header and forwarding table.
● The routing algorithms are used for routing the packets. The routing
algorithm is nothing but a software responsible for deciding the
optimal path through which packet can be transmitted.
● The routing protocols use the metric to determine the best path for
the packet delivery. The metric is the standard of measurement such
as hop count, bandwidth, delay, current load on the path, etc. used
by the routing algorithm to determine the optimal path to the
destination.
● The routing algorithm initializes and maintains the routing table for
the process of path determination.
TYPES OF ROUTING
TYPES OF ROUTING

Static Routing
● 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.
TYPES OF ROUTING

Disadvantages of Static Routing:

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.
TYPES OF ROUTING

Default Routing
● Default Routing is a technique in which a router is configured to send all
the packets to the same hop device, and it doesn't matter whether it
belongs to a particular network or not. A Packet is transmitted to the
device for which it is configured in default routing.
● Default Routing is used when networks deal with the single exit point.
● It is also useful when the bulk of transmission networks have to transmit
the data to the same hp device.
● When a specific route is mentioned in the routing table, the router will
choose the specific route rather than the default route. The default route
is chosen only when a specific route is not mentioned in the routing table.
TYPES OF ROUTING

Dynamic Routing
● It is also known as Adaptive Routing.
● It is a technique in which a router adds a new route in the routing table for each packet
in response to the changes in the condition or topology of the network.
● Dynamic protocols are used to discover the new routes to reach the destination.
● In Dynamic Routing, RIP and OSPF are the protocols used to discover the new routes.
● If any route goes down, then the automatic adjustment will be made to reach the
destination.

The Dynamic protocol should have the following features:

● All the routers must have the same dynamic routing protocol in order to exchange the
routes.
● If the router discovers any change in the condition or topology, then router broadcast
this information to all other routers.
TYPES OF ROUTING

Advantages of Dynamic Routing:

● It is easier to configure.
● It is more effective in selecting the best route in response to the
changes in the condition or topology.

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.
CLASSIFICATION OF ROUTING ALGORITHMS
CLASSIFICATION OF ROUTING ALGORITHMS
1. Adaptive Algorithms
These are the algorithms that change their routing decisions whenever network topology or traffic load changes. The changes in
routing decisions are reflected in the topology as well as the traffic of the network. Also known as dynamic routing, these make use of
dynamic information such as current topology, load, delay, etc. to select routes. Optimization parameters are distance, number of hops,
and estimated transit time.
Further, these are classified as follows
● Isolated: In this method each, node makes its routing decisions using the information it has
without seeking information from other nodes. The sending nodes don’t have information
about the status of a particular link. The disadvantage is that packets may be sent through a
congested network which may result in delay. Examples: Hot potato routing, and backward
learning.
● Centralized: In this method, a centralized node has entire information about the network and
makes all the routing decisions. The advantage of this is only one node is required to keep
the information of the entire network and the disadvantage is that if the central node goes
down the entire network is done. The link state algorithm is referred to as a centralized
algorithm since it is aware of the cost of each link in the network.
CLASSIFICATION OF ROUTING ALGORITHMS
● Distributed: In this method, the node receives information from its neighbors and then takes
the decision about routing the packets. A disadvantage is that the packet may be delayed if
there is a change in between intervals in which it receives information and sends packets. It is
also known as a decentralized algorithm as it computes the least-cost path between source
and destination.

2. Non-Adaptive Algorithms
These are the algorithms that do not change their routing decisions
once they have been selected. This is also known as static routing
as a route to be taken is computed in advance and downloaded to
routers when a router is booted.
CLASSIFICATION OF ROUTING ALGORITHMS
Further, these are classified as follows:

● Flooding: This adapts the technique in which every incoming packet is

sent on every outgoing line except from which it arrived. One problem
with this is that packets may go in a loop and as a result of which a node
may receive duplicate packets. These problems can be overcome with
the help of sequence numbers, hop count, and spanning trees.
● Random walk: In this method, packets are sent host by host or node by
node to one of its neighbors randomly. This is a highly robust method that
is usually implemented by sending packets onto the link which is least
queued.
CLASSIFICATION OF ROUTING ALGORITHMS

3. Hybrid Algorithms
As the name suggests, these algorithms are a combination of both adaptive and
non-adaptive algorithms. In this approach, the network is divided into several
regions, and each region uses a different algorithm.
Further, these are classified as follows:

● Link-state: In this method, each router creates a detailed and complete map
of the network which is then shared with all other routers. This allows for more
accurate and efficient routing decisions to be made.
● Distance vector: In this method, each router maintains a table that contains
information about the distance and direction to every other node in the
network. This table is then shared with other routers in the network. The
disadvantage of this method is that it may lead to routing loops.
Difference between Adaptive and Non-Adaptive Routing Algorithms
Delivery
Forwarding
Forwarding Techniques

Route Method versus next-hop method

Hierarchical routing

Hierarchical routing is the procedure of arranging routers in a

hierarchical manner. A good example would be to consider a
corporate intranet. Most corporate intranets consist of a high speed
backbone network. Connected to this backbone are routers which
are in turn connected to a particular workgroup. These workgroups
occupy a unique LAN. The reason this is a good arrangement is
because even though there might be dozens of different
workgroups, the span (maximum hop count to get from one host to
any other host on the network) is 2. Even if the workgroups divided
their LAN network into smaller partitions, the span could only
increase to 4 in this particular example. Refer book for theory
What is Routing Information Protocol (RIP)?

Routing Information Protocol (RIP) is a distance vector protocol that uses

hop count as its primary metric. RIP defines how routers should share
information when moving traffic among an interconnected group of local
area networks.
Hop Count

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. RIP
prevents routing loops by limiting the number of hops allowed in a path from
source and destination. The maximum hop count allowed for RIP is 15 and a
hop count of 16 is considered as network unreachable.
What is Routing Information Protocol (RIP)?

How Routing Information Protocol works

RIP uses a distance vector algorithm to decide which path to put a packet on to get to
its destination. Each RIP router maintains a routing table, which is a list of all the
destinations the router knows how to reach. Each router broadcasts its entire routing
table to its closest neighbors every 30 seconds. In this context, neighbors are the other
routers to which a router is connected directly -- that is, the other routers on the same
network segments as the selected router. The neighbors, in turn, pass the information
on to their nearest neighbors, and so on, until all RIP hosts within the network have the
same knowledge of routing paths. This shared knowledge is known as convergence.
What is Routing Information Protocol (RIP)?

If a router receives an update on a route, and the new path is shorter, it will update its table
entry with the length and next-hop address of the shorter path. If the new path is longer, it
will wait through a "hold-down" period to see if later updates reflect the higher value as well.
It will only update the table entry if the new, longer path has been determined to be stable.

If a router crashes or a network connection is severed, the network discovers this because
that router stops sending updates to its neighbors, or stops sending and receiving updates
along the severed connection. If a given route in the routing table isn't updated across six
successive update cycles (that is, for 180 seconds) a RIP router will drop that route and let
the rest of the network know about the problem through its own periodic updates.

Versions of RIP
There are three versions of the Routing Information Protocol:

1. RIPv1.
2. RIPv2.
3. RIPng
OSPF Protocol
The OSPF stands for Open Shortest Path First. It is a widely used and
supported routing protocol. It is an intradomain protocol, which means that it is
used within an area or a network. It is an interior gateway protocol that has been
designed within a single autonomous system. It is based on a link-state routing
algorithm in which each router contains the information of every domain, and
based on this information, it determines the shortest path. The goal of routing is to
learn routes. The OSPF achieves by learning about every router and subnet within
the entire network. Every router contains the same information about the network.
The way the router learns this information by sending LSA (Link State
Advertisements). These LSAs contain information about every router, subnet, and
other networking information. Once the LSAs have been flooded, the OSPF stores
the information in a link-state database known as LSDB. The main goal is to have
the same information about every router in an LSDBs.
OSPF Protocol
How does OSPF work?
There are three steps that can explain the working of OSPF:

Step 1: The first step is to become OSPF neighbors. The two connecting
routers running OSPF on the same link creates a neighbor relationship.

Step 2: The second step is to exchange database information. After becoming

the neighbors, the two routers exchange the LSDB information with each
other.

Step 3: The third step is to choose the best route. Once the LSDB information
has been exchanged with each other, the router chooses the best route to be
added to a routing table based on the calculation of SPF.
OSPF Protocol
OSPF Message Format
OSPF Protocol
● Version: It is an 8-bit field that specifies the OSPF protocol version.
● Type: It is an 8-bit field. It specifies the type of the OSPF packet.
● Message: It is a 16-bit field that defines the total length of the message, including
the header. Therefore, the total length is equal to the sum of the length of the
message and header.
● Source IP address: It defines the address from which the packets are sent. It is a
sending routing IP address.
● Area identification: It defines the area within which the routing takes place.
● Checksum: It is used for error correction and error detection.
● Authentication type: There are two types of authentication, i.e., 0 and 1. Here, 0
means for none that specifies no authentication is available and 1 means for pwd
that specifies the password-based authentication.
● Authentication: It is a 32-bit field that contains the actual value of the
authentication data.
BGP Protocol
What is BGP? Border Gateway Protocol (BGP) refers to a gateway protocol that
enables the internet to exchange routing information between autonomous systems
(AS). As networks interact with each other, they need a way to communicate. This is
accomplished through peering. BGP makes peering possible. Without it, networks
would not be able to send and receive information with each other.

How Does BGP Work?

When you have a network router that connects to other networks, it does not know
which network is the best one to send its data to. BGP takes into consideration all the
different peering options a router has and chooses the one closest to where the router
is. Each potential peer communicates the routing information it has and that gets stored
within a routing information base (RIB). BGP can access this information and use it to
choose the best peering option.
BGP Protocol

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 the Next-Hop Paradigm.
● Coordination among multiple BGP speakers within the AS (Autonomous System).
● Path Information: BGP advertisements 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 conserves network Bandwidth.
● BGP supports CIDR.
● BGP also supports Security.
BGP Protocol
Types of Border Gateway Protocol
External BGP: It is used to interchange routing information between the routers in different autonomous
systems, it is also known as eBGP(External Border Gateway Protocol). The below image shows how
eBGP interchange routing information.
BGP Protocol
Internal BGP: It is used to interchange routing information between the routers in the same
autonomous system, it is also known as iBGP(Internal Border Gateway Protocol). Internal
routers also ensure consistency among routers for sharing routing information. The below
image shows how iBGP interchange routing information.
BROADCAST ROUTING
1. Broadcast
Broadcast transfer (one-to-all) techniques and can be classified into two types : Limited
Broadcasting and direct Broadcasting. In broadcasting mode, transmission happens from one host
to all the other hosts connected on the LAN. In simple words, broadcasting is a communication
mechanism where data is sent to all the nodes in a network. The broadcast address is a special
reserved address bits for broadcasting messages in a network, we can calculate the broadcast
address given its IP address and the subnet Mask.
MULTICAST ROUTING
2. Multicast
Multicasting has one/more senders and one/more recipients participate in data transfer traffic. In
multicasting traffic recline between the boundaries of unicast and broadcast. It server’s direct
single copies of data streams and that are then simulated and routed to hosts that request it. IP
multicast requires support of some other protocols such as IGMP (Internet Group Management
Protocol), Multicast routing for its working. And also in Classful IP addressing Class D is reserved
for multicast groups.
Multicast Routing Protocols

Unicasting :
Difference Between Broadcast and Multicast
Difference Between Broadcast and Multicast
DVMRP

Distance vector multicast routing protocol (DVMRP) is a protocol used for routing multicast
data packets. It is based on the distance vector algorithm, similar to the routing information
protocol (RIP), but the DVMRP is specifically adapted for multicast, or sending data packets
to multiple destinations simultaneously, rather than unicast routing. It can be used in video
conferencing, live streaming events, company communications, online education, and
real-time data distribution.

To send the packets, DVMRP creates a routing table with the shortest path from each node
in the network to a multicast group. Then, it uses reverse path forwarding (RPF) to ensure
efficient delivery of multicast packets.

DVMRP is not universally supported across all network equipment, so you should always
check if it’s compatible with your system. It is most effective in scenarios where multicast
data needs to be efficiently distributed to multiple recipients. (refer book for diagram and
theory)
DVMRP

The distance vector multicast routing protocol is multicast routing

protocol that takes the routing decision based upon the source
address of the packet.
• This algorithm constructs the routing tree for a network.
• Whenever a router receives a packet, it forwards it to some of its
ports based on the source address of packet.
• The rest of the routing tree is made by downstream routers.
• In this way, routing tree is created from destination to source.
DVMRP

The protocol must achieve the following tasks:

1. It must prevent the formation of loops in the network.

2. It must prevent the formation of duplicate packets.

3. It must ensure that the path traveled by a packet is the shortest from its source to the router.

4. It should provide dynamic membership.

To accomplish this, the DVMR algorithm uses a process based on following decision making
strategies:

. Reverse Path Forwarding (RPF)

• In this strategy, the router only forwards those packets that have traveled the shortest path from
source to destination.

• To achieve this, the router pretends that it has a packet to send to the source from where the
DVMRP

• In this way, the shortest path to the sender of the packet is computed.

• If the same route is followed by the received packet, it is forwarded to the next
router and it is discarded otherwise.

• The reverse path forwarding ensures that the network receives a copy of the
packet without formation of loops. A loop occurs when a packet that has left the
router may come back again from another interface or the same interface and be
forwarded again.

• RPF does not guarantee that there would be no duplicate packets in the network
i.e. the network may receive two or more copies.

• The reason for this is that the routing is based on the source address and not on
the destination address.
DVMRP

2. Reverse Path Broadcasting (RPB)

• In order to solve the problem, RPB is used.
• In this method, one parent router is defined for each network.
• The network could accept the multicast packets from this parent router
only.router sends packets to those ports for which it is designated as
parent.
• Thus, RPB principle’ allows a router to broadcast the packet in the
network.
This creates duplicate packets on the network and reduces the network
efficiency.
DVMRP

3. Reverse Path Multicasting (RPM)

• To overcome the problem of broadcasting in RPB, Reverse Path Multicasting in used.

• In this the desired multicast network tree is created by using two different methods: Pruning
and grafting.

• A router can send a prune message to its upstream router whenever it finds that its network
is not interested in a multicast packet. In this way a router prunes (cuts) its network from
multicasting.

• If a router receives prune message from all the downstream routers, it in turn, sends a
prune message to its upstream router.

• A router can also send a graft message to its upstream router if it finds that its network is
again interested in receiving the multicast packet. In this way, graft message forces the
upstream router to resume sending the multicast message. The network is again grafted
(joined).
DVMRP

4. Multicast Open Shortest Path First (MOSPF)

• Multicast open shortest path first is the multicast version of open shortest
path first protocol.

• It is an extension of OSPF that uses multicast link state routing method to

create source based trees.

• The method used by MOSPF is different from DVMRP.

• The first difference is· that in this method, the tree is least cost tree instead
of shortest path tree.

• The second .difference is that the tree is not made gradually. It is made
immediately it is prepruned and ready to use.
DVMRP
DISTANCE VECTOR ROUTING
DISTANCE VECTOR ROUTING
DISTANCE VECTOR ROUTING
DISTANCE VECTOR ROUTING
DISTANCE VECTOR ROUTING
DISTANCE VECTOR ROUTING
DISTANCE VECTOR ROUTING
TWO NODE INSTABILITY
TWO NODE INSTABILITY
SPLIT HORIZON AND POISON REVERSE
THREE NODE INSTABILITY
THREE NODE INSTABILITY
NOTE- YOU CAN DRAW DIAGRAMS FOR 2 AND 3 NODE
INSTABILITY WHICH I EXPLAINED IN CLASS.
Count to Infinity problem

The main issue with Distance Vector Routing (DVR) protocols is Routing Loops since
Bellman-Ford Algorithm cannot prevent loops. This routing loop in the DVR network causes
the Count to Infinity Problem. Routing loops usually occur when an interface goes down or
two routers send updates at the same time.

Counting to infinity problem:

So in this example, the Bellman-Ford algorithm will converge for

each router, they will have entries for each other. B will know that it
can get to C at a cost of 1, and A will know that it can get to C via B
at a cost of 2.
Count to infinity problem

If the link between B and C is disconnected, then B will know that it can no longer
get to C via that link and will remove it from its table. Before it can send any
updates it’s possible that it will receive an update from A which will be advertising
that it can get to C at a cost of 2. B can get to A at a cost of 1, so it will update a
route to C via A at a cost of 3. A will then receive updates from B later and update
its cost to 4. They will then go on feeding each other bad information toward
infinity which is called as Count to Infinity problem.
Solution for Count to Infinity problem:-

Split horizon:
If the link between B and C goes down, and B had received a route from A, B could end
up using that route via A. A would send the packet right back to B, creating a loop. But
according to the Split horizon Rule, Node A does not advertise its route for C (namely A
to B to C) back to B. On the surface, this seems redundant since B will never route via
node A because the route costs more than the direct route from B to C.

Consider the following network topology showing Split horizon-

 Solution for Count to Infinity problem:-

Poison Revert:

When a route fails, distance vector protocols spread the bad news about a route failure by
poisoning the route. Route poisoning refers to the practice of advertising a route, but with a special
metric value called Infinity. Routers consider routes advertised with an infinite metric to have failed.
Each distance vector routing protocol uses the concept of an actual metric value that represents
infinity. RIP defines infinity as 16. The main disadvantage of poison reverse is that it can
significantly increase the size of routing announcements in certain fairly common network
topologies.