- Overview
- IP Addressing
- IPv4 Datagram
- IPv6
- Routing Fundamentals
- Routing Algorithms
- Intra-AS Routing
- Inter-AS Routing
- ICMP
- NAT
- Summary
- References
The network layer provides host-to-host communication, routing packets across networks from source to destination.
| Function | Description |
|---|---|
| Addressing | Logical addressing (IP addresses) |
| Routing | Determine path from source to destination |
| Forwarding | Move packets from input to output port |
| Fragmentation | Break packets to fit link MTU |
| Error Reporting | ICMP messages |
Data Plane: Per-router functions, determines how packet arriving on input port is forwarded to output port
Control Plane: Network-wide logic, determines how packets are routed among routers along end-to-end path
- IP (Internet Protocol): Addressing, datagram format, packet handling
- ICMP (Internet Control Message Protocol): Error reporting, diagnostics
- Routing Protocols: OSPF, RIP, BGP
32-bit identifier for host or router interface.
Dotted-Decimal Notation:
192.168.1.1
= 11000000.10101000.00000001.00000001 (binary)
Interface: Connection between host/router and physical link
- Router: Multiple interfaces
- Host: Typically one or two interfaces (Ethernet, WiFi)
| Class | First Bits | Range | Default Mask | Hosts per Network |
|---|---|---|---|---|
| A | 0 | 0.0.0.0 - 127.255.255.255 | 255.0.0.0 (/8) | 16,777,214 |
| B | 10 | 128.0.0.0 - 191.255.255.255 | 255.255.0.0 (/16) | 65,534 |
| C | 110 | 192.0.0.0 - 223.255.255.255 | 255.255.255.0 (/24) | 254 |
| D | 1110 | 224.0.0.0 - 239.255.255.255 | N/A | Multicast |
| E | 1111 | 240.0.0.0 - 255.255.255.255 | N/A | Reserved |
Problems: Inflexible, address space exhaustion
Notation: a.b.c.d/x where x is number of network bits
Example:
200.23.16.0/23
Network: 200.23.16.0 - 200.23.17.255 (512 addresses)
Hosts: 510 (minus network and broadcast addresses)
Binary:
11001000.00010111.0001000|0.00000000
↑
23 bits for network
Subnet Mask Calculation:
/24 = 255.255.255.0
/23 = 255.255.254.0
/22 = 255.255.252.0
/16 = 255.255.0.0
/8 = 255.0.0.0
Divide network into smaller subnetworks.
Example: Subnet 200.23.16.0/23 into 4 subnets
Original: 200.23.16.0/23 (512 addresses)
Subnet 1: 200.23.16.0/25 (128 addresses)
Subnet 2: 200.23.16.128/25 (128 addresses)
Subnet 3: 200.23.17.0/25 (128 addresses)
Subnet 4: 200.23.17.128/25 (128 addresses)
Each subnet:
- Network address: First address
- Broadcast address: Last address
- Usable hosts: Middle addresses
Subnetting Steps:
- Determine number of subnets needed
- Calculate subnet bits: ⌈log₂(subnets)⌉
- New prefix length = original + subnet bits
- Calculate subnet addresses
| Address | Purpose |
|---|---|
| 0.0.0.0 | This host, this network |
| 127.0.0.0/8 | Loopback (127.0.0.1) |
| 10.0.0.0/8 | Private (Class A) |
| 172.16.0.0/12 | Private (Class B) |
| 192.168.0.0/16 | Private (Class C) |
| 169.254.0.0/16 | Link-local (APIPA) |
| 224.0.0.0/4 | Multicast |
| 255.255.255.255 | Limited broadcast |
Automatically assigns IP addresses to hosts.
Client DHCP Server
│ │
├──DHCP Discover (broadcast)──────→│
│ │
│←──DHCP Offer (available IP)───────┤
│ │
├──DHCP Request (accept IP)───────→│
│ │
│←──DHCP ACK (confirm)──────────────┤
│ │
[Client uses IP address]
DHCP provides:
- IP address
- Subnet mask
- Default gateway
- DNS server addresses
- Lease time
0 16 31
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Version| IHL |Type of Service| Total |
| (4) | (4) | (8) | Length |
| | | | (16) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Identification (16) |Flags| Frag |
| | (3) | Offset|
| | | (13) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Time to | Protocol | Header |
| Live(8) | (8) | Checksum(16)|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source IP Address (32) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination IP Address (32) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Options (if any) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Data (Payload) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Version (4 bits): IP version (4 for IPv4)
IHL (Internet Header Length, 4 bits): Header length in 32-bit words
- Minimum: 5 (20 bytes)
- Maximum: 15 (60 bytes)
Type of Service (8 bits): QoS, priority
Total Length (16 bits): Entire packet size (header + data)
- Maximum: 65,535 bytes
Identification (16 bits): Uniquely identifies datagram
Flags (3 bits):
- Bit 0: Reserved
- Bit 1: Don't Fragment (DF)
- Bit 2: More Fragments (MF)
Fragment Offset (13 bits): Position of fragment in original datagram
Time to Live (TTL, 8 bits): Maximum hops
- Decremented at each router
- Packet discarded when TTL = 0
Protocol (8 bits): Upper layer protocol
- 1 = ICMP
- 6 = TCP
- 17 = UDP
Header Checksum (16 bits): Error detection for header only
Source/Destination IP Address (32 bits each)
When datagram too large for link MTU (Maximum Transmission Unit).
Example:
Original: 4000 byte datagram, MTU = 1500 bytes
Fragment 1:
Length = 1500, MF = 1, Offset = 0
Data = bytes 0-1479
Fragment 2:
Length = 1500, MF = 1, Offset = 185 (1480/8)
Data = bytes 1480-2959
Fragment 3:
Length = 1040, MF = 0, Offset = 370 (2960/8)
Data = bytes 2960-3999
Offset in 8-byte units: Offset = byte_position / 8
Reassembly: Performed at destination only
128-bit addresses to solve IPv4 address exhaustion.
2001:0db8:85a3:0000:0000:8a2e:0370:7334
Compressed:
2001:db8:85a3::8a2e:370:7334
(leading zeros omitted, consecutive zeros replaced with ::)
Simplified compared to IPv4:
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Version| Traffic Class | Flow Label |
| (4) | (8) | (20) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Payload Length | Next Header(8) |
| (16) | Hop Limit(8) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Source Address (128 bits) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Destination Address (128 bits) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Key Changes from IPv4:
- No header checksum (faster processing)
- No fragmentation at routers
- Fixed 40-byte header (no options in main header)
- Flow label for QoS
Dual Stack: Nodes run both IPv4 and IPv6
Tunneling: IPv6 datagram carried as payload in IPv4 datagram
IPv6 → [IPv4 Header][IPv6 Datagram] → IPv6
Forwarding: Move packet from input port to output port (data plane, nanoseconds)
Routing: Determine route taken by packets (control plane, seconds)
Maps destination addresses to next-hop routers.
Destination Network Next Hop Interface
192.168.1.0/24 192.168.1.1 eth0
10.0.0.0/8 10.1.1.1 eth1
default (0.0.0.0/0) 192.168.1.1 eth0
Longest Prefix Match: Use most specific route
Packet to 192.168.1.50:
Matches: 192.168.1.0/24, 0.0.0.0/0
Use: 192.168.1.0/24 (longest prefix)
| Metric | Description |
|---|---|
| Hop Count | Number of routers to destination |
| Bandwidth | Link capacity |
| Delay | Propagation + transmission + queueing |
| Cost | Administrative weight |
| Load | Link utilization |
| Reliability | Error rate, availability |
Network as graph:
Nodes = Routers
Edges = Links
Weights = Cost (delay, bandwidth, etc.)
1
A───B
│ 2 │ 5
│ │
3 C
│ │ 3
│ │
D───E
1
Dijkstra's Algorithm - Computes least-cost paths from one node to all others.
Algorithm:
1. Initialize:
- dist[source] = 0
- dist[all others] = ∞
- unvisited = all nodes
2. While unvisited not empty:
- u = node in unvisited with minimum dist
- remove u from unvisited
- for each neighbor v of u:
alt = dist[u] + cost(u,v)
if alt < dist[v]:
dist[v] = alt
prev[v] = u
Example:
Step-by-step from A:
Initial: A=0, B=∞, C=∞, D=∞, E=∞
Step 1: Visit A
Update: B=1, D=3
Step 2: Visit B (dist=1)
Update: C=6
Step 3: Visit D (dist=3)
Update: E=4
Step 4: Visit E (dist=4)
Update: C=7 (no change, 6 < 7)
Step 5: Visit C (dist=6)
Result:
A→B: 1 (direct)
A→C: 6 (A→B→C)
A→D: 3 (direct)
A→E: 4 (A→D→E)
Characteristics:
- Complexity: O(n²) or O(n log n) with priority queue
- Message Complexity: O(n × E) messages
- Convergence: Fast
- Oscillation: Possible with load-based costs
Bellman-Ford Algorithm - Distributed, iterative, asynchronous.
Bellman-Ford Equation:
dx(y) = min{c(x,v) + dv(y)}
over all neighbors v
where:
dx(y) = cost of least-cost path from x to y
c(x,v) = cost from x to neighbor v
dv(y) = distance from v to y
Algorithm:
Each node:
1. Initialize own distance vector
2. Send distance vector to neighbors
3. Receive distance vectors from neighbors
4. Recompute own distance vector using Bellman-Ford
5. If distance vector changed, notify neighbors
6. Repeat until convergence
Example:
Network: A---1---B
| |
2 3
| |
C---1---D
Initial:
A: {A:0, B:∞, C:∞, D:∞}
B: {A:∞, B:0, C:∞, D:∞}
C: {A:∞, B:∞, C:0, D:∞}
D: {A:∞, B:∞, C:∞, D:0}
After exchanges and updates:
A: {A:0, B:1, C:2, D:3}
B: {A:1, B:0, C:3, D:3}
C: {A:2, B:3, C:0, D:1}
D: {A:3, B:3, C:1, D:0}
Count-to-Infinity Problem:
Good news travels fast, bad news travels slow.
A---1---B---1---C
If A-B link fails:
- B updates: B→A = ∞
- But C tells B: C→A = 2
- B thinks: B→C→A = 3
- B tells C: B→A = 3
- C thinks: C→B→A = 4
- Continues until reaches ∞
Solutions:
- Poisoned Reverse: If B routes through C, B tells C distance is ∞
- Split Horizon: Don't advertise route back to source
- Limit: Set ∞ to reasonable value (e.g., 16 for RIP)
| Aspect | Link-State | Distance-Vector |
|---|---|---|
| Algorithm | Dijkstra | Bellman-Ford |
| Knowledge | Complete topology | Only neighbors' distances |
| Messages | Flood link states | Exchange distance vectors |
| Computation | Each node computes independently | Iterative, distributed |
| Convergence | Fast | Slow (count-to-infinity) |
| Complexity | O(n²) or O(n log n) | O(n × iterations) |
| Robustness | More robust | Less robust |
| Examples | OSPF, IS-IS | RIP, BGP |
Autonomous System (AS): Collection of routers under same administrative control.
Intra-AS Routing (IGP - Interior Gateway Protocol): Routing within AS.
Distance-vector protocol based on hop count.
Characteristics:
- Metric: Hop count (max 15, 16 = ∞)
- Updates: Every 30 seconds
- Timers: Invalid (180s), Holddown (180s), Flush (240s)
- Uses UDP port 520
RIP Message:
Command | Version | Zero
Entry 1: Address Family | Route Tag | IP Address | Mask | Next Hop | Metric
Entry 2: ...
...
(up to 25 routes)
Example:
Router A's Table:
Destination Metric Next Hop
192.168.1.0/24 1 direct
192.168.2.0/24 2 RouterB
192.168.3.0/24 3 RouterB
Limitations:
- Slow convergence
- Count-to-infinity problem
- Limited to small networks (max 15 hops)
Link-state protocol using Dijkstra's algorithm.
Characteristics:
- Metric: Cost (can be based on bandwidth, delay)
- Updates: Triggered by topology changes
- Area hierarchy for scalability
- Uses IP protocol 89
OSPF Areas:
Area 0 (Backbone)
┌──────────┬──────────┐
│ │ │
Area 1 Area 2 Area 3
OSPF Message Types:
- Hello: Discover/maintain neighbors
- Database Description: Summary of link-state database
- Link-State Request: Request specific link-state records
- Link-State Update: Flood link-state advertisements
- Link-State Acknowledgment: Acknowledge LSAs
OSPF Cost Calculation:
Cost = Reference Bandwidth / Interface Bandwidth
Default Reference = 100 Mbps
Examples:
10 Gbps link: 100/10000 = 0.01 → 1 (minimum)
1 Gbps link: 100/1000 = 0.1 → 1
100 Mbps: 100/100 = 1
10 Mbps: 100/10 = 10
Advantages over RIP:
- Fast convergence
- Scalability (hierarchical areas)
- Load balancing (equal-cost multi-path)
- Authentication
- Efficient use of bandwidth
Border Gateway Protocol (BGP) - Routing between autonomous systems.
- Path-vector protocol: Avoids loops by including full AS path
- Policy-based routing: ASes control traffic flow based on agreements
- Scalability: Handles entire Internet routing table
- Uses TCP port 179: Reliable transport
eBGP (External BGP): Between routers in different ASes
iBGP (Internal BGP): Between routers within same AS
AS 100 AS 200 AS 300
[R1]──eBGP──[R2]──eBGP──[R3]
│ │ │
iBGP iBGP iBGP
│ │ │
[R4] [R5] [R6]
- OPEN: Establish BGP session
- UPDATE: Advertise/withdraw routes
- KEEPALIVE: Maintain session
- NOTIFICATION: Error, close session
AS Path: Sequence of ASes to reach destination
Example:
AS 100 advertises: 200.23.0.0/16 via [AS100]
AS 200 advertises: 200.23.0.0/16 via [AS200, AS100]
AS 300 advertises: 200.23.0.0/16 via [AS300, AS200, AS100]
Loop Prevention: If AS sees itself in AS path, rejects route
When multiple routes to destination, prefer in order:
- Local preference: Administratively set
- AS path length: Shorter is better
- Origin type: IGP > EGP > Incomplete
- MED (Multi-Exit Discriminator): Preferred entry point to AS
- eBGP over iBGP
- IGP cost to next hop
- Router ID
ISP A's Policy:
- Accept routes from customers (make money)
- Accept routes from peers (settlement-free)
- Don't transit traffic between peers/providers
(only for customers)
Result: Customer routes preferred over peer/provider routes
Internet Control Message Protocol - Error reporting and diagnostics.
Carried in IP datagrams (Protocol = 1).
┌────────────────────────────────────┐
│ IP Header │
├────────────────────────────────────┤
│ Type | Code | Checksum │
├────────────────────────────────────┤
│ Message-specific data │
└────────────────────────────────────┘
| Type | Code | Description | Use |
|---|---|---|---|
| 0 | 0 | Echo Reply | ping response |
| 3 | 0-15 | Destination Unreachable | Network/host/port unreachable |
| 5 | 0-3 | Redirect | Better route available |
| 8 | 0 | Echo Request | ping |
| 11 | 0 | Time Exceeded (TTL) | traceroute |
| 11 | 1 | Fragment Reassembly Timeout | Fragmentation issue |
Uses ICMP Time Exceeded messages to discover route.
Send UDP packets with increasing TTL:
TTL=1 → Router 1 → ICMP Time Exceeded (identifies Router 1)
TTL=2 → Router 2 → ICMP Time Exceeded (identifies Router 2)
TTL=3 → Router 3 → ICMP Time Exceeded (identifies Router 3)
...
TTL=n → Destination → ICMP Port Unreachable (reached destination)
Network Address Translation - Maps private IPs to public IPs.
Private Network NAT Router Public Internet
(10.0.0.0/8) (138.76.29.7)
[10.0.0.1] │
[10.0.0.2] ──────→ [NAT] ──────→ Internet
[10.0.0.3] Translation
NAT Translation Table:
Private IP:Port Public IP:Port
10.0.0.1:3345 ←→ 138.76.29.7:5001
10.0.0.2:3346 ←→ 138.76.29.7:5002
10.0.0.3:3347 ←→ 138.76.29.7:5003
1. Static NAT: One-to-one mapping
10.0.0.1 ←→ 138.76.29.7
2. Dynamic NAT: Pool of public IPs
10.0.0.1 → 138.76.29.7 (from pool)
10.0.0.2 → 138.76.29.8 (from pool)
3. PAT (Port Address Translation / NAPT): Many-to-one with ports
10.0.0.1:3345 → 138.76.29.7:5001
10.0.0.2:3346 → 138.76.29.7:5002
- Address conservation: Many private IPs share few public IPs
- Security: Hides internal network structure
- Flexibility: Change internal IPs without affecting external
- Violates end-to-end principle: Modifies packets
- Port exhaustion: Limited to 65,535 ports
- Breaks some protocols: FTP, SIP, IPsec
- Complicates server hosting: Port forwarding needed
The network layer provides host-to-host communication:
IP Addressing:
- IPv4: 32-bit, dotted-decimal, CIDR notation
- IPv6: 128-bit, hexadecimal, simplified header
- Subnetting: Divide networks into subnetworks
- DHCP: Dynamic address assignment
IP Datagram:
- Header: Version, TTL, protocol, checksum, addresses
- Fragmentation: Split packets for MTU
- Best-effort delivery: No guarantees
Routing:
- Forwarding: Data plane, fast (ns)
- Routing: Control plane, slow (s)
- Longest prefix match in routing tables
Routing Algorithms:
- Link-State: Dijkstra, complete topology, fast convergence (OSPF)
- Distance-Vector: Bellman-Ford, neighbor info, slow convergence (RIP)
Inter/Intra-AS:
- Intra-AS (IGP): RIP, OSPF within AS
- Inter-AS (EGP): BGP between ASes, policy-based
ICMP: Error reporting, diagnostics (ping, traceroute)
NAT: Map private to public IPs, conserve addresses
Course Materials:
- CSEE 4119: An Introduction to Computer Networks - Columbia University
Textbooks:
- Kurose, James F., and Keith W. Ross. Computer Networking: A Top-Down Approach. 8th Edition, Pearson, 2021.
RFCs:
- RFC 791: Internet Protocol (IPv4)
- RFC 2460: Internet Protocol Version 6 (IPv6)
- RFC 2131: DHCP
- RFC 792: ICMP
- RFC 2453: RIP Version 2
- RFC 2328: OSPF Version 2
- RFC 4271: BGP-4
- RFC 3022: Traditional NAT