COMPUTER COMMUNICATION

& NETWORKING
UNIT 2: NETWORK LAYER & ROUTING PROTOCOLS
Detailed Study Notes with Solved Numericals
Reference: Computer Networking: A Top-Down Approach | Kurose & Ross
UNIT 2 SYLLABUS OVERVIEW

Topic Sub-Topics Importance

Forwarding vs Routing, Data Plane vs
Network Layer Basics HIGH
Control Plane
Link State (Dijkstra), Distance Vector
Routing Algorithms VERY HIGH
(Bellman-Ford)
Routing in Internet RIP, OSPF, BGP Protocols VERY HIGH
Autonomous Systems, Intra/Inter-AS
Hierarchical Routing HIGH
Routing
Datagram format, IPv4, IPv6, NAT, CIDR,
IP Protocol VERY HIGH
Subnetting
Input/Output ports, Switching fabrics,
Router Architecture HIGH
Scheduling
Broadcast & Multicast Flooding, Spanning Tree, Multicast Trees MEDIUM
TOPIC 1: NETWORK LAYER - INTRODUCTION

1.1 What is the Network Layer?

The Network Layer (Layer 3 in OSI model) is responsible for transporting segments from the sending
host to the receiving host. It provides logical addressing and routing of packets through the network.
Every router and host in a network contains network layer protocols.

KEY DEFINITION
The Network Layer operates in EVERY HOST and ROUTER in the network. It encapsulates
transport-layer segments into datagrams (on the sending side) and delivers segments to the
transport layer (on the receiving side).

Functions of the Network Layer:

• Transports segments from sending to receiving host
• On sending side: encapsulates segments into datagrams
• On receiving side: delivers segments to transport layer
• Network layer protocols in every host and router
• Router examines header fields in all IP datagrams passing through it

1.2 Two Key Network Layer Functions

Function Description Analogy Plane

Move packets from router's
FORWARDIN Getting through a single
input to appropriate router Data Plane
G interchange on a highway
output. A LOCAL operation.
Determine the route taken by
packets from source to Planning the complete trip
ROUTING Control Plane
destination. A NETWORK- from source to destination
WIDE operation.

ANALOGY: Imagine driving from city A to city Z. Routing is the process of planning your entire trip
(which roads to take). Forwarding is the process of navigating each individual intersection or
interchange during the trip.
1.3 Data Plane vs. Control Plane

Aspect Data Plane Control Plane

Scope Local, per-router function Network-wide logic
Determines how datagram arriving at Determines how datagram is routed along
Function
router input is forwarded to output end-to-end path from source to destination
Operation Hardware, nanosecond timeframe Software, millisecond timeframe
Traditional routing algorithms OR SDN
Methods Forwarding table lookup
(Software-Defined Networking)
Matching header to forwarding table
Example OSPF, BGP, RIP algorithms
entry

1.4 Interplay Between Routing and Forwarding

The routing algorithm determines the end-to-end path through the network. It populates the local
forwarding table. The forwarding table determines where each packet goes at THIS specific router.

HOW IT WORKS
Step 1: Routing algorithm runs network-wide and computes best paths. Step 2: Routing
algorithm populates forwarding table in each router. Step 3: When a packet arrives, router
checks the header value against the forwarding table. Step 4: Packet is forwarded to the
output link indicated in the table.

1.5 Network Service Model

The network service model defines what kind of service the network layer provides for transporting
datagrams from sender to receiver.

Network Congestion
Service Model Bandwidth Loss Order Timing
Architecture Feedback
No No No
Internet Best Effort None guaran guaran guaran No (inferred via loss)
tee tee tee
Constant Bit Constant
ATM Yes Yes Yes Congestion-free
Rate (CBR) rate
Available Bit Guaranteed
ATM No Yes No Yes
Rate (ABR) min
Internet Guaranteed Yes Yes Yes Yes Congestion-free
(IntServ) (RFC 1633)
Internet Differentiated Possibl Possibl
Possible No Possibly
(DiffServ) (RFC 2475) y y

INTERNET'S BEST EFFORT MODEL

The Internet uses the "best-effort" service model - there are NO guarantees on: (i)
successful delivery to destination, (ii) timing or order of delivery, (iii) bandwidth available to
end-to-end flow. Despite this seeming weakness, best-effort has been enormously
successful because: (a) simplicity allows wide deployment, (b) sufficient bandwidth
provisioning makes real-time apps work "good enough", (c) distributed services (CDNs,
datacenters) compensate for lack of guarantees.
TOPIC 2: ROUTING ALGORITHMS

2.1 Graph Abstraction of Networks

Networks are represented as graphs for the purpose of routing algorithms:
• Graph G = (N, E) where N = set of routers (nodes), E = set of links (edges)
• Each link has a cost c(x, y) = cost from node x to neighbor y
• Cost can represent: bandwidth (inversely), congestion (inversely), or simply 1 for each hop
• If x and y are not direct neighbors: c(x, y) = infinity (∞)

EXAMPLE GRAPH
N = {u, v, w, x, y, z} E = {(u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z)} Link costs:
c(u,v)=2, c(u,x)=1, c(v,x)=2, c(v,w)=3, c(x,w)=3, c(x,y)=1, c(w,y)=1, c(w,z)=5, c(y,z)=2 Cost
of a path (x1, x2, ..., xp) = c(x1,x2) + c(x2,x3) + ... + c(xp-1,xp) Goal: Find LEAST-COST
PATH from source to destination.

2.2 Classification of Routing Algorithms

Classification Type 1 Type 2

DECENTRALIZED: Router knows only
GLOBAL: All routers have complete
By Information physically-connected neighbors and
topology and link cost info. "Link
Used their costs. Iterative exchange.
State" algorithms.
"Distance Vector" algorithms.
DYNAMIC: Routes change more
STATIC: Routes change slowly over
By Change Rate quickly. Periodic updates or in
time.
response to link cost changes.

2.3 Link State Algorithm: Dijkstra's Algorithm

PREREQUISITES
Dijkstra's Algorithm requires: 1. Complete network topology is known to ALL nodes (via "link
state broadcast") 2. All nodes have the SAME information 3. It computes LEAST-COST
PATHS from ONE source node to ALL other nodes 4. After k iterations, we know the least
cost path to k destinations
Notation Used:
Symbol Meaning
c(x, y) Link cost from node x to node y. = ∞ if not direct neighbors.
D(v) Current value of cost of path from source to destination v.
p(v) Predecessor node along path from source to v.
N' Set of nodes whose least cost path is definitively known (visited set).

Algorithm Steps:
1. Initialization: Set D(source) = 0. Set D(v) = c(source, v) for all neighbors v. Set D(v) = ∞ for all
non-neighbors. Add source to N'.
2. Loop: Find the node w NOT in N' with the minimum D(w). Add w to N'.
3. Update: For each neighbor v of w NOT in N': D(v) = min(D(v), D(w) + c(w, v)). If D(v) decreases,
set p(v) = w.
4. Repeat steps 2-3 until all nodes are in N'.
5. Construct shortest path tree by tracing predecessor nodes from destination back to source.

SOLVED NUMERICAL 1: Dijkstra's Algorithm (Basic Example)

PROBLEM STATEMENT
Given network graph with nodes u, v, w, x, y, z: c(u,v)=2, c(u,x)=1, c(u,w)=5, c(v,x)=2,
c(v,w)=3, c(x,w)=3, c(x,y)=1, c(w,y)=1, c(w,z)=5, c(y,z)=2 Find the shortest path from u to all
other nodes using Dijkstra's Algorithm.

STEP-BY-STEP SOLUTION:

Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)

0 (Init) u 2,u 5,u 1,u ∞ ∞
1 u,x 2,u 4,x - 2,x ∞
2 u,x,v - 3,y - - 4,y
3 u,x,v,y - 3,y - - 4,y
4 u,x,v,y,w - - - - 4,y
5 u,x,v,y,w,z - - - - -

FINAL SHORTEST PATHS FROM u:

Destination Shortest Path Cost Next Hop (Forwarding)
v u→x→v 3 (1+2) (u, x)
w u→x→y→w 4 (1+1+1+1) (u, x)
x u→x 1 (u, x)
y u→x→y 2 (1+1) (u, x)
z u→x→y→z 4 (1+1+2) (u, x)

SOLVED NUMERICAL 2: Dijkstra's Algorithm (From Textbook Example)

GIVEN NETWORK
Nodes: u, v, w, x, y, z Costs: u-v=7, u-x=5, u-w=3 (via u directly) v-w=3, w-x=4, x-y=9, w-
y=8, w-z=7, y-z=4, x-z=2 (Exact costs from lecture diagram) Find shortest paths from u.

Step N' D(v) D(w) D(x) D(y) D(z)

0 u 7,u 3,u 5,u ∞ ∞
1 u,w 6,w - 5,u 11,w ∞
14,x (=5+9?
2 u,w,x 6,w - - 11,w
check)
10,v
3 u,w,x,v - - - 12 or 14
(=6+4?)
4 u,w,x,v,y - - - - 12,y
5 COMPLE
u,w,x,v,y,z
(Done) TE

EXAM TIP - Dijkstra's Algorithm

For exams, always: 1. Draw the initialization row first (Step 0) 2. At each step, find the
minimum D(v) among unvisited nodes 3. Add that node to N' and update all its neighbors 4.
Use infinity (∞) for non-reachable nodes initially 5. Show p(v) (predecessor) clearly for each
update 6. Construct forwarding table from final results

2.4 Distance Vector Algorithm (Bellman-Ford)

The Bellman-Ford Equation:

BELLMAN-FORD EQUATION (Core Formula)

dx(y) = min_v { c(x,v) + dv(y) }
 Where: dx(y) = cost of least-cost path from x to y c(x,v) = cost from x to its neighbor v dv(y) = cost
from neighbor v to destination y The minimum is taken over ALL neighbors v of x

Key Properties of Distance Vector:

• DISTRIBUTED: Each node sends its own distance vector to neighbors
• ITERATIVE: Process repeats until no more updates needed
• ASYNCHRONOUS: Nodes don't have to work in lockstep
• Each node x maintains: Dx(y) for all y in N (distance to each destination)
• Each node x maintains its neighbors' distance vectors too
• When x receives new DV from neighbor, updates its own using B-F equation

DV Algorithm Pseudocode:
ALGORITHM PSEUDOCODE
INITIALIZATION: For all destinations y in N: Dx(y) = c(x, y) // cost to direct neighbors, ∞
to others Send Dx to all neighbors LOOP (runs continuously): Wait for (change in local
link cost OR message from neighbor) Recompute Dx(y) = min_v { c(x,v) + Dv(y) } for each
destination y If Dx(y) changed for any destination y: Send updated Dx to all neighbors

SOLVED NUMERICAL 3: Bellman-Ford Basic Example

PROBLEM
Network: Three nodes x, y, z with: c(x,y) = 2, c(x,z) = 7, c(y,z) = 1 Find all distance vectors
after convergence.

INITIAL STATE (t=0) - Before any exchange:

Node Dx(x) Dx(y) Dx(z)

x's table 0 2 7
y's table ∞ 0 1
z's table ∞ ∞ 0

AFTER 1st EXCHANGE (t=1):

Node x receives y's DV [∞, 0, 1] and z's DV [∞, ∞, 0]:

x computes Dx(z):
Dx(z) = min { c(x,y) + Dy(z), c(x,z) + Dz(z) } = min { 2+1, 7+0 } =
min{3, 7} = 3
 Node to x to y to z
x's updated DV 0 2 3 (changed from 7!)
y's updated DV 2 0 1
z's updated DV 3 1 0

CONVERGENCE: No further changes occur. The algorithm has converged!

SOLVED NUMERICAL 4: Bellman-Ford Full Example (Textbook)

PROBLEM
Given: du(z) = ? in graph with nodes u,v,w,x,y,z dv(z) = 5, dx(z) = 3, dw(z) = 3 c(u,v) = 2,
c(u,x) = 1, c(u,w) = 5 Find du(z) using Bellman-Ford equation.

SOLUTION:
du(z) = min { c(u,v)+dv(z), c(u,x)+dx(z), c(u,w)+dw(z) } =
min { 2+5, 1+3, 5+3 } = min { 7, 4, 8 } = 4
The next hop is node x (achieves the minimum). So u routes to z via x.

2.5 Link State vs Distance Vector: Comparison

Property Link State (Dijkstra) Distance Vector (Bellman-Ford)

Message
O(n*E) messages sent total Exchange between neighbors only
Complexity
Speed of
O(n²) algorithm; may oscillate Slow convergence; count-to-infinity
Convergence
Router can advertise incorrect path
Router can advertise incorrect link
Robustness cost. Errors propagate through
cost. Each node computes own table.
network.
Information Used Global: entire topology map Local: only neighbor costs
Example Protocol OSPF RIP, BGP (path vector variant)

2.6 Count-to-Infinity Problem in Distance Vector

A serious problem with Distance Vector routing is the "count-to-infinity" problem, which occurs when
link costs increase significantly.
 THE PROBLEM EXPLAINED
Example: Nodes x-y-z, cost x-y=4, y-z=1 Scenario: c(x,y) suddenly increases from 4 to 60.
1. y detects link change: new cost to x via z = c(y,z)+dz(x) = 1+5 = 6? But dz(x) was learned
THROUGH y! So it's wrong! 2. This creates a routing loop: y routes to x via z, z routes to x
via y 3. The algorithm increments by 1 each iteration 4. Eventually reaches infinity (60 in this
case) - takes 44+ iterations! This is "BAD NEWS TRAVELS SLOW" problem.

Solution: Poisoned Reverse

Poisoned Reverse solves the count-to-infinity problem for 2-node loops:
• If Z routes through Y to reach X, then Z tells Y that its distance to X is INFINITY
• This prevents Y from routing to X via Z (which would create a loop)
• However: Poisoned Reverse does NOT solve 3+ node loops!

POISONED REVERSE RULE:

If Z uses path Z→Y→X to reach X: Z advertises to Y: Dz(X) = ∞
(Even though actual Dz(X) = some finite value)
This "lies" to prevent Y from routing back through Z to reach X
TOPIC 3: HIERARCHICAL ROUTING & AUTONOMOUS
SYSTEMS

3.1 Why Hierarchical Routing?

In theory, all routers could run the same routing algorithm. In practice, this is impossible due to two
major issues:

Problem Details Impact

With ~600 million+ destinations, cannot store all
Routing table size and update
SCALE destinations in routing tables. Routing table
traffic is unmanageable
exchange would consume all link bandwidth.
The Internet is a "network of networks". Each
ADMINISTRATIV ISP/organization wants to control its own No single entity can dictate
E AUTONOMY routing. Different organizations may use routing policy for entire Internet
different routing algorithms.

3.2 Autonomous Systems (AS)

DEFINITION
An Autonomous System (AS) is a group of routers that are: 1. Under the SAME
administrative control 2. Running the SAME intra-AS routing protocol 3. Identified by a
unique AS number (ASN) Example: All routers belonging to AT&T, or all routers in a
university network, form an AS.

Types of Routers in AS Architecture:

Router Type Location Function
Runs only intra-AS routing protocol. Connects to other
Internal Router Inside the AS
routers within same AS.
Has links to routers in OTHER autonomous systems.
Gateway Router At the "edge" of AS
Runs both intra-AS and inter-AS protocols.
Border between Summarizes distances to nets in own area, advertises to
Area Border Router
OSPF areas other area border routers.
In OSPF backbone
Backbone Router Runs OSPF routing limited to backbone area.
area
Boundary Router Connects to other Connects to other autonomous systems.
 AS

3.3 Intra-AS vs. Inter-AS Routing

Aspect Intra-AS Routing Inter-AS Routing

Also Known As Interior Gateway Protocol (IGP) Exterior Gateway Protocol (EGP)
Scope Within a single AS Between different ASes
Admin wants control over traffic
Single admin, no policy decisions
Policy routing and who routes through their
needed
network
Performance Focus Can focus on performance (least cost) Policy dominates over performance
Scale Works within one organization Must scale to entire Internet
Examples RIP, OSPF, IGRP BGP
TOPIC 4: RIP - ROUTING INFORMATION PROTOCOL

4.1 Overview of RIP

KEY FACTS ABOUT RIP

1. Type: Distance Vector Algorithm (Bellman-Ford) 2. Distance Metric: NUMBER OF HOPS
(not bandwidth, not delay) 3. Maximum Hops: 15 (hop count of 16 = infinity/unreachable) 4.
Advertisement Frequency: Every 30 seconds 5. Advertisement Method: UDP packets (via
route-d daemon) 6. Each advertisement: list of up to 25 destination subnets 7. Link failure
timeout: 180 seconds of no advertisement = dead link

4.2 RIP Operation

How RIP Works:
6. Each router maintains a routing table (distance vector)
7. Every 30 seconds, each router sends its COMPLETE routing table to all neighbors
8. If a better path is found (fewer hops), the routing table is updated
9. If a router doesn't hear from a neighbor in 180 seconds, that neighbor is declared dead
10. Failure information propagates to entire network via new advertisements

SOLVED NUMERICAL 5: RIP Example

PROBLEM
Network with routers A, B, C, D. Subnets: u, v, w, x, y, z. Router A connects directly to
subnets u(1 hop), v(2 hops), w(2 hops), x(3 hops), y(3 hops), z(2 hops). Router D has
routing table: w via A: 2 hops y via B: 2 hops z via B: 7 hops x: directly connected Now
Router A sends advertisement: dest=w, hops=1; dest=x, hops=1; dest=z, hops=4. Update
D's routing table.

D's ROUTING TABLE BEFORE ADVERTISEMENT:

Destination Next Router # Hops
w A 2
y B 2
z B 7
x -- 1 (direct)
A's advertisement contains: {w:1 hop, x:1 hop, z:4 hops}
D's new cost via A = A's cost + 1 (hop from D to A)

UPDATES:
• For w: A advertises 1 hop. D via A = 1+1 = 2. Current = 2 via A. NO CHANGE.
• For x: A advertises 1 hop. D via A = 1+1 = 2. But D knows x directly = 1 hop. NO CHANGE
(direct is better).
• For z: A advertises 4 hops. D via A = 4+1 = 5. Current best = 7 via B. UPDATE! Use A with 5
hops.

D's ROUTING TABLE AFTER ADVERTISEMENT:

Destination Next Router # Hops Change?
w A 2 No Change
y B 2 No Change
UPDATED (was 7 via
z A 5
B)
x -- 1 (direct) No Change

4.3 RIP Link Failure and Recovery

Time Event
t=0 No advertisement heard from neighbor for 180 seconds
t=180s Neighbor/link declared DEAD. Routes via that neighbor invalidated.
t=180s+ New advertisements sent to neighbors with invalidated routes.
t=180s+ Neighbors in turn send out new advertisements if their tables changed.
Eventually Link failure info propagates to entire network.

RIP TABLE MANAGEMENT

RIP routing tables are managed by an application-level process called route-d (daemon).
Advertisements are sent in UDP packets and periodically repeated. RIP uses the transport
layer (UDP) and runs on top of IP. This means RIP treats network routing as an
APPLICATION - unusual compared to OSPF!
TOPIC 5: OSPF - OPEN SHORTEST PATH FIRST

5.1 OSPF Overview

Feature Details
Type Link State Algorithm (Dijkstra's)
Open Publicly available specification (unlike IGRP which is Cisco proprietary)
Algorithm Uses Dijkstra's algorithm for route computation
Information Sharing Link State Packets (LSPs) flooded to ENTIRE AS
Topology Map Each node has complete topology map of the AS
Advertisement Unit One entry per neighbor in each advertisement
Security All OSPF messages are authenticated (prevents malicious intrusion)
Multiple Paths Supports multiple equal-cost paths (RIP supports only one)
Multicast Integrated unicast and multicast support (MOSPF)
Hierarchy Hierarchical OSPF for large domains

5.2 Hierarchical OSPF

For large networks, OSPF uses a two-level hierarchy:

OSPF HIERARCHY STRUCTURE

LEVEL 1 - BACKBONE (Area 0): - All backbone routers run OSPF among themselves -
Acts as the "super-network" connecting all areas - Link-state advertisements only within
backbone LEVEL 2 - LOCAL AREAS: - Each area is a subset of the AS - Link-state
advertisements stay within the area - Each node knows detailed topology of its own area
only - For other areas: knows only direction/shortest path

OSPF Router Types:

• AREA BORDER ROUTERS: Summarize distances to nets in own area. Advertise to other Area
Border Routers.
• BACKBONE ROUTERS: Run OSPF routing limited to backbone area.
• BOUNDARY ROUTERS: Connect to other autonomous systems.
• INTERNAL ROUTERS: Operate only within one area.
5.3 OSPF vs RIP: Comparison

Feature OSPF RIP

Algorithm Link State (Dijkstra) Distance Vector (Bellman-Ford)
Cost (configurable, reflects
Metric Hop count (max 15)
bandwidth)
Convergence Faster Slower (count-to-infinity risk)
Security Authentication supported No authentication
Equal-cost paths Supported (load balancing) Only one path
Multicast MOSPF integrated Not natively supported
Hierarchy Areas supported Flat structure
Max network size Very large (no hop limit) Small (15 hop limit)
Advertisement Flooded to entire AS Every 30 sec to neighbors
TOPIC 6: BGP - BORDER GATEWAY PROTOCOL

6.1 What is BGP?

IMPORTANT DEFINITION
BGP (Border Gateway Protocol) is the de facto standard inter-domain routing protocol for the
Internet. It is described as the "glue that holds the Internet together." BGP is a PATH
VECTOR protocol - it maintains the complete path (list of ASes) to reach a destination, not
just the cost. This helps prevent routing loops between ASes.

6.2 BGP Functions

BGP Session
Full Name Purpose
Type
Obtain subnet reachability information from NEIGHBORING
eBGP External BGP
autonomous systems
iBGP Internal BGP Propagate reachability information to ALL AS-internal routers

Overall BGP Goal:

• BGP provides each AS a means to advertise its existence to the rest of the Internet: "I am here"
• Allows subnet to advertise reachability to other networks
• Determines "good" routes based on reachability information AND POLICY
• Policy is critical: an AS admin wants control over who routes through their network

6.3 BGP Operation

BGP Sessions:
• Two BGP routers ("peers") exchange BGP messages over semi-permanent TCP connections
• BGP messages advertise "paths" to different destination network prefixes
• When AS3 advertises a prefix to AS1: AS3 PROMISES to forward datagrams toward that prefix
• AS3 can aggregate multiple prefixes in a single advertisement

BGP Path Attributes (included in advertisements):

• AS-PATH: list of ASes through which the prefix advertisement has passed (e.g., AS-PATH:
AS3, AS1)
 • NEXT-HOP: the specific internal AS router to next-hop to begin this external route
• LOCAL-PREF: local preference for the path (set by AS admin, higher = more preferred)
• MED: Multi-Exit Discriminator, used when two ASes are connected through multiple links

6.4 Why Different Intra- and Inter-AS Routing?

Reason Intra-AS Inter-AS

Different organizations want control.
Single admin controls entire AS, so no
Policy Policy: who to route through, what traffic
policy decisions needed
to accept/reject
Hierarchical routing saves table size and
Scale Only covers one organization's network reduces update traffic across entire
Internet
Can optimize purely for performance Policy often dominates over performance
Performance
(speed, bandwidth) optimization
TOPIC 7: ROUTER ARCHITECTURE

7.1 Overview of Router Architecture

A router has two main planes of operation: the Control Plane (software, milliseconds) and the Data
Plane (hardware, nanoseconds).

Component Description Operates At

Control Plane
Executes routing protocols (OSPF, BGP, RIP).
Routing Processor (Software) -
Computes forwarding tables. Management functions.
milliseconds
High-Speed Transfers packets from input ports to output ports. Data Plane (Hardware)
Switching Fabric Core of the router. - nanoseconds
Line termination, link-layer protocol, lookup & Data Plane -
Input Ports
forwarding, queuing. nanoseconds
Queuing, link-layer protocol, line termination. Sends Data Plane -
Output Ports
packets out. nanoseconds

7.2 Input Port Functions

Input Port Operations (in order):
11. LINE TERMINATION: Physical layer bit-level reception.
12. LINK LAYER PROTOCOL: Process link-layer frame (e.g., Ethernet header).
13. LOOKUP/FORWARDING: Use forwarding table to determine output port. This is the critical
step!
14. QUEUING: If packets arrive faster than switching rate, queue them.

DECENTRALIZED SWITCHING
Modern routers do lookup at INPUT PORT (not at a central router CPU)! - Goal: Complete
input port processing at "line speed" - Uses hardware forwarding table stored in input port
memory - Much faster than sending each packet to routing processor - This is called "match
plus action" paradigm

7.3 Longest Prefix Matching

When looking up a destination address in the forwarding table, routers use the LONGEST PREFIX
MATCH rule.
 DEFINITION
LONGEST PREFIX MATCHING: When multiple forwarding table entries match a destination
address, choose the entry with the LONGEST (most specific) address prefix.

SOLVED NUMERICAL 6: Longest Prefix Matching

PROBLEM
Forwarding Table: Link 0: 11001000 00010111 00010*** ******** Link 1: 11001000 00010111
00011*** ******** Link 2: 11001000 00010111 0001**** ******** Link 3: Otherwise Find the
output link for: Address A: 11001000 00010111 00010110 10100001 Address B: 11001000
00010111 00011000 10101010

SOLUTION:
Address A: 11001000 00010111 00010110 10100001
• Match Link 0? 11001000 00010111 00010*** - Check bits 1-22: YES! The pattern "00010"
matches "00010110" (first 5 bits after "000101")
• Match Link 1? 11001000 00010111 00011*** - "00011" vs "00010" - NO MATCH
• Match Link 2? 11001000 00010111 0001**** - "0001" matches "0001" - YES (shorter match)
• ANSWER: Link 0 wins (longer/more specific match of 21 bits vs Link 2's 20 bits)

Address B: 11001000 00010111 00011000 10101010

• Match Link 0? "00010" vs "00011" - NO
• Match Link 1? "00011" matches "00011" - YES (21 bits match)
• Match Link 2? "0001" matches "0001" - YES (20 bits match)
• ANSWER: Link 1 wins (more specific 21-bit match)

7.4 Switching Fabrics

The switching fabric transfers packets from input ports to output ports. Switching rate = rate of transfer
from inputs to outputs.

Type Mechanism Speed Limitation

Packet copied to system
Limited by
Switching via memory. CPU controls 2 bus crossings per datagram.
memory
Memory switching. Traditional Memory bandwidth bottleneck.
bandwidth
computers.
Datagram moves from
Switching via input port memory to Limited by bus Bus contention. Only one packet
Bus output port memory via a bandwidth at a time. ~32 Gbps (Cisco 5600).
SHARED BUS.
Switching via Crossbar or Clos Much faster (can More complex. Can fragment
 network. Multiple parallel
Interconnection match line
paths. Exploits datagrams into fixed-length cells.
Network speed)
parallelism.

SWITCHING RATE GOAL

With N input ports each at rate R: Desirable switching rate = N × R (so no bottleneck) E.g.,
32 input ports × 10 Gbps = 320 Gbps switching fabric needed Only crossbar/interconnection
networks can achieve this.

7.5 Input and Output Port Queuing

Queue Type Where it occurs Cause Problem

Head-of-Line (HOL) Blocking:
Switching fabric slower queued datagram at front of
INPUT
At input ports than input ports queue prevents others from
QUEUING
combined moving forward even if their
output port is free
Datagrams arrive from Need drop policy: which
OUTPUT
At output ports fabric faster than link datagrams to drop when buffer
QUEUING
transmission rate full? (tail drop, priority drop)

HOW MUCH BUFFER?

RFC 3439 Rule of Thumb: Average buffer = RTT × C Where: RTT = typical round-trip time
(≈250 ms), C = link capacity More recent recommendation (with N flows): Buffer = RTT × C /
√N Example: C = 10 Gbps link: Buffer ≈ 250ms × 10Gbps = 2.5 Gbit Warning: Too much
buffering increases delays! Particularly harmful for real-time applications and causes
sluggish TCP response (called "bufferbloat").

7.6 Packet Scheduling

Packet scheduling decides WHICH packet to send next on the output link.

Scheduling Policy Description Advantage Disadvantage

No differentiation
First Come, First Served.
Simple. Fair in terms of between traffic types.
FCFS / FIFO Packets transmitted in
arrival order. One heavy flow can
order of arrival.
starve others.
Arriving traffic classified Low priority traffic can
into priority queues. Important traffic gets starve (never get
Priority Scheduling
Highest priority queue lower delay. served) under heavy
served first. load.
 Traffic classified into
All classes treated
queues. Server cyclically Fair across classes. No
Round Robin (RR) equally regardless of
serves one packet from starvation.
importance.
each class in turn.
Generalized RR. Each
Minimum bandwidth
Weighted Fair class i has weight wi. More complex to
guarantee per class.
Queuing (WFQ) Gets wi/Σwj fraction of implement.
Flexible.
bandwidth.

WFQ BANDWIDTH FORMULA:

Bandwidth fraction for class i = wi / (w1 + w2 + ... + wn)
Each class gets proportional service based on its weight
TOPIC 8: IP PROTOCOL - INTERNET PROTOCOL

8.1 IP Datagram Format

An IP datagram is the basic unit of data in the IP protocol. Understanding the header is critical for exam
purposes.

Field Size (bits) Description

Version (ver) 4 IP version number (4 for IPv4, 6 for IPv6)
Length of header in 32-bit words (minimum = 5, meaning
Header Length 4
20 bytes)
Diffserv (6 bits) + ECN (2 bits). Specifies quality of
Type of Service (ToS) 8
service.
Total datagram length in bytes (header + data). Max =
Total Length 16
65,535 bytes. Typical ≤ 1500 bytes.
Identifier 16 Used for fragmentation and reassembly identification
Used for fragmentation control (DF=Don't Fragment,
Flags 3
MF=More Fragments)
Fragment Offset 13 Position of fragment in original datagram
Maximum remaining hops. Decremented at each router.
TTL (Time to Live) 8
Packet dropped when TTL=0.
Upper Layer Protocol 8 Transport layer protocol: TCP=6, UDP=17, ICMP=1
Header Checksum 16 Error detection for header only (not data)
Source IP Address 32 32-bit IPv4 source address
Destination IP Address 32 32-bit IPv4 destination address
Options Variable Optional fields: timestamp, record route taken, etc.
Data/Payload Variable Actual payload data (typically a TCP or UDP segment)

IP OVERHEAD
Minimum IP overhead = 20 bytes (header, no options) Minimum TCP overhead = 20 bytes
Minimum combined overhead for TCP/IP = 40 bytes All this before even counting application
layer data!
8.2 IPv4 Addressing

DEFINITION OF IP ADDRESS
An IP address is a 32-bit identifier associated with each HOST or ROUTER INTERFACE.
An INTERFACE is the connection between a host/router and a physical link. - Routers
typically have MULTIPLE interfaces (one per link) - Hosts typically have ONE or TWO
interfaces (wired + wireless) Dotted-decimal notation: [Link] = 11011111 00000001
00000001 00000001

8.3 Classful IPv4 Addressing (HISTORICAL)

Originally, IPv4 addresses were divided into 5 classes (A, B, C, D, E). This is now mostly obsolete but
still tested in exams.

Number Hosts
Clas First First Byte Network
Default Mask Host Part of per
s Bits Range Part
Networks Network
16,777,2
A 0 1-126 [Link] or /8 8 bits 24 bits 126
14
[Link]
B 10 128-191 16 bits 16 bits 16,384 65,534
or /16
[Link]
C 110 192-223 24 bits 8 bits 2,097,152 254
or /24
D 1110 224-239 N/A Multicast Multicast N/A N/A
Reserved/
E 1111 240-255 N/A Experimen Reserved N/A N/A
tal

SOLVED NUMERICAL 7: Finding IP Address Class

PROBLEMS
Find the class of each IP address: a) 00000001 00001011 00001011 11101111 b) 11000001
10000011 00011011 11111111 c) [Link] d) [Link]

SOLUTIONS:
• a) First bit = 0. Therefore: CLASS A (Class A starts with 0)
• b) First bits = 110. Therefore: CLASS C (Class C starts with 110, third bit is 0)
• c) First byte = 14. Range 1-126 = Class A. Therefore: CLASS A
• d) First byte = 252. Range 240-255 = Class E. Therefore: CLASS E
8.4 CIDR - Classless Inter-Domain Routing

CIDR FORMAT
CIDR (Classless InterDomain Routing) - pronounced "cider" Address format: a.b.c.d/n
Where n = number of bits in the subnet/network portion Example: [Link]/23 - First 23
bits = network/subnet portion - Remaining 9 bits = host portion - Block size = 2^(32-23) =
2^9 = 512 addresses

CIDR Key Formulas:

FIRST ADDRESS:
First Address = Set rightmost (32-n) bits to 0 Equivalent: Given
Address AND Subnet Mask

LAST ADDRESS:
Last Address = Set rightmost (32-n) bits to 1 Equivalent: Given
Address OR (Complement of Subnet Mask)

NUMBER OF ADDRESSES:
Number of Addresses = 2^(32-n)

SOLVED NUMERICAL 8: CIDR Block Calculation

PROBLEM
A block of addresses is granted to a small organization. One of the addresses is
[Link]/28. Find: a) First address in the block b) Last address in the block c) Number
of addresses

SOLUTION:
Given: [Link]/28 → n = 28
Binary: 11001101 00010000 00100101 00100111

a) FIRST ADDRESS: Set rightmost (32-28) = 4 bits to 0:

11001101 00010000 00100101 00100000 = [Link]

b) LAST ADDRESS: Set rightmost 4 bits to 1:

11001101 00010000 00100101 00101111 = [Link]
c) NUMBER OF ADDRESSES:
Number = 2^(32-28) = 2^4 = 16 addresses

VERIFICATION
Range: [Link] to [Link] Count: 32, 33, 34, ... 47 = 16 addresses ✓ First
address ([Link]) is the NETWORK ADDRESS (not assigned to any device) Last
address ([Link]) is the BROADCAST ADDRESS Usable addresses = 16 - 2 = 14

SOLVED NUMERICAL 9: CIDR using Mask Operations

PROBLEM
Same problem as above ([Link]/28). Solve using subnet mask (32-bit) representation.

/28 mask = 11111111 11111111 11111111 11110000

a) First address (AND with mask):
Octet 1 Octet 2 Octet 3 Octet 4

Address 11001101 00010000 00100101 00100111

Mask 11111111 11111111 11111111 11110000
AND Result 11001101 00010000 00100101 00100000
32 ← First
Decimal 205 16 37
Address

b) Last address (OR with complement of mask):

Octet 1 Octet 2 Octet 3 Octet 4

Address 11001101 00010000 00100101 00100111

~Mask 00000000 00000000 00000000 00001111
OR Result 11001101 00010000 00100101 00101111
47 ← Last
Decimal 205 16 37
Address

SOLVED NUMERICAL 10: ISP Address Allocation

PROBLEM
An ISP is granted block [Link]/16 (65,536 addresses). Distribute to: a) Group 1: 64
customers, each needs 256 addresses b) Group 2: 128 customers, each needs 128
 addresses c) Group 3: 128 customers, each needs 64 addresses Design subblocks and find
remaining addresses.

SOLUTION:

a) Group 1: 64 customers × 256 addresses each = 16,384 total addresses

• 256 addresses → 2^8 → 8 bits for host part → prefix = 32-8 = /24
• First customer: [Link]/24 ([Link] to [Link])
• Second customer: [Link]/24 ([Link] to [Link])
• ...
• 64th customer: [Link]/24 to [Link]
• Total used: 64 × 256 = 16,384 addresses

b) Group 2: 128 customers × 128 addresses each = 16,384 total addresses

• 128 addresses → 2^7 → 7 bits for host → prefix = /25
• Starts at [Link]/25 (after Group 1 ends at [Link])
• First customer: [Link]/25 ([Link] to [Link])
• Second customer: [Link]/25 ([Link] to [Link])
• Last customer: [Link]/25 to [Link]
• Total used: 128 × 128 = 16,384 addresses

c) Group 3: 128 customers × 64 addresses each = 8,192 total addresses

• 64 addresses → 2^6 → 6 bits for host → prefix = /26
• Starts at [Link]/26
• Total used: 128 × 64 = 8,192 addresses

Count

Total ISP addresses 65,536

Group 1 (64 × 256) 16,384
Group 2 (128 × 128) 16,384
Group 3 (128 × 64) 8,192
Total Allocated 40,960
REMAINING AVAILABLE 24,576

8.5 Subnetting
 WHAT IS A SUBNET?
A SUBNET is a group of device interfaces that can physically reach each other WITHOUT
passing through an intervening router. Subnet Part: High-order bits of IP address (same for
all devices in subnet) Host Part: Low-order bits (unique per device in subnet) Subnet Mask
(/24 means first 24 bits identify the subnet) Recipe to find subnets: Detach each interface
from its host or router, creating "islands" of isolated networks. Each island is a subnet.

SOLVED NUMERICAL 11: Finding Subnets

PROBLEM
A network has the following IP addresses assigned: [Link], [Link], [Link],
[Link] (all with /24) [Link], [Link], [Link] (all with /24) [Link], [Link],
[Link] (all with /24) Identify the subnets.

SOLUTION:
• Subnet 1: [Link]/24 - Contains [Link], .2, .3, .4 (first 24 bits = 223.1.1)
• Subnet 2: [Link]/24 - Contains [Link], .2, .9 (first 24 bits = 223.1.2)
• Subnet 3: [Link]/24 - Contains [Link], .2, .27 (first 24 bits = 223.1.3)
Each /24 subnet can have 2^8 - 2 = 254 usable host addresses.
TOPIC 9: NAT - NETWORK ADDRESS TRANSLATION

9.1 Problem NAT Solves

IPv4 addresses are being exhausted. NAT allows multiple devices in a private network to share a
SINGLE public IP address.

PRIVATE IP ADDRESS RANGES (RFC 1918)

[Link]/8 → [Link] to [Link] (16,777,216 addresses) [Link]/12 →
[Link] to [Link] (1,048,576 addresses) [Link]/16 → [Link] to
[Link] (65,536 addresses) These addresses are for PRIVATE NETWORKS
ONLY - NOT routable on public Internet.

9.2 How NAT Works

Direction NAT Action

OUTGOING (LAN → Replace (Source IP, Source Port) with (NAT IP, New Port). Record
Internet) translation in NAT table.
INCOMING (Internet → Look up (Destination IP, Destination Port) in NAT table. Replace with
LAN) original (Private IP, Original Port).

SOLVED NUMERICAL 12: NAT Translation Trace

PROBLEM
Host [Link] sends packet to web server [Link]:80 NAT router has public IP:
[Link] Source port chosen by host: 3345 Trace the packet through NAT.

Step Event Packet Source Packet Destination

1 Host sends packet [Link] : 3345 [Link] : 80
NAT router translates [Link] : 5001 (new
2 [Link] : 80
outgoing port!)
[[Link]:5001 ↔
2b NAT table entry created (recorded for later)
[Link]:3345]
Reply comes back from
3 [Link] : 80 [Link] : 5001
server
 NAT router looks up Finds: 5001 →
4
table [Link]:3345
4b NAT translates incoming [Link] : 80 [Link] : 3345

5 Packet delivered to host Host [Link] receives reply correctly

9.3 NAT Advantages and Controversies

Advantages Controversies/Disadvantages
Only ONE public IP needed for entire private Routers "should" only process up to Layer 3 (NAT
network operates at Layer 4 - port numbers)
Can change private addresses without notifying Port number manipulation violates end-to-end
outside world argument
Can change ISP without changing private Address shortage should be solved by IPv6, not
addresses NAT
Security: private devices not directly visible to NAT traversal problems: How can external clients
Internet connect to servers behind NAT?
TOPIC 10: IPv6

10.1 Motivation for IPv6

• Primary: 32-bit IPv4 address space would be completely allocated (ICANN exhausted IPv4 in
2011)
• Processing speed: Fixed 40-byte header allows faster forwarding
• Different treatment of "flows": Quality of Service support
• IPv6 has 128-bit addresses = 2^128 ≈ 3.4 × 10^38 addresses

10.2 IPv6 Datagram Format

Field Size Description

Version 4 bits IPv6 = 0110 (6 in binary)
Priority/Traffic Class 8 bits Identify priority among datagrams in a flow
Flow Label 20 bits Identify datagrams in the same "flow" (concept not fully defined)
Payload Length 16 bits Length of payload in bytes
Next Header 8 bits Identifies upper-layer protocol (similar to IPv4 Protocol field)
Hop Limit 8 bits Like IPv4 TTL. Decremented at each router. Packet dropped at 0.
Source Address 128 bits 128-bit IPv6 source address (16 bytes)
Destination Address 128 bits 128-bit IPv6 destination address
Data/Payload Variable Upper layer payload

10.3 What's MISSING in IPv6 vs IPv4?

Feature in IPv4 Status in IPv6 Reason

Speed up processing at routers. Upper layers handle
Checksum REMOVED
error checking.
Fragmentation/ Routers no longer fragment. Sender uses Path MTU
REMOVED
Reassembly Discovery. Simplifies router processing.
Available as upper-layer, "next-header" protocol at router.
Options field REMOVED (sort of)
Keeps basic header fixed at 40 bytes.
10.4 IPv6 Address Format
IPv6 ADDRESS FORMAT
IPv6 uses 128 bits written as 8 groups of 4 hexadecimal digits separated by colons Example:
2001:0DB8:0000:0000:0000:0000:0000:0001 ABBREVIATION RULES: 1. Leading zeros in
each group can be omitted: 0DB8 → DB8 2. One sequence of consecutive all-zero groups
can be replaced by :: Example: 2001:0DB8:0000:0000:0000:0000:0000:0001 =
2001:DB8::1 NOTE: :: can only be used ONCE in an address!

10.5 Transition from IPv4 to IPv6: Tunneling

Not all routers can be upgraded simultaneously (no "flag days"). The solution is tunneling.

TUNNELING EXPLAINED
Tunneling: An IPv6 datagram is carried as PAYLOAD inside an IPv4 datagram among IPv4
routers. This is "packet within a packet" or "encapsulation". How it works: 1. IPv6 packet
arrives at "tunnel entry" (IPv6/v4 border router) 2. Border router encapsulates IPv6 packet in
IPv4 datagram 3. IPv4 datagram travels through the IPv4 network 4. IPv4 datagram arrives
at tunnel exit (another IPv6/v4 border router) 5. IPv6 packet is extracted and forwarded
normally The IPv4 header has: source = tunnel entry router, destination = tunnel exit router

10.6 IPv4 vs IPv6: Complete Comparison

Feature IPv4 IPv6

Address Length 32 bits 128 bits
Address Space ~4.3 billion ~3.4 × 10^38
Header Size 20 bytes (min), variable 40 bytes (fixed)
Header Checksum Yes No (removed for speed)
Fragmentation At routers Only at source (not routers)
Extension headers (next header
Options In header (variable length)
chain)
NAT Required Often needed Not needed (huge address space)
Configuration Manual or DHCP Auto-configuration supported
Security (IPSec) Optional Mandatory (built-in)
TTL/Hop Limit TTL (8-bit) Hop Limit (8-bit)
Notation Dotted decimal (x.x.x.x) Colon hexadecimal (x:x:x:x:x:x:x:x)
TOPIC 11: BROADCAST AND MULTICAST ROUTING

11.1 Broadcast Routing

Broadcast routing delivers packets from source to ALL other nodes in the network.

Method Description Problem

Inefficient: source must know all
Source sends N separate copies (one
Source Duplication recipients. N copies transmitted even if
per destination)
same link used.
In-Network Network routers create copies as
More efficient. Better scalability.
Duplication needed

In-Network Broadcast Approaches:

Approach How It Works Problem

Node receives broadcast
CYCLES and BROADCAST STORMS (infinite
Flooding packet → sends copy to ALL
looping)
neighbors
Node broadcasts only if it
hasn't broadcast same packet
Controlled Flooding Better, but more complexity
before. Uses packet IDs or
RPF.
Forward packet only if it
Reverse Path
arrived on the shortest path Efficient. No storms. Standard in practice.
Forwarding (RPF)
between this node and source
Broadcast only along edges of
Spanning Tree a spanning tree (no cycles, No redundant packets. Most efficient.
reaches all nodes)

11.2 Multicast Routing

Multicast routing delivers packets from source to a GROUP of destinations (not all, not one).

MULTICAST PROBLEM STATEMENT

Goal: Find a TREE (or trees) connecting routers that have local multicast group members.
Two types of multicast trees: 1. SHARED TREE: Same tree used by ALL group members.
One tree for entire group. 2. SOURCE-BASED TREE: Different tree from each sender to
receivers. N trees for N senders. Multicast uses Class D addresses ([Link] to
[Link] in IPv4)
TOPIC 12: SOFTWARE DEFINED NETWORKING (SDN)

12.1 Traditional vs SDN Control Plane

Aspect Traditional Routing SDN Control Plane

Control Location Distributed (in each router) Centralized (remote controller)
Each router runs routing algorithm Remote controller computes
Intelligence
independently forwarding tables, installs in routers
Very flexible (software can implement
Flexibility Limited (fixed algorithm per protocol)
any algorithm)
Configuration Configure each router individually Central controller configures all routers
Examples OSPF, BGP, RIP in routers OpenFlow, OpenDaylight, ONOS

12.2 Generalized Forwarding: Match+Action

Modern routers (especially SDN) use the "match+action" paradigm, which generalizes traditional
destination-based forwarding.

MATCH+ACTION PRINCIPLE
MATCH: Match packet header fields (can be ANY field: IP src, IP dst, TCP port, MAC addr,
etc.) ACTION: Take an action based on the match: - Forward: Send to specific output port
- Drop: Discard the packet - Modify: Change field values - Send to controller: Let controller
decide - Rate limit: Throttle traffic OpenFlow is the most well-known match+action
standard.
IMPORTANT EXAM QUESTIONS & ANSWERS

Short Answer Questions

Q1: What is the difference between routing and forwarding?

ANSWER
ROUTING is the process of determining the path taken by packets from source to
destination (a network-wide, control plane function using routing algorithms like Dijkstra or
Bellman-Ford). FORWARDING is the process of moving packets from a router's input link to
the appropriate output link (a local, data plane function using the forwarding table).
ANALOGY: Routing = planning a road trip. Forwarding = navigating each individual
intersection.

Q2: What is the count-to-infinity problem?

ANSWER
Count-to-infinity is a problem in Distance Vector routing that occurs when a link cost
increases (bad news). When node Y used to reach X via Z, and the direct link cost suddenly
increases, Y checks its neighbor Z's distance. But Z's distance was learned via Y, creating a
routing loop. The algorithm then slowly increments the cost (1, 2, 3, ...) until it reaches actual
cost or infinity. This is "bad news travels slow". Solution: Poisoned Reverse (Z tells Y its
distance to X is ∞ if Z routes via Y).

Q3: What is longest prefix matching and why is it used?

ANSWER
Longest Prefix Matching is the rule that when multiple forwarding table entries match a
destination address, the router chooses the entry with the LONGEST (most specific) prefix.
Why: More specific prefixes represent smaller, more targeted address ranges. A longer
match is more precise. Example: /28 match is more specific than /20 match for the same
address. This allows routers to have both general routes and specific routes, with specific
routes taking priority.

Q4: Differentiate between RIP and OSPF.

ANSWER
RIP (Distance Vector): Hop count metric (max 15), advertisements every 30 sec via UDP,
slow convergence, count-to-infinity vulnerable, simple, limited to small networks. OSPF (Link
State): Cost metric (reflects bandwidth), floods to entire AS, uses Dijkstra's algorithm,
 supports authentication, multiple equal-cost paths, hierarchical areas, suitable for large
networks.

Q5: What is NAT and why is it controversial?

ANSWER
NAT (Network Address Translation) allows multiple devices with private IP addresses (10.x,
172.16.x, 192.168.x) to share a single public IP address. NAT translates (private IP, port) ↔
(public IP, new port) in outgoing/incoming packets. Controversies: 1. Routers should only
process Layer 3, but NAT modifies Layer 4 (port numbers) 2. Violates end-to-end argument
(network devices shouldn't modify transport addresses) 3. Address shortage should be
solved by IPv6, not workarounds 4. NAT traversal: external hosts cannot initiate connections
to servers behind NAT

Q6: What is an Autonomous System? Why is hierarchical routing needed?

ANSWER
An Autonomous System (AS) is a group of routers under the same administrative control
running the same intra-AS routing protocol, identified by a unique AS number. Hierarchical
routing is needed because: 1. SCALE: With billions of destinations, flat routing tables are
impossibly large 2. ADMINISTRATIVE AUTONOMY: Each organization wants control over
its own routing 3. EFFICIENCY: Hierarchical routing reduces table size and update traffic
Solution: Intra-AS routing (RIP/OSPF within AS) + Inter-AS routing (BGP between ASes)

Q7: Why was IPv6 introduced? What are its main improvements?
ANSWER
IPv6 was introduced because: 1. IPv4 32-bit address space exhausted (ICANN allocated last
blocks in 2011) 2. Need for faster processing and more flexible QoS IPv6 improvements
over IPv4: 1. 128-bit addresses (3.4×10^38 possible addresses) 2. Fixed 40-byte header
(faster processing) 3. No checksum (faster router processing) 4. No fragmentation at routers
(simpler) 5. Built-in IPSec security 6. Auto-configuration support 7. Transition via tunneling
(IPv6 inside IPv4)

QUICK REFERENCE: All Key Formulas

Formula/Concept Expression Use Case

Bellman-Ford dx(y) = min_v { c(x,v) + dv(y) } Distance Vector routing, RIP
Address AND Mask (set last
CIDR First Address Find network address of a block
32-n bits to 0)
 Address OR ~Mask (set last
CIDR Last Address Find broadcast address
32-n bits to 1)
Block Size 2^(32-n) Number of addresses in /n block
Subtract network and broadcast
Usable Hosts 2^(32-n) - 2
addresses
n = 32 - log2(addresses
Prefix from hosts Find CIDR prefix for required addresses
needed)
Weighted Fair Queuing fraction for class
WFQ Bandwidth wi / Σwj
i
Buffer Size RTT × C / √N Output port buffer sizing (N flows)
Path Cost (Dijkstra) Sum of link costs along path Total cost of route

UNIT 2 COMPLETE TOPIC SUMMARY

Topic Key Points for Exam

Layer 3. Forwarding (local, data plane) vs Routing (network-wide, control
Network Layer
plane). Best-effort service model.
G=(N,E), costs on links, least-cost path problem. Routing algorithms solve
Graph Abstraction
this.
Global info, iterative, O(n²). Initialize D(v), find min, update neighbors. After
Dijkstra (LS)
k iterations, know k shortest paths.
Local info only. dx(y)=min{c(x,v)+dv(y)}. Distributed, asynchronous. Count-
Bellman-Ford (DV)
to-infinity solved by Poisoned Reverse.
AS = group under same admin. Intra-AS (IGP: RIP/OSPF) vs Inter-AS
Hierarchical Routing
(BGP). Gateway routers connect ASes.
DV algorithm. Hop count metric. Max 15 hops. 30-sec advertisements via
RIP
UDP. 180-sec timeout = dead link.
LS algorithm. Dijkstra. Flooded to entire AS. Authentication. Multiple
OSPF
equal-cost paths. Two-level hierarchy (areas).
Path vector. "Glue of Internet". eBGP (between ASes) + iBGP (within AS).
BGP
Policy over performance. TCP sessions.
Input ports (lookup), Switching fabric (memory/bus/crossbar), Output ports
Router Architecture
(queuing). HOL blocking at input.
FCFS, Priority, Round Robin, WFQ. WFQ gives guaranteed minimum
Packet Scheduling
bandwidth per class.
20-byte min header. TTL (hop limit). Upper layer protocol field. No
IP Datagram
fragmentation in IPv6.
 A(0-126), B(128-191), C(192-223), D(multicast), E(reserved). Classful is
IPv4 Classes
obsolete → CIDR.
a.b.c.d/n. First=AND with mask. Last=OR with ~mask. Size=2^(32-n).
CIDR
Enables variable-length prefixes.
Divide network into smaller blocks. Subnet mask determines network vs
Subnetting
host portion.
Private IPs share one public IP. Translates (private IP, port) ↔ (public IP,
NAT
new port). Controversial but widely used.
128-bit addresses. Fixed 40-byte header. No checksum/fragmentation at
IPv6
routers. Tunneling for IPv4 interop.
Source duplication vs in-network. RPF prevents storms. Spanning tree
Broadcast
most efficient.
Shared tree (one for group) vs source-based trees (one per sender). Class
Multicast
D addresses.

END OF UNIT 2 NOTES