PadhaikoAll subjects

Network Layer (part 1: 4.1–4.6)

Computer Networks (ENCT 304)

Open in the Padhaiko app

4.1 Network layer functions and services

The Network Layer (Layer 3) provides end-to-end, host-to-host packet delivery across multiple interconnected, heterogeneous networks. While the data link layer is responsible for transmitting frames between adjacent nodes on the same physical link, the network layer orchestrates packet delivery across diverse intermediate routers from source to destination.

Definition

Core Functions of the Network Layer

  1. Packetizing: Encapsulates transport-layer segments (TCP/UDP) into network-layer packets (IP datagrams) by attaching an IP header containing source and destination logical addresses.
  2. Logical Addressing: Provides a globally unique, hierarchical addressing scheme (IPv4 / IPv6) that abstracts away physical hardware MAC addresses and enables scalable internetwork routing.
  3. Routing: Evaluates network topology using distributed routing algorithms (e.g., OSPF, BGP) to select the mathematically optimal end-to-end path through the network.
  4. Forwarding: The local hardware mechanism of transferring an incoming packet from a router's input interface to the appropriate outbound interface based on routing table lookups.
  5. Fragmentation and Reassembly: Dynamically partitions large IP datagrams into smaller fragments when traversing a link whose Maximum Transmission Unit (MTU) is smaller than the incoming packet size.
  6. Internetworking: Bridges heterogeneous transmission technologies (e.g., Ethernet, Wi-Fi, optical DWDM, satellite links) into a unified communication fabric.

4.2 Connection oriented and connectionless network services

At the network layer, communication between hosts follows one of two distinct architectural models:

AspectConnection-Oriented ServiceConnectionless Service
Circuit EstablishmentMandatory end-to-end connection setup phase prior to data transmissionNo call setup; packets are injected immediately onto the network
Packet AddressingPackets carry a compact local Virtual Circuit Identifier (VCI)Every packet carries the complete global source and destination IP addresses
Path ConsistencyAll packets belonging to a session follow the exact same predetermined physical pathEach packet is routed independently; packets may follow completely different paths
State InformationIntermediate routers maintain per-connection state tables mapping VCIsRouters are stateless with respect to end-to-end application sessions
Failure VulnerabilityIf an intermediate router crashes, all virtual circuits traversing it are severedHighly resilient; subsequent datagrams are dynamically routed around failed nodes
Quality of Service (QoS)Straightforward to reserve bandwidth and buffer capacity during call setupHistorically best-effort; requires complex DiffServ/IntServ mechanisms for QoS
Representative SystemsATM, X.25, Frame Relay, MPLSThe Internet Protocol (IPv4 / IPv6)

The Internet End-to-End Design Philosophy

The global Internet explicitly chose the connectionless datagram model. The network core is kept intentionally simple ("dumb"), performing stateless, best-effort packet forwarding at wire speed. Complex reliability, flow control, error recovery, and in-order reassembly mechanisms are pushed entirely to the end hosts at the transport layer (TCP). This End-to-End Principle ensures immense scalability, low core router cost, and high resilience against hardware outages.


4.3 Logical addressing and its importance

A fundamental requirement of internetworking is a universal addressing scheme that functions uniformly across all transmission media:

Why Physical (MAC) Addressing Fails at Global Scale

  1. Flat Non-Hierarchical Architecture: MAC addresses are flat identifiers assigned by hardware manufacturers based on manufacturing batches. They carry zero geographical or topological information. An internet router cannot aggregate routes based on MAC addresses; routing tables would have to store billions of flat entries, causing catastrophic lookup failure and memory exhaustion.
  2. Media Heterogeneity: Different physical-layer links use different addressing schemes (or none at all, such as point-to-point leased optical lines). Encapsulating packets with logical IP addresses provides a uniform, media-independent abstraction over all underlying link technologies.

The Power of Hierarchical Logical Addressing

Logical IP addresses are hierarchical, conceptually partitioned into two distinct components:


4.4 IPv4 addressing and classes, private and public IP address, sub-netting and super-netting, VLSM, CIDR

An IPv4 address is a () binary integer, universally formatted as four decimal integers (–) separated by dots: dotted-decimal notation (e.g., 192.168.1.1). The total IPv4 address space encompasses distinct addresses.

1. Classful Addressing (Legacy Architecture)

Originally defined in RFC 791, the IPv4 address space was divided into five distinct classes identified by the leading bits of the first octet:

IPv4 Classful Addressing Structure
ClassLeading BitsFirst Octet RangeDefault Subnet MaskNetID / HostID BitsMax NetworksMax Usable Hosts per Network
Class A0... to 255.0.0.0 (/8) () ()
Class B10.. to 255.255.0.0 (/16) () ()
Class C110. to 255.255.255.0 (/24) () ()
Class D1110 to UndefinedMulticast Groups—Multicast Group Addresses
Class E1111 to UndefinedReserved for Research—Experimental / Future Use

2. Private vs. Public IP Addresses (RFC 1918)

RFC 1918 Private IPv4 Address Allocations
Class ScopePrivate IP Network BlockCIDR PrefixTotal Host Capacity
Class A10.0.0.0 to 10.255.255.25510.0.0.0/8 addresses ( Class A)
Class B172.16.0.0 to 172.31.255.255172.16.0.0/12 addresses ( Class Bs)
Class C192.168.0.0 to 192.168.255.255192.168.0.0/16 addresses ( Class Cs)

3. Subnetting

Subnetting partitions a single large classful network into multiple smaller, logically independent subnetworks:

(Two addresses are always reserved in every subnet: all host bits designates the Subnet Address, and all host bits designates the Directed Broadcast Address).

4. Classless Inter-Domain Routing (CIDR) and Supernetting

Classful addressing suffered from massive address exhaustion (a Class B block with 65,534 addresses was too large, while Class C with 254 was too small). RFC 1519 abolished address classes in 1993 in favor of CIDR:

5. Variable Length Subnet Masking (VLSM)

In classic subnetting, all subnets share an identical fixed-length subnet mask, wasting addresses on small subnets (such as point-to-point router links requiring only 2 hosts). VLSM allows an organization to assign subnets with masks of different lengths tailored dynamically to the exact host requirements of each subnetwork.


4.5 Unicast, multicast and broadcast addresses

IP packets are classified according to the cardinality and distribution of their destination addresses:

  1. Unicast Addressing:
    • One-to-one communication between a single source interface and a single specific destination interface (e.g., standard HTTP web browsing, SSH).
  2. Broadcast Addressing (One-to-All):
    • Transmits a packet to every active host on the local physical network:
      • Limited Broadcast Address (255.255.255.255): Sent to all devices on the local broadcast domain. Routers never forward limited broadcast packets beyond the local subnet.
      • Directed Broadcast Address (e.g., 192.168.1.255 for /24): Carries the specific network ID with all host bits set to . Routers drop directed broadcasts by default to prevent denial-of-service amplification attacks (Smurf attacks).
  3. Multicast Addressing (One-to-Group):
    • Transmits a single packet to an arbitrary group of interested hosts registered with a specific multicast group address (Class D: 224.0.0.0 to 239.255.255.255).
    • Packets are replicated only along diverging tree branches by multicast routers (using IGMP and PIM).
    • IP-to-Ethernet Multicast MAC Mapping: The IANA allocated the Ethernet MAC address block 01:00:5E:00:00:00 to 01:00:5E:7F:FF:FF ( of address space) for IPv4 multicast. The lower of the Class D IP multicast group are placed directly into the low-order of the MAC address. Because of the IP address are lost in translation (), exactly () different IP multicast addresses map to the exact same Ethernet MAC multicast address.

4.6 Routing and types of routing: Static and dynamic, unicast and multicast, interior and exterior, distance vector and link state

Routing is the process by which intermediate routers discover network topologies, select mathematically optimal paths, and forward packets toward their destinations:

Major Classifications of Routing

  1. Static vs. Dynamic Routing:
    • Static Routing: Network routes are manually entered into router tables by network administrators (ip route 10.0.0.0 255.0.0.0 192.168.1.1). Secure and zero protocol bandwidth overhead, but does not adapt automatically to link failures or topology changes.
    • Dynamic Routing: Routers run routing protocol daemons that automatically exchange topology updates, compute optimal paths, and adapt dynamically to link failures without human intervention.
  2. Interior vs. Exterior Gateway Protocols:
    • Interior Gateway Protocols (IGP): Route traffic within a single Autonomous System (AS) managed by a single administrative organization (e.g., RIP, OSPF, EIGRP).
    • Exterior Gateway Protocols (EGP): Route traffic between different Autonomous Systems across the global Internet backbone (e.g., Border Gateway Protocol, BGP-4).

Fundamental Paradigms: Distance Vector vs. Link State Routing

AspectDistance Vector RoutingLink State Routing
Underlying AlgorithmBellman-Ford AlgorithmDijkstra's Shortest Path First (SPF) Algorithm
Information ExchangedSends its complete routing table ("tells its neighbors about the whole world")Sends Link State Advertisements (LSAs) containing status of directly connected links ("tells the whole world about its neighbors")
Exchange ScopeExchanged strictly between immediate directly connected neighborsLSAs are flooded to all routers across the entire routing area
Topology KnowledgeRouters have no global map; they know only the distance and next hop (routing by rumor)Every router maintains an identical Link State Database (LSDB) containing the complete global network topology
Convergence SpeedSlow convergence; susceptible to routing loops and Count-to-InfinityRapid convergence upon topology changes; completely immune to routing loops
Resource ConsumptionLow CPU and memory requirementsHigher memory (to store complete LSDB) and CPU processing (Dijkstra SPF runs)
Standard ProtocolsRouting Information Protocol (RIPv1, RIPv2), IGRPOpen Shortest Path First (OSPF), IS-IS

The Count-to-Infinity Problem in Distance Vector Routing

When an active link fails, distance vector routers may continuously bounce incremental metric updates back and forth, slowly incrementing the hop count toward infinity (RIP defines infinity as ).


Worked Out Examples

Example 4.1

4.1

An engineering college is allocated the classless IPv4 address block:

The network engineering team must design a Variable Length Subnet Mask (VLSM) scheme to satisfy the following departmental requirements:

For each of the four subnets, calculate:

  1. The number of host bits required and the corresponding CIDR prefix length.
  2. The Subnet Network Address.
  3. The Subnet Mask in dotted-decimal notation.
  4. The Usable Host IP Address Range.
  5. The Directed Broadcast Address.

Designing Subnet A (Computer Lab — 60 Hosts):

  • Host requirement: ().
  • CIDR prefix length: .
  • Block size: addresses.
  • Subnet Network Address: 192.168.10.0/26
  • Subnet Mask: 255.255.255.192
  • Usable Host Range: 192.168.10.1 to 192.168.10.62
  • Directed Broadcast Address: 192.168.10.63

Designing Subnet B (Faculty Offices — 28 Hosts):

  • Starting immediately after Subnet A at address 192.168.10.64.
  • Host requirement: ().
  • CIDR prefix length: .
  • Block size: addresses.
  • Subnet Network Address: 192.168.10.64/27
  • Subnet Mask: 255.255.255.224
  • Usable Host Range: 192.168.10.65 to 192.168.10.94
  • Directed Broadcast Address: 192.168.10.95

Designing Subnet C (Administrative Block — 12 Hosts):

  • Starting immediately after Subnet B at address 192.168.10.96.
  • Host requirement: ().
  • CIDR prefix length: .
  • Block size: addresses.
  • Subnet Network Address: 192.168.10.96/28
  • Subnet Mask: 255.255.255.240
  • Usable Host Range: 192.168.10.97 to 192.168.10.110
  • Directed Broadcast Address: 192.168.10.111

Designing Subnet D (WAN Router Link — 2 Hosts):

  • Starting immediately after Subnet C at address 192.168.10.112.
  • Host requirement: ().
  • CIDR prefix length: .
  • Block size: addresses.
  • Subnet Network Address: 192.168.10.112/30
  • Subnet Mask: 255.255.255.252
  • Usable Host Range: 192.168.10.113 to 192.168.10.114
  • Directed Broadcast Address: 192.168.10.115

Total allocated addresses: addresses. Addresses 192.168.10.116 through 192.168.10.255 ( addresses) remain unallocated for future expansion.

Answer:
  1. Subnet A: 192.168.10.0/26 (255.255.255.192), hosts: .1–.62, broadcast: .63.
  2. Subnet B: 192.168.10.64/27 (255.255.255.224), hosts: .65–.94, broadcast: .95.
  3. Subnet C: 192.168.10.96/28 (255.255.255.240), hosts: .97–.110, broadcast: .111.
  4. Subnet D: 192.168.10.112/30 (255.255.255.252), hosts: .113–.114, broadcast: .115.
Example 4.2

4.2

A regional Internet Service Provider (ISP) receives advertisements for four contiguous Class C network prefixes:

  1. Convert the third octet of each network address into binary.
  2. Determine the longest common matching bit prefix across all four routes.
  3. Formulate the single aggregated supernet route advertisement in CIDR notation.
  4. Calculate the total number of individual IP host addresses encompassed by the aggregated supernet.

Binary Representation of the Diverging Third Octet: The first two octets (200.16) are identical across all four routes. Representing the third octet in 8-bit binary:

Determining Longest Matching Prefix and CIDR Mask:

  • Inspecting the third octet from left to right: The first are identical across all four entries: 000100. The remaining vary ().
  • Total contiguous common prefix length:
  • The aggregated base network address has the common bits followed by zeros:
  • Aggregated Subnet Mask:

Calculating Encompassed Address Capacity:

  • Host bits available: .
  • Total IP addresses encompassed:

This exactly equals .

Answer:
  1. Third octets in binary: , , , .
  2. Longest matching prefix: (/22).
  3. Aggregated supernet advertisement: 200.16.16.0/22 (mask: 255.255.252.0).
  4. Total encompassed IP addresses: addresses.
Example 4.3

4.3

Consider a network consisting of five routers () running a Link State routing protocol. The bidirectional link costs between directly connected routers are:

Use Dijkstra's Shortest Path First (SPF) algorithm to find the shortest path from source router to all other routers. Show the step-by-step evolution of the permanent set and tentative distance vector , and write the final routing table for Router .

Step-by-Step Execution of Dijkstra's Algorithm from Root Node :

  • Let be the set of nodes whose shortest path is confirmed. Initialize .
  • Initial distances from :
  • Iteration 1:
    • Minimum distance among unvisited nodes is node with .
    • Add to .
    • Update neighbors of :
      • To : (via ).
      • To : (via ).
  • Iteration 2:
    • Minimum unvisited node is with .
    • Add to .
    • Update neighbors of :
      • To : (via ).
      • To : (via ).
  • Iteration 3:
    • Minimum unvisited node is with .
    • Add to .
    • Update neighbors of :
      • To : (remains ).
  • Iteration 4:
    • Add remaining node with . . Algorithm terminates.

Final Routing Table for Router : Tracing back the optimal paths from source :

  • Destination : Shortest Path , Cost , Next Hop .
  • Destination : Shortest Path , Cost , Next Hop .
  • Destination : Shortest Path , Cost , Next Hop .
  • Destination : Shortest Path (or ), Cost , Next Hop .
Answer:
  1. Shortest paths and costs from :
    • To : Cost (via )
    • To : Cost (via )
    • To : Cost (via )
    • To : Cost (via or )
  2. All outbound traffic from Router in this topology is directed to Next Hop .

Practice Exercises

Practice Exercises — Network Layer Principles & Addressing

Question 1

Compare Datagram Networks and Virtual-Circuit Networks with respect to:

  1. Routing decision timing.
  2. State information stored inside core routers.
  3. Effect of a router crash on active communications.
  4. Support for Quality of Service (QoS) guarantees.

Comparison of Network Layer Service Models:

  • Routing Decision Timing: In datagram networks, routing decisions are evaluated dynamically for every single individual packet at every hop based on destination IP. In virtual-circuit networks, the path is computed once during connection setup; subsequent packets are forwarded along the fixed circuit via fast hardware label swapping.
  • Router State Information: Datagram routers are stateless; they maintain only general routing tables without keeping per-connection state. Virtual-circuit switches maintain state tables recording incoming and outgoing VCI mappings for every active connection traversing them.
  • Impact of Router Crash: If a datagram router crashes, packets can be dynamically routed around the failure as soon as routing protocols converge. In a virtual-circuit network, all active virtual circuits traversing the failed switch are immediately severed and must be torn down and re-established.
  • QoS Guarantees: Virtual-circuit architectures can easily provide strict bandwidth, delay, and jitter guarantees because resources are reserved during the connection setup phase. Datagram networks operate on best-effort delivery and require supplementary complex priority queuing (DiffServ/IntServ) to achieve QoS.
Answer:

Datagram networks make per-packet routing decisions without maintaining connection state, providing superior resilience against router crashes but only best-effort delivery. Virtual-circuit networks use an initial connection setup with stateful VCI forwarding tables, enabling deterministic QoS guarantees at the cost of vulnerability to intermediate switch failures.

Question 2

An enterprise is assigned the Class B network address:

The network administrator must divide this network into at least distinct subnets while maximizing the number of usable hosts per subnet.

  1. Determine the minimum number of subnet bits that must be borrowed from the host portion.
  2. State the new custom subnet mask in dotted-decimal and CIDR notation.
  3. Calculate the total number of subnets created.
  4. Calculate the number of usable host IP addresses supported per subnet.

Calculating Subnet Bits and New Subnet Mask:

  • Required subnets: at least .
  • Borrowing bits from the host field:
  • New CIDR prefix length:
  • Custom Subnet Mask in binary:

Evaluating Subnet Count and Usable Host Capacity:

  • Total subnets created:
  • Host bits remaining:
  • Usable host IP addresses per subnet:

(Subtracting for the Subnet Address and Directed Broadcast Address).

Answer:
  1. Subnet bits borrowed: .
  2. New subnet mask: 255.255.252.0 (/22).
  3. Total subnets created: subnets.
  4. Usable hosts per subnet: hosts.
Question 3

Explain the necessity of RFC 1918 Private IP addresses.

  1. List the three defined private IPv4 address blocks along with their CIDR prefix lengths.
  2. Explain why private IP addresses cannot be routed across the public Internet backbone.
  3. Describe the mechanism that allows thousands of private hosts to access the public Internet simultaneously using a single public IP address.

RFC 1918 Address Blocks and Internet Routing Policy:

  1. Three Defined Private IPv4 Address Blocks:
    • Class A: 10.0.0.0/8 (10.0.0.0 to 10.255.255.255)
    • Class B: 172.16.0.0/12 (172.16.0.0 to 172.31.255.255)
    • Class C: 192.168.0.0/16 (192.168.0.0 to 192.168.255.255)
  2. Why Private Addresses are Non-Routable on the Public Internet: Private address blocks are deliberately unallocated to any single organization and are reused independently by millions of private homes and enterprises globally. If public Internet routers forwarded packets with private destination IPs, routing would fail due to ambiguous, duplicated address assignments. Public ISP backbone routers are explicitly configured to drop packets with private source or destination addresses immediately.

Enabling Public Internet Access: Network Address Translation (NAT): To access the Internet, private networks deploy Network Address Translation (NAT), specifically Port Address Translation (PAT) / NAPT:

  • When a private host (192.168.1.50:49152) initiates an outbound connection, the edge router replaces the private source IP and port with its own public IP and an ephemeral port (203.0.113.1:50001).
  • The router records the mapping in its stateful NAT translation table.
  • When response packets return to 203.0.113.1:50001, the router rewrites the destination back to 192.168.1.50:49152 and forwards it into the private network.
Answer:
  1. Private ranges: 10.0.0.0/8, 172.16.0.0/12, and 192.168.0.0/16.
  2. They are universally reused across millions of private networks and are discarded by public core routers to prevent duplicate routing conflicts.
  3. Network Address Port Translation (NAPT/PAT) rewrites private IP/port combinations to a single public IP address and unique external port numbers, tracking sessions in a stateful NAT table.
Question 4

Explain the Count-to-Infinity Problem in Distance Vector routing. Using a simple linear topology where link costs are , describe how the failure of the link between and causes count-to-infinity, and explain how Split Horizon and Poison Reverse resolve this problem.

How Count-to-Infinity Occurs in :

  • Initially, router reaches with metric (), and reaches via with metric ().
  • Suppose the physical link between and fails.
  • Router detects the failure and sets its distance to as .
  • However, before can advertise this failure, sends its periodic update to , stating: "I can reach with cost ."
  • Router mistakenly concludes: "I can reach via with cost !" updates its table.
  • In the next update cycle, advertises to : "I can reach with cost ." updates its distance to .
  • This ping-pong loop continues indefinitely, slowly counting upward () until the defined metric of infinity ( in RIP) is reached.

Resolution via Split Horizon and Poison Reverse:

  • Split Horizon: A router is forbidden from advertising a learned route back out the same interface over which it learned that route. Since learned about from , will never advertise a path to back to . When breaks, receives no false routes from and immediately marks unreachable.
  • Poison Reverse: When sends updates out the interface toward , it explicitly lists the route to with an infinite metric (), actively "poisoning" the reverse path and guaranteeing that never routes packets back to .
Answer:

Count-to-infinity occurs when adjacent distance vector routers exchange stale metric updates about a severed link, gradually incrementing costs until reaching infinity. Split Horizon prevents a router from advertising a route back out the interface from which it learned it; Poison Reverse explicitly advertises that route back with an infinite metric (), terminating the routing loop immediately.

Question 5

Explain the architecture of IPv4 Multicast Addressing.

  1. State the IPv4 Class D address range and describe its leading bit prefix.
  2. Explain how a Class D IP multicast address is mapped into a IEEE 802.3 Ethernet multicast MAC address (01:00:5E:...).
  3. Calculate the number of distinct IPv4 multicast group addresses that map to the exact same physical Ethernet MAC address, explaining the practical consequence for receiving hosts.

IPv4 Multicast Address Structure and Class D Range:

  • Class D addresses occupy the range:
  • The high-order four leading bits are fixed as 1110.
  • The remaining identify the specific multicast group ID.

IP-to-Ethernet Multicast MAC Mapping Mechanism:

  • IANA reserved the IEEE OUI prefix 01:00:5E:00:00:00 for multicast mapping.
  • By specification, the high-order of the MAC address are fixed as:

leaving the lower free for mapping.

  • The lower of the Class D IP multicast group are copied directly into the lower of the Ethernet MAC address.

Ambiguity Calculation and Host Consequence:

  • Number of unmapped bits:
  • Number of overlapping IP multicast addresses:
  • Practical Consequence: Thirty-two distinct IP multicast groups share the exact same hardware MAC address on an Ethernet switch. When the NIC filters frames at Layer 2, it delivers frames for all 32 groups up to the host operating system kernel; the Layer 3 IP stack must perform secondary software filtering to discard datagrams for multicast groups the host did not join.
Answer:
  1. Class D range: 224.0.0.0 to 239.255.255.255 (leading bits 1110).
  2. The lower of the IP multicast address are inserted into the lower of Ethernet MAC address 01:00:5E:00:00:00.
  3. Exactly () distinct IP multicast addresses map to the same MAC address, requiring the host OS network layer to discard unwanted multicast packets accepted by the NIC.
← Data Link LayerNetwork Layer (part 2: 4.7–4.12) →