What is Routing?

OSPF (Open Shortest Path First) Overview

Routing is the process of determining the best OSPF (Open Shortest Path First) is a link-state
path for data packets to travel from a source to a routing protocol widely used in large enterprise
destination across a network. It involves routers networks. It operates within an Autonomous
that forward packets based on routing tables and System (AS) and ensures efficient routing by
protocols to ensure efficient and reliable data dynamically calculating the shortest path using
delivery. the Dijkstra algorithm.
Types of Routing features of the OSPF.
1. Static Routing
Routes are manually configured by the network 1. OSPF supports multiple circuit load balancing
administrator. because it can store multiple routes to a
Suitable for small, simple, and stable networks. destination.
2. OSPF can converge very quickly to network
Example: Home or small office networks.
topology change.
3. OSPF support multiple metrics.
2. Dynamic Routing 4. OSPF is not susceptible to routing loops.
Routes are automatically adjusted based on 5. OSPF support for variable length subnetting by
network conditions using routing protocols. including the subnet mask in the routing message.
Suitable for large, complex, and constantly
changing networks. Advantages:
Efficient routing with minimal bandwidth usage.
Examples: OSPF (Open Shortest Path First), RIP Supports large and complex networks through
(Routing Information Protocol), BGP hierarchical design.
Quick convergence and fault recovery.
Characteristics of a Routing Algorithm
Disadvantages:
1. Correctness
More complex configuration than distance-vector
Should ensure accurate delivery of packets to protocols.
their intended destination. Higher memory and CPU usage due to database
2. Simplicity management.
Should be easy to implement and maintain.
Path vector routing
3. Robustness
Should handle changes in the network, such as link is a type of routing protocol used in networking
failures, without crashing. where each router or node maintains a list of
4. Stability the paths (or sequences of nodes) that data
Should not cause frequent route changes that can should traverse to reach a destination. Unlike
lead to oscillations and network instability. other routing protocols that focus on metrics
like distance or cost, path vector routing
5. Fairness
emphasizes the sequence of network segments
Should distribute network resources equitably (called paths) a packet must take.
across all users.
6. Efficiency
Should minimize overhead and maximize Advantages of Path Vector Routing:
throughput by choosing optimal paths.
1. Simple Path Representation: The use of simple
7. Scalability paths (lists of AS numbers) makes the routing
Should work effectively in both small and large process easy to understand and follow.
networks. 2. Loop Prevention: The path vector approach
8. Convergence inherently prevents routing loops by tracking and
The time it takes for all routers to update their propagating the entire path
routing tables and reach a consistent state. 3. Scalability: Path vector routing can efficiently
scale to large, distributed networks, as
9. Optimality demonstrated by BGP, which handles the vast
Should find the shortest or least-cost path to the interconnections between global Autonomous
destination. Systems.
Direct and Indirect Delivery in Networking Routing Information Protocol (RIP)

Direct and indirect delivery are two methods Routing Information Protocol (RIP) is a distance-
used for delivering packets in a network vector routing protocol used to dynamically route
data in an IP network. It is one of the oldest
depending on the destination's proximity to
routing protocols and operates by periodically
the source. sharing routing information with neighboring
1. Direct Delivery routers.
Definition: Direct delivery occurs when the
source and destination are on the same Key Characteristics of RIP:
physical or logical network (i.e., within the
same subnet). 1. Distance-Vector Protocol: Routes are chosen
Process: based on the hop count (number of routers
between the source and destination).
1. The source device checks the destination IP
2. Hop Count Limit: The maximum allowable hop
address. count is 15. A hop count of 16 indicates an
2. If the destination IP is within the same unreachable destination.
subnet, the packet is sent directly using the 3. Periodic Updates: Routers send updates every
MAC address obtained through ARP (Address 30 seconds to their neighbors, sharing their entire
Resolution Protocol). routing table.
Example: 4. Routing Algorithm: Uses the Bellman-Ford
A device with IP [Link] sending a packet to algorithm to calculate the best path.
5. Classful and Classless Support:
[Link] within the same subnet
RIP v1: Classful, does not support subnet masks.
([Link]/24). RIP v2: Classless, supports Variable Length Subnet
Use Case: Local Area Networks (LANs) where Masking (VLSM) and authentication.
devices communicate without routing.
Advantages of RIP:
2. Indirect Delivery Simple Configuration: Easy to set up and manage.
Definition: Indirect delivery occurs when the Broad Compatibility: Supported by almost all
networking devices.
source and destination are on different Low Resource Requirement: Minimal CPU and
networks, requiring the packet to be forwarded memory usage.
through one or more routers. Disadvantages of RIP:
Process: Limited Scalability: The hop count limit of 15
1. The source device sends the packet to the restricts its use in large networks.
Slow Convergence: Periodic updates cause slower
default gateway (router). convergence compared to modern protocols.
2. The router forwards the packet to the next Inefficient Bandwidth Usage: Regular updates
appropriate router until it reaches the consume network bandwidth.
destination’s network. No Advanced Features: Lacks support for modern
3. The final router performs direct delivery to enhancements like traffic engineering or load
balancing.
the destination.

Link-State Routing Protocol

Link-state routing is a type of routing protocol that maintains a comprehensive map of the network
by exchanging detailed information about the network's topology. Each router in a link-state
protocol independently calculates the best path to each destination using this information.

Key Characteristics of Link-State Routing:

1. Complete Network View: Each router builds a complete topology map of the network.
2. Frequent Updates: Updates are triggered by network changes, not periodic broadcasts.
3. Dijkstra's Algorithm: Used to compute the shortest path to all destinations.
4. Hierarchical Design Support: Reduces overhead by segmenting the network into areas.
5. Fast Convergence: Quickly adapts to topology changes, minimizing downtime

How Link-State Routing Works:

1. Neighbor Discovery: Routers use "Hello" packets to discover and maintain neighbors.
2. Link-State Advertisements (LSAs): Routers share LSAs containing information about their links and
neighbors.
3. Link-State Database (LSDB): Each router maintains an LSDB containing all received LSAs.
4. Shortest Path Calculation: Routers run Dijkstra’s algorithm on the LSDB to determine the best
paths.
5. Routing Table Update: The calculated shortest paths are installed in the routing table.
IGMP Distance-Vector Routing Protocol
Distance-vector routing is a type of routing
is an acronym for Internet Group protocol that determines the best path to a
Management Protocol. IGMP is a destination based on distance (measured in hops
communication protocol used by hosts and or other metrics) and the direction (next hop).
adjacent routers for multicasting Routers share their routing tables with directly
connected neighbors periodically or when
communication with IP networks and uses
changes occur.
the resources efficiently to transmit the Key Characteristics of Distance-Vector Routing:
message/data packets. Multicast 1. Simple Routing Information: Routers advertise
communication can have single or multiple their entire routing table to neighbors.
senders and receivers and thus, IGMP can 2. Metric-Based: Routes are selected based on
be used in streaming videos, gaming, or web metrics such as hop count, bandwidth, or delay.
conferencing tools, This protocol is used on 3. Periodic Updates: Routing updates are sent at
IPv4 networks and for using this on IPv6, regular intervals.
multicasting is managed by Multicast 4. Bellman-Ford Algorithm: Used to calculate the
Listener Discovery (MLD). shortest path to destinations.
5. No Full Network Knowledge: Routers only know
Working of IGMP the direction and distance, not the entire network
topology.
IGMP works on devices that are capable of
handling multicast groups and dynamic Distance-Vector Routing Algorithm (Bellman-Ford
multicasting. These devices allow the host Algorithm)
to join or leave the membership in the
The Bellman-Ford algorithm is used in distance-
multicast group. These devices also allow to vector routing to calculate the shortest path to
add and remove clients from the group. each destination in a network. Each router
This communication protocol is operated maintains a routing table with information about
between the host and the local multicast the distance and next hop for every known
router. When a multicast group is created, destination
the multicast group address is in the range Example Network Diagram:
of class D (224-239) IP addresses and is
forwarded as the destination IP address in A -----1----- B -----3----- C
the packet. | |
2 1
L2 or Level-2 devices such as switches are
used in between host and multicast router | |
for IGMP snooping. IGMP snooping is a D ------------ E
process to listen to the IGMP network
traffic in controlled manner. Switch
receives the message from host and
forwards the membership report to the
local multicast router. The multicast traffic
is further forwarded to remote routers from
local multicast routers using PIM (Protocol
Independent Multicast) so that clients can
receive the message/data packets. Clients
wishing to join the network sends join
message in the query and switch intercepts
the message and adds the ports of clients
to its multicast routing table.
Unicast Routing vs. Multicast Routing Inter-Domain vs. Intra-Domain Routing

Both unicast and multicast routing are Both inter-domain and intra-domain routing are
methods of delivering data packets, but they
essential for managing traffic in different parts of
differ in how they handle the delivery and the
number of recipients. a network, but they operate at different scopes
and with different protocols.
1. Unicast Routing
Definition: Unicast routing is the process of 1. Intra-Domain Routing
sending data from one source to one specific Definition: Intra-domain routing occurs within a
destination.
single Autonomous System (AS)—a network or
Key Characteristics:
One-to-One communication. group of networks under a single administrative
Each packet is sent individually to each control.
destination. Scope: Internal routing within an organization's
Uses standard routing protocols like OSPF, network.
RIP, EIGRP, and BGP.
Advantages: Routing Protocols:
Simple to implement and manage.
OSPF (Open Shortest Path First): Link-state
Ensures dedicated communication between
sender and receiver. protocol, fast convergence.
Disadvantages: EIGRP (Enhanced Interior Gateway Routing
Inefficient when sending the same data to Protocol): Hybrid protocol (Cisco proprietary).
multiple recipients (e.g., video streaming to RIP (Routing Information Protocol): Distance-
multiple users). vector protocol, simpler but less scalable.
Example:
A client requests a webpage from a web server
(HTTP request Characteristics:
Focuses on optimizing routes within the AS.
2. Multicast Routing Uses metrics like hop count, bandwidth, and delay
Definition: Multicast routing is the process of for route selection.
sending data from one source to multiple Example: Routing between different departments
specific destinations that belong to a
within a corporate LAN.
multicast group.
Key Characteristics:
One-to-Many or Many-to-Many 2. Inter-Domain Routing
communication. Definition: Inter-domain routing manages traffic
Data is sent to a multicast group identified by between multiple Autonomous Systems (ASes),
a special multicast IP address ([Link] to often across different organizations or ISPs.
[Link]). Scope: External routing between organizations or
Routers use multicast routing protocols like
across the Internet.
PIM (Protocol Independent Multicast), IGMP
(Internet Group Management Protocol), and
DVMRP (Distance Vector Multicast Routing Routing Protocols:
Protocol). BGP (Border Gateway Protocol): The standard
Advantages: protocol for inter-domain routing, focusing on
Efficient for sending the same data to multiple path-vector routing.
recipients, reducing bandwidth usage.
Ideal for applications like live video streaming,
IPTV, and online gaming. Characteristics:
Disadvantages: Emphasizes policy-based routing rather than
More complex to configure and manage. shortest path.
Requires support from network infrastructure Handles scalability, policy enforcement, and route
(routers, switches). aggregation.
Example:
Example: Routing traffic between two ISPs or from
A live video conference streamed to multiple
users in different locations. a corporate network to the Internet.
BGP. BORDER GATE WAY PROTOCOL

The purpose of an exterior gateway protocol is to

enable two different Autonomous System (AS) to
exchange routing information so that IP traffic can
flow across the autonomous system border.

BGP was developed for use in conjunction with

internets that employ the TCP/IP protocol suite.
The BGP is an interdomain routing protocol that is
used to exchange network reachability
information among BGP routers (Also called BGP
speakers).

• Each BGP speaker establishes a TCP connection

with one or more BGP speakers (routers). Two
routers are considered to be neighbours if they
are attached to the same subnetwork.

Explain the Djkastra’s algorithm for shortest

If the two routers are in different autonomous
path routing.
systems, they may wish to exchange routing
information.
Ans. The algorithm maintains a set of visited
BGP performs three functional procedures. vertices and a set of unvisited vertices. It
1. Neighbour acquisition 2. Neighbour reachability starts at the source
3. Network reachability. vertex and iteratively selects the unvisited
vertex with the smallest tentative distance
• Neighbour acquisition procedures used for from the source. It
exchanging the routing information between two then visits the neighbors of this vertex and
routers in different Autonomous Systems (AS). To updates their tentative distances if a shorter
perform neighbour acquisition, one router sends path is found. This
an open message to another. If the target router
process continues until the destination
accepts the request, it returns a keepalive
vertex is reached, or all reachable vertices
message in response.
have been visited.
Once a neighbour relationship is established, the
• The algorithm starts at a vertex and works
neighbour reachability procedure is used to
its way through all the other vertices,
maintain the relationship. Both sides needs to be
assured that the other side still exists and is still following a set of steps:
engaged in the neighbour relationship. For this 1. Create a set of all unvisited nodes
purpose, both routers send keepalive messages to 2. Assign each node a distance from the
each other. Both sides router maintains a starting node
database of the subnetworks that it can reach and 3. Select the unvisited node with the shortest
the perferred route for reaching that subnetwork. distance from the starting node as the
If the database changes, router issues an update current node
message that is broadcast to all other routers 4. Update the distances of the current node's
implementing BGP. By the broadcasting of these unvisited neighbors
updata message, all the BGP routers can build up 5. Mark the current node as visited and
and maintain routing information. remove it from the set of unvisited nodes
BGP connections inside an autonomous system 6. Repeat steps 3–5 until the unvisited set is
are called internal BGP (iBGP) and BGP empty or contains only unreachable nodes
connections between different autonomous
systems are called external BGP (eBGP).