02 June 2024 12:27

• The Distance vector algorithm is iterative, asynchronous and distributed.

○ Distributed: It is distributed in that each node receives information from one or more of its
directly attached neighbors, performs calculation and then distributes the result back to its
neighbors.
○ Iterative: It is iterative in that its process continues until no more information is available to be
exchanged between neighbors.
○ Asynchronous: It does not require that all of its nodes operate in the lock step with each other.
• The Distance vector algorithm is a dynamic algorithm.
• It is mainly used in ARPANET, and RIP.
• Each router maintains a distance table known as Vector.

Three Keys to understand the working of Distance Vector

Routing Algorithm:
• Knowledge about the whole network: Each router shares its knowledge through the entire
network. The Router sends its collected knowledge about the network to its neighbors.
• Routing only to neighbors: The router sends its knowledge about the network to only those
routers which have direct links. The router sends whatever it has about the network through the
ports. The information is received by the router and uses the information to update its own
routing table.
• Information sharing at regular intervals: Within 30 seconds, the router sends the information
to the neighboring routers.
Distance Vector Routing Algorithm
Let dx(y) be the cost of the least-cost path from node x to node y. The least costs are related by
Bellman-Ford equation,
dx(y) = minv{c(x,v) + dv(y)}
Where the minv is the equation taken for all x neighbors. After traveling from x to v, if we consider the
least-cost path from v to y, the path cost will be c(x,v)+dv(y). The least cost from x to y is the minimum
of c(x,v)+dv(y) taken over all neighbors.
With the Distance Vector Routing algorithm, the node x contains the following routing
information:
• For each neighbor v, the cost c(x,v) is the path cost from x to directly attached neighbor, v.
• The distance vector x, i.e., Dx = [ Dx(y) : y in N ], containing its cost to all destinations, y, in N.
• The distance vector of each of its neighbors, i.e., Dv = [ Dv(y) : y in N ] for each neighbor v of x.
Distance vector routing is an asynchronous algorithm in which node x sends the copy of its distance
vector to all its neighbors. When node x receives the new distance vector from one of its neighboring
vector, v, it saves the distance vector of v and uses the Bellman-Ford equation to update its own
distance vector. The equation is given below:

Classification of Routing Algorithms

Routing is the process of establishing the routes that data packets must follow to
reach the destination. In this process, a routing table is created which contains
information regarding routes that data packets follow. Various routing algorithms
are used for the purpose of deciding which route an incoming data packet needs
to be transmitted on to reach the destination efficiently.
Classification of Routing Algorithms
The routing algorithms can be classified as follows:
1. Adaptive Algorithms
2. Non-Adaptive Algorithms
3. Hybrid Algorithms

New Section 25 Page 1

1. Adaptive Algorithms
2. Non-Adaptive Algorithms
3. Hybrid 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.
• 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.
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

New Section 25 Page 2

 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.

A distance-vector routing (DVR) protocol requires that a router inform its

neighbors of topology changes periodically. Historically known as the old
ARPANET routing algorithm (or known as Bellman-Ford algorithm).
Bellman Ford Basics – Each router maintains a Distance Vector table
containing the distance between itself and ALL possible destination nodes.
Distances,based on a chosen metric, are computed using information from the
neighbors’ distance vectors.
Distance Vector Algorithm –
1. A router transmits its distance vector to each of its neighbors in a routing
packet.
2. Each router receives and saves the most recently received distance vector
from each of its neighbors.
3. A router recalculates its distance vector when:
• It receives a distance vector from a neighbor containing different information
than before.
• It discovers that a link to a neighbor has gone down.
The DV calculation is based on minimizing the cost to each destination
Advantages of Distance Vector routing –
• It is simpler to configure and maintain than link state routing.
Disadvantages of Distance Vector routing –
• It is slower to converge than link state.
• It is at risk from the count-to-infinity problem.
• It creates more traffic than link state since a hop count change must be
propagated to all routers and processed on each router. Hop count updates
take place on a periodic basis, even if there are no changes in the network
topology, so bandwidth-wasting broadcasts still occur.
• For larger networks, distance vector routing results in larger routing tables
than link state since each router must know about all other routers. This can
also lead to

Border Gateway Protocol (BGP)

The protocol can connect any internetwork of the autonomous system using
an arbitrary topology. The only requirement is that each AS have at least one
router that can run BGP and that is the router connected to at least one other
AS’s BGP router. BGP’s main function is to exchange network reachability
information with other BGP systems. Border Gateway Protocol constructs an
autonomous systems graph based on the information exchanged between

New Section 25 Page 3

 autonomous systems graph based on the information exchanged between
BGP routers.
Functionality of Border Gateway Protocol (BGP)
BGP peers perform 3 functions, which are given below.
• The first function consists of initial peer acquisition and authentication. both
the peers established a TCP connection and performed message exchange
that guarantees both sides have agreed to communicate.
• The second function mainly focuses on sending negative or positive reach -
ability information.
• The third function verifies that the peers and the network connection between
them are functioning correctly.
Importance of Border Gateway Protocol(BGP)
• Security: BGP is highly secure because it authenticates messages between
routers using preconfigured passwords through which unauthorized traffic is
filtered out.
• Scalability: BGP is more scalable because it manages a vast number of
routes and networks present on the internet.
• Supports Multihoming: BGP allows multihoming means an organization can
connect to multiple networks simultaneously.
• Calculate the Best Path: As we know data packets is traveled across the
internet from source to destination every system in between the source and
destination has to decide where the data packet should go next
• TCP/IP Model: BGP is based on the TCP/IP model and it is used to control
the network layer by using transport layer 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.

eBGP

• 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.

Open Shortest Path First (OSPF) Protocol

fundamentals
Last Updated : 22 Feb, 2023
Open shortest path first (OSPF) is a link-state routing protocol that is used
to find the best path between the source and the destination router using its
own shortest path first (SPF) algorithm. A link-state routing protocol is a
protocol that uses the concept of triggered updates, i.e., if there is a change

New Section 25 Page 4

 protocol that uses the concept of triggered updates, i.e., if there is a change
observed in the learned routing table then the updates are triggered only, not
like the distance-vector routing protocol where the routing table is exchanged
at a period of time.
Open shortest path first (OSPF) is developed by Internet Engineering Task
Force (IETF) as one of the Interior Gateway Protocols (IGP), i.e., the protocol
which aims at moving the packet within a large autonomous system or routing
domain. It is a network layer protocol that works on protocol number 89 and
uses AD value 110. OSPF uses multicast address 224.0.0.5 for normal
communication and 224.0.0.6 for updating to the designated router
(DR)/Backup Designated Router (BDR).
Criteria –
To form a neighborship in OSPF, there is a criterion for both routers:
1. It should be present in the same area.
2. The router I’d be unique.
3. The subnet mask should be the same.
4. Hello, and the dead timer should be the same.
5. The stub flag must match.
6. Authentication must match.

New Section 25 Page 5

New Section 25 Page 6
New Section 25 Page 7
New Section 25 Page 8