Basic Routing Concepts and Protocols

1. Features of routing protocols

Routers use routing protocols for the following purposes.

 To discover all the available paths in the network.

 To learn how many paths exist between each source and destination.
 To select the fastest path if multiple paths exist between a source and the
destination.

2. Functions of routing protocols

The main functions of routing protocols are the following.

 Learn routing information from neighboring routers

 Advertise local routing information to neighboring routers
 Calculate the best route for each subnet of the network
 Provide a virtual map of all routes of the network
 Calculate the cost of each route and help the router choose the best and fastest
route

 Detect any change in the network and update all routers about that change
3. Types of routing protocols

There are three types of routing protocols: distance-vector, link-state, and hybrid.
Let's understand how each type of routing protocol works and how it differs from others.

Distance-vector routing protocols

Routers running distance-vector routing protocols periodically broadcast routing and

reachability information from all active interfaces. They also receive the same information
from their neighbors on their enable interfaces.

Distance-vector protocols use timers to broadcast routing information. Once their

periodic timer expires, they broadcast their routing information from all enable
interfaces, no matter whether the routing information has changed since the previous
broadcast or not.

Calculating/selecting the best route

 Distance-vector protocols use distance and direction to calculate and select the
best route for each subnet in the network. Distance is the number of routers that a
packet crosses to reach its destination.
 Distance is measured in terms of hops. Each instance where a packet goes through
a router is called a hop. For example, if a packet crosses four routers to reach its
destination, the number of hops is 4. The route with the least number of hops is
selected as the best route.
 The vector indicates the direction that a packet uses to reach its destination.

The following figure shows an example of a network running distance victor protocol.
In this network, the router R1 has three routes to reach the destination network. These
routes are the following.

1. The four-hop route (distance) through R2 (vector)

2. The two-hop route (distance) through R6 (vector)

3. The three-hop route (distance) through R7 (vector)

Since the second route has the lowest hop count, the router R1 uses this route to forward
all packets of the destination network.

Key points: -

 Distance-vector protocols do not use any mechanism to know who their neighbors
are.

 Distance-vector protocols learn about their neighbors by receiving their

broadcasts.

 Distance-vector protocols do not perform any formal handshake or hello process

with neighbors before broadcasting routing information.

 Distance-vector protocols do not verify whether neighbors received routing

updates or not.

 Distance-vector protocols assume that if a neighbor misses an update, it will learn

about the change in the next broadcast update.

 RIPv1 and IGRP are examples of distance-vector routing protocols.

Link-state routing protocols

Unlike distance-vector routing protocols, the link-state routing protocols do not share
routing and reachability information with anyone. Routers running link-state protocols
share routing information only with neighbors. To discover neighbors, link-state
protocols use a special protocol known as the Hello protocol.

After discovering all neighbors, the link-state protocols create three separate tables. One
of these tables keeps track of directly attached neighbors, one determines the topology of
the entire internetwork, and one is used as the routing table.

From all available routes, to select the best route for each destination in the network, the
link-state protocols use an algorithm called the Shortest Path First (SPF) algorithm.
OSPF is an example of link-state routing protocols.

Differences between distance-vector routing protocols and link-state routing protocols

Unlike distance-vector routing protocols that broadcast the entire routing table
periodically whether there are any changes or not, link-state routing protocols do not
exchange routing information periodically. They exchange information only when they
detect any change in the network.

Distance-vector protocols use local broadcasts, which are processed by every router on
the same segment, while link-state protocols use multicasts which are processed only by
the routers running the link-state protocol.

Distance-vector protocols do not verify routing broadcasts. They don't care whether the
neighboring routers received them or not. Link-state protocols verify routing updates. A
destination router running link-state protocol responds to the source router with an
acknowledgment when it receives a routing update.

Hybrid routing protocols

Hybrid routing protocols are the combination of both distance-vector and link-state
protocols. Hybrid routing protocols are based on distance-vector routing protocols but
contain many of the features and functions of link-state routing protocols.

Hybrid routing protocols are built upon the basic principles of a distance-vector protocol
but act like a link-state routing protocol. Hybrid protocols use the Hello protocol to
discover neighbors and form neighbor relationships. Hybrid protocols also send updates
only when a change occurs.

Hybrid routing protocols reduce the CPU and memory overhead by functioning like a
distance-vector protocol when it comes to processing routing updates; but instead of
sending out periodic updates like a distance-vector protocol, hybrid routing protocols
send out incremental, reliable updates via multicast messages, providing a more secure
network environment.

RIPv2, EIGRP, and BGR are examples of hybrid routing protocols.

That's all for this tutorial. If you like this tutorial, please don't forget to share it with
friends through your favorite social networking site
 OSI Model

 OSI stands for Open System Interconnection is a reference model that describes
how information from a software application in one computer moves through a
physical medium to the software application in another computer.

 OSI consists of seven layers, and each layer performs a particular network
function.

 OSI model was developed by the International Organization for Standardization

(ISO) in 1984, and it is now considered as an architectural model for the inter-
computer communications.

 OSI model divides the whole task into seven smaller and manageable tasks. Each
layer is assigned a particular task.

 Each layer is self-contained, so that task assigned to each layer can be performed
independently.

Characteristics of OSI Model:

  The OSI model is divided into two layers: upper layers and lower layers.

 The upper layer of the OSI model mainly deals with the application related issues,
and they are implemented only in the software. The application layer is closest to
the end user. Both the end user and the application layer interact with the
software applications. An upper layer refers to the layer just above another layer.

 The lower layer of the OSI model deals with the data transport issues. The data
link layer and the physical layer are implemented in hardware and software. The
physical layer is the lowest layer of the OSI model and is closest to the physical
medium. The physical layer is mainly responsible for placing the information on
the physical medium.

7 Layers of OSI Model

There are the seven OSI layers. Each layer has different functions. A list of seven layers
are given below:

1. Physical Layer

2. Data-Link Layer

3. Network Layer

4. Transport Layer

5. Session Layer

6. Presentation Layer

7. Application Layer
1) Physical layer

o The main functionality of the physical layer is to transmit the individual bits from
one node to another node.

o It is the lowest layer of the OSI model.

o It establishes, maintains and deactivates the physical connection.

o It specifies the mechanical, electrical and procedural network interface

specifications.

Functions of a Physical layer:

o Line Configuration: It defines the way how two or more devices can be
connected physically.

o Data Transmission: It defines the transmission mode whether it is simplex, half-

duplex or full-duplex mode between the two devices on the network.

o Topology: It defines the way how network devices are arranged.

o Signals: It determines the type of the signal used for transmitting the information.
2) Data-Link Layer

o This layer is responsible for the error-free transfer of data frames.

o It defines the format of the data on the network.

o It provides a reliable and efficient communication between two or more devices.

o It is mainly responsible for the unique identification of each device that resides on
a local network.

o It contains two sub-layers:

o Logical Link Control Layer

o It is responsible for transferring the packets to the Network layer of

the receiver that is receiving.

o It identifies the address of the network layer protocol from the

header.

o It also provides flow control.

o Media Access Control Layer

o A Media access control layer is a link between the Logical Link

Control layer and the network's physical layer.
 o It is used for transferring the packets over the network.

Functions of the Data-link layer

o Framing: The data link layer translates the physical's raw bit stream into packets
known as Frames. The Data link layer adds the header and trailer to the frame. The
header which is added to the frame contains the hardware destination and source
address.

o Physical Addressing: The Data link layer adds a header to the frame that
contains a destination address. The frame is transmitted to the destination address
mentioned in the header.

o Flow Control: Flow control is the main functionality of the Data-link layer. It is
the technique through which the constant data rate is maintained on both the
sides so that no data get corrupted. It ensures that the transmitting station such as
a server with higher processing speed does not exceed the receiving station, with
lower processing speed.

o Error Control: Error control is achieved by adding a calculated value CRC (Cyclic
Redundancy Check) that is placed to the Data link layer's trailer which is added to
the message frame before it is sent to the physical layer. If any error seems to
occurr, then the receiver sends the acknowledgment for the retransmission of the
corrupted frames.

o Access Control: When two or more devices are connected to the same
communication channel, then the data link layer protocols are used to determine
which device has control over the link at a given time.
3) Network Layer

o It is a layer 3 that manages device addressing, tracks the location of devices on the
network.

o It determines the best path to move data from source to the destination based on
the network conditions, the priority of service, and other factors.

o The Data link layer is responsible for routing and forwarding the packets.

o Routers are the layer 3 devices, they are specified in this layer and used to provide
the routing services within an internetwork.

o The protocols used to route the network traffic are known as Network layer
protocols. Examples of protocols are IP and Ipv6.

Functions of Network Layer:

o Internetworking: An internetworking is the main responsibility of the network

layer. It provides a logical connection between different devices.

o Addressing: A Network layer adds the source and destination address to the
header of the frame. Addressing is used to identify the device on the internet.

o Routing: Routing is the major component of the network layer, and it determines
the best optimal path out of the multiple paths from source to the destination.
 o Packetizing: A Network Layer receives the packets from the upper layer and
converts them into packets. This process is known as Packetizing. It is achieved by
internet protocol (IP).

4) Transport Layer

o The Transport layer is a Layer 4 ensures that messages are transmitted in the order
in which they are sent and there is no duplication of data.

o The main responsibility of the transport layer is to transfer the data completely.

o It receives the data from the upper layer and converts them into smaller units
known as segments.

o This layer can be termed as an end-to-end layer as it provides a point-to-point

connection between source and destination to deliver the data reliably.

The two protocols used in this layer are:

o Transmission Control Protocol

o It is a standard protocol that allows the systems to communicate over the

internet.

o It establishes and maintains a connection between hosts.

o When data is sent over the TCP connection, then the TCP protocol divides
the data into smaller units known as segments. Each segment travels over
the internet using multiple routes, and they arrive in different orders at the
 destination. The transmission control protocol reorders the packets in the
correct order at the receiving end.

o User Datagram Protocol

o User Datagram Protocol is a transport layer protocol.

o It is an unreliable transport protocol as in this case receiver does not send

any acknowledgment when the packet is received, the sender does not wait
for any acknowledgment. Therefore, this makes a protocol unreliable.

Functions of Transport Layer:

o Service-point addressing: Computers run several programs simultaneously due

to this reason, the transmission of data from source to the destination not only
from one computer to another computer but also from one process to another
process. The transport layer adds the header that contains the address known as a
service-point address or port address. The responsibility of the network layer is to
transmit the data from one computer to another computer and the responsibility
of the transport layer is to transmit the message to the correct process.

o Segmentation and reassembly: When the transport layer receives the message
from the upper layer, it divides the message into multiple segments, and each
segment is assigned with a sequence number that uniquely identifies each
segment. When the message has arrived at the destination, then the transport
layer reassembles the message based on their sequence numbers.

o Connection control: Transport layer provides two services Connection-oriented

service and connectionless service. A connectionless service treats each segment as
an individual packet, and they all travel in different routes to reach the
destination. A connection-oriented service makes a connection with the transport
layer at the destination machine before delivering the packets. In connection-
oriented service, all the packets travel in the single route.

o Flow control: The transport layer also responsible for flow control but it is
performed end-to-end rather than across a single link.

o Error control: The transport layer is also responsible for Error control. Error
control is performed end-to-end rather than across the single link. The sender
transport layer ensures that message reach at the destination without any error.
5) Session Layer

o It is a layer 3 in the OSI model.

o The Session layer is used to establish, maintain and synchronizes the interaction
between communicating devices.

Functions of Session layer:

o Dialog control: Session layer acts as a dialog controller that creates a dialog
between two processes or we can say that it allows the communication between
two processes which can be either half-duplex or full-duplex.

o Synchronization: Session layer adds some checkpoints when transmitting the

data in a sequence. If some error occurs in the middle of the transmission of data,
then the transmission will take place again from the checkpoint. This process is
known as Synchronization and recovery.
6) Presentation Layer

o A Presentation layer is mainly concerned with the syntax and semantics of the
information exchanged between the two systems.

o It acts as a data translator for a network.

o This layer is a part of the operating system that converts the data from one
presentation format to another format.

o The Presentation layer is also known as the syntax layer.

Functions of Presentation layer:

o Translation: The processes in two systems exchange the information in the form
of character strings, numbers and so on. Different computers use different
encoding methods, the presentation layer handles the interoperability between the
different encoding methods. It converts the data from sender-dependent format
into a common format and changes the common format into receiver-dependent
format at the receiving end.

o Encryption: Encryption is needed to maintain privacy. Encryption is a process of

converting the sender-transmitted information into another form and sends the
resulting message over the network.
 o Compression: Data compression is a process of compressing the data, i.e., it
reduces the number of bits to be transmitted. Data compression is very important
in multimedia such as text, audio, video.

7) Application Layer

o An application layer serves as a window for users and application processes to

access network service.

o It handles issues such as network transparency, resource allocation, etc.

o An application layer is not an application, but it performs the application layer

functions.

o This layer provides the network services to the end-users.

Functions of Application layer:

o File transfer, access, and management (FTAM): An application layer allows a

user to access the files in a remote computer, to retrieve the files from a computer
and to manage the files in a remote computer.

o Mail services: An application layer provides the facility for email forwarding and
storage.

o Directory services: An application provides the distributed database sources and is

used to provide that global information about various objects.
Routing Protocols in Computer Networks

Routing protocols are the set of rules and algorithms that routers use to communicate
with each other to find the most efficient path to transmit data packets from a sender to a
receiver. There are many routing protocols in computer networks, which we are going to
discuss in this article, but to understand routing protocols properly, let us first
understand routing.

Routing in Computer Networks

The term "routing" comes from the word "route", which means the path used to
transport data packets in computer networks. Routing is a procedure of moving data
packets from one network to another by discovering the finest path from the source to
the destination. The device that helps in finding the best path to forward data packets
from the source of one network to the destination of another network is called a router.

Types of Routing Protocols

There are three kinds of routing protocols in computer networks, which are given as:

1. Static Routing Protocol:

It can also be called non-adaptive routing. It is a manual configuration technique in

which the network administrator selects the best path to transfer the data packet from
source to destination. When a network administrator configures each router in the
routing table by hand, it is called static routing. After that, the router forwards the data
packets to the destination along the path defined by the network administrator.

It provides security because only the administrator has control over routing. It is ideal for
small organizations as it requires less bandwidth; hence, the cost is low.

2. Default Routing Protocol:

The default routing protocol can also be called the default route. When a router faces a
situation where it does not know the destination network of a data packet, then it uses a
method called "default routing". It is an approach in which the router transfers all data
packets to the single-hop device, regardless of the network.

The default route is the predetermined path the router uses to send all data packets when
encountering such a situation. When the destination network is unknown to the router,
then the router uses the default route and sends all data packets to that route.

3. Dynamic Routing Protocol:

It can also be called adaptive routing. It is an approach in which a router automatically

finds the best path to transmit data packets from the sender to the receiver and puts the
selected path information into the routing table of each router.

The router selects the path based on situations of the communication circuit or the
network topology. If there is any loss of connection between the nodes or there is a
problem with the route decided, the packed data is automatically adjusted on the new
route to be forwarded towards the destination. It is ideal for larger organizations where
many routers are used.
 Types of Dynamic Routing Protocols

There are 2 types of routing protocols, which are as follows:

1. Interior gateway protocols (IGPs):

The routing protocols that are used within the same network or autonomous system
(AS) facilitate the swapping of routing details between routers. The main function
of IGP is to search for the best route for forwarding data packets from sender to receiver
within an autonomous system.

2. Exterior gateway protocols (EGPs):

The routing protocols are used in various autonomous systems that facilitate the
swapping of routing details between routers. The main function of EGP is to search for
the best route for forwarding data packets from sender to receiver between various
autonomous systems.

Interior gateway protocols (IGPs)

They are further categorized into link-state routing protocols, distance-vector

routing protocols, and hybrid routing protocols.

1. Link-state routing protocols:

Link-state routing protocols are a type of interior gateway protocol which are used in
computer networks to decide the most suitable path to send data packets from one point
to another over the network. These protocols have a very good knowledge of the network
topology to forward the data packets to their destination efficiently. These protocols track
the status and connection type of each link; based on these factors, they produce
calculated metrics with the help of which routing is done.

There are several link-state routing protocols, which are discussed below:

o OSPF (Open Shortest Path First):

It is the popular and most widely used open standard protocol. It was introduced 34
years ago in 1989. It is one of the internal gateway protocols that use a link-state routing
algorithm or shortest path first algorithm that works within a single routing domain. This
algorithm was designed by an expert named Dijkstra, which is why it is also known
as Dijkstra Algorithm.

It uses Internet Protocol (IP) type 89 for communication. It supports Classless Inter-
Domain Routing (CIDR) and Variable Length Subnet Mask (VLSM). It is developed to
work with both IPv4 and IPv6 networks. It can divide a larger internetwork into smaller
internetwork called areas.

The OSPF router keeps the information of network topology, such as routers, links, and
networks within the same autonomous system. This information is stored in the form
of Link-State Advertisements (LSAs) in a database called the Link-State Database
(LSDB). Each router has a distinctive Router ID (RID) identifying an individual router.
Each router contains information about every other router connected to the network, due
to which the size of the link state database increases.

In OSPF, a large autonomous system is divided into OSPF areas, which reduces the size of
the LSDB.

Each area has its network, hosts, routers, and other devices. Each area is assigned an
identification number called area identification. Each area only stores information about
the devices within its area and doesn't need detailed knowledge about the network
topology.

The OSPF network must have a backbone area, also referred to as Area 0, to which all
other areas are connected. This connection allows routers in different areas to
communicate indirectly. In OSPF, there are Area Border Routers (ABRs) that connect
OSPF areas within an autonomous system and Autonomous System Border Routers
(ASBRs) that connect OSPF domains to external networks. The Open Shortest Path First
uses cost metrics to determine the most cost-effective route to get to the destination

o IS-IS (Intermediate System to Intermediate System):

The IS-IS protocol was developed by Digital Equipment Corporation (DEC) for the
International Standards Organization (ISO) in the late 1980s. It is one of the internal
gateway protocols that use link-state routing protocol, exchanges Link-State
Advertisements (LSAs), and maintains the Link-State Databases (LSDBs) for routing
within an autonomous system. Like OSPF, it also uses the Dijkstra Algorithm for finding
the best route to pass the data packets from source to destination, but IS-IS does not use
IP routing to exchange the routes like OSPF. IS-IS is based on Connectionless Network
Service (CLNS) for exchanging routes. It also supports Classless Inter-Domain Routing
(CIDR) and Variable Subnet Length Masking (VLSM).

It uses a two-level hierarchy: Level 1 routing and Level 2 routing. In Level 1 routing,
routers exchange routing information within the same area. In Level 2 routing, a router
provides connectivity between different areas. The routers that only directly
communicate with the routers of the same area are called Level 1 routers. The routers
which are communicating with routers in another area are called Level 2 routers. L2
routers are also responsible for routing traffic between different autonomous systems. IS-
IS can be used to route any network layer protocol. This flexibility makes it suitable for
diverse networks.

2. Distance-vector routing protocols

Distance-vector routing protocols are interior gateway protocols that are used in
computer networks to choose the most profitable path to transmit data packets from one
point to another within autonomous systems (ASes).

In distance-vector routing protocols, distance is the measurement of the path between

the two networks, and vector is the direction in which the data packets should be
forwarded so that they reach the destination by covering the distance. In routers, the
vector indicates the interfaces.

Distance-vector routing protocols calculate paths using distance and vectors to reach the
data packets to the destination network. This protocol periodically sends information
about routers to their neighbors whenever there is a change in the network topology.

There are several distance-vector routing protocols, which are discussed below:

o RIP (Routing Information Protocol):

It is one of the oldest dynamic routing protocols. It is a type of interior gateway protocol
used in computer networks, so it performs routing within an autonomous system. It is a
distance-vector routing protocol that uses a hop-count metric to discover the most
suitable route for transmitting data packets to the destination network.

This protocol routinely sends information about routers to their neighbors whenever
there is a modification in the network topology. It is a unicast routing protocol that is
used to establish one-to-one communication in which there will be one sender and one
receiver. It supports classful routing.

The metric used by RIP is hop count. From one router to another, one hop is counted.
RIP calculates the distance by counting the number of hops between the sender and
receiver. The distance with the minimum number of hop counts is considered the best
route for forwarding data packets. If all routes between the source and destination have
the same hop count, then RIP will send messages on all routes to balance the load on the
network. It is important to know that the maximum number of hop counts allowed in RIP
is 15 hops, which is why the maximum number of routers in the network can be 16
routers. The distance greater than 15 hops is considered unreachable.

To update the routers with the information about the routes present in the network, RIP
sends messages. There are two types of RIP messages: request message (it is sent by new
routers entering the network to obtain information about their neighboring routers) and
response message, which are classified into two types: solicited message (it is sent in
response to request message) and unsolicited message (it is sent at regular interval of 30
seconds to update neighboring routers regarding the routes and the networks).

There are 2 versions of the routing information protocol: RIP Version 1 (RIPv1) and RIP
Version 2 (RIPv2).

RIPv1 is the oldest version of RIP, which is a classful protocol, so it does not support
VLSM. It uses the hop count metric to find the finest path between source and
destination. It provides routing updates periodically to neighboring routers.

RIPv2 is a modern version of RIP, which is a classless routing protocol and supports
VLSM. It uses the hop count metric, but it can hold more information in routing updates.
It enhances security by supporting authentication.

o IGRP (Interior Gateway Routing Protocol):

It is a Cisco proprietary protocol since Cisco created it in the mid-1980s, so IGRP can only
be used within networks that use Cisco devices. It is a distance-vector routing protocol
that exchanges details between routers within the same autonomous system. It was
created to overcome the disadvantages of Routing Information Protocol (RIP), which
has a limited hop count of only 15. IGRP uses several metrics such as bandwidth,
reliability, load, Maximum Transmission Unit (MTU) size, and delay to select the best
path to the destination network, which results in a more accurate selection of routes.

The maximum limit of hop count in IGRP is 100, and it sends updates to the router
periodically, every 90 seconds. It provides more security to data packets traveling from
sender to receiver.

3. Hybrid Routing Protocols

It is a combination of link-state routing protocols and distance-vector routing

protocols. It has features of both of these protocols. It is used to provide the best route
to transfer data packets in a more reliable and faster manner.

The hybrid routing protocol is as follows:

EIGRP (Enhanced Interior Gateway Routing Protocol):

It is a Cisco proprietary protocol that is an improved version of the Interior Gateway

Routing Protocol. It is the successor to IGRP developed by Cisco to overcome the
shortcomings of IGRP. It is also known as a hybrid routing protocol as it has features of
both link-state routing protocols and distance-vector routing protocols.

The metrics it uses are bandwidth, load, delay, and reliability. It uses a Diffusing Update
Algorithm (DUAL) algorithm to ensure loop-free routing. It supports both Classless Inter-
Domain Routing (CIDR) and Variable Length Subnet Mask (VLSM). It is used for efficient
use of bandwidth and fast convergence.

Exterior gateway protocols (EGP)

The most widely used EGP is the Border Gateway Protocol (BGP).

Border Gateway Protocol (BGP):

It is a dynamic routing protocol that is used to figure out the best path to transfer data
packets from one network to another. It is an exterior gateway protocol that allows
routers to exchange information between different autonomous systems. It uses a path-
vector routing protocol, which maintains route details that get updated dynamically.

BGP enables efficient routing to determine the best route to the destination network that
provides the most reliable and faster communication. It is highly scalable as it can
seamlessly manage the growing number of interconnected devices and networks. It
supports multi-home connectivity, which means the organization can connect to multiple
internet service providers simultaneously and automatically select the best path.

BGP provides organizations with control over Internet traffic, which helps avoid
congested routes. BGP enhances internet resilience by quickly adapting to network
changes. If routes become congested with traffic, BGP can redirect the traffic to an
alternate path that ensures uninterrupted communication. It provides global
connectivity, which means that BGP allows networks from different locations to
interconnect and exchange routing information, which facilitates seamless data transfer
across borders.

Conclusion

o In this article, you have learned about routing protocols in computer networks.

o You have learned about routing, which is the process of finding the best possible
path to forward a data packet towards the destination network.

o You have learned that there are three types of routing protocols: static, default,
and dynamic routing protocols.

o Dynamic routing protocols are further classified into internal gateway protocols
and external gateway protocols.

o Interior gateway protocols are further classified into distance-vector routing

protocols, link-state routing protocols, and hybrid routing protocols.

o Link-state routing protocols are classified into Intermediate System to

Intermediate System (IS-IS) and Open Shortest Path First (OSPF).

o Distance-vector routing protocols are subclassified into Interior Gateway Routing

Protocol (IGRP) and Routing Information Protocol (RIP).

o Hybrid routing protocols include Enhanced Interior Gateway Routing Protocol

(EIGRP).

o External gateway protocols include the Border Gateway Protocol (BGP).

Distance Vector Routing Algorithm

ADVERTISEMENT

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

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

o Iterative: It is iterative in that its process continues until no more

information is available to be exchanged between neighbors.

o Asynchronous: It does not require that all of its nodes operate in the lock
step with each other.

o The Distance vector algorithm is a dynamic algorithm.

o It is mainly used in ARPANET, and RIP.

o Each router maintains a distance table known as Vector.

Three Keys to understand the working of Distance Vector Routing Algorithm:

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

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

o 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)+d v(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:
 o For each neighbor v, the cost c(x,v) is the path cost from x to directly attached
neighbor, v.

o The distance vector x, i.e., Dx = [ Dx(y) : y in N ], containing its cost to all

destinations, y, in N.

o The distance vector of each of its neighbors, i.e., D v = [ 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:

Backward Skip 10sPlay VideoForward Skip 10s

dx(y) = minv{ c(x,v) + dv(y)} for each node y in N

The node x has updated its own distance vector table by using the above equation and
sends its updated table to all its neighbors so that they can update their own distance
vectors.

Algorithm

At each node x,

Initialization

for all destinations y in N:

Dx(y) = c(x,y) // If y is not a neighbor then c(x,y) = ∞

for each neighbor w

Dw(y) = ? for all destination y in N.

for each neighbor w

send distance vector Dx = [ Dx(y) : y in N ] to w

loop

wait(until I receive any distance vector from some neighbor w)

 for each y in N:

Dx(y) = minv{c(x,v)+Dv(y)}

If Dx(y) is changed for any destination y

Send distance vector Dx = [ Dx(y) : y in N ] to all neighbors

forever

Note: In Distance vector algorithm, node x update its table when it either see any cost
change in one directly linked nodes or receives any vector update from some neighbor.

Let's understand through an example:

Sharing Information

o In the above figure, each cloud represents the network, and the number inside the
cloud represents the network ID.

o All the LANs are connected by routers, and they are represented in boxes labeled
as A, B, C, D, E, F.

o Distance vector routing algorithm simplifies the routing process by assuming the
cost of every link is one unit. Therefore, the efficiency of transmission can be
measured by the number of links to reach the destination.
 o In Distance vector routing, the cost is based on hop count.

In the above figure, we observe that the router sends the knowledge to the immediate
neighbors. The neighbors add this knowledge to their own knowledge and sends the
updated table to their own neighbors. In this way, routers get its own information plus
the new information about the neighbors.

Routing Table

Two process occurs:

o Creating the Table

o Updating the Table

Creating the Table

Initially, the routing table is created for each router that contains atleast three types of
information such as Network ID, the cost and the next hop.
 o NET ID: The Network ID defines the final destination of the packet.

o Cost: The cost is the number of hops that packet must take to get there.

o Next hop: It is the router to which the packet must be delivered.

o In the above figure, the original routing tables are shown of all the routers. In a
routing table, the first column represents the network ID, the second column
represents the cost of the link, and the third column is empty.

o These routing tables are sent to all the neighbors.

For Example:

1. A sends its routing table to B, F & E.

2. B sends its routing table to A & C.

 3. C sends its routing table to B & D.

4. D sends its routing table to E & C.

5. E sends its routing table to A & D.

6. F sends its routing table to A.

Updating the Table

o When A receives a routing table from B, then it uses its information to update the
table.

o The routing table of B shows how the packets can move to the networks 1 and 4.

o The B is a neighbor to the A router, the packets from A to B can reach in one hop.
So, 1 is added to all the costs given in the B's table and the sum will be the cost to
reach a particular network.

o After adjustment, A then combines this table with its own table to create a
combined table.

o The combined table may contain some duplicate data. In the above figure, the
combined table of router A contains the duplicate data, so it keeps only those data
which has the lowest cost. For example, A can send the data to network 1 in two
ways. The first, which uses no next router, so it costs one hop. The second requires
 two hops (A to B, then B to Network 1). The first option has the lowest cost,
therefore it is kept and the second one is dropped.

o The process of creating the routing table continues for all routers. Every router
receives the information from the neighbors, and update the routing table.

Final routing tables of all the routers are given below:

 Link State Routing

Link state routing is a technique in which each router shares the knowledge of its
neighborhood with every other router in the internetwork.

The three keys to understand the Link State Routing algorithm:

ADVERTISEMENT

o Knowledge about the neighborhood: Instead of sending its routing table, a

router sends the information about its neighborhood only. A router broadcast its
identities and cost of the directly attached links to other routers.

o Flooding: Each router sends the information to every other router on the
internetwork except its neighbors. This process is known as Flooding. Every router
that receives the packet sends the copies to all its neighbors. Finally, each and
every router receives a copy of the same information.

o Information sharing: A router sends the information to every other router only
when the change occurs in the information.

Link State Routing has two phases:

Reliable Flooding

o Initial state: Each node knows the cost of its neighbors.

o Final state: Each node knows the entire graph.

Route Calculation

Each node uses Dijkstra's algorithm on the graph to calculate the optimal routes to all
nodes.

o The Link state routing algorithm is also known as Dijkstra's algorithm which is
used to find the shortest path from one node to every other node in the network.

o The Dijkstra's algorithm is an iterative, and it has the property that after
kth iteration of the algorithm, the least cost paths are well known for k destination
nodes.

Let's describe some notations:

o c( i , j): Link cost from node i to node j. If i and j nodes are not directly linked,
then c(i , j) = ∞.
 o D(v): It defines the cost of the path from source code to destination v that has the
least cost currently.

o P(v): It defines the previous node (neighbor of v) along with current least cost
path from source to v.

o N: It is the total number of nodes available in the network.

Algorithm

Initialization

N = {A} // A is a root node.

for all nodes v

if v adjacent to A

then D(v) = c(A,v)

else D(v) = infinity

loop

find w not in N such that D(w) is a minimum.

Add w to N

Update D(v) for all v adjacent to w and not in N:

D(v) = min(D(v) , D(w) + c(w,v))

Until all nodes in N

In the above algorithm, an initialization step is followed by the loop. The number of times
the loop is executed is equal to the total number of nodes available in the network.

Backward Skip 10sPlay VideoForward Skip 10s

Let's understand through an example:

In the above figure, source vertex is A.

Step 1:

The first step is an initialization step. The currently known least cost path from A to its
directly attached neighbors, B, C, D are 2,5,1 respectively. The cost from A to B is set to 2,
from A to D is set to 1 and from A to C is set to 5. The cost from A to E and F are set to
infinity as they are not directly linked to A.

Ste N D(B),P( D(C),P( D(D),P( D(E),P( D(F),P(

p B) C) D) E) F)

1 A 2,A 5,A 1,A ∞ ∞

Step 2:

In the above table, we observe that vertex D contains the least cost path in step 1.
Therefore, it is added in N. Now, we need to determine a least-cost path through D
vertex.

a) Calculating shortest path from A to B

 1. v = B, w = D

2. D(B) = min( D(B) , D(D) + c(D,B) )

3. = min( 2, 1+2)>

4. = min( 2, 3)

5. The minimum value is 2. Therefore, the currently shortest path from A to B is 2.

b) Calculating shortest path from A to C

1. v = C, w = D

2. D(B) = min( D(C) , D(D) + c(D,C) )

3. = min( 5, 1+3)

4. = min( 5, 4)

5. The minimum value is 4. Therefore, the currently shortest path from A to C is 4.</
p>

c) Calculating shortest path from A to E

1. v = E, w = D

2. D(B) = min( D(E) , D(D) + c(D,E) )

3. = min( ∞, 1+1)

4. = min(∞, 2)

5. The minimum value is 2. Therefore, the currently shortest path from A to E is 2.

Note: The vertex D has no direct link to vertex E. Therefore, the value of D(F) is infinity.

Ste N D(B),P( D(C),P( D(D),P( D(E),P( D(F),P(

p B) C) D) E) F)

1 A 2,A 5,A 1,A ∞ ∞

 2 A 2,A 4,D 2,D ∞
D

Step 3:

In the above table, we observe that both E and B have the least cost path in step 2. Let's
consider the E vertex. Now, we determine the least cost path of remaining vertices
through E.

a) Calculating the shortest path from A to B.

1. v = B, w = E

2. D(B) = min( D(B) , D(E) + c(E,B) )

3. = min( 2 , 2+ ∞ )

4. = min( 2, ∞)

5. The minimum value is 2. Therefore, the currently shortest path from A to B is 2.

b) Calculating the shortest path from A to C.

1. v = C, w = E

2. D(B) = min( D(C) , D(E) + c(E,C) )

3. = min( 4 , 2+1 )

4. = min( 4,3)

5. The minimum value is 3. Therefore, the currently shortest path from A to C is 3.

c) Calculating the shortest path from A to F.

1. v = F, w = E

2. D(B) = min( D(F) , D(E) + c(E,F) )

3. = min( ∞ , 2+2 )

4. = min(∞ ,4)

5. The minimum value is 4. Therefore, the currently shortest path from A to F is 4.

 Ste N D(B),P( D(C),P( D(D),P( D(E),P( D(F),P(
p B) C) D) E) F)

1 A 2,A 5,A 1,A ∞ ∞

2 AD 2,A 4,D 2,D ∞

3 AD 2,A 3,E 4,E

E

Step 4:

In the above table, we observe that B vertex has the least cost path in step 3. Therefore, it
is added in N. Now, we determine the least cost path of remaining vertices through B.

a) Calculating the shortest path from A to C.

1. v = C, w = B

2. D(B) = min( D(C) , D(B) + c(B,C) )

3. = min( 3 , 2+3 )

4. = min( 3,5)

5. The minimum value is 3. Therefore, the currently shortest path from A to C is 3.

b) Calculating the shortest path from A to F.

1. v = F, w = B

2. D(B) = min( D(F) , D(B) + c(B,F) )

3. = min( 4, ∞)

4. = min(4, ∞)

5. The minimum value is 4. Therefore, the currently shortest path from A to F is 4.

 Ste N D(B),P( D(C),P( D(D),P( D(E),P( D(F),P(
p B) C) D) E) F)

1 A 2,A 5,A 1,A ∞ ∞

2 AD 2,A 4,D 2,D ∞

3 ADE 2,A 3,E 4,E

4 ADE 3,E 4,E

B

Step 5:

In the above table, we observe that C vertex has the least cost path in step 4. Therefore, it
is added in N. Now, we determine the least cost path of remaining vertices through C.

a) Calculating the shortest path from A to F.

1. v = F, w = C

2. D(B) = min( D(F) , D(C) + c(C,F) )

3. = min( 4, 3+5)

4. = min(4,8)

5. The minimum value is 4. Therefore, the currently shortest path from A to F is 4.

Ste N D(B),P( D(C),P( D(D),P( D(E),P( D(F),P(

p B) C) D) E) F)

1 A 2,A 5,A 1,A ∞ ∞

2 AD 2,A 4,D 2,D ∞

 3 ADE 2,A 3,E 4,E

4 ADEB 3,E 4,E

5 ADEB 4,E
C

Final table:

Ste N D(B),P( D(C),P( D(D),P( D(E),P( D(F),P(

p B) C) D) E) F)

1 A 2,A 5,A 1,A ∞ ∞

2 AD 2,A 4,D 2,D ∞

3 ADE 2,A 3,E 4,E

4 ADEB 3,E 4,E

5 ADEB 4,E
C

6 ADEB
CF

Disadvantage:

Heavy traffic is created in Line state routing due to Flooding. Flooding can cause an
infinite looping, this problem can be solved by using Time-to-leave field

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 Areas

OSPF divides the autonomous systems into areas where the area is a collection of
networks, hosts, and routers. Like internet service providers divide the internet into a
different autonomous system for easy management and OSPF further divides the
autonomous systems into Areas.

Routers that exist inside the area flood the area with routing information

In Area, the special router also exists. The special routers are those that are present at the
border of an area, and these special routers are known as Area Border Routers. This
router summarizes the information about an area and shares the information with other
areas.

Backward Skip 10sPlay VideoForward Skip 10s

All the areas inside an autonomous system are connected to the backbone routers, and
these backbone routers are part of a primary area. The role of a primary area is to provide
communication between different areas.

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.

How a router forms a neighbor relationship?

The first thing is happened before the relationship is formed is that each router chooses
the router ID.

Router ID (RID): The router ID is a number that uniquely identifies each router on a
network. The router ID is in the format of the IPv4 address. There are few ways to set the
router ID, the first way is to set the router ID manually and the other way is to let the
router decides itself.

The following is the logic that the router chooses to set the router ID:

o Manually assigned: The router checks whether the router ID is manually set or not.
If it manually set, then it is a router ID. If it is not manually set, then it will choose
the highest 'up' status loopback interface IP address. If there are no loopback
interfaces, then it will choose the highest 'up' status non-loopback interface IP
address.

Two routers connected to each other through point to point or multiple routers are
connected can communicate with each other through an OSPF protocol. The two routers
are adjacent only when both the routers send the HELLO packet to each other. When
both the routers receive the acknowledgment of the HELLO packet, then they come in a
two-way state. As OSPF is a link state routing protocol, so it allows to create the neighbor
relationship between the routers. The two routers can be neighbors only when they
belong to the same subnet, share the same area id, subnet mask, timers, and
authentication. The OSPF relationship is a relationship formed between the routers so
that they can know each other. The two routers can be neighbors if atleast one of them is
designated router or backup designated router in a network, or connected through a
point-to-point link.

Types of links in OSPF

A link is basically a connection, so the connection between two routers is known as a link.

There are four types of links in OSPF:

1. Point-to-point link: The point-to-point link directly connects the two routers
without any host or router in between.

2. Transient link: When several routers are attached in a network, they are known
as a transient link.
The transient link has two different implementations:
Unrealistic topology: When all the routers are connected to each other, it is known
as an unrealistic topology.
Realistic topology: When some designated router exists in a network then it is
known as a realistic topology. Here designated router is a router to which all the
routers are connected. All the packets sent by the routers will be passed through
the designated router.

3. Stub link: It is a network that is connected to the single router. Data enters to the
network through the single router and leaves the network through the same
router.

4. Virtual link: If the link between the two routers is broken, the administration
creates the virtual path between the routers, and that path could be a long one
also.

OSPF Message Format

The following are the fields in an OSPF message format:

 o Version: It is an 8-bit field that specifies the OSPF protocol version.

o Type: It is an 8-bit field. It specifies the type of the OSPF packet.

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

o Source IP address: It defines the address from which the packets are sent. It is a
sending routing IP address.

o Area identification: It defines the area within which the routing takes place.

o Checksum: It is used for error correction and error detection.

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

o Authentication: It is a 32-bit field that contains the actual value of the

authentication data.

OSPF Packets

There are five different types of packets in OSPF:

o Hello
 o Database Description

o Link state request

o Link state update

o Link state Acknowledgment

Let's discuss each packet in detail.

1. Hello packet

The Hello packet is used to create a neighborhood relationship and check the neighbor's
reachability. Therefore, the Hello packet is used when the connection between the
routers need to be established.

2. Database Description

After establishing a connection, if the neighbor router is communicating with the system
first time, it sends the database information about the network topology to the system so
that the system can update or modify accordingly.

ADVERTISEMENT

3. Link state request

The link-state request is sent by the router to obtain the information of a specified route.
Suppose there are two routers, i.e., router 1 and router 2, and router 1 wants to know the
information about the router 2, so router 1 sends the link state request to the router 2.
When router 2 receives the link state request, then it sends the link-state information to
router 1.

4. Link state update

The link-state update is used by the router to advertise the state of its links. If any router
wants to broadcast the state of its links, it uses the link-state update.

5. Link state acknowledgment

The link-state acknowledgment makes the routing more reliable by forcing each router to
send the acknowledgment on each link state update. For example, router A sends the link
state update to the router B and router C, then in return, the router B and C sends the
link- state acknowledgment to the router A, so that the router A gets to know that both
the routers have received the link-state update.
OSPF States

The device running the OSPF protocol undergoes the following states:

o Down: If the device is in a down state, it has not received the HELLO packet.
Here, down does not mean that the device is physically down; it means that the
OSPF process has not been started yet.

o Init: If the device comes in an init state, it means that the device has received the
HELLO packet from the other router.

o 2WAY: If the device is in a 2WAY state, which means that both the routers have
received the HELLO packet from the other router, and the connection gets
established between the routers.

o Exstart: Once the exchange between the routers get started, both the routers
move to the Exstart state. In this state, master and slave are selected based on the
router's id. The master controls the sequence of numbers, and starts the exchange
process.

o Exchange: In the exchange state, both the routers send a list of LSAs to each other
that contain a database description.

o Loading: On the loading state, the LSR, LSU, and LSA are exchanged.

o Full: Once the exchange of the LSAs is completed, the routers move to the full
state.

Router attributes

Before going to the Extract state, OSPF chooses one router as a Designated router and
another router as a backup designated router. These routers are not the type, but they are
the attributes of a router. In the case of broadcast networks, the router selects one router
as a designated router and another router as a backup designated router. The election of
designated and the backup designated router is done to avoid the flooding in a network
and to minimize the number of adjacencies. They serve as a central point for exchanging
the routing information among all the routers. Since point-to-point links are directly
connected, so DR and BDR are not elected.

If DR and BDR are not elected, the router will send the update to all the adjacent
neighbors, leading to the flooding in a network. To avoid this problem, DR and BDR are
elected. Each non-DR and non-BDR send the update only to the DR and BDR instead of
exchanging it with other routers in a network segment. DR then distributes the network
topology information to other routers in the same area whereas the BDR serves a
substitute for the DR. The BDR also receives the routing information from all the router
but it does not distribute the information. It distributes the information only when the
DR fails.

The multicast address 224.0.0.6 is used by the non-DR and non-BDR to send the routing
information to the DR and BDR. The DR and BDR send the routing information to the
multicast address 224.0.0.5.

Based on the following rules, the DR and BDR are elected:

o The router with the highest OSPF priority is chosen as the DR. By default, the
highest priority is set as 1.

o If there is no highest priority, then the router with the highest router Id is chosen
as the DR, and the router with the second-highest priority is chosen as the BDR.

Let's understand this scenario through an example.

In the above figure, R1 is chosen as the DR, while R2 is chosen as the BDR as R1 has the
highest router ID, whereas the R2 has the second-highest router ID. If the link fails
between R4 and the system, then R4 updates only R1 and R4 about its link failure. Then,
DR updates all the non-DR and non-BDR about the change, and in this case, except R4,
only R3 is available as a non-DR and non-BDR.