Link State Routing-Open Shortest Path First (OSPF)-Types of links,
Graphical representation
Link-State Routing (LSR) – OSPF
Definition
Link-State Routing is a routing protocol in which each router maintains a map of the
network (called a link-state database) and independently calculates the shortest path to
every other router using algorithms like Dijkstra’s Shortest Path First (SPF).
OSPF (Open Shortest Path First) is a widely used link-state intra-domain (within an
autonomous system) routing protocol.
Key Features of OSPF
1. Hierarchical Structure: Uses areas (Area 0 = Backbone Area) to reduce routing
overhead.
Imagine a huge network with 100+ routers. If every router tries to know everything
about all routers, it becomes:
Too much information to store
Slower to calculate best paths
More traffic with updates
Solution: Divide the network into areas.
Simple,
What is an Area?
An area is like a “neighborhood” in the network.
Routers inside an area know everything about their own area.
For other areas, they only know summary information, not every detail.
Area 0 (Backbone Area)
There is always a central area called Area 0 (backbone).
All other areas must connect to Area 0 to communicate with each other.
Think of Area 0 as the main highway and other areas as local roads.
R1
Ba
R2 R3 R4 R5
R2, R3 are inside Area 1 → know all routers in Area 1.
R4, R5 are inside Area 2 → know all routers in Area 2.
R1 (ABR) connects Area 1 and Area 2 to backbone Area 0.
If R2 wants to send data to R4:
1. R2 sends packet to ABR1
2. ABR1 forwards it via Area 0 (backbone)
3. ABR2 forwards to Area 2 → R4
2. Supports VLSM: Can use variable-length subnet masks.
3. Cost-based Routing: Each link has a cost (based on bandwidth). OSPF chooses the
path with the lowest cumulative cost.
4. Uses Dijkstra SPF algorithm to compute the shortest path tree.
Types of Links in OSPF
OSPF recognizes different types of network links:
Link Type Description
Point-to-Point A direct connection between two routers. Cost = bandwidth
dependent.
Broadcast Multiple routers on the same network (like Ethernet). OSPF elects
a DR (Designated Router) and BDR (Backup DR) to reduce
LSAs.
Non-Broadcast Multi-router networks without broadcasting capability (like Frame
Multi-Access Relay). Uses manual neighbor configuration.
(NBMA)
Point-to-Multipoint One router connected to multiple routers over a network. Treats
each as a point-to-point link logically.
Virtual Link Connects OSPF areas that are not physically contiguous to Area 0
via another area.
Inter domain Routing-Path Vector Routing- Border Gateway Protocol
(BGPv4)
Inter-domain Routing
Definition: Inter-domain routing refers to routing between different
autonomous systems (AS).
Autonomous System (AS): A collection of IP networks and routers under
the control of a single organization (e.g., an ISP) that presents a common
routing policy to the Internet.
Purpose: Allows different networks (like ISPs) to exchange routing
information and reach destinations outside their own AS.
Key Points:
Works between ASs (unlike intra-domain routing like OSPF or RIP which
works within one AS).
Path Vector Routing
Definition: Path Vector Routing is a type of routing used for inter-domain
routing, where each route maintains the entire path (sequence of ASs) to
the destination.
How Path Vector Routing Works
1. Sharing reachable networks:
o Each Autonomous System (AS) tells its neighbors:
“I can reach these networks, and here’s the path of ASs to get
there.”
o Example:
AS1 can reach network [Link]/24 → AS_PATH = {AS1}
AS2 receives this and adds itself → AS_PATH = {AS2,
AS1}
2. Preventing loops:
o Every AS checks the AS_PATH before accepting a route.
o If the AS sees its own AS number in the path, it ignores the route.
o This avoids sending packets in a loop.
Key Points:
Avoids routing loops by keeping a path history.
Each route has:
o Destination network
o AS path (sequence of AS numbers)
o Other optional attributes like next-hop, origin, and policy
Border Gateway Protocol (BGPv4)
Definition: BGPv4 is the standard inter-domain routing protocol used on
the Internet today.
Type: It’s a path vector protocol.
Key Features:
1. Inter-domain routing: Exchanges routing information between ASs.
2. Path vector: Maintains AS path info for loop prevention.
3. Policy-based routing: Routing decisions are based on policies, not just
metrics like hop count.
4. Scalability: Handles thousands of routes on the Internet.
5. TCP-based: Uses TCP port 179 for reliable communication.
BGP Route Advertisement:
Advertises reachable networks (prefixes) and path info.
Each BGP router maintains a routing table, which includes:
o Network prefix
o Next hop
o AS path
o Other attributes like local preference, MED, etc.
BGP Attributes:
AS_PATH: Sequence of ASs a route passes through (used to prevent
loops).
NEXT_HOP: IP address of next router to reach destination.
LOCAL_PREF: Preference for exit routes within an AS.
MED (Multi-Exit Discriminator): Suggests preferred entry points into an
AS.
BGP Types:
1. External BGP (eBGP): Between different ASs.
2. Internal BGP (iBGP): Within the same AS.
Advantages of BGPv4
Highly scalable for the Internet.
Supports policy-based routing, not just shortest path.
Prevents routing loops across ASs.
Can handle multiple paths and failover.
Disadvantages / Limitations
Slower convergence compared to intra-domain protocols (like OSPF).
Complex configuration and policy management.