1️⃣ The Optimality Principle (Bellman, 1️957)

📌 Simple Statement:
If router J is on the optimal (best) path from I to K, then the path from J to K must also be
optimal.

2️⃣ Sink Tree Concept

A sink tree shows the optimal routes from ALL routers to ONE destination. It's called a "sink"
because all traffic flows toward one destination (like water to a sink).
Tree Properties:
 No loops - each router has exactly ONE path to destination F
 All paths are optimal (minimum hops in this example)
 F is the "root" where all traffic flows
 Every router knows which direction to send packets destined for F

3️⃣ How to Build a Sink Tree

Step 1: Choose a destination router (e.g., F)

Step 2: Find the shortest/best path from each router to F
Step 3: Mark only these optimal paths - they form a tree
Step 4: Each router only needs to know "which neighbor is on my optimal path to F"
[Link] PATH ALGORITHM

Shortest" doesn't always mean physically shortest - it depends on what you're optimizing
for.
Simple Examples:
1. Number of Hops (Fewest Stops)
 Path A→B→C = 2 hops
 Path A→B→E = 2 hops
→ Both are "equal" using this metric
2. Geographic Distance
 Path A→B→C = 10 + 50 = 60 km
 Path A→B→E = 10 + 20 = 30 km
→ A→B→E is "shorter"
3. Travel Time (Delay)
 Path via highway: 50 km but 30 minutes
  Path via city streets: 20 km but 45 minutes
→ Highway is "shorter" in time
Real-World Analogy:
Ask students: "Going to school: Do you take the route with fewest turns, shortest distance, or
fastest time?"
The Algorithm's Power: You can "weight" each edge with any metric (distance, time, cost,
bandwidth), and Dijkstra's algorithm finds the optimal path for whatever metric you choose.
Example weights:
 Distance in km
 Delay in milliseconds
 Cost in dollars
 Bandwidth capacity
 Combination of factors
3️.FLOODING
[Link] VECTOR ROUTING
[Link] STATE ROUTING’

Link State Routing is an advanced routing algorithm that replaced Distance Vector Routing
in the ARPANET in 1️979. Unlike Distance Vector Routing (which only exchanges distance
information with neighbors), Link State Routing allows each router to have a complete
map of the entire network topology.
Why was it developed?
Distance Vector Routing suffered from the Count-to-Infinity problem, causing slow
convergence when network topology changed. Link State Routing solves this by giving
every router complete network knowledge.

STEP 1️: DISCOVER NEIGHBORS

How it works:
 When router boots up: It sends special HELLO packets on each point-to-point line

 Response: The router on the other end sends back a reply with its globally unique
name

 Why unique names? So distant routers can distinguish between different routers
with similar connections
Case 1️: Point-to-Point Links (Simple)

Case 2️: Broadcast LAN (More Complex)

Problem: Multiple routers connected to same LAN - modeling as individual links is

wasteful
Solution: Introduce an artificial node 'N' to represent the LAN

Note: Path from A to C through the LAN is represented as A-N-C in the graph model. One
router on the LAN is designated to play the role of node N in the routing protocol.
STEP 2️: SET LINK COSTS (METRICS)
Purpose:
Each link needs a cost/distance metric for finding shortest paths
Methods to Determine Link Cost:
STEP 3️: BUILD LINK STATE PACKETS (LSP)
What is a Link State Packet?
A packet containing information about a router's direct neighbors and the cost to reach
them
Structure of Link State Packet:
LSP = [ Router ID | Sequence Number | Age | List of Neighbors with Costs ]
 Router ID: Identity of the sender router

 Sequence Number: Incrementing number for each new packet (to detect
duplicates/old packets)
 Age: Time-to-live field (decremented each second, packet discarded when age = 0)
 Neighbor List: All directly connected neighbors and cost to reach each
When to Build Link State Packets:

Trigger Description

Periodically At regular intervals (e.g., every 3️0 seconds)

Event-Driven When a line/neighbor goes down or comes up

Significant Change When link properties change appreciably (e.g., cost changes)

STEP 4: DISTRIBUTE LINK STATE PACKETS

Critical Requirement: ALL routers must get ALL link state packets quickly and reliably. If
different routers have different topology views, routing loops and unreachable
destinations can occur!
Distribution Method: CONTROLLED FLOODING
How Controlled Flooding Works:
1️. Each packet has a sequence number that increments with each new packet
2️. Routers maintain a list of all (source router, sequence number) pairs they've seen
3️. When LSP arrives:
o Check if it's NEW → Forward on all lines except incoming line
o Check if it's DUPLICATE → Discard
o Check if sequence number is LOWER than highest seen → Reject as obsolete
 4. Age field decremented each second; packet discarded when age = 0

Problems and Solutions:

Problem Solution

Sequence number wrap-around Use 3️2️-bit sequence number (takes 1️3️7 years to wrap at 1️ packet

Router crashes and loses sequence Age field timeout ensures old packets expire; fresh start after cras

Sequence corruption Age field prevents packets from living indefinitely

Packet lost forever Age decremented at each hop; packet discarded when age = 0

Packet Buffer Example at Router B:

STEP 5: COMPUTE SHORTEST PATHS (DIJKSTRA'S ALGORITHM)
Once router has collected all LSPs:
1️. Router can construct the complete network graph (knows all links and costs)
2️. Run Dijkstra's shortest path algorithm locally
3️. Build routing table showing which outgoing link to use for each destination
4. Install routing table and resume normal packet forwarding
[Link] Routing

 THE PROBLEM
 As networks grow larger, routing tables become HUGE!
• More router memory consumed
• More CPU time to scan tables
• More bandwidth to send routing updates
Eventually: It's not feasible for every router to know about every other router!
 ✅ THE SOLUTION: Hierarchical Routing
 Divide routers into REGIONS (like organizing a phone book by area codes)
• Each router knows detailed routes within its own region
• For other regions, router only needs one entry per region
• No need to know internal structure of other regions!
Hierarchical Routing.

+
Example: 5 Regions Network
[Link] Routing Methods
The RPF Algorithm
Step 1️: Broadcast packet arrives at router
Step 2️: Router asks: "Did this packet arrive on the link I normally use to send packets TO the
source?"
Step 3️a: If YES → This is probably the first copy → Forward on all other links
Step 3️b: If NO → This is probably a duplicate → Discard

[Link] ROUTING

multicasting: Sending a packet to a SPECIFIC GROUP of receivers

Use Cases:
• Multiplayer online games
• Live sports streaming to multiple locations
• Video conferencing
• Stock market data feeds
• Software updates to selected servers
Unicast vs Broadcast vs Multicast
APPROACH 1️: Dense Groups - Pruned Spanning Tree
Idea: Start with broadcast spanning tree, then PRUNE (remove) links that don't lead to group
members

Broadcast tree: 10 links (reaches everyone, even non-members)

• Group 1️ multicast tree: 7 links (only reaches Group 1 members) - 30% savings!
• Group 2️ multicast tree: 5 links (only reaches Group 2 members) - 50% savings!
• Different groups have different trees!
APPROACH 2️: Sparse Groups - Core-Based Tree (Shared Tree)
Idea: Build ONE shared tree for the entire group using a central "core" router
When to Use Each
Use Pruned Tree when:
• Group members scattered throughout network (dense)
• Need optimal paths from each sender
• Have enough memory for multiple trees

Use Core-Based Tree when:

• Small group in large network (sparse)
• Want to minimize memory and computation
• Single sender or core near sender
• This is what the Internet uses! (PIM-SM protocol)
[Link] ROUTING

Anycast: Send packet to the NEAREST member of a group

One-to-Nearest-One routing
Four Routing Types Comparison
Use Cases:
 DNS Servers: Query the nearest DNS server (faster response)
 Content Delivery Networks (CDNs): Get content from closest server
 Time Servers: Get time from nearest time server
 Load Balancing: Distribute load across multiple identical servers
 Key Idea: When any server with the right information will do, pick the nearest one!
1️[Link] FOR MOBILE HOSTS
THE PROBLEM

Challenge: How do we send packets to a host that keeps MOVING?

• Laptop moves from office to coffee shop to home

• Smartphone moves between cell towers
• Device changes networks constantly

Problem: How does the network find the mobile host to deliver packets?

✅ THE SOLUTION

Key Concepts:
• Permanent Home Address: Never changes (like your permanent mailing address)
• Home Agent: Representative at home location that tracks where you are
• Care-of Address: Temporary address at current location (like a forwarding address)
• Tunneling: Wrapping packets to forward them to the current location
The Mobile Routing Process (5 Steps)

The 5 Steps Explained

STEP 1️: Register Care-of Address

What happens: Mobile host arrives in San Diego and gets a local address (1️0.5.2️0.55)
Action: Mobile host sends registration message to home agent: "I'm now at 1️0.5.2️0.55"
Result: Home agent updates its records with the current location
STEP 2️: Sender Sends Packet to Home Address
What happens: Sender in Seattle wants to reach mobile host
Action: Sender uses permanent home address (1️92️.1️68.1️.1️00)
Result: Packet routed to New York (home location)
STEP 3️: Home Agent Tunnels Packet
What happens: Home agent intercepts packet (mobile not at home)
Action: Wraps original packet with NEW header addressed to care-of address (1️0.5.2️0.55)
Result: Encapsulated packet tunneled to San Diego
This is called: Tunneling - packet inside a packet!
STEP 4: Mobile Host Replies Directly
What happens: Mobile host receives encapsulated packet and unwraps it
Action: Sends reply DIRECTLY to sender (not through home agent)
Result: Triangle routing - outbound goes via home, return is direct
Bonus: Sender may learn care-of address during this step
STEP 5: Optimized Subsequent Packets (Optional)
What happens: Sender now knows care-of address
Action: Sender tunnels packets DIRECTLY to care-of address
Result: Bypasses home agent entirely - much faster!
Fallback: If mobile moves, sender can always use home address
What is Tunneling?

Triangle Routing Problem

The Issue: Packets take a circuitous route:

• Sender (Seattle) → Home Agent (New York) → Mobile Host (San Diego)
• This is inefficient if San Diego is far from New York!

The Solution: Step 5 optimization

• After first exchange, sender learns care-of address
• Subsequent packets go directly: Seattle → San Diego
• Bypasses home agent entirely!
1️1️.AD HOC NETWORK ROUTING

📌 What is an Ad Hoc Network (MANET)?

Ad Hoc Network: Mobile wireless nodes that act as BOTH hosts AND routers

Examples:
• Emergency workers at disaster site 🚒
• Military vehicles on battlefield 🪖
• Ships at sea ⛴️
• Laptops in area without WiFi 💻

Key Feature: No fixed infrastructure - nodes communicate peer-to-peer!

Fixed Network vs Ad Hoc Network
⚠️ THE CHALLENGE

Dynamic Topology:
• Nodes constantly moving in/out of range
• Connections appear and disappear randomly
• Routes become invalid without warning
• Must find NEW routes quickly!

Traditional routing algorithms assume stable topology - won't work here!

✅ SOLUTION: AODV Algorithm

AODV (Ad hoc On-Demand Distance Vector)

Key Ideas:
• On-Demand: Find routes ONLY when needed (saves battery & bandwidth)
• Route Discovery: Broadcast request using flooding
• Route Reply: Unicast reply back to sender
• Route Maintenance: Detect broken links and purge invalid routes
Route Discovery Process (Example: A wants to send to I)
Key Features of AODV

 On-Demand: Routes discovered only when needed (saves battery &

bandwidth)

 Sequence Numbers: Prevent loops and ensure fresh routes

 Limited Flooding: Uses TTL (Time to Live) to search in expanding rings

 Shared Routes: Multiple nodes can reuse discovered routes

 Quick Repair: Detects broken links and finds new routes quickly