NETWORK LAYER

🌐 Network Layer – Big Picture

●​ The network layer is inside every device connected to the Internet — billions of routers
and hosts.
●​ It is the glue that holds the Internet together.
●​ The study of the network layer is split into two parts:
1.​ Data Plane
2.​ Control Plane

🟦 1. Data Plane (Chapter 4)

Local, per-router actions

●​ It is about forwarding: moving a datagram from input link → output link.

●​ Happens very fast (nanoseconds).
●​ Implemented in hardware.

What we study in Data Plane:

●​ Big-picture view of network layer

●​ Inside a router (“guts” of a router)
●​ IP protocol
●​ IP datagram format
●​ IP addressing
●​ NAT
●​ IPv6
●​ Generalized forwarding

🟩 2. Control Plane (Chapter 5)

Network-wide logic, end-to-end view

●​ Determines the path a packet takes from source → destination.

 ●​ Involves routing and network management.
●​ Routing = network-wide process; happens in seconds, runs in software.

⭐ Difference Between Forwarding & Routing

Feature Forwarding Routing

Where Inside one router Across all routers

Action Move packet to correct out port Decide end-to-end

path

Speed Nanoseconds (hardware) Seconds (software)

Analogy Passing through one Planning full road trip

roundabout

🟧 Network Layer Services at Sender

●​ Takes TCP/UDP segment
●​ Encapsulates into an IP datagram
●​ Adds IP addresses
●​ Passes to link layer

🟧 At Receiver
●​ Network layer receives datagram
●​ Checks checksum
●​ Removes IP header
●​ Sends segment to TCP/UDP

🟥 Network Layer Service Model

(Important!)
Different networks can offer guarantees like:

●​ Guaranteed delivery
●​ Guaranteed delay
●​ In-order delivery
●​ Minimum bandwidth

BUT…

Internet uses BEST-EFFORT service

●​ No guarantee of delivery
●​ No guarantee of delay
●​ No guarantee of order or bandwidth

Why is best-effort successful?

●​ Simpler and easy to deploy

●​ Internet has enough bandwidth today
●​ Apps (like Netflix/CDNs) built huge infrastructures to compensate
●​ TCP congestion control helps
●​ Made the Internet scalable

🔵 Control Plane Approaches

There are two approaches:

🟣 1. Traditional Control Plane

●​ Every router runs routing algorithms itself.
●​ Algorithms like OSPF, RIP, BGP run inside each router.
●​ Routers exchange routing info with other routers. Router talks to each other.
●​ Each router computes its own forwarding table.
🟢 2. Software-Defined Networking (SDN)
●​ A central controller (remote server) makes decisions.
●​ The controller computes the forwarding tables.
●​ Routers do NOT run routing algorithms.
●​ Routers simply forward based on the table the controller gives them.

Sure! Here’s a detailed, structured set of notes from the lecture you provided. I’ve organized
it clearly and included all the important points you emphasized, using consistent terminology for
easy recall.

Router Forwarding Function – Detailed

Notes
1. Router Architecture Overview
●​ Router’s main job: forward packets from input port → output port.
●​ Router consists of:
○​ Input ports
○​ Output ports
○​ Switching fabric (core that connects inputs → outputs)
○​ Routing processor (CPU) – handles control plane functions.
●​ Input/Output ports implement:
○​ Physical layer (signal reception, conversion to bits)
○​ Link layer (assemble frames, error checking)
○​ Part of network layer (forwarding functions)
●​ Router sizes:
○​ Home router: ~6 ports
○​ Backbone router: hundreds of ports
○​ Port speed: multiple Gbps
●​ Data plane vs Control plane:
○​ Data plane → high-speed, hardware-based forwarding.
○​ Control plane → slower, software-based routing table computation.
2. Input Port – Functions
Three main layers at input port:

1.​ Physical Layer (Line Termination)

○​ Receives raw bits from copper, fiber, or wireless link.
2.​ Link Layer
○​ Groups bits into frames (Ethernet, etc.)
○​ Checks frame integrity (CRC)
○​ Extracts IP packet for network layer
3.​ Network Layer – Lookup & Forwarding
○​ Main task: determine output port for packet
○​ Operates as “match + action”:
■​ Match: destination IP (or other header fields for generalized forwarding)
■​ Action: forward packet to the chosen output port

3. Forwarding Tables
●​ Maps destination addresses / prefixes → output ports.
●​ Problem: 2³² (~4 billion) possible IP addresses → cannot store all individually.
●​ Solution: aggregate into ranges or prefixes.

Destination-Based Forwarding (Traditional)

●​ Forward based only on destination IP.

●​ Table example:

4. Longest Prefix Matching

●​ Uses prefix + wildcard rather than explicit ranges.
●​ Rule: choose the longest matching prefix → most specific match.
●​ Example:​
Packet destination [Link] matches both /21 and /24 → choose /24 → output port 1.
●​ Why needed: flexible, hierarchical routing; can override parts of larger blocks.

5. TCAM – Fast Forwarding Lookup

●​ Forwarding table stored in input port memory.
 ●​ Hardware used: TCAM (Ternary Content Addressable Memory).

Features of TCAM

1.​ Stores prefixes + output port mappings

2.​ Supports 3 states: 0, 1, * (“don’t care”)
3.​ Matches packet destination against all entries in parallel
4.​ Returns longest prefix match in 1 clock cycle
5.​ Ensures line-rate forwarding
●​ Flow: Packet arrives → input port → TCAM lookup → output port determined → send to
switching fabric

6. Generalized Forwarding
●​ Forwarding can consider any header field, not just destination IP:
○​ IP source/dest, protocol type
○​ TCP/UDP source/dest ports
○​ Link layer (MAC) addresses
●​ Example:
○​ TCP packet from source [Link] → output port 1
○​ UDP packet from same source → output port 2

7. Switching Fabric
●​ Core of router: moves packet input → output port.
●​ Key characteristic: switching rate
○​ Non-blocking switch: can handle all incoming traffic simultaneously
○​ Cheaper switches may block → packets queue at input ports

Switching via memory :

Packet arrives at input port

●​ Physical layer + link layer read the bits and assemble the packet.
●​ Packet is stored in input port memory (input buffer).

CPU looks at the packet header

●​ Checks destination IP address.

●​ Looks up the forwarding table in memory (match + action).
 ●​ Finds the correct output port.

Packet transfer via memory

●​ CPU reads the packet from input buffer.

●​ CPU writes it into the memory (buffer) of the correct output port.​

Output port sends packet on the link

●​ Output port reads the packet from its memory.

●​ Sends bits to the physical link.

Switching via bus :

1.​ Shared Bus Concept​

○​ Inside the router, there is one internal bus (like a high-speed wire connecting all
input and output ports).
○​ All input ports are connected to this bus.​

○​ All output ports are also connected to the same bus.​

2.​ Writing to the Bus​

○​ An input port wants to send a packet to a specific output port.

○​ The input port places the packet on the bus, along with information: “This
packet is for output port X”.
○​ At this moment, the bus carries the packet physically to all outputs, but the
packet is tagged.​

3.​ Reading from the Bus​

○​ Every output port monitors the bus.

○​ Only the output port that matches the tag actually accepts/reads the packet.
○​ Other output ports ignore it and do not read it.​

✅ So:
●​ Input port “writes” packet onto the bus.
●​ The bus transmits the packet to all outputs electrically, but only the intended output
reads it.
●​ Other outputs see the signal but discard it.
 1. Router Input Port Memory
The input port memory in a router actually consists of different types of memory for different
purposes:

1.​ Packet buffer memory

○​ Stores the entire packet temporarily when it arrives at the router.
○​ Needed because packets may have to wait in a queue before being forwarded.
2.​ Forwarding table memory (lookup memory)
○​ Stores the forwarding table entries.
○​ This is not the packet itself, only the rules that map destination addresses →
output ports.
○​ TCAM is often used here for very fast lookups.

✅ So: input port memory = packet buffers + forwarding table memory (can be TCAM).
●​ TCAM is for fast header lookup, not storing packets.

2. What is TCAM?
●​ TCAM = Ternary Content Addressable Memory.
●​ Unlike normal memory (RAM) which uses an address to retrieve data, TCAM works in
reverse:
○​ You give it a value (like a destination IP).
○​ It returns the matching entry and associated action.
●​ “Ternary” = supports three states for each bit: 0, 1, or X (don’t care / wildcard).

3. How TCAM Works in a Router

Step-by-Step Example

1.​ Forwarding table in TCAM​

* = wildcard (don’t care).
2.​ Packet arrives at input port
 ○​ Physical + link layer assemble packet.
○​ Network layer reads destination IP from header.
3.​ Destination IP lookup in TCAM
○​ Destination IP is presented to all TCAM entries simultaneously.
○​ TCAM returns all matches, then the router selects the longest prefix match.
4.​ Output port decision
○​ TCAM provides the output port associated with the longest matching prefix.
○​ Packet is forwarded into the switching fabric → correct output port.

✅ 1. INPUT PORT QUEUING & HEAD OF

LINE (HOL) BLOCKING
Why does input port queuing happen?

Because:

●​ Incoming packets arrive faster than the switching fabric can move them to outputs.​

HOL BLOCKING — simplest definition

HOL blocking happens when:

The first packet in an input queue is waiting for an output port that is busy → and it
blocks all packets behind it even if THEY want other ports.

Tiny Example

3 input ports → 3 output ports.

Input port Queue (front → back)

IN1 Red, Blue

IN2 Green
 IN3 Red, Yellow

Assume:

●​ Red packets → Output 1​

●​ Blue → Output 2​

●​ Green → Output 3​

●​ Yellow → Output 3​

At time T:

●​ IN1 has Red (goes to Out1)

●​ IN3 also has Red (goes to Out1)​

Switch fabric can send only 1 packet per output per time slot.

What happens?

●​ IN1 sends Red → Output1.

●​ IN3 must WAIT because Output1 already got a packet this time slot.

👉
●​ The Yellow packet BEHIND the Red in IN3 also must wait.​
This is HOL blocking.​

✅ 2. OUTPUT PORT QUEUING (THE

REAL CONGESTION)
Output port has link speed = R

Switch fabric can deliver = N × R

→ Packets arriving faster than packets leaving.

So the output port needs a buffer (queue).

If buffer fills → packet loss happens here.

✅ 3. PACKET DROP POLICIES (AT

OUTPUT PORT)
Tail Drop (most common)

If buffer is full → drop the newly arriving packet.

Priority-based drop

If buffer is full:

●​ Drop low-priority packet

●​ Keep high-priority traffic​

ECN Marking (no drop, just warning)

Router sets ECN bits in IP header → tells sender “slow down”.

✅ 4. PACKET SCHEDULING (WHICH

PACKET TO SEND NEXT)
This happens at the output queue.

Here are the scheduling algorithms:

⭐ A. First Come First Serve (FCFS)

Send packets in exact arrival order.​
Like a normal line.

⭐ B. Priority Queueing
Packets are classified into classes:

●​ High
●​ Medium
●​ Low

Rule:

Send the highest-priority non-empty queue first.

Example

Packets arriving:

●​ P1 (low)
●​ P2 (low)
●​ P3 (high)
●​ P4 (medium)

Transmission order:

1.​ P3 (high)
2.​ P4 (medium)
3.​ P1
4.​ P2

⭐ C. Round Robin (RR)

Classes take turns:

●​ Send 1 packet from Class 1

●​ Then 1 packet from Class 2
●​ Then Class 3
●​ Repeat​
Even if Class 1 has 100 packets and Class 2 has 1 packet → still fair cycle.

⭐ D. Weighted Fair Queueing (WFQ)

This is RR with weights.

If link = 10 Mbps​
Weights:

●​ Class A = 0.5
●​ Class B = 0.3
●​ Class C = 0.2

Then each class gets:

●​ A → 5 Mbps
●​ B → 3 Mbps
●​ C → 2 Mbps

Even when the link is busy.

WFQ = bandwidth guarantee.

✅ 5. BUFFER SIZE DISCUSSION

(important exam theory)
Two recommendations exist:

📌 1. Rule of Thumb (RFC 3439)

Buffers = RTT × Link Capacity

Example:​
RTT = 200 ms​
Capacity = 1 Gbps​
Buffer = 0.2 × 1G = 200 Mb

But this is too large for today.

📌 2. Modern Research (divide by sqrt(N))
If many flows share the link:​
Buffer = (RTT × Link Capacity) / √N

Much smaller buffers → reduces delay (“bufferbloat” problem).

Alright, I’ll explain this whole lecture clearly, in real networking terms, step-by-step,
exam-oriented, and nothing important will be skipped.​
I’ll structure it exactly how exam answers are expected.

PART 1: Network Layer Big Picture

Control Plane vs Data Plane (quick recap)
●​ Control plane: decides what the forwarding table should contain
○​ Uses routing protocols (RIP, OSPF, BGP) or SDN controllers
●​ Data plane: actually forwards packets
○​ Uses the forwarding table
○​ Works at line speed

👉 IP protocol is DATA PLANE, not control plane.

PART 2: What IP (IPv4) Really Does

The IP protocol is responsible for:

1.​ Datagram format (header + payload)

2.​ IP addressing
3.​ Packet handling rules
○​ Fragmentation
○​ TTL decrement
○​ Best-effort delivery (no guarantees)

❌ IP does NOT do:

●​ Routing algorithms
●​ Path computation
 ●​ Congestion control

PART 3: IPv4 Datagram (Header) – EXAM

CRITICAL
IPv4 Header = usually 20 bytes

Important Fields (what to remember)

1. Version (4 bits)

●​ Value = 4 → IPv4

2. Header Length

●​ Tells where payload starts

●​ Needed because options may exist

3. Total Length

●​ Header + data
●​ Max = 65,535 bytes
●​ Typical = ≤ 1500 bytes (Ethernet MTU)

4. Type of Service (ToS)

Now used for:

●​ ECN (Explicit Congestion Notification) → 2 bits

●​ Traffic classes → for scheduling & QoS

Routers use these bits for:

●​ Priority queuing
●​ Weighted Fair Queuing

5. TTL (Time To Live)

●​ Decremented by every router

●​ When TTL = 0 → packet dropped
●​ Prevents infinite routing loops
6. Protocol Field

Tells IP which transport protocol to give data to:

●​ TCP → 6
●​ UDP → 17
●​ ICMP → 1

7. Header Checksum

●​ Checks only the IP header

●​ Recomputed at every router (TTL changes)
●​ Removed in IPv6 (performance reason)

8. Source IP Address (32 bits)

9. Destination IP Address (32 bits)

●​ Used for forwarding table lookup

●​ Longest Prefix Match applied

10. Fragmentation Fields

●​ Used if packet > MTU

●​ Rare today
●​ Not in IPv6

PART 4: What an IP Address Represents

VERY IMPORTANT CONCEPT

❌ IP address does NOT identify a host​

✅ IP address identifies an INTERFACE
Examples:

●​ Laptop:
○​ Wi-Fi interface → one IP
○​ Ethernet interface → another IP
●​ Router:
○​ Every port = separate IP
PART 5: Subnets (Must Know for Exams)
Definition

A subnet is:

A group of interfaces that can reach each other without passing through a router

Key Rule

Interfaces on the same subnet:

●​ Share the same prefix

●​ Have different host bits

Subnet Mask / CIDR Notation

Format:

a.b.c.d / x

Where:

●​ x = number of subnet bits

●​ Remaining bits = host bits

Example:

[Link] /24

●​ First 24 bits = subnet

●​ Last 8 bits = host

PART 6: How Forwarding Uses Addresses

Routers do:
Destination IP → Forwarding Table → Output Port

Forwarding Table Stores:

●​ Address prefix
●​ Output interface

Longest Prefix Match (EXAM FAVORITE)

If multiple prefixes match:​

➡ choose the most specific (longest) one

Example:

[Link]/20

[Link]/23

✅
Destination = [Link]​
Match = /23 (longer prefix)

PART 7: DHCP – How Hosts Get IP

Addresses
Why DHCP?

●​ Manual configuration impossible

●​ Hosts join/leave constantly

DHCP Runs Over:

●​ UDP
●​ Client port: 68
●​ Server port: 67
DHCP Message Sequence (MEMORIZE)

1.​ DHCP DISCOVER

○​ Broadcast
○​ Source IP = [Link]
○​ Destination IP = [Link]
○​ “Is there a DHCP server?”
2.​ DHCP OFFER
○​ Server proposes IP address
○​ Includes lease time
3.​ DHCP REQUEST
○​ Client accepts one offer
○​ Broadcast (others know rejected)
4.​ DHCP ACK
○​ Server confirms
○​ IP officially assigned

DHCP Also Provides:

●​ Subnet mask
●​ Default gateway (first-hop router)
●​ DNS server IP

PART 8: How Networks Get Address

Blocks
Hierarchical Allocation

1.​ ICANN
○​ Owns global IPv4 space
2.​ Regional Internet Registries (RIRs)
○​ ARIN, RIPE, APNIC, etc.
3.​ ISPs
4.​ Customer networks
PART 9: Address Aggregation (Route
Summarization)
Key Idea

ISPs advertise one large prefix instead of many small ones

Example:

[Link] /20

Covers:

●​ 223.16.x.x
●​ 223.17.x.x
●​ 223.18.x.x
●​ 223.19.x.x

✅ Reduces routing table size​

✅ Improves scalability

When Aggregation Breaks

If a customer changes ISP but keeps same IP block:

●​ Old ISP advertises /20

●​ New ISP advertises /23

👉 Longest Prefix Match fixes this

Packets go to:

●​ More specific prefix (/23)

PART 10: IPv4 Address Exhaustion

 ●​ IPv4 = 32 bits
●​ Total ≈ 4.3 billion addresses
●​ ICANN ran out in 2011

Why 32-bit?

Historical reasons (1970s):

●​ Few networks
●​ Few computers
●​ No idea Internet would explode

PART 11: Why NAT and IPv6 Exist

NAT

●​ Multiple devices share one public IP

●​ Uses private IP ranges internally

IPv6

●​ 128-bit addresses
●​ Practically infinite
●​ Simplified header
●​ No checksum
●​ No fragmentation by routers

FINAL EXAM SUMMARY (ONE LOOK)

IP Protocol Does:

✔ Addressing​
✔ Datagram formatting​
✔ Best-effort delivery

Routers:
✔ Forward using destination IP​
✔ Use longest prefix match​
✔ Decrement TTL

DHCP:

✔ Automatic IP assignment​
✔ Uses UDP 67/68​
✔ Discover → Offer → Request → ACK

Subnets:

✔ Same prefix​
✔ No router inside

Aggregation:

✔ Reduces routing table size​

✔ Depends on longest prefix match

PART 1: Why NAT and IPv6 Exist

(Motivation)
IPv4 problem
●​ IPv4 address = 32 bits
●​ Total ≈ 4.3 billion addresses
●​ Internet grew far beyond expectations
●​ By 2011, ICANN ran out of IPv4 blocks

Two responses to this crisis:

1.​ Network Address Translation (NAT) → short-term, practical fix

2.​ IPv6 → long-term architectural solution

Both started in the mid–late 1990s

PART 2: Network Address Translation
(NAT)
What NAT actually is
NAT is a technique where:

●​ Many internal hosts

●​ Share one public IPv4 address
●​ Using port number translation

📌 NAT is usually implemented on a border router​

→ called a NAT router or NAT box

Private IP Addresses (MEMORIZE)

These addresses:

●​ Are not routable on the public Internet

●​ Used only inside local networks

Private address ranges:

●​ [Link] /8
●​ [Link] /12
●​ [Link] /16

If your laptop shows one of these → you are behind NAT

NAT Basic Idea (Core Concept)

Inside the LAN:

●​ Hosts communicate normally

●​ Using private IP addresses

Outside the LAN:

 ●​ All packets appear to come from:
○​ One public IP address
○​ Different source port numbers

👉 NAT hides internal structure from the Internet

PART 3: NAT Advantages (Exam Question

Favorite)
1. Address conservation

●​ Thousands of devices
●​ One public IPv4 address

2. ISP independence

●​ Internal addresses don’t change

●​ Even if ISP changes

3. Security (partial)

●​ Internal hosts not directly reachable

●​ Acts like a basic firewall

PART 4: How NAT Works (Step-by-Step,

Exam Level)
NAT performs THREE functions
(1) Outgoing packet translation

For every outgoing datagram:

●​ Replace:
○​ Source IP
 ○​ Source port
●​ With:
○​ NAT’s public IP
○​ New unique port number

(2) Maintain NAT Translation Table

The NAT router stores mappings like:

Internal IP Internal Port NAT IP NAT Port

[Link] 3345 138.76.29. 5001

7

📌 This table is state​

→ NAT is NOT stateless

(3) Incoming packet translation

For incoming packets:

●​ Use destination IP + destination port

●​ Look up mapping in NAT table
●​ Rewrite:
○​ Destination IP
○​ Destination port
●​ Forward into LAN

PART 5: NAT in Action (Concrete Packet

Flow)
Step 1: Host sends packet
Src: [Link] : 3345

Dst: [Link] : 80

Step 2: NAT rewrites packet

Src: [Link] : 5001

Dst: [Link] : 80

And stores mapping.

Step 3: Server replies

Src: [Link] : 80

Dst: [Link] : 5001

Step 4: NAT reverses translation

Dst becomes: [Link] : 3345

Packet delivered to correct host & process.

PART 6: Why NAT Is Controversial

Violates layering

●​ Router modifies transport layer ports

●​ Ports should be end-host concern
Breaks end-to-end principle

●​ External hosts cannot initiate connections

●​ NAT traversal required (STUN, TURN, ICE)

Application complications

●​ VoIP
●​ P2P
●​ Online gaming

📌 NAT is widely deployed despite these issues

PART 7: IPv6 – The Long-Term Solution

Why IPv6?
1. Massive address space

●​ 128 bits
●​ ≈ 3.4 × 10³⁸ addresses

2. Faster router processing

●​ Fixed-length header
●​ No checksum
●​ No router fragmentation

3. Flow-based networking support

PART 8: IPv6 Datagram Header (EXAM

CRITICAL)
Key IPv6 Header Fields
 Field Purpose

Version Always 6

Traffic Class Priority / QoS

Flow Label Identifies flows

Payload Length Data size

Next Header TCP / UDP / ICMPv6

Hop Limit Like TTL

Source Address 128 bits

Destination 128 bits

Address

Flow Label (Important Concept)

●​ Identifies packets belonging to the same flow
●​ Allows routers to:
○​ Treat packets consistently
○​ Apply QoS or scheduling

📌 IPv6 provides mechanism, not policy​

(ISPs decide how to use it)
What IPv6 REMOVED (VERY IMPORTANT)

Removed Field Why

Header checksum Slow to recompute

Fragmentation Done only at endpoints

Variable header Slows forwarding

length

Options Moved to extension

headers

✅
Result:​

✅
Faster forwarding​
Hardware-friendly

PART 9: IPv4 → IPv6 Transition Problem

❌ Cannot switch Internet overnight​
❌ IPv4 and IPv6 are incompatible
So we need:​
✔ Coexistence​
✔ Incremental deployment
PART 10: Tunneling (Key Transition
Technique)
What tunneling means
IPv6 datagram carried inside IPv4 datagram

Encapsulation:

IPv4 Header

└── IPv6 Datagram (payload)

Why tunneling works

●​ IPv4 routers don’t need to understand IPv6
●​ They forward IPv4 packets as usual
●​ IPv6 routers extract IPv6 packet at tunnel exit

PART 11: Tunneling Example

(Router-Level)
Network:

●​ A, F → IPv6-only
●​ C, D → IPv4-only
●​ B, E → Dual-stack (IPv4 + IPv6)

Step-by-step

1.​ A → B
 ○​ Normal IPv6 forwarding
2.​ B → E
○​ B sees next IPv6 hop is E
○​ But path is IPv4
○​ B encapsulates IPv6 inside IPv4
○​ Sends IPv4 packet to E
3.​ C, D
○​ Forward IPv4 packet normally
4.​ E
○​ Receives IPv4 packet
○​ Extracts IPv6 datagram
○​ Forwards to F

📌 IPv4 network behaves like a virtual link (tunnel)

PART 12: IPv6 Deployment Reality

●​ ~30% of Google traffic uses IPv6
●​ ~1/3 US government domains IPv6-capable
●​ IPv4 still dominant due to:
○​ NAT
○​ Legacy infrastructure
○​ Deployment cost

FINAL EXAM-READY SUMMARY

NAT:

✔ Conserves IPv4 addresses​

✔ Uses private IPs + port mapping​
✔ Breaks end-to-end principle

IPv6:

✔ 128-bit addressing​
✔ Faster forwarding​
✔ Flow-aware networking
Tunneling:

✔ IPv6 over IPv4​

✔ Encapsulation​
✔ Enables gradual transition

1️⃣ First: What problem are we solving?

Traditional router (OLD thinking)

Router does only ONE thing:

Look at destination IP address → choose output port

Example:

Destination IP = [Link]

Forward out port = 2

That’s it.

❌ Router cannot:
●​ Block SSH
●​ Treat video traffic differently
●​ Do firewalling
●​ Do NAT-like rewriting
●​ Make decisions based on ports or protocols

2️⃣ Enter: Generalized Forwarding (NEW

thinking)
Instead of only looking at destination IP, the router/switch can now:
🔍 MATCH on:
●​ Source IP
●​ Destination IP
●​ Protocol (TCP/UDP/ICMP)
●​ Source port
●​ Destination port
●​ MAC address
●​ Input port
●​ Traffic class, etc.

⚙️ ACTIONS it can take:

●​ Forward to port X
●​ Drop
●​ Modify header
●​ Send to controller
●​ Duplicate packet

This is called:

MATCH + ACTION

3️⃣ VERY IMPORTANT: What is a FLOW?

(This is your confusion)
Simple definition (exam-ready):

A flow is a group of packets that are treated the same way by the network.

Packets belong to the same flow if they match the same rule.

🔹 Flow example (real life)

You open YouTube.

Packets share:
 ●​ Source IP = your laptop
●​ Destination IP = YouTube server
●​ Protocol = TCP
●​ Destination port = 443

➡ Router says:

“All packets with these properties → treat them the same”

That set of packets = ONE FLOW

Flow ≠ connection (important)

●​ Flow is network’s view

●​ Connection is transport layer (TCP) concept

4️⃣ Flow Table (Generalized Forwarding

Table)
Instead of a forwarding table, we now have a FLOW TABLE

MATCH (conditions) ACTION

dst IP = [Link]/16 forward to port 1

src IP = [Link]/16 DROP

src IP = [Link] send to controller

5️⃣ Step-by-step Packet Processing
(CRUCIAL)
Let’s walk a real packet through a router.

Packet arrives:

Src IP: [Link]

Dst IP: [Link]

Protocol: TCP

Dst Port: 22

Router logic:

1.​ Packet arrives at input port

2.​ Router checks flow table

Matches rule:​
If TCP dst port = 22 → DROP

3.​
4.​ Action executed → packet dropped

🔥 That router just acted like a firewall

6️⃣ Examples You MUST know (exam gold)

✅ Example 1: Destination-based forwarding (old router

behavior)
Rule
Match: dst IP = [Link]/24

Action: forward to port 6

✔ Same as traditional routing​

✔ Generalized forwarding can do everything old routers did

✅ Example 2: Firewall (SSH blocking)

Rule

Match: TCP destination port = 22

Action: DROP

📌 Effect:
●​ Nobody can SSH to hosts behind this router

✅ Example 3: Blacklisting a host

Rule

Match: source IP = [Link]

Action: DROP

📌 That host is completely blocked

✅ Example 4: NAT-like behavior (header rewriting)

Rule
Match: src IP = [Link]

Action:

rewrite src IP → [Link]

rewrite src port → 5001

forward to port 2

📌 That’s NAT implemented using match+action

✅ Example 5: Layer-2 switching (Ethernet)

Rule

Match: dst MAC = AA:BB:CC:DD

Action: forward to port 3

📌 This is a switch, not a router​

📌 SAME abstraction works for both

7️⃣ So what device is this? Router? Switch?

🔥 Answer: BOTH.
Using match + action, one device can behave as:

●​ Router (L3)
●​ Switch (L2)
●​ Firewall
●​ NAT
●​ Load balancer

This is why we call it generalized forwarding

8️⃣ What is OpenFlow?
OpenFlow = a standard way to implement match + action

It defines:

●​ What fields you can match

●​ What actions you can take
●​ How a controller programs the device

OpenFlow match fields (OpenFlow 1.0)

Can match on:

●​ IP src / dst
●​ Protocol
●​ TCP/UDP ports
●​ MAC addresses
●​ Input port

OpenFlow actions
●​ Forward
●​ Drop
●​ Modify header
●​ Send to controller
●​ Duplicate packet

9️⃣ SDN Controller (BIG PICTURE)

Traditional networks:

●​ Each router decides on its own

 ●​ Uses routing protocols (OSPF, RIP)

SDN world:

●​ Controller computes rules

●​ Installs flow tables into switches
●​ Devices just obey rules

📌 Router becomes programmable

🔟 Network-wide behavior example

(routing without routing protocols)
Goal:

Traffic from Host 5 & 6 → Host 3 & 4​

Must go through S1, not the direct link.

Controller:

●​ Computes path
●​ Installs flow rules in S3, S1, S2

Each switch just follows rules → no OSPF needed

🔥 Routing is now software-defined

1️⃣1️⃣ Why is this powerful? (EXAM ANSWER)

Because match + action is:

●​ A form of programmability
●​ Per-packet decision making
●​ Supports innovation (firewalls, QoS, NAT, routing)
1️⃣2️⃣ One-line FLOW definition (memorize)
A flow is a set of packets that match the same header fields and are
processed with the same action by the network.

1️⃣3️⃣ Common exam traps (VERY

IMPORTANT)
❌ Flow ≠ single packet​
❌ Flow ≠ TCP connection​
❌ OpenFlow ≠ routing protocol​
❌ SDN ≠ faster forwarding (it’s about control)
Zara, this is one of the most conceptual + confusing lectures, so it’s normal that it feels
fuzzy. I’ll rebuild it cleanly, using real-world examples, clear definitions, and exam-focused
explanations.​
By the end, you’ll clearly know:

✅ What middleboxes are

✅ Why they exist
●​

✅ How they relate to generalized forwarding

●​

✅ What the IP hourglass means

●​

✅ What end-to-end principle really says

●​

✅ Why people say “software is eating the network”

●​
●​

I’ll avoid fancy language and stick to intuition.

1️⃣ Start from what you ALREADY know

What is a normal IP router?

A normal router:

●​ Looks only at destination IP

●​ Forwards packet to next hop
That’s it.

👉 This is called destination-based forwarding

2️⃣ So what is a Middlebox?

Official (exam) definition:

A middlebox is a network device on the data path that performs functions

beyond standard IP routing.

Simple definition (memorize this):

Anything inside the network that does more than “just forward based on
destination IP” is a middlebox.

🚨 Key idea
●​ Middleboxes are NOT end hosts
●​ They sit inside the network
●​ They inspect, modify, block, or redirect packets

3️⃣ Real-life examples of middleboxes

(VERY IMPORTANT)
Let’s connect each one to something you already studied.

✅ 1. NAT (Network Address Translation)

You already know NAT.

What does NAT do?

 ●​ Changes IP addresses
●​ Changes port numbers
●​ Keeps a translation table

🚫 A normal router never modifies headers​

✔ NAT modifies headers

➡ NAT = Middlebox

✅ 2. Firewall
Firewall rule:

Block all TCP packets to port 22

Router question:

Does destination-based routing do this?

❌ No​
✔ Firewall inspects transport layer fields

➡ Firewall = Middlebox

✅ 3. Load Balancer (very common)

Imagine:

●​ Google has 100 identical web servers

●​ All have same content

Load balancer:

●​ Receives HTTP request

●​ Decides which server to send it to

Example:

Request 1 → Server A
Request 2 → Server B

Request 3 → Server C

This decision is:

●​ Not based on destination IP alone

●​ Often based on application-layer info (HTTP)

➡ Load balancer = Middlebox

📌 Sometimes called:
●​ Layer 7 switch
●​ Application-layer switch

✅ 4. Web Cache
You studied web caching earlier.

Cache:

●​ Stores popular content

●​ Replies instead of the server

That’s not routing.​

That’s storage + computation.

➡ Web cache = Middlebox

✅ 5. CDN (Content Distribution Network)

Netflix, YouTube, Facebook use CDNs.

What CDN does:

●​ Places servers inside the network

●​ Serves content closer to users

CDN nodes:
 ●​ Are not end users
●​ Are not routers
●​ Do computation + storage

➡ CDN = Advanced middlebox

4️⃣ Why did middleboxes suddenly

explode?
Old days:

●​ Routers = proprietary hardware

●​ Closed software
●​ Expensive

Now:

●​ Whitebox hardware
●​ Generic switches
●​ Programmable via software (SDN, OpenFlow)

📢 Famous quote:
“Software is eating the world”

Meaning:

●​ Hardware is simple
●​ Software defines behavior

5️⃣ NFV – Network Functions Virtualization

Instead of:

●​ Physical firewall box

●​ Physical NAT box
●​ Physical load balancer
We do:

●​ Software running on servers

Example:

Firewall = software VM

NAT = software VM

Load balancer = software VM

➡ This is NFV

📌 Uses:
●​ Virtualization
●​ SDN
●​ Whitebox switches

6️⃣ Now the BIG question:

Are middleboxes breaking the Internet’s architecture?

To answer that, we must understand Internet architecture philosophy

7️⃣ IP Hourglass (VERY IMPORTANT)

Visual idea:

Applications (many)

Transport (TCP, UDP, QUIC)

IP ← narrow waist

Link layers (Ethernet, WiFi, LTE, Fiber)

Meaning:

●​ Many applications
●​ Many link technologies
●​ ONE network protocol: IP

📌 IP hides:
●​ WiFi
●​ Ethernet
●​ Cellular
●​ Optical fiber

➡ That’s why the Internet scales so well

8️⃣ The “Thin Waist” principle

Why IP is special:

●​ Every device speaks IP

●​ IP is simple
●​ IP provides best-effort connectivity

9️⃣ Intelligence at the edge (END-TO-END

principle)
Key statement (RFC 1958):

“The intelligence is end-to-end rather than in the network.”

What does this mean?

Functions like:

●​ Reliability
 ●​ Congestion control
●​ Ordering
●​ Error recovery

Are implemented:

●​ ❌ NOT in routers
●​ ✔ In end hosts (TCP)

Example: Reliable data transfer

Two design choices:

Option A: Smart network

●​ Routers do ACKs
●​ Routers do retransmissions

Option B: Smart endpoints (Internet choice)

●​ TCP at sender & receiver

●​ Routers stay simple

➡ Internet chose Option B

🔑 Why?
Because:

●​ Only end hosts know if data is correct

●​ Routers can fail
●​ End-to-end correctness still needed

📌 This is the End-to-End Argument

🔟 Telephone network vs Internet (EXAM
GOLD)
Old telephone network

●​ Endpoints = dumb phones

●​ Network = smart switches

Internet

●​ Endpoints = computers
●​ Network = simple routers

Diagram idea:

Telephone: [SMART NETWORK]

Internet: [SMART EDGES]

1️⃣1️⃣ So… aren’t middleboxes violating this

principle?
Yes — partially.

Middleboxes:

●​ Add intelligence inside the network

●​ Modify packets
●​ Break transparency

But…

●​ They solve real problems

●​ NAT delayed IPv4 exhaustion
●​ Firewalls provide security
●​ CDNs improve performance
➡ Architecture evolved, not broken

1️⃣2️⃣ Modern Internet reality

Today we have:

●​ Smart endpoints (phones, servers)

●​ Smart network elements (SDN, middleboxes)
●​ Dumb hardware + smart software

So the internet waist is:

●​ Still IP
●​ But “thicker” than before

1️⃣3️⃣ One-paragraph FINAL SUMMARY

(memorize)
Middleboxes are network-layer devices that perform functions beyond traditional
destination-based IP forwarding, such as NAT, firewalls, load balancing, caching,
and content distribution. Their rise has been enabled by programmable whitebox
hardware, SDN, and NFV. While the original Internet architecture emphasized a thin
IP waist and intelligence at the network edge (end-to-end principle), modern
networks place increasing intelligence inside the network to meet performance,
security, and scalability demands.

1️⃣ Complexity of Dijkstra: Computational vs. Message

A. Computational Complexity (O(n²))

●​ This is about how much computation the algorithm does inside a router when
calculating paths.
●​ Suppose we have n nodes in the network. Dijkstra has to:
 1.​ Pick the node with the minimum tentative distance (loop through n nodes →
O(n))
2.​ Update distances of neighbors (loop through n nodes in worst case → O(n))
●​ Doing this for all nodes → O(n × n) = O(n²)
●​ Basically: if network gets bigger, computation grows roughly with square of nodes.

B. Message Complexity (O(n²))

●​ This is about how many messages the routers need to exchange so everyone knows
the network topology.
●​ In link-state routing:
○​ Each router broadcasts its link-state info (its directly connected links and costs)
to all other routers.
○​ For n routers, each router’s broadcast touches all other routers → roughly O(n²)
messages.
●​ Example: 4 routers → each sends info to 3 others → 4 × 3 = 12 messages
●​ If n = 100, each router sends to 99 others → roughly 10,000 messages
●​ So message complexity measures communication overhead, while computational
complexity measures CPU/algorithm work inside a router.

2️⃣ Global (Centralized) vs. Decentralized (Distributed)

Clarification
A. Global / Centralized / Link State

●​ When we say “one node knows the entire network topology” in Dijkstra, it doesn’t
mean the router magically knows everything initially.
●​ Step by step:
1.​ Each router broadcasts its directly connected links and their costs to all
other routers (this is called a link-state advertisement).
2.​ After receiving all these messages, every router now knows the full network
topology:
■​ Every node
■​ Every link
■​ Every link’s cost
3.​ Once a router has complete network information, it can run Dijkstra locally to
compute the shortest paths to all destinations.
✅ So “knows entire network” means after all link-state messages have been received, the
router has a global map of the network.

●​ Important: This is why it’s centralized in logic — each router independently computes
complete paths using full knowledge.

B. Decentralized / Distributed / Distance Vector

●​ Each router only knows its own neighbors’ link costs initially.
●​ It doesn’t know the full network topology.
●​ Instead, routers:
○​ Exchange their current estimates of shortest distances with neighbors.
○​ Update their own table using neighbor info (iteratively).
○​ Eventually, all routers converge to the correct least-cost paths.
●​ Example: Bellman-Ford
○​ Router A knows only its neighbors B and C
○​ Receives their distance vectors → updates its own vector
○​ Repeats until paths to all nodes stabilize

✅ Here, computation is distributed, no single router has the full network map.

Difference in simplest words:

Feature Global / Link-State Decentralized / Distance

Vector

Initial knowledge Full network (after link-state Only neighbors

messages)

Computation Each router computes complete paths Iterative updates with neighbors

Algorithm example Dijkstra Bellman-Ford

Info exchange Broadcast link states Exchange distance vectors

 Speed/accuracy Fast convergence, accurate Slower, depends on iterations

Key Insight about Dijkstra

●​ Even though the source node initially knows only adjacent links, once all link-state
broadcasts propagate, it has a complete network map, then it can compute all
shortest paths using Dijkstra.
●​ Think of it like this:
1.​ You only know your friends (neighbors) at first.
2.​ Then each friend tells you about their friends, and their friends tell you about their
friends…
3.​ After a while, you know everyone in the town (full network topology).
4.​ Now you can plan the shortest path from yourself to anyone else.

Exactly! ✅ You’ve got it perfectly. Let me rephrase it in the simplest way to make it crystal clear:
●​ Why Dijkstra is centralized (link-state):
○​ Suppose there are 10 routers. Each router knows only its directly connected
links at first.
○​ Step 1: Each router broadcasts its link info (which routers it’s connected to + link
costs) to all other routers.
○​ Step 2: After all broadcasts, every router now knows the entire network
topology — all nodes, all links, and their costs.
○​ Step 3: Each router independently runs Dijkstra on this complete network map
to compute the shortest paths to all other routers.

✅
○​ The result of this computation fills its forwarding table.
●​ It’s centralized because each router is using the complete network view (global
info) to compute the paths. Even though each router does the calculation locally, the
logic relies on global knowledge.
●​ Compare that to distance-vector (distributed):
○​ Each router only knows its neighbors.
○​ They iteratively exchange distance info to slowly learn shortest paths.
○​ No single router ever sees the complete network at once.

Link-State Routing (LS) Oscillation —

Simple Exam Notes
1. What the topic is about
●​ This section explains a problem (pathology) that can happen in link-state routing.
●​ The problem is called routing oscillation.
●​ It happens when link costs depend on traffic (congestion/delay).

2. Network idea used in the book

●​ Routers: x, y, z want to send traffic to destination w.
●​ Traffic amounts:
○​ x → 1 unit
○​ z → 1 unit
○​ y → ε (very small amount)
●​ There are two paths to reach w:
○​ Clockwise
○​ Counterclockwise

3. Link cost model (very important)

●​ Link cost = load (traffic) on the link
●​ More traffic ⇒ more delay ⇒ higher cost
●​ Costs are dynamic, not fixed

Asymmetric costs

●​ Cost from u → v may be different from v → u

●​ Reason: traffic in both directions may not be equal

4. Initial routing (Figure a)

●​ Routers are already using some paths
●​ Link costs reflect current traffic
●​ This is the starting state
5. First LS recomputation (Figure b)
●​ Routers run Dijkstra using current link costs
●​ y sees:
○​ Clockwise path cost = 1
○​ Counterclockwise path cost = 1 + ε
●​ y switches to clockwise
●​ x makes the same decision
●​ Result: more traffic on clockwise links

6. Second LS recomputation (Figure c)

●​ Because traffic moved:
○​ Clockwise links become congested
○​ Counterclockwise links become almost empty
●​ New LS run:
○​ x, y, z all see zero-cost counterclockwise path
●​ All routers switch to counterclockwise

7. Third LS recomputation (Figure d)

●​ Counterclockwise links now become congested
●​ Clockwise links become cheaper
●​ All routers again switch to clockwise

8. Routing oscillation
●​ Routers keep switching paths back and forth
●​ No stable routing is reached
●​ This repeated switching is called oscillation

9. Why oscillation happens

Two main reasons:
 1.​ Traffic affects link cost
○​ Changing routes changes traffic
○​ Changing traffic changes cost
2.​ Routers recompute routes at the same time
○​ All routers see the same costs
○​ All make the same decision
○​ All switch together

10. Important observation from the book

●​ This problem:
○​ Is not limited to link-state routing
○​ Can occur in any routing algorithm
○​ If link cost depends on congestion or delay

11. Rejected solution

Idea:

●​ Make link costs independent of traffic

Why rejected:

●​ Routing should avoid congestion

●​ Traffic-based metrics are useful
●​ So this solution is unacceptable

12. Accepted solution (textbook solution)

●​ Do not let all routers run the LS algorithm at the same time
●​ Routers should recompute routes at different times

13. Self-synchronization problem

 ●​ Even if routers start at different times:
○​ They may slowly become synchronized
○​ They may start running LS at the same instant

14. Final practical solution

●​ Each router should randomize the time it sends:
○​ Link-state advertisements
●​ This random delay is called jitter
●​ Randomization prevents synchronization
●​ Reduces oscillations

15. One-line exam answers

●​ Routing oscillations occur when congestion-sensitive link costs and synchronized route
recomputation cause routers to repeatedly switch paths.
●​ Randomizing the timing of link-state updates helps prevent routing oscillations.

16. Ultra-short summary

●​ Cost depends on traffic
●​ Traffic changes cost
●​ Simultaneous recomputation causes switching
●​ Random timing reduces oscillation

Perfect — this is a core DV topic, and I’ll now explain EVERY SINGLE THING the book says,
in order, without skipping anything, but in very simple language, and I’ll also walk you
through Figure 5.7 step-by-step so the example finally clicks.

I’ll divide this into clear sections exactly matching the book.

1️⃣ What this section is about (big picture)

This section explains:
 ✅
●​ What happens in Distance Vector routing when​

❌
a link cost decreases (good news)​
a link cost increases (bad news)
●​ Why bad news travels slowly
●​ What count-to-infinity is
●​ How poisoned reverse helps (but not fully)
●​ Final DV vs LS comparison

2️⃣ What DV routers do when a link cost

changes
📌 Rule (from algorithm lines 10–17):
When a router:

●​ notices a change in cost to a neighbor, OR

●​ receives a distance vector update

then it:

1.​ Recomputes its distances using Bellman-Ford

2.​ If anything changed → tells neighbors
3.​ If nothing changed → stays quiet

3️⃣ Figure 5.7(a): Link cost DECREASE

(GOOD NEWS)
Network (simple view)

x ——4—— y ——1—— z

\________50________/

Now link cost y → x changes from 4 → 1

Step-by-step (exact book sequence)
⏱ Time t0

●​ y notices link cost dropped from 4 to 1

y updates:​
Dy(x) = 1

●​
●​ y sends update to neighbors

⏱ Time t1

●​ z receives update from y

z recalculates cost to x:​

via y = 1 + 1 = 2

●​

✅
●​ Earlier Dz(x) = 5
●​ New Dz(x) = 2
●​ z sends update to neighbors

⏱ Time t2

●​ y receives z’s update

●​ y checks:

❌
○​ No better path found
●​ No update sent

✅ Result
●​ Network stabilizes in 2 iterations
●​ Good news spreads fast

📌 Important book line:

 “The good news about decreased cost propagates quickly.”

😬
4️⃣ Figure 5.7(b): Link cost INCREASE (BAD
NEWS )
Now link cost y → x increases from 4 → 60

This is where problems begin.

Initial state (before change)

●​ Dy(x) = 4
●​ Dz(x) = 5
●​ y→z=1
●​ z→y=1

⏱ Step-by-step bad scenario

⏱ Time t0 (link cost increases)

y recomputes:

via x = 60

via z = 1 + 5 = 6

So:

Dy(x) = 6

⚠️ This is WRONG, but y doesn’t know that.

Why?

●​ y only knows:
○​ x is now expensive (60)
○​ z claimed it could reach x in 5

⏱ Time t1 (routing loop starts)

y sends update to z:​

Dy(x) = 6

●​

z now thinks:​
via y = 1 + 6 = 7

●​
●​ z updates Dz(x) = 7
●​ z sends update to y

⚠️ Now we have a routing loop

●​ y routes to x via z
●​ z routes to x via y

📌 Book analogy:
“Routing loop is like a black hole.”

Packets bounce forever 🔁

⏱ Time t2, t3, t4, …

This keeps happening:

Router New
Cost
 y 8

z 9

y 10

z 11

... ...

📈 Costs slowly increase

⏱ When does it stop?

Eventually:

●​ z calculates a path via y that costs more than 50

●​ z finally uses direct link z → x (50)

Only then:

●​ Loop breaks
●​ Network stabilizes

📌 Book fact:
44 iterations needed!

5️⃣ Count-to-Infinity problem

📌 Definition (from book):​
When bad news causes routers to slowly increase their distance values step by step.
Example:

6 → 7 → 8 → 9 → ...

If:

●​ link cost jumps to 10,000

●​ alternate path is 9,999

Then DV may take thousands of iterations

That’s why it’s called count-to-infinity.

6️⃣ Poisoned Reverse (partial solution)

Core idea:

“If I route to X through you, I will lie to you and say I cannot reach X.”

In the example

●​ z routes to x via y

z tells y:​
Dz(x) = ∞

●​

So y never tries to route to x via z.

How poisoned reverse fixes Figure 5.7(b)

1.​ Link y–x increases to 60

2.​ y sticks to direct link (cost 60)
3.​ y informs z
4.​ z immediately switches to direct link (50)
5.​ z informs y
 6.​ y updates to 51
7.​ y poisons reverse path

✅ No loop​
✅ Fast convergence

❌ Limitation (VERY IMPORTANT)

Poisoned reverse:

❌ only fixes 2-node loops

❌ does NOT fix loops with 3+ routers
●​
●​

📌 Book explicitly says this.

7️⃣ DV vs LS comparison (don’t skip —

exam favorite)

🔹 Communication style
DV

●​ Talks only to neighbors

●​ Shares full distance vectors

LS

●​ Broadcasts to all routers

●​ Shares only link costs

🔹 Message complexity
●​ LS: O(N × E)
 ●​ DV: Neighbor-to-neighbor messages only

🔹 Speed
●​ LS: Fast convergence
●​ DV: Can be slow, especially with failures

🔹 Loops & problems

●​ DV:
○​ Routing loops
○​ Count-to-infinity
●​ LS:
○​ Rare loops
○​ No count-to-infinity

🔹 Robustness
LS

●​ Errors stay localized

●​ Each router computes independently

DV

●​ One bad router can poison whole network

●​ Errors propagate hop-by-hop

📌 Book example:​
1997 Internet outage due to DV-like error

8️⃣ Final conclusion (book’s conclusion)

📌 Exact meaning:
 ●​ DV and LS both have pros and cons
●​ Neither is perfect
●​ Both are used in the Internet

✅ Ultra-short exam summary (you can

memorize)
In Distance Vector routing, good news propagates quickly, but bad news
propagates slowly, leading to routing loops and the count-to-infinity problem.
Poisoned reverse helps prevent simple loops but does not solve the general
problem. Link State routing converges faster and is more robust but requires higher
message overhead.