PadhaikoAll subjects

Network Layer (part 2: 4.7–4.12)

Computer Networks (ENCT 304)

Open in the Padhaiko app

4.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.

2. Open Shortest Path First (OSPF)

OSPF is an open-standard Link State IGP based on Dijkstra's Shortest Path First (SPF) algorithm.

With Cisco's default reference bandwidth of (), a Fast Ethernet link has cost , while a link has cost .

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).

4. Border Gateway Protocol (BGP)

BGP (currently BGP-4) is the sole Exterior Gateway Protocol (EGP) that interconnects Autonomous Systems on the global Internet.

Comparison of Major Dynamic Routing Protocols
FeatureRIPv2OSPFEIGRPBGP-4
ScopeIGPIGPIGPEGP
ParadigmDistance VectorLink StateAdvanced Distance VectorPath Vector
AlgorithmBellman-FordDijkstra (SPF)DUALBest-Path Attribute Selection
Primary MetricHop count (max )Cumulative cost (bandwidth)Composite (bandwidth, delay)Policy attributes and AS_PATH
TransportUDP port IP protocol IP protocol TCP port
ConvergenceSlowFastVery fastSlow (scale-oriented)

4.8 Network address translation (NAT)

Definition

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

  1. Mitigating IPv4 Exhaustion: Allows an entire organization of thousands of devices to share one or a small pool of public IPv4 addresses.
  2. 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

  1. 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.
  2. 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.
  3. 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.
Example PAT (NAT Overload) Translation Table
ProtocolInside Local (Private IP:Port)Inside Global (Public IP:Port)Outside Global (Server IP:Port)
TCP192.168.1.10:51422203.0.113.5:1000193.184.216.34:443
TCP192.168.1.25:51422203.0.113.5:1000293.184.216.34:443
UDP192.168.1.18:53210203.0.113.5:100038.8.8.8:53

Limitations of NAT


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

  1. Expanded Address Space: Provides unique addresses, eliminating the need for NAT.
  2. 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).
  3. Extension Headers: Optional capabilities (routing, fragmentation, IPsec security) are chained after the base header via the Next Header field, processed only when needed.
  4. Stateless Address Autoconfiguration (SLAAC): Hosts automatically configure a globally routable IPv6 address using router advertisements (RAs) without requiring a DHCP server.
  5. Built-in Security and Flow Labeling: Native support for IPsec and a Flow Label field 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:

  1. Omit Leading Zeros: Within each 4-digit hextet, leading zeros are removed (0db8 db8, 0000 0). Never omit trailing zeros (0800 800, not 8).
  2. 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

Primary IPv6 Address Categories
Address TypePrefix / RangeScope & Purpose
Global Unicast2000::/3Globally unique, Internet-routable addresses (analogous to public IPv4)
Link-Local Unicastfe80::/10Automatically 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
Multicastff00::/8One-to-many delivery; replaces broadcast completely (e.g., ff02::1 all nodes on link, ff02::2 all routers)
AnycastAllocated from Unicast spaceAssigned 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:

2. ARP (Address Resolution Protocol)

ARP resolves a known IPv4 address to an unknown physical MAC address on the local LAN (RFC 826):

  1. 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 ."
  2. All hosts on the LAN inspect the request; only the host owning IP sends a unicast ARP Reply containing its MAC address .
  3. Host A caches the mapping with a finite aging timer.

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:

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:


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.

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.

3. Header Translation (Protocol Translation)

Used when an IPv6-only host must communicate directly with an IPv4-only server that lacks dual-stack capability.


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

Traffic Shaping Algorithms

Traffic shaping smooths bursty source traffic into a predictable flow conforming to a Service Level Agreement (SLA):

AspectLeaky Bucket AlgorithmToken Bucket Algorithm
Core AnalogyWater enters an irregular bucket and leaks through a small hole at a constant rateTokens accumulate in a bucket at rate up to capacity ; each byte/packet transmitted consumes tokens
Output RateStrictly constant rate , even when the input is idleAllows controlled bursts up to peak rate as long as accumulated tokens remain
Idle Period BehaviorDoes not accumulate credit while idleAccumulates tokens up to maximum bucket size while idle
Overflow ActionPackets arriving when the buffer is full are droppedIf tokens are exhausted, packets wait (shaping) or are dropped/marked (policing)
Burst FormulaNo burst above permittedMax burst duration (for ); max burst data

Queue Management and Congestion Avoidance


Worked Out Examples

Example 4.4

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.

  1. Calculate the maximum duration (in milliseconds) for which the shaper can transmit at the full peak rate .
  2. Calculate the total volume of data (in ) transmitted during this peak burst.
  3. 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.

Answer:
  1. Maximum peak-rate burst duration: .
  2. Total data transmitted during the burst: ().
  3. After , the output rate is throttled to the token arrival rate of .
Example 4.5

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.

  1. How many /64 subnets can the organization create from its /48 allocation?
  2. Write the compressed (RFC 5952) representation of the LAN subnet prefix 2001:0db8:004a:0000::/64.
  3. 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:

  1. Split MAC and insert FFFE: 001A:2BFF:FE3C:4D5E.
  2. First octet is 0x00 (00000000 in binary). Inverting the bit (XOR with 0x02) changes 00000000 to 00000010 (0x02).
  3. Resulting Modified EUI-64 Interface ID: 021a:2bff:fe3c:4d5e.
  4. Combining with the /64 prefix and dropping the leading zero in 021a gives the full SLAAC global address:
Answer:
  1. /64 subnets.
  2. Compressed prefix: 2001:db8:4a::/64.
  3. Interface ID: 021a:2bff:fe3c:4d5e; full global IPv6 address: 2001:db8:4a::21a:2bff:fe3c:4d5e/64.
Example 4.6

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
Answer:

Three fragments (all with ):

  1. Fragment 1: Total Length , , Offset .
  2. Fragment 2: Total Length , , Offset .
  3. Fragment 3: Total Length , , Offset .

Practice Exercises

Practice Exercises — Routing Protocols, NAT, IPv6 & Congestion Control

Question 1

Differentiate between RIP, OSPF, and BGP based on:

  1. Routing algorithm and metric used.
  2. Transport mechanism (protocol and port number, if any).
  3. 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.
Answer:

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 .

Question 2

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:

  1. Breaks End-to-End Connectivity: External clients cannot initiate unsolicited inbound connections to private hosts behind PAT without static port forwarding.
  2. 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.
Answer:

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).

Question 3

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 .
Answer:

Three fragments:

  • Fragment 1: Total Length , , Offset .
  • Fragment 2: Total Length , , Offset .
  • Fragment 3: Total Length , , Offset .
Question 4

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 :

Answer:

Maximum burst duration is and maximum burst size is .

Question 5

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:

  1. 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.
  2. Tunneling: Encapsulates IPv6 packets inside IPv4 headers (Protocol = 41) at ingress edge routers to traverse IPv4-only intermediate networks, then decapsulates at egress.
  3. 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:

Answer:
  1. 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.
  2. Full expanded form: 2001:0db8:85a3:0000:0000:8a2e:0370:7334.
← Network Layer (part 1: 4.1–4.6)Transport Layer →