Network Layer (part 2: 4.7–4.12)
Open in the Padhaiko app4.7 Routing protocols: RIP, OSPF, EIGRP, BGP
Dynamic routing protocols allow routers to discover remote networks, build forwarding tables automatically, and adapt to link failures without manual reconfiguration. They fall into Interior Gateway Protocols (IGPs) used inside a single Autonomous System (AS) and Exterior Gateway Protocols (EGPs) used between Autonomous Systems.
1. Routing Information Protocol (RIP)
RIP is a classic Distance Vector IGP based on the Bellman-Ford algorithm.
- Metric: Hop count (each router traversed counts as hop). Any destination at hops is treated as unreachable (), limiting RIP to small networks.
- Updates & Encapsulation: Broadcasts (RIPv1) or multicasts to
224.0.0.9(RIPv2) the entire routing table every over UDP port . - RIPv1 vs. RIPv2: RIPv1 is classful and sends no subnet mask (no VLSM/CIDR support); RIPv2 is classless, sends subnet masks, and supports authentication.
- Loop Prevention: Uses split horizon, route poisoning, hold-down timers ( invalid timer, flush timer), and triggered updates.
2. Open Shortest Path First (OSPF)
OSPF is an open-standard Link State IGP based on Dijkstra's Shortest Path First (SPF) algorithm.
- Metric: Cost, inversely proportional to link bandwidth:
With Cisco's default reference bandwidth of (), a Fast Ethernet link has cost , while a link has cost .
- Operation: Routers form neighbor adjacencies (
Hellopackets), exchange Link State Advertisements (LSAs) to synchronize an identical Link State Database (LSDB), and run Dijkstra's algorithm independently to compute loop-free shortest paths. - Encapsulation & Hierarchy: Runs directly over IP protocol number (multicast
224.0.0.5for all OSPF routers,224.0.0.6for Designated Routers). Supports hierarchical areas centered on backbone Area 0 to scale to large enterprise networks.
3. Enhanced Interior Gateway Routing Protocol (EIGRP)
EIGRP is an advanced hybrid (advanced distance-vector) IGP originally developed by Cisco and later published as an informational RFC (RFC 7868).
- Algorithm: Uses the Diffusing Update Algorithm (DUAL) to guarantee loop-free paths and near-instantaneous convergence via pre-computed backup routes (Feasible Successors).
- Composite Metric: Computes path cost using bandwidth and cumulative delay by default (with optional load and reliability), scaled by .
- Updates: Sends bounded, incremental (partial) updates only when a topology change occurs, using the Reliable Transport Protocol (RTP) directly over IP protocol number (multicast
224.0.0.10).
4. Border Gateway Protocol (BGP)
BGP (currently BGP-4) is the sole Exterior Gateway Protocol (EGP) that interconnects Autonomous Systems on the global Internet.
- Routing Paradigm: Path Vector routing. Instead of exchanging hop counts or link costs, BGP advertises network reachability along with the full sequence of Autonomous System numbers (AS_PATH) traversed, preventing inter-AS loops by rejecting any route containing its own AS number.
- Transport & Types: Runs over TCP port for reliable session maintenance.
- eBGP (External BGP): Peers in different Autonomous Systems (default ).
- iBGP (Internal BGP): Peers inside the same Autonomous System to distribute external reachability across the transit AS.
- Policy-Based Metric: Rather than shortest distance alone, BGP selects routes using administrative path attributes (Weight, Local Preference, AS_PATH length, Origin, MED) reflecting business and peering policies.
| Feature | RIPv2 | OSPF | EIGRP | BGP-4 |
|---|---|---|---|---|
| Scope | IGP | IGP | IGP | EGP |
| Paradigm | Distance Vector | Link State | Advanced Distance Vector | Path Vector |
| Algorithm | Bellman-Ford | Dijkstra (SPF) | DUAL | Best-Path Attribute Selection |
| Primary Metric | Hop count (max ) | Cumulative cost (bandwidth) | Composite (bandwidth, delay) | Policy attributes and AS_PATH |
| Transport | UDP port | IP protocol | IP protocol | TCP port |
| Convergence | Slow | Fast | Very fast | Slow (scale-oriented) |
4.8 Network address translation (NAT)
Network Address Translation (NAT)
Network Address Translation (NAT) is a mechanism implemented at a border router or firewall that translates private internal IPv4 addresses (RFC 1918, e.g., 192.168.1.x, 10.x.x.x) into globally routable public IPv4 addresses as packets cross between a private stub network and the public Internet.
Need for NAT
- Mitigating IPv4 Exhaustion: Allows an entire organization of thousands of devices to share one or a small pool of public IPv4 addresses.
- Topology Independence & Privacy: Internal IP addressing schemes can be reorganized without changing public ISP allocations, and internal host addresses remain hidden from external observers.
Types of NAT
- Static NAT (One-to-One): Maps one specific private IP permanently to one specific public IP (e.g., exposing an internal web server to the Internet). Saves no IPv4 addresses.
- Dynamic NAT (Pool-to-Pool): Maps a private IP dynamically to the next available public IP from a pre-configured pool. Once the pool is exhausted, new connections are blocked.
- Port Address Translation (PAT) / NAT Overload (Many-to-One): Maps multiple private IP addresses simultaneously to a single public IP address by rewriting both the source IP address and the source TCP/UDP port number, storing each active flow in a NAT translation table. Because the port field is (–), one public IP can theoretically multiplex over concurrent flows.
| Protocol | Inside Local (Private IP:Port) | Inside Global (Public IP:Port) | Outside Global (Server IP:Port) |
|---|---|---|---|
| TCP | 192.168.1.10:51422 | 203.0.113.5:10001 | 93.184.216.34:443 |
| TCP | 192.168.1.25:51422 | 203.0.113.5:10002 | 93.184.216.34:443 |
| UDP | 192.168.1.18:53210 | 203.0.113.5:10003 | 8.8.8.8:53 |
Limitations of NAT
- Breaks End-to-End Principle: Routers modify Layer 3 and Layer 4 headers and must recalculate IP/TCP/UDP checksums, adding processing overhead.
- Complicates Inbound Connections & P2P: External hosts cannot initiate connections to hosts behind PAT without explicit port forwarding or NAT traversal techniques (STUN/TURN).
- Breaks Embedded IP Applications & IPsec: Protocols that embed IP addresses inside application payloads (e.g., FTP active mode, SIP) require Application Layer Gateways (ALGs), and IPsec Authentication Header (AH) fails because NAT alters header fields covered by cryptographic integrity checks.
4.9 IPv6 addressing, need and features of IPv6
Need for IPv6
The rapid growth of smartphones, cloud infrastructure, and IoT sensors exhausted the IPv4 space ( addresses). While CIDR and NAT delayed exhaustion, NAT broke end-to-end connectivity and complicated security and mobility. IPv6 (RFC 8200) resolves address exhaustion permanently while simplifying router packet processing.
Key Features of IPv6
- Expanded Address Space: Provides unique addresses, eliminating the need for NAT.
- Simplified Fixed-Length Header: Fixed base header with fields (down from IPv4's variable – header with fields). No header checksum (error checking is delegated to Layer 2 and Layer 4) and no router fragmentation (only the source host performs Path MTU Discovery).
- Extension Headers: Optional capabilities (routing, fragmentation, IPsec security) are chained after the base header via the
Next Headerfield, processed only when needed. - Stateless Address Autoconfiguration (SLAAC): Hosts automatically configure a globally routable IPv6 address using router advertisements (RAs) without requiring a DHCP server.
- Built-in Security and Flow Labeling: Native support for IPsec and a
Flow Labelfield for real-time QoS stream identification.
IPv6 Address Representation and Compression Rules
An IPv6 address is long, written as eight hexadecimal groups (hextets) separated by colons (:):
Two standard compression rules (RFC 5952) shorten the notation unambiguously:
- Omit Leading Zeros: Within each 4-digit hextet, leading zeros are removed (
0db8db8,00000). Never omit trailing zeros (0800800, not8). - Zero Compression (
::): A single contiguous run of two or more all-zero hextets (:0:0:) may be replaced with::. This::shorthand may appear at most once in an address so the original length remains unambiguous.
IPv6 Address Types
| Address Type | Prefix / Range | Scope & Purpose |
|---|---|---|
| Global Unicast | 2000::/3 | Globally unique, Internet-routable addresses (analogous to public IPv4) |
| Link-Local Unicast | fe80::/10 | Automatically assigned on every interface; valid only on the local link (used by NDP and routing protocols) |
| Unique Local (ULA) | fc00::/7 (typically fd00::/8) | Private internal addressing (analogous to RFC 1918), not routed on the public Internet |
| Multicast | ff00::/8 | One-to-many delivery; replaces broadcast completely (e.g., ff02::1 all nodes on link, ff02::2 all routers) |
| Anycast | Allocated from Unicast space | Assigned to multiple interfaces; packet is delivered to the topologically nearest interface |
| Special Addresses | ::1/128, ::/128 | ::1 is Loopback (127.0.0.1 equivalent); :: is the Unspecified address (0.0.0.0 equivalent) |
4.10 Protocols: IPv4, ARP, ICMP, IPv6, ICMPv6
1. IPv4 (Internet Protocol Version 4)
IPv4 provides connectionless, best-effort datagram delivery using a variable – header:
- Key Header Fields:
Version(),IHL(Header Length in words, min ),Type of Service / DSCP,Total Length(, max ),Identification,Flags(DF= Don't Fragment,MF= More Fragments),Fragment Offset(measured in units),TTL(Time to Live, decremented by per hop),Protocol(, , , ),Header Checksum,Source IP,Destination IP. - Fragmentation Rule: When a packet exceeds a link's MTU, every non-final fragment must carry a payload size divisible by because
Fragment Offsetcounts blocks of .
2. ARP (Address Resolution Protocol)
ARP resolves a known IPv4 address to an unknown physical MAC address on the local LAN (RFC 826):
- Host A checks its local ARP cache. If absent, it sends an ARP Request as a Layer 2 broadcast (
FF:FF:FF:FF:FF:FF) asking: "Who has IP ? Tell IP , MAC ." - All hosts on the LAN inspect the request; only the host owning IP sends a unicast ARP Reply containing its MAC address .
- Host A caches the mapping with a finite aging timer.
- Variants: Proxy ARP (router answers on behalf of another network) and Gratuitous ARP (host announces its own IP-to-MAC mapping to detect duplicate IPs or update switches).
3. ICMP (Internet Control Message Protocol for IPv4)
Because IP is connectionless and provides no built-in diagnostics, ICMP (IP protocol ) reports delivery errors and performs network queries:
- Error-Reporting Messages:
Destination Unreachable(Type 3),Time Exceeded(Type 11, sent when , poweringtraceroute),Redirect(Type 5),Parameter Problem(Type 12). - Query Messages:
Echo Request(Type 8) andEcho Reply(Type 0), which power thepingutility.
4. IPv6 Header Format
The IPv6 base header is strictly and contains only fields: Version (), Traffic Class, Flow Label (), Payload Length (excludes the header), Next Header (identifies Layer 4 protocol or first extension header), Hop Limit (replaces TTL), Source Address (), and Destination Address ().
5. ICMPv6 (Internet Control Message Protocol for IPv6)
ICMPv6 (Next Header = 58) expands on ICMPv4 by absorbing essential link-layer functions that were separate protocols in IPv4:
- Diagnostics & Errors:
Destination Unreachable,Packet Too Big(essential for Path MTU Discovery since routers do not fragment),Time Exceeded,Echo Request(Type 128),Echo Reply(Type 129). - Neighbor Discovery Protocol (NDP): Replaces IPv4 ARP, ICMP Router Discovery, and Redirect using five ICMPv6 message types: Router Solicitation (RS), Router Advertisement (RA), Neighbor Solicitation (NS), Neighbor Advertisement (NA), and Redirect.
- Multicast Listener Discovery (MLD): Replaces IPv4 IGMP for multicast group management.
4.11 Transition from IPv4 to IPv6 and strategies
Because billions of legacy IPv4 devices cannot upgrade simultaneously ("flag day" is impossible), migration relies on three coexistence strategies defined in RFC 4213 and subsequent IETF standards:
1. Dual Stack
A host or router runs both IPv4 and IPv6 protocol stacks concurrently, possessing both an IPv4 and an IPv6 address.
- Applications query DNS for both
AAAA(IPv6) andA(IPv4) records; modern operating systems prefer IPv6 when reachable (Happy Eyeballs algorithm) and fall back cleanly to IPv4 if the destination only supports IPv4. - Pros/Cons: Easiest and cleanest long-term architecture; requires double routing table memory and dual configuration management on routers.
2. Tunneling
When two IPv6 networks must communicate across an intermediate IPv4-only network, border routers encapsulate the entire IPv6 packet inside an IPv4 packet (Protocol = 41) at the tunnel entry and decapsulate it back to IPv6 at the tunnel exit.
- Common Mechanisms: Configured manual point-to-point IPv6-in-IPv4 tunnels, 6to4, Teredo (UDP-encapsulated to traverse NAT), and ISATAP.
- Drawbacks: Adds of IPv4 header overhead (reducing effective MTU) and introduces encapsulation processing delay.
3. Header Translation (Protocol Translation)
Used when an IPv6-only host must communicate directly with an IPv4-only server that lacks dual-stack capability.
- NAT64 / DNS64: DNS64 synthesizes a special IPv6 address (embedding the server's IPv4 address into a
64:ff9b::/96prefix) when noAAAArecord exists. A stateful NAT64 gateway translates the IPv6 packet header to an IPv4 header (and vice versa) in transit. - Limitations: Not all header fields map one-to-one (e.g., IPv6 Flow Label has no IPv4 equivalent), and embedded IP literals in payloads require ALGs.
4.12 Traffic shaping and congestion control mechanisms
Congestion occurs when offered packet load approaches or exceeds network capacity, causing router queues to overflow, packet drops, high queuing delay, and congestion collapse (goodput plunges as retransmissions flood links).
Open-Loop vs. Closed-Loop Congestion Control
- Open-Loop (Preventive): Designs policies beforehand so congestion does not occur (e.g., admission control, traffic shaping, traffic policing).
- Closed-Loop (Reactive): Monitors live network feedback to throttle sources after congestion begins (e.g., Explicit Congestion Notification ECN, choke packets, TCP congestion control).
Traffic Shaping Algorithms
Traffic shaping smooths bursty source traffic into a predictable flow conforming to a Service Level Agreement (SLA):
| Aspect | Leaky Bucket Algorithm | Token Bucket Algorithm |
|---|---|---|
| Core Analogy | Water enters an irregular bucket and leaks through a small hole at a constant rate | Tokens accumulate in a bucket at rate up to capacity ; each byte/packet transmitted consumes tokens |
| Output Rate | Strictly constant rate , even when the input is idle | Allows controlled bursts up to peak rate as long as accumulated tokens remain |
| Idle Period Behavior | Does not accumulate credit while idle | Accumulates tokens up to maximum bucket size while idle |
| Overflow Action | Packets arriving when the buffer is full are dropped | If tokens are exhausted, packets wait (shaping) or are dropped/marked (policing) |
| Burst Formula | No burst above permitted | Max burst duration (for ); max burst data |
Queue Management and Congestion Avoidance
- Tail Drop: Simplest router queue policy—drops newly arriving packets once the FIFO buffer is full. Causes TCP global synchronization, where many flows drop and halve their rates simultaneously.
- Random Early Detection (RED): Proactively monitors the average queue length . Below threshold , all packets are queued; between and , arriving packets are dropped (or ECN-marked) with probability increasing linearly up to ; above , all arrivals are dropped. This signals senders early before the buffer saturates.
- Explicit Congestion Notification (ECN, RFC 3168): Instead of dropping packets, RED-enabled routers set the
CE(Congestion Experienced) bits in the IP header; the receiver echoes this back in the TCP header so the sender slows down without packet loss.
Worked Out Examples
4.4
A host connects to a network via a Token Bucket traffic shaper with a bucket capacity (), a token replenishment rate , and a physical link peak output rate . Suppose the bucket is completely full when a large burst of data arrives.
- Calculate the maximum duration (in milliseconds) for which the shaper can transmit at the full peak rate .
- Calculate the total volume of data (in ) transmitted during this peak burst.
- Explain what happens immediately after time .
Applying the Token Bucket Burst Relation: Let be the duration of the peak-rate burst. During interval , tokens are drained at output rate and replenished simultaneously at rate , so the bucket empties when:
Substituting , , and :
Calculating Total Data Transmitted During the Burst: At output rate , the volume sent during is:
(Cross-check: initial in bucket plus newly generated tokens .)
Post-Burst Behavior: Once , the bucket contains tokens. Thereafter, the host can only transmit at the steady token arrival rate until an idle period allows the bucket to refill.
- Maximum peak-rate burst duration: .
- Total data transmitted during the burst: ().
- After , the output rate is throttled to the token arrival rate of .
4.5
An organization is allocated the IPv6 prefix 2001:0db8:004a::/48 and assigns the subnet 2001:0db8:004a:0000::/64 to an Ethernet LAN. A workstation on this LAN has the MAC address 00:1A:2B:3C:4D:5E.
- How many
/64subnets can the organization create from its/48allocation? - Write the compressed (RFC 5952) representation of the LAN subnet prefix
2001:0db8:004a:0000::/64. - Derive the workstation's Modified EUI-64 Interface ID and its resulting global IPv6 address via SLAAC.
Counting Available /64 Subnets: The subnetting field spans from bit to bit , giving subnet bits:
Compressing the Subnet Prefix: The full prefix is 2001:0db8:004a:0000:0000:0000:0000:0000/64. Removing leading zeros gives 2001:db8:4a:0:0:0:0:0/64. Collapsing the longest contiguous run of zeros into :: yields:
Generating the Modified EUI-64 Interface ID:
- Split MAC and insert
FFFE:001A:2BFF:FE3C:4D5E. - First octet is
0x00(00000000in binary). Inverting the bit (XOR with0x02) changes00000000to00000010(0x02). - Resulting Modified EUI-64 Interface ID:
021a:2bff:fe3c:4d5e. - Combining with the
/64prefix and dropping the leading zero in021agives the full SLAAC global address:
-
/64subnets. - Compressed prefix:
2001:db8:4a::/64. - Interface ID:
021a:2bff:fe3c:4d5e; full global IPv6 address:2001:db8:4a::21a:2bff:fe3c:4d5e/64.
4.6
An IPv4 datagram with a Total Length of (including a standard IPv4 header) and Identification 4512 arrives at a router whose outbound Ethernet interface has . Assume the DF flag is . Calculate the Total Length, MF (More Fragments) flag, and Fragment Offset for every generated fragment.
Determining Payload Sizes:
- Original IPv4 payload size:
- Maximum data per fragment allowed by :
- Check alignment for the Fragment Offset field:
Thus each non-final fragment carries of payload.
Constructing Each Fragment:
- Fragment 1: Carries bytes – ( payload).
- Total Length
- (more fragments follow)
- Fragment Offset
- Fragment 2: Carries bytes – ( payload).
- Total Length
- Fragment Offset
- Fragment 3: Carries remaining (bytes –).
- Total Length
- (final fragment)
- Fragment Offset
Three fragments (all with ):
- Fragment 1: Total Length , , Offset .
- Fragment 2: Total Length , , Offset .
- Fragment 3: Total Length , , Offset .
Practice Exercises
Practice Exercises — Routing Protocols, NAT, IPv6 & Congestion Control
Differentiate between RIP, OSPF, and BGP based on:
- Routing algorithm and metric used.
- Transport mechanism (protocol and port number, if any).
- Typical deployment scope.
Evaluating the Three Protocols:
- RIP: Uses the Bellman-Ford distance-vector algorithm with hop count (maximum , = unreachable) as its metric. It encapsulates routing updates in UDP port and is suited only for small, flat IGP networks.
- OSPF: Uses Dijkstra's Shortest Path First (SPF) link-state algorithm with interface cost inversely proportional to bandwidth. It runs directly over IP protocol and scales to large enterprise IGPs via multi-area hierarchy.
- BGP: Uses path-vector routing based on the AS_PATH and administrative policy attributes rather than pure shortest distance. It establishes peer sessions over TCP port and operates as the global Internet's EGP between Autonomous Systems.
RIP is an IGP using Bellman-Ford hop counts over UDP port ; OSPF is a hierarchical IGP using Dijkstra's SPF bandwidth cost over IP protocol ; BGP is the Internet's EGP using path-vector policy attributes over TCP port .
Explain how Port Address Translation (PAT / NAT Overload) enables hundreds of private hosts to share a single public IPv4 address, and state two architectural limitations of NAT.
PAT Multiplexing Mechanism: When internal hosts send outbound packets, the NAT router replaces each packet's private source IP with the router's single public IP and assigns a unique source port number from the port space. The router records (Private IP, Private Port) <-> (Public IP, Translated Port) in its NAT translation table. When return packets arrive from the Internet, the router inspects the destination port number to demultiplex the traffic back to the exact originating private host.
Architectural Limitations:
- Breaks End-to-End Connectivity: External clients cannot initiate unsolicited inbound connections to private hosts behind PAT without static port forwarding.
- Header Modification Overhead and Protocol Friction: Rewriting IP/port headers forces Layer 3/4 checksum recalculation, breaks IPsec AH integrity checks, and requires ALGs for applications that carry IP addresses inside payloads.
PAT maps multiple private (IP, Port) pairs onto one public IP paired with distinct translated source ports via a state table. Limitations include blocking unsolicited inbound connections and breaking end-to-end integrity/embedded-IP protocols (e.g., IPsec AH, active FTP).
An IPv4 packet of Total Length (with a header) must pass through a link with (). Determine the number of fragments produced and the Total Length, MF flag, and Fragment Offset of each fragment.
Computing Aligned Payload Size per Fragment:
- Original payload .
- Available data space per fragment .
- Because Fragment Offset counts in blocks, round down to the largest multiple of :
Computing Fragment Parameters:
- Fragment 1: payload, Total Length , , Offset .
- Fragment 2: payload, Total Length , , Offset .
- Fragment 3: Remaining payload , Total Length , , Offset .
Three fragments:
- Fragment 1: Total Length , , Offset .
- Fragment 2: Total Length , , Offset .
- Fragment 3: Total Length , , Offset .
A Token Bucket shaper has capacity , token generation rate , and maximum output line rate . If the bucket starts full, calculate the maximum burst duration (in ) and the maximum burst size (in ) transmitted at .
Calculating Burst Duration and Size: Using :
Maximum burst size transmitted at peak rate :
Maximum burst duration is and maximum burst size is .
Briefly describe the three IPv4-to-IPv6 transition strategies (Dual Stack, Tunneling, Header Translation), and expand the compressed IPv6 address 2001:db8:85a3::8a2e:370:7334 to its full 32-hexadecimal-digit form.
Transition Strategies:
- Dual Stack: Devices run both IPv4 and IPv6 stacks simultaneously, selecting IPv6 when end-to-end paths support it and falling back to IPv4 otherwise.
- Tunneling: Encapsulates IPv6 packets inside IPv4 headers (
Protocol = 41) at ingress edge routers to traverse IPv4-only intermediate networks, then decapsulates at egress. - Header Translation (NAT64/DNS64): Translates IPv6 headers to IPv4 headers (and back) at a stateful gateway so IPv6-only clients can reach IPv4-only servers.
Expanding the Compressed IPv6 Address: An IPv6 address has hextets; 2001:db8:85a3::8a2e:370:7334 explicitly shows hextets, so :: represents zero hextets (0000:0000). Padding each hextet to hexadecimal digits with leading zeros gives:
- Dual Stack runs both IP protocols concurrently; Tunneling encapsulates IPv6 inside IPv4 across legacy cores; Header Translation (NAT64) converts headers between IPv6-only and IPv4-only endpoints.
- Full expanded form:
2001:0db8:85a3:0000:0000:8a2e:0370:7334.